整理 — 深入剖析数组与指针

留下评论

数组与指针声明有如此多的共同点,以至于我们通常觉得它们之间没有区别。其实不然。
首先,我们有必要重申一下一些常见形式的代码:
int a[3] = {0, 0, 0};
int *pa = a;
pa[1] = 1; //语句1
a[1] = 2; //语句2
从功效上看,语句1跟语句2一样设置数组中第2个元素的值。
但是其所产生的汇编代码却不一样,如下所示。
mov eax, dword ptr[pa]
mov dword ptr [eax + 4], 1 // 语句1
mov dword ptr [ebp-18h], 2 // 语句2
 
由此,我们可以看出变量名a实际上是一个常量,并且只能作为右值(rvalue)。
显然,
pa++; // 编译通过
a++; // 编译错误
 
另外,在使用sizeof时,它们的区别也是一目了然的。
sizeof(pa)只与编译器相关,受逻辑地址空间大小的影响;而sizeof(a)与数组长度成正比。
比如,在32位编译器中,
sizeof(pa)=4
sizeof(a)=3*sizeof(int)
 
有一个情况需要特别注意,就是当数组名作形参时。例如一下代码
void func(int a[])
{
int i = sizeof(a);
}
在这里,形参a仅仅是一个指针。
 
Advertisements

诡异的iterator在STL中的实现

留下评论

template <typename _Category, typename _Tp, typename _Distance=ptrdiff_t,
                 typename _Pointer=_Tp*, typename _Reference=_Tp&>
struct iterator
{
    typedef _Category iterator_category; // 有很多不同种类的iterator,
                                                              // 比如下面的reverse_iterator,random_access_iterator等等
    typedef _Tp value_type;
    typedef _Distance difference_type;    // 计算两个iterator之间的相对值
    typedef _Pointer pointer;
    typedef _Reference reference;
}

// Traits只是将typedef转向到_Iterator上;然后定义了2个偏特化,为了在模板实例化时找到更好的匹配。
template <typename _Iterator>
struct iterator_traits
{
    typedef typename _Iterator::iterator_category iterator_category;
    typedef typename _Iterator::value_type value_type;
    typedef typename _Iterator::difference_type difference_type;
    typedef typename _Iterator::pointer pointer;
    typedef typename _Iterator::reference reference;
};

template <typename _Tp>
struct iterator_traits<_Tp*>
{
    typedef random_access_iterator_tag iterator_category; // 注意这个地方,iterator的类型不是primary template
                                                                                           // 中的iterator::iterator_category。
    typedef _Tp value_type;
    typedef ptrdiff_t difference_type;
    typedef _Tp* pointer;
    typedef _Tp& reference;
};

template <typename _Tp>
struct iterator_traits<const _Tp*>
{
    typedef random_access_iterator_tag iterator_category;
    typedef _Tp value_type;
    typedef ptrdiff_t difference_type;
    typedef const _Tp* pointer;
    typedef const _Tp& reference;
};

template <typename _Iterator>
class reverse_iterator
    : public iterator<typename iterator_traits<_Iterator>::iterator_category,
                              typename iterator_traits<_Iterator>::value_type,
                              typename iterator_traits<_Iterator>::difference_type,
                              typename iterator_traits<_Iterator>::pointer,
                              typename iterator_traits<_Iterator>::reference>
{
protected:
    _Iterator current;
public:
    // 实际上,接下来的typedef,我认为是没有有必要的,因为它跟其继承自iterator里的typedef是一样的。
    // 但是STL作为一个具有工业强度的类库,难道会包含无用的代码?
    // 无解
    typedef _Iterator iterator_type;
    typedef typename iterator_traits<_Iterator>::difference_type difference_type;
    typedef typename iterator_traits<_Iterator>::reference reference;
    typedef typename iterator_triats<_Iterator>::pointer pointer;
public:
    … // other implementations.
};

Argument Depend Look-up

留下评论

Argument Depend Look-up的由来

 

查找有三种对象:1. 限定名查找;2. 非限定名查找(包含常规查找和ADL)

限定名查找很简单,就是在构造限定对象所需的域内查找;如果限定域是一个类,那么我们也要查找其父类。

普通查找就更简单了,就是相对当前查找位置而言的所有可见区域。虽然如此,有时候,仅仅依赖普通查找仍然不能解决所有问题。

参考如下代码

Namespace BigMatch {

Class BigNumber {
    };

Bool operator < (BigNumber const&, BigNumber const&);

};

 

Using BigMatch::BigNumber;

Void g(BigNumber const& a, BigNumber const& b)

{

BigNumber x = max(a, b);


}

max()模板函数不能感应到名字空间BigMatch,普通查找并不能确定BigNumber的比较重载操作符。

 

什么时候会发生ADL

ADL只对不非限定名有效,并且这些非限定名不能是成员函数名。如果普通查找找到名字相同的成员函数名或类名,ADL不会发生。如果待查找的名字在圆括号内,ADL也不会发生。(VS2008下该规则不适用)

 

ADL会查找与传入参数类型相关的类和命名空间。

一个给定类型的相关类与命名空间定义如下:

l  内建类型没有相关类与命名空间

l  指针与数组,所指代和包含类型的相关类和命名空间

l  枚举类型,枚举被定义的命名空间。类成员,包含它的类

l  Class类型(包含union),就是它自己,以及其基类。如果class为模板实例,那么模板参数的类型以及该类型所在的名字空间也包含其中

l  Function类型,所有参数和返回值的类型以及相关命名空间

l  指向成员变量的指针,包含该成员函数的类和该成员变量的类型。如果是指向成员函数的指针,包含该成员函数的类和该成员函数的参数类型和返回值类型

 

注意:ADL在搜索相关类和命名空间时,会忽略掉using指令。

COM原理实用技巧入门(1)-表驱动查找接口

留下评论

#include "stdafx.h"
#include "unknwn.h"
#include "GuidDef.h"
#include <iostream>
// {1E99B41C-B941-4274-8E08-514872284C2A}
static const GUID IID_IPig =
{ 0x1e99b41c, 0xb941, 0x4274, { 0x8e, 0x8, 0x51, 0x48, 0x72, 0x28, 0x4c, 0x2a } };
// {D7C8F89F-C7A6-4569-AF08-9AC68A165C39}
static const GUID IID_ICat =
{ 0xd7c8f89f, 0xc7a6, 0x4569, { 0xaf, 0x8, 0x9a, 0xc6, 0x8a, 0x16, 0x5c, 0x39 } };
 
typedef HRESULT (*INTERFACE_FINDER)
 (void *pThis, DWORD dwData, REFIID riid, void **ppv);
#define ENTRY_IS_OFFSET INTERFACE_FINDER(-1)
typedef struct _INTERFACE_ENTRY
{
 const IID *pIID;
 INTERFACE_FINDER pfnFinder;
 DWORD dwData;
} INTERFACE_ENTRY;
#define BASE_OFFSET(ClassName, BaseName) \
 (DWORD (static_cast<BaseName*>(reinterpret_cast\
 <ClassName*>(0x10000000))) – 0x10000000)
#define BEGIN_INTERFACE_TABLE(ClassName) \
 typedef ClassName _ITCls; \
 const INTERFACE_ENTRY *GetInterfaceTable(void) {\
 static const INTERFACE_ENTRY table[] = {
#define IMPLEMENTS_INTERFACE(Itf) \
{&IID_##Itf, ENTRY_IS_OFFSET, BASE_OFFSET(_ITCls, Itf)},
#define IMPLEMENTS_INTERFACE_AS(req, Itf) \
{&IID_##req, ENTRY_IS_OFFSET, BASE_OFFSET(_ITCls, Itf)},
#define END_INTERFACE_TABLE \
{0, 0, 0}}; return table; }
HRESULT InterfaceTableQueryInterface(void *pThis,
          const INTERFACE_ENTRY *pTable,
          REFIID riid,
          void **ppv)
{
 if (IsEqualIID (riid, IID_IUnknown))
 {
  *ppv = (char *)pThis + pTable->dwData;
  ((IUnknown*)(*ppv))->AddRef();
  return S_OK;
 }
 else
 {
  HRESULT hr = E_NOINTERFACE;
  while(pTable->pfnFinder)
  {
   if (!pTable->pIID ||
    IsEqualIID(riid, *(pTable->pIID)))
   {
    if (pTable->pfnFinder == ENTRY_IS_OFFSET)
    {
     *ppv = (char*)pThis + pTable->dwData;
     //((IUnknown*)(*ppv))->AddRef();
     ((IUnknown*)pThis)->AddRef();
     hr = S_OK;
     break;
    }
    else
    {
     hr = pTable->pfnFinder(pThis,
      pTable->dwData, riid, ppv);
     if (hr == S_OK) break;
    }
   }
   pTable++;
  }
  if (hr != S_OK) *ppv = 0;
  return hr;
 }
}
struct AUTO_LONG
{
 LONG value;
 AUTO_LONG(void) : value(0) {}
};
#define IMPLEMENT_UNKNOWN(ClassName) \
 AUTO_LONG m_cRef; \
 HRESULT STDMETHODCALLTYPE QueryInterface(REFIID riid, void **ppv) { \
  return InterfaceTableQueryInterface(this, \
  GetInterfaceTable(), riid, ppv); \
} \
 ULONG STDMETHODCALLTYPE AddRef(void) { \
  return InterlockedIncrement(&m_cRef.value); \
} \
 ULONG STDMETHODCALLTYPE Release(void) { \
 ULONG res = InterlockedDecrement(&m_cRef.value); \
 if (res == 0) \
  delete this; \
 return res; \
}
interface IPig : public IUnknown{
};
interface ICat : public IUnknown{
};
class PigCat : public IUnknown, public IPig, public ICat {
protected:
 virtual ~PigCat (void);
public:
 PigCat(void);
 IMPLEMENT_UNKNOWN(PigCat)
  BEGIN_INTERFACE_TABLE (PigCat)
   IMPLEMENTS_INTERFACE (IPig)
   IMPLEMENTS_INTERFACE (ICat)
  END_INTERFACE_TABLE()
};
PigCat::~PigCat()
{
 // nothing to do.
}
PigCat::PigCat()
{
 // nothing to do.
}
int _tmain(int argc, _TCHAR* argv[])
{
 PigCat *t = new PigCat;
 std::cout << t->AddRef() << std::endl;
 IPig* t1 = NULL;
 t->QueryInterface(IID_IPig, (void**)(&t1));
 ICat* t2 = NULL;
 t->QueryInterface(IID_ICat, (void**)(&t2));
 if (t1 != NULL) {
  std::cout << t->Release() << std::endl;
  t1 = NULL;
 }
 if (t2 != NULL) {
  std::cout << t->Release() << std::endl;
  t2 = NULL;
 }
 std::cout << t->Release() << std::endl;
 
 return 0;
}

Boost::Tuple (Part 2)

留下评论

拷贝构造器和tuple赋值

一个tuple对象可以通过拷贝其他tuple对象来构建,假设它们包含的元素类型也是可以通过拷贝

来构建。与此类似,一个tuple对象可以赋值给另一个tuple对象,如果它们包含的元素类型也是

可以通过赋值来构建的。例如:

Class A {};

Class B : public A {};

Struct C { C(); C(const B&); };

Struct D { operator C() const; };

Tuple<char, B*, B, D> t;

Tuple<int, A*, C, C> a(t); // ok

a = t; // ok

tuple<float, int> a = std::make_pair(1, ‘a’); //ok

 

关系运算符

·         a==b iff for each i: ai == bi

·         a != b iff exists i: ai != bi

·         <><=>=采用词典编纂的比较顺序

·         如果试图比较两个长度不一样的tuple对象,会引起编译期错误

·         采用短路比较策略

 

Tier机制

Tier是一种特殊的tuple对象,它所包含的所有元素都是非const引用类型。它们可以通过tie

模板函数创建:

Int i; char c; double d;

Tie(i, c, a); // tuple<int&, char&, double&>

                    // equal to make_tuple(ref(i), ref(c), ref(a))

一个包含非const引用类型的tuple能够把另一个tuple分拆成变量:

int I; char c; double d;

tie(I, c, d) = make_tuple(1, ‘a’, 5.5);

std::cout << i << “ ” << c << “ ” << d;

下面一种形式也是正确的:

int i; char c;

tie(i, c) = std::make_pair(1, ‘a’);

 

Ignore对象

Ignore对象允许你忽略一个右值tuple的某些元素。这其中的思想是,可能有这样一个函数,它

返回一个tuple,你只对它的某部分元素感兴趣,这个时候,你就可以用Ignore对象。

char c;

tie(tuples::ignore, c) = std::make_pair(1, ‘a’);

 

输入/输出流

重载了全局operator<<operator>>,另外就是怎样标定每个元素的起始,以及每个元素之间的

分隔符。

·         set_open(char)

·         set_close(char)

·         set_delimiter(char)

 

性能

因为tuple的大部分成员函数都只是很短的实现,所以,它的性能非常依赖于编译期的代码优化

功能。另外,与直接返回非const的引用参数相比较,tier机制可能会带来很小的性能牺牲。

代码示例:

void f1(int&, double&);

tuple<int, double> f2();

 

引用

[1] Järvi J.: Tuples and multiple return values in C++, TUCS Technical Report No 249, 1999.

[2] Järvi J.: ML-Style Tuple Assignment in Standard C++ – Extending the Multiple Return Value Formalism, TUCS Technical Report No 267, 1999.

[3] Järvi J.:Tuple Types and Multiple Return Values, C/C++ Users Journal, August 2001.

 

Boost::Tuple (Part 1)

留下评论

原文地址 http://www.boost.org/doc/libs/1_39_0/libs/tuple/doc/tuple_users_guide.html

 

Tuple类型

一个Tuple类型通过初始化Tuple模板可以得到。模板参数声明tuple中元素的类型。当前

Tuple所支持的元素个数上限时10。如果有比要的话,这个数目当然可以增加。元素类型

可以使任意的C++类型。注意voidplain function type是合法的C++类型,但是这些类型的

对象并不存在。所以,如果Tuple类型包含那些类型,那么这个Tuple类型可以存在,但是

该类型的对象并不存在。另外,还对元素类型有一些理所当然的限制,能否被copy,是否

需要有默认构造器等。

下面是一些Tuple类型声明的合法例子 (ABC是自定义类型)

Tuple<int>

Tuple<double&, const double&, const double, double*, const double*>

Tuple<A, int(*)(char, int), B(A::*)(C&), C>

Tuple<std::string, std::pair<A, B>>

Tuple<A*, tuple<const A*, const B&, C>, bool, void*>

 

构造tuple对象

如果在初始化时没有提供初始值,那么元素必须有默认构造器。

另外,因为引用类型没有默认构造器,所以这时要显示初始化该元素的值。

Tuple<double&>() // error

Double d = 5

Tuple<double&>(d) // ok

Tuple<double&>(d + 3.14) // error: can’t initialize

                                                // non-const reference a dangling reference

Tuple<const double&>(d + 3.14) // ok, but dangerous:

                                                           // the element becomes a dangling reference

对元素使用那些不能被拷贝的初始值在编译时就会报错:

Class Y {

                Private:

Y(const Y&);

Public:

Y();
};

Char a[10];

Tuple<char[10], Y>(a, Y()); // error, neither arrays nor Y can be copied

Tuple<char[10], Y>(); // ok

注意以下的声明形式:

Y y;

Tuple<char(&)[10], Y&>(a, y);

这样子可能会产生一个不能被构造的tuple类型。如果一个不能被初始化的元素比一个必须

被初始化的元素拥有更低的索引,那种情况就会发生。例如:

Tuple<char[10], int&>

总的来说,tuple的构造器语义上就是一组独立元素的构造。

 

Make_tuple函数

也可以使用make_tuple辅助函数来完成tuple的初始化工作。

Tuple<int, int, double> add_multiply_divide(int a, int b) {

Return make_tuple(a + b, a * b, double(a) / double(b));
}

默认情况下,元素类型被转化为普通的非引用类型,例如:

Void foo(const A& a, B& b) {

Make_tuple(a, b); //产生的类型为tuple<A, B>

}

 

有时候普通的非引用类型并不合适,例如元素不能被拷贝。因此,程序员可以控制类型转换

过程,要求使用指向const的引用或者指向非const的引用来代替之。通过两个辅助模板

函数refcref可以做到这一点。Make_tuple的任何参数都可以通过这两个函数包装以获得

需要的元素类型。这种机制并不能保证const的正确性,因为一个const对象用ref包装后

只能产生const引用类型。例如:

A a; B b; const A ca = a;

Make_tuple(cref(a), b); // tuple<const A&, B>

Make_tuple(ref(a), b); // tuple<A& B>

Make_tuple(ref(a), cref(b)); // tuple<A&, const B&>

Make_tuple(cref(ca)); // tuple<const A&>

Make_tuple(ref(ca)); // tuple<const A&>

Make_tuple的数组参数默认产生指向const类型的引用,因此没有必要使用cref来包装。例如:

Make_tuple(“Hello”, “World”); // tuple<const char(&)[7], const char(&)[6]>

                                                        // 注意string字符串是一个const字符的数组,并不是const char*

尽管如此,为了利用make_tuple创建一个包含非const数组类型的元素的tuple,我们必须使用

ref包装函数。

Void f(int i);

Make_tuple(&f);

Tuple<tuple<void (&)(int)>> a(f); // ok

Make_tuple(f); // not ok

 

访问tuple中的元素

t.get<N>()

or

get<N>(t)

t代表一个tuple对象,N是一个整型常量表达式,代表被访问元素的索引。返回第N个元素

的指向const或非const的引用取决于t是否是const。元素的索引值从0开始。越界访问会引起

编译期错误。

Double d = 2.7; A a;

Tuple<int double&, const A&> t(1, d, a);

Const tuple<int, double&, const A&> ct = t;

Int I = get<0>(t); I = t.get<0>(); // ok

Int j = get<0>(ct); //ok

Get<0>(t) = 5; // ok

Get<0>(ct) = 5; // error

Double e = get<1>(t); // ok

Get<1>(t) = 3.14; // ok

Get<2>(t) = A(); // error

A aa = get<3>(t); // error

++get<0>(t); // ok

Tips:在MS VC++下,要对get函数使用namespace限定。

 

Tuple

留下评论

Building Tuple

 

使用示例

Static void Main(string[] args) {

Object[] t = new object[2];

T[0] = “”;

T[1] = 4;

PrintStringAndInt((string)t[0], (int)t[1]);
}

Static void PrintStringAndInt(string s, int i) {

Console.WriteLine(“{0} {1}”, s, i);
}

 

Static void Main(string[] args) {

Tuple<string, int> t = new Tuple<string, i>(“hello”, 4);

PrintStringAndInt(t.Item1, t.Item2);
}

 

Tuple是在.NET Framework4.0中引入的,但是在以前的版本中我们可以看到它的影子:

System.Collections.Generic KeyValuePair是也。

但是Tuple可以有任意元数,而KeyValuePair只支持二元。在它加入.NET Framework4.0

之前,其实有已经有很多team已经在使用他们自己的Tuple实现了。

 

语言互操作性

Microsoft使用Tuple最多的要数语言开发团队他们自己了。当C#VB.NET并没有把Tuple作为

语言本身支持的一个概念的时候,很多函数式编程语言已经把它当作一个情理之中的特性了。

当需要使这种函数式编程语言运行于.NET Framework运行时时,语言开发者就需要定义托管的

Tuple声明,然而这会导致不必要的冗余。F#就是一个例子,它已经在FSharp.Core.dll中定义了

Tuple类型,所以不会使用.NET Framework中新增的Tuple定义。

 

因此把Tuple类型提到.NET Framework类库中除了可以移除冗余的Tuple定义之外,它还可以便于

跨语言边界访问函数。

 

C#中使用Tuple

Var t = new Tuple<string, int>(“Hello”, 4);

Var p = Tuple.Create(“Hello”, 4);

 

引用类型还是值类型?

乍看起来,实现Tuple类型只要一个周末就可以轻松搞定。但是,表象一般会欺骗你的眼睛。

实际上,在Tuple的开发过程中有很多有趣的设计决策。

第一个主要决定就是我们应该把Tuple当成引用类型还是值类型。Tuple的值是不可改变的(

immutable);如果你想改变Tuple的值,那么就不得不创建一个新的Tuple对象。如果把Tuple

当作引用类型,那么就会产生大量的内存垃圾需要被回收如果你在一个很大的循环中不断

修改Tuple对象的值。F#Tuple就是引用类型,但是它的开发团队认为如果把二元,甚至

三元Tuple当作值类型,那可能会提升性能。也有其他team在实现他们自己的Tuple类型时,

把它也当作值类型,因为他们的应用场景对创建大量托管对象很敏感,他们发现如果把Tuple

当做值类型可以获得更好的性能。在我们第一份Tuple的设计草案中,认为二元,

三元和四元Tuple为值类型,其他元的Tuple为引用类型。然而,在一次设计评审会上,与会的

还包含其它语言开发团队的代表,最后得出结论:这种划分很容易让人迷茫,仅仅是因为这

两者之间的细微区别。相比之于提升性能,行为与设计上的一致性被认为应该具有更高的优先

级。基于这样的决定,我们最终决定还是把所有的Tuple作为引用类型,虽然,我们请F#团队

对于把特定大小的Tuple当做值类型做一些性能检测,以确定这是否真会带来好处。他们真的有

非常好的方法来满足我们的请求,因为他们的编译器就是用F#编写的,这本身就是一个在不同场景

下使用Tuple的大型程序。最后,他们发现那并不会提升性能。这也让我们对于把Tuple当做

引用类型的决定感觉好多了。

 

任意元的Tuple

理论上,没有任何根据去限制Tuple的元数。但是,我们也无法提供无限多的Tuple类型来

满足这一需要。既然.NET Framework4中新引入的ActionFunc代理只能接受8个参数,

所以我们也让Tuple这样子。不过后来,ActionFuncOwner把参数个数添加到16个,

我们并没有跟进,认为这不是必须的;同时,这样做也不值。那么,当我们需要使用很大的

Tuple的时候,该怎么办呢?

Tuple.Create(1, 2, 3, 4, 5, 6, 7, Tuple.Create(8)); —这就是解决方案

关于属性的名字还有一些有趣的事情。起初,我们使用Item1Item2依次这样的名字。但是,

后来我们收到了一些来自框架设计评审人的有趣反馈。他们认为这些名字就像是自动生成的,

而不像是设计的。他们建议使用英文单词FirstSecond之类的词。最终,我们没有改变初衷,

基于如下几点原因:第一,我们更倾向于改变属性名字中的一个字符来切换我们想访问的

元素;第二,英文数字将会导致很差的自动提示用户体验,因为它们是按照字母顺序而不是

数字顺序排列。

 

接口实现

System.Tuple实现了很少量的接口并且这些接口中不包含通用接口。

 

结构性等价,比较和等价

有三个概念:

l  Structural equality

l  Structural comparison

l  Partial equivalence relations

对于Tuple这种简单地保存其他数据的类型来说,Structural equalitycomparison

Equals方法相关。

F#中,tuplearray的相等是结构性的。那就是说,两个tuple或者array相等当

且仅当他们的每个元素都相等。这与C#不同,默然情况下,arraytuple中的内容和

它们是否相等并没有关系。关键是它们在内存中的位置。

既然structural equalitycomparison已经是F#规范的一部分,因此F#团队已经提出了

这个问题的部分解决方案。尽管如此,它也仅仅是对他们自己创建的类型才有用。既然

它同样需要在array上使用structural equality,因此编译器会生成特殊的代码来检测它是否

是在一个array上进行等价比较操作。如果是这样的话,它将进行structural comparison而不是

仅仅调用Equals方法。设计团队尝试了几种不同的设计方案来解决这些structural equality

Comparison的问题。它寄希望于创建几个structural type必须实现的接口。

 

IStructualEquatableIStructuralComparable

这两个接口提供了一种方式便于类型来优化它的structural equalitycomparison。它们允许

进行深比较,并且对象内每个元素都可以使用一个比较器。

Public interface IStructuralComparable {

Int32 CompareTo(Object other, ICompare compare);
}

Public interface IStructuralEquatable {

Boolean Equals(Object other, IEqualityComparer comparer);

Int32 GetHashCode(IqualityComparer comparer);
}

 

偏序等价关系

Tuple需要支持偏序关系。在.NET Framework中偏序关系的例子有NaN和浮点型数字。

(NaN < NaN) == false, (NaN > NaN) == false, (NaN != NaN) == false

这是因为NaN是不可比较的,既然它们不碉堡任何数字。我们可以用操作符重载来描述这种

关系,但是我们不能用IComparable::CompareTo()方法。这是因为CompareTo没有代表

不可比较的返回值。

F#中,([NaN, NaN] == [NaN, NaN]) == false, ([NaN, NaN] != [NaN, NaN]) == false

 

Older Entries