前言

 
C++允许重载标题所提及的三种操作符，但本节禁止其重载的原因很简单，易于引发歧义或者说与预期设想不符。

“&&”、”||”

 
众所周知，&&与||具备短路特性。当你重载&&或者||以后，你以函数调用代替了短路求值。
这样会造成两个缺点：

1. 函数调用需要计算所有参数，你的表达式不再具备短路特性。
2. c++没有规定函数参数的计算顺序，最终表达式结果由编译器决定。

“,”

 
一个包含逗号的表达式首先计算逗号左边的表达式，然后计算逗号右边的表达式；整个表达式的结果是逗号右边表达式的值。自定义的operator,没有这样的特性，最终结果由编译器决定。

禁止重载的操作符

允许重载的操作符

总结

 
操作符重载的目的是为了令程序更容易阅读，书写和理解，而不是炫耀技巧。如果没有重载操作符的必要，就不要重载。

前言

 
上一节描述了何时需要自定义operator new与operator delete，但并没有描述自定义时应当遵循何种规则。实际上这些规则并不难奉行，只是不太直观。

operator new

 
operator new共有四个要求：

1. 返回正确的值
2. 内存不足时必须调用new-handling函数
3. 考虑0内存需求
4. 避免掩盖global new（虽然这更偏近class接口要求）。

operator new 返回值

一般而言，operator new返回值很简单，分配成功则返回一个指向那块内存的指针，反之则遵循Effective C++ 50的约定，并抛出一个bad_alloc异常。

其实也不是特别简单，因为它实际上不只一次尝试分配内存，并在每一次失败后都调用new-handling函数。这里假设new-handling也许能够释放一些内存，当只有指向new-handling函数的指针是nullptr时，operator new才会抛出异常。

0内存需求

c++规定，即使客户需要0bytes，也必须提供合法指针而不得返回nullptr。为了满足约定，有伪代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void* operator new(size_t size) throw(bad_alloc){
    using namespace std;
    if(size==0) size=1;
    while(true){
        ...//尝试分配内存
        if(分配成功）
        return （一个指向分配内存的指针）；
        new_handler globalHandler = set_new_handler(nullptr);
        set_new_handler(globalHandler);
        if(globalHandler)
            *globalHandler();
        else throw bad_alloc();
    }
}

operator new与继承体系

 
在上述实例中我们没有考虑过继承。一般而言，定制内存管理器的常见理由是针对某个class的对象进行优化，而不是对其derived class对象作出优化。也就是说，针对class X而设计的operator new其行为只是刚好为sizeof（X）的对象而设计。众所周知，dc对象一般要大于bc对象：

1
2
3
4
5
6
7

class Base{
public:
    static void* operator new(size_t size) throw(bad_alloc);
    ...
};
class Derived:public Base {...};//未声明operator new
Derived* p = new Derived;//调用Base::operator new

1
2
3
4
5

void* Base::operator new(size_t size) throw(bad_alloc){
    if(size!=sizeof(Base))
        return ::operator new(size);//std::operator new
    ...
}

operator new[]

 
如果我们需要实现new[],我们要做的事情只有一个：分配一块raw memory。因为我们既不知道这个array具体有多少元素，也不知道其元素的大小（因为dc的对象往往比bc的对象大），另外传递给new[]的size_t参数未必就是真正的元素个数，因为实际上array会有一部分负责存放其元素个数，它们也需要占据内存。

operator delete

 
operator delete的情况简单一些，你只需要记住“删除nullptr永远安全即可”：

1
2
3
4

void operator delete(void* rawMemory) throw(){
    if(rawMemory == nullptr) return;
    ...//释放内存
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Base{
public:
    static void* operator new(size_t size) throw(bad_alloc);
    static void* operator delete(void* rawMemory,size_t size) throw();
    ...
};
void* Base::operator delete(void* rawMemory,size_t size) throw();
    if(rawMemory==nullptr) return;
    if(size!=sizeof(Base)){
        ::operator delete(rawMemry);
        return;
    }
    ...//释放内存
    return;
}

总结

1. operator new内部有一个死循环，并在其中尝试分配内存，如果它不能分配，则调用new-handler，同时它应该能够处理0 bytes申请。class member版本则应该处理“比正确大小大或者小的申请”。
2. operator delete应该在收到nullptr时不做任何事，class版本还应该处理“比正确大小大或者小的申请”。

前置与后置操作符

 
重载函数间的区别在于它们参数类型上的差异，但是无论increment还是decrement的前缀与后缀都只有一个参数。为了解决问题，c++规定后缀形式有一个int类型参数，当函数被调用时编译器传递一个0作为int参数的值:

1
2
3
4
5
6
7
8
9
10
11

class UPInt { //unlimited precision int
public:
    UPInt& operator++();
    const UPInt operator++(int);
    UPInt& operator--();
    const UPInt operator--(int);
    ...
};
UPInt i;
++i; //i.operator++();
i++; //i.operator++(0);

具体实现

 
以自增为例，前缀表达的意思是“增加然后取出”，后缀表达的意思是“取出然后增加”，以下是具体实现：

1
2
3
4
5
6
7
8
9

UPInt& UPInt::operator++(){
    *this += 1;
    return *this;
}
const UPInt UPInt::operator++(int){
    UPInt oldValue = *this;
    ++(*this);
    return oldValue;
}

返回值

 
很明显一个后缀操作符必须返回一个对象，但是为什么必须是const对象呢？
假设返回值不是const 对象，下面的代码就是正确的：

1
2

UPInt i;
i++++;//i.operator++(0).operator++(0);

1. 保证与内置类型具备行为一致
2. 直觉上我们认为i++++应该自增2次，但实际上它只自增了一次，只有最后一个++生效

如果后缀返回const对象，那么第二个++由于是non-const成员函数，将无法通过编译。

效率

 
由于后缀操作符需要返回对象的原因（不可避免的构造与析构），前缀比后缀的效率要高，在用户自定义类型上更是明显，因此我们在能用前缀的时候应该使用前缀。

为何需要自定义opertaor new与operator delete？

 
有三个理由:

1. 检测运用上的错误
   如果new所得的内存delete失败，会导致内存泄漏。如果试图多次delete，则又会导致未定义行为。针对该误操作的解决方法是：令operator new持有一串动态分配所得地址，delete将地址从中移除。
   各式各样的编程错误可能会导致数据overruns(写入点在分配区段尾部之后）或者underruns（起点之前）。其解决方法是：自定义operator new，分配超额内存，以额外空间放置特定的byte patterns（signature）operator delete执行时先检查这段签名是否原封不动，若否则表明出现了overrun或者underrun，log此事实以及这个指针。
2. 强化效能
   编译器所带的operator new与operator delete总是惯于采取通用解（不针对特殊情况使用最优解），如果你针对自己的程序作出特定优化（内存大小，分配形态，持续分配与归还），性能将会得到极大的提高。
3. 统计使用数据
   在自定义内存管理服务前我们当然需要采集目前程序对内存的使用情况，我们可以通过自定义operator new与operator delete来搜集内存使用信息。

自定义operator new实例

 
以下是一个帮助检查overruns或underruns的operator new实例，其中存在着一些小错误：

1
2
3
4
5
6
7
8
9
10
11
12
13

static const int signature = 0xDEADBEEF;//签名
typedef unsigned char Byte;

//存在一些小错误
void* operator new(size) throw(bad_alloc){
    using namespace::std;
    size_t realSize = size+2*sizeof(int);//实际需要额外塞入两个signature
    void* pMem = malloc(realSize);
    if(!pMem) throw bad_alloc();
    *(static_cast<int*>(pMem) = signature;
    *(reinterpret_cast<int*>(static_cast<Byte*>(pMem)+realSize-sizeof(int))) = signature;
    return static_cast<Byte*>(pMem) +sizeof(int);
}

齐位

 
许多计算机体系结构会要求特定类型存放于特定的地址，比如指针的地址必须是4倍数或者double的地址必须是8倍数。有的体系不遵循该规则会导致硬件异常，有的体系则无此要求，只是如果遵循齐位则提供较佳焦虑。
在上一个实例中，malloc返回的指针必然是齐位的，但是自定义的operator new并没有返回得自malloc的指针，而是做了一些偏移，这可能会造成错误或效率低下。事实上，各个库的内存管理函数或者部分开源内存管理器均考虑了齐位特性。如果我们也有自定义内存管理的需求，记得考虑诸如可移植性，齐位，线程安全等等细节。

何时需要自定义opertaor new与operator delete

• 需要检测运用错误（如前所述）
• 需要收集使用信息（如前所述）
• 需要增加分配与归还的速度
  举例而言，如果在profile时发现线程安全性降低了运行速度，而我们的程序只在单线程下运行，则没必要使用线程安全的operator new。
• 需要降低默认内存管理器带来的空间额外开销
• 弥补默认分配器带来的非最佳齐位
• 需要将对象成簇集中
  如果每个数据结构往往被一起使用，而你有希望使用它们时page faults的频率降至最低，那么为此创建一个heap就很有必要。new与delete的placement版本可以完成这样的行为。
• 需要获得非传统行为
  例如分配和归还共享内存。

前言

 
除了c++提供的四种强制类型转换操作外，自定义类型在建立时我们可以提供某些函数以供编译器拿来作隐式转换。有两种函数允许编译器执行这样的转换：单自变量构造函数与隐式类型转换操作符。

隐式类型转换函数

单自变量构造函数

所谓单自变量构造函数，指的是能够以单一自变量成功调用的构造函数。该构造函数分为两种情况：

1. 拥有单一形参
2. 具备多个形参，但第一个形参之后的所有形参均具备默认值

1
2
3
4
5
6
7
8
9
10

class Name {
public:
    Name(const string& s);
    ...
};
class Rational {
public:
    Rational(int numerator = 0,int denominator = 1); // 有理数类
    ...
};

隐式类型转换操作符

隐式类型转换操作，是一个拥有奇怪名字的成员函数：operator关键词之后加一个类型名称。我们无法指定其返回值类型，因为其返回类型就体现在名称上。举例如下：

1
2
3
4
5

class Rational {
public:
    ...
    operator double() const;
};

1
2

Rational r(1,2);
double d=0.5*r;//转换r，从Rational至double

自定义类型转换函数的弊端

隐式转换可能会在你并未打算调用他们的时候被调用，从而产生不正确的后果，我们很难调试中发现这一问题。

隐式类型转换操作符

问题实例

假设存在一个如上所述的 Rational类，我们希望他能够像内置类型一样兼容opertaor<<。但由于我们的疏忽，忘记了为Ration对象定义opertaor<<，你会惊奇地发现，如下语句还是能够编译和运行：

1
2

Rational r(1, 2);
cout << r;//本意是打印“1/2”，现在打印出了“0.5”

解决方案

解决方法很简单，以一个功能对等的函数取代它，例如：

1
2
3
4
5

class Rational {
public:
    ...
    double asDouble() const;
};

单自变量构造函数

通过单自变量constructors完成的隐式转换难于消除，且其破坏性也较大。

问题实例

现有一个针对数组结构写的class template。这些数组允许用户指定索引值的上界与下界：

1
2
3
4
5
6
7
8

template<class T>
class Array {
public:
    Array(int lowBound, int highBound);
    Array(int size);//单自变量构造函数
    T& operator[](int index);
    ...
};

1
2
3
4
5
6
7
8
9
10
11

bool operator==( const Array<int>& lhs,const Array<int>& rhs);
Array<int> a(10);
Array<int> b(10);
...
for (int i = 0; i < 10; ++i)
    if (a == b[i]) {//误将a[i]写作a
        ...
    }
    else {
        ...
    }

1
2

for (int i = 0; i < 10; ++i)
    if (a == static_cast< Array<int> >(b[i]))

解决方案

我们不能禁止单参数构造函数，但同时我们也希望防止编译器不加鉴别地调用这个构造函数，因此我们可以使用explicit关键词。构造函数用 explicit 声明后，编译器会拒绝为了隐式类型转换而调用构造函数，同时显式类型转换依然合法。

总结

 
让编译器进行隐式类型转换所带来的弊端要大于它所带来的好处，因此除非确实需要，否则不要定义隐式类型转换函数。

前言

 
当operator new无法满足某一个内存分配需求时，它会抛出异常，在其抛出异常之前，它会先调用一个客户制定的错误处理函数，一个所谓的new-handler。（实际上更复杂一些）

set_new_handler

 
为了指定这个“用以处理内存不足”的函数，用户必须调用set_new_handler，那是声明于<new>的一个标准库函数：

1
2
3
4

namespace std｛
    typedef void (*new_handler)();
    new_handler set_new_handler(new_handler p) throw();
}

显然，new_handler是一个函数指针的typedef，该函数没有任何参数也不返回任何东西。set_new_handler则是接受一个new_handler参数并返回一个new_handler参数。set_new_handler尾端的throw()表明该函数理论上不会抛出异常，详见Effective C++ 30。

set_new_handler的使用

set_new_handler的参数是一个指针，指向operator new无法分配足够内存时需要被调用的函数，其返回值指向set_new_handler被调用前正在执行的那个函数。具体使用方法如下：

1
2
3
4
5
6
7
8
9

void outOfMem(){
    cerr << “Unable to satisfy request for memory\n”；
    abort()；//使程序异常中止
｝
int main()｛
    set_new_handler(outOfMem);
    int *pBigDataArray = new int [10000000];
    ...
}

new-handler设计要求

 
一个设计良好的new-handler可以提供如下功能：

• 让更多内存可被调用
  一种实现方法是程序一开始执行时就分配一大块内存，而后当new_handler第一次被调用时，将它释放给程序使用。
• 安装另一个new-handler
  如果当前无法获取更多内存，但又明确知道其他某个new-handler有这个能力，就应该主动使用set-handler进行替换。
• 卸载new-handler
  将nullptr传递给set-new-handler。如果new-handler为nullptr，operator new会在分配内存不成功时抛出异常。
• 抛出bad_alloc（或派生自bad_alloc）的异常
  这样的异常不会被operator new捕捉，因此会被传播到内存索求处。
• 不返回
  直接调用abort或者exit。

针对class定制new-handler

 
或许你会希望不同的class以不同的new-handler来处理内存分配失败情况:

1
2
3
4
5
6
7
8
9
10
11
12

class X{
public:
    static void outOfMemory();
    ...
};
class Y{
public:
    static void outOfMemory();
    ...
};
X *px = new X;//分配失败时调用X::outOfMemory
Y *py = new Y;//分配失败时调用Y::outOfMemory

问题实例

假设当前我们准备处理Widget class的内存分配失败情况。首先必须定义Widget专有的new—handler，于是我们先声明一个类型为new handler的static成员：

1
2
3
4
5
6
7

class Widget{
public:
    static new_handler set_new_handler(new_handler p) throw();
    static void* operator new(size_t size) throw(bad_alloc);
private:
    static new_handler currentHandler;
};

1

new_handler Widget::currentHandler = nullptr;

1
2
3
4
5

new_handler Widget::set_new_handler(new_handler p) throw() {
    new_handler oldHandler = currentHandler;
    currentHandler = p;
    return oldHandler;
}

实例剖析

Widget的operator new做了如下事情：

1. 调用标准set_new_handler，告知A的错误处理函数。
   执行完毕后，A的new_handler被安装为global new_handler.
2. 调用global operator new，执行实际内存分配。
   如果失败，global operator new会调用Widget的new_handler，因为它刚才被安装为global.如果最终确实无法分配足够内存，会抛出一个bad_alloc的异常。此时A的operator new必须恢复global new_handler，然后再传播该异常。为了保证原本的new-handler总是正确安装，应该将global new_handler视为资源，使用RAII.
3. 如果global operator new能够分配足够的内存，A的operator new会返回一个指向分配所得的指针。
   Widget的析构函数会管理global new_handler，它会自动将Widget的operator new被调用前的global new_handler恢复。

解决方案

我们首先从资源管理类开始：

1
2
3
4
5
6
7
8
9
10

class NewHandlerHolder{
public:
    explicit NewHandlerHolder(new_handler nh):handler(nh) {}
    ~NewHandlerHolder() {set_new_handler(handler);}//恢复global new_handler
private:
    new_handler handler;//记录
    //阻止copy 详见Effective C++ 15
    NewHandlerHolder(const NewHandlerHolder&);
    NewHandlerHolder& operator=(const NewHandlerHolder&);
};

1
2
3
4
5

void* Widget::operator new(size_t size) throw(bad_alloc){
    NewHandlerHolder h(set_new_handler(currentHandler));//安装Widget::new_handler
    return ::operator new(size);//分配内存或抛出异常
    //资源管理对象析构 global new_handler恢复
}

1
2
3
4

void outOfMem();//声明内存分配失败处理函数
Widget::set_new_handler(outOfMem);
Widget* pw = new Widget;//分配失败调用outOfMem
string* ps = new string;//分配失败调用global new_handler

设计模板解决方案

 
我们通过观察可以发现，这一Widget::set_new_handler这一实现方案并不因class发生改变而改变，因此可以对实现复用。一种简单的做法是建立一个“mixin”风格的base class，这种bc允许dc继承某种特定能力—本实例中中是“设定class专属new_handler的能力”。然后将这个base class转换为template，这样每一个dc都将获得实体互异的class data复件。
该设计得bc让dc继承它们所需的set_new_handler与operator new，template则是为了保证每一个dc拥有一个实体互异的currentHandler成员变量。具体如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

template<typename T>
class NewHandlerHolderSupport{
public:
    static new_handler set_new_handler(new_handler p) throw();
    static void* operator new(size_t size) throw(bad_alloc);
    ...
private:
   static new_handler currentHandler;
};
template<typename T>
new_handler NewHandlerSupport<T>::set_new_handler(new_handler p) throw(){
    new_handler oldHandler = currentHandler;
    currentHandler = p;
    return oldHandler;
}
template<typename T>
void* NewHandlerSupport<T>::operator new(size_t size) throw(bad_alloc){
    NewHandlerHolder h(set_new_handler(currentHandler));
    return ::operator new(size);
}
template<typename T>
new_handler NewHandlerSupport<T>::currentHandler = nullptr;//static对象定义

1

class Widget::public NweHandlerSupport<Widget> {...}

class A继承自一个模版化的base class ，而后者又以A作为模板参数，这种技术被称为CRTP(curiously recuring template pattern)。

总结

1. set_new_handler允许客户指定一个函数，在内存无法分配时被调用。
2. Nothrow new只能保证内存分配时不会抛出异常，但是后续构造函数调用还是可能会抛出异常。

前言

 
所谓默认构造函数，指的是无需任何信息即可构造对象。有些对象需要它，诸如容器默认构造为空之类。但也有很多对象不需要它，比如工厂里每一个设备对应一个id，不存在没有id就能创建的设备。

缺乏默认构造函数所带来的限制

 
一般来说，如果一个类不存在默认构造函数，那么它的使用会有诸多限制。举例而言，现有一个class表示公司内部设备，其对象必须通过id才能生成：

1
2
3
4
5

class EquipmentPiece {
public:
    EquipmentPiece(int IDNumber);
    ...
};

数组初始化

我们无法构建一个由Equipment对象构成的数组，因为在产生数组时无法为数组中的对象指定构造参数:

1
2

EquipmentPiece bestPieces[10]; //error
EquipmentPiece *bestPieces = new EquipmentPiece[10];//error

使用non-heap数组(不在堆中给数组分配内存）

1
2
3
4
5
6
7
8
9

int ID1, ID2, ID3, ..., ID10; 
...
EquipmentPiece bestPieces[] = {
   EquipmentPiece(ID1), 
   EquipmentPiece(ID2),
   EquipmentPiece(ID3),
   ...,
   EquipmentPiece(ID10)
};

不过此法无法延伸至heap数组。

使用指针数组而非对象数组

1
2
3
4

typedef EquipmentPiece* PEP; 
PEP *bestPieces = new PEP[10];
for (int i = 0; i < 10; ++i)
    bestPieces[i] = new EquipmentPiece(ID Number);

不过该方案有两个缺点：

1. 删除数组前必须现删除数组里每个指针所指向的对象，否则内存泄漏。
2. 增加了内存分配量，比一般性数组多存储了指针。

这两个缺点均可解决，针对第一条，我们可以使用RAII避免内存泄漏。针对第二条，我们可以使用placement new操作完成构造（Effecive C++ 53）。具体如下：

1
2
3
4

void *rawMemory = operator new[](10*sizeof(EquipmentPiece));
EquipmentPiece *bestPieces = static_cast<EquipmentPiece*>(rawMemory);
for (int i = 0; i < 10; ++i)
    new(&bestPieces[i]) EquipmentPiece(ID Number);//placement new 在指定位置构造对象

不适用于template-based container classes

对于那些基于模板的容器类而言，被实例化的目标类型必须要有一个默认构造函数，因为那些template中几乎总会有一个以template类型参数作为元素类型的数组，举例而言：

1
2
3
4
5
6
7
8
9
10
11
12
13

template<class T>
class Array {
public:
    Array(int size);
    ...
private:
    T *data;
};
template<class T>
Array<T>::Array(int size){
    data = new T[size]; // 为每个数组元素依次调用 T::T()
    ...
}

virtual base class

不提供缺省构造函数的虚基类，使用起来及其低效。因为几乎所有的派生类在实例化时都必须给虚基类构造函数提供参数，这就要求所有由没有缺省构造函数的虚基类继承下来的派生类(无论有多远)都必须知道并理解提供给虚基类构造函数的参数的含义。

总结

 
如果构造函数可以确保对象的所有字段正确初始化，默认构造函数就可以不必出现。

前言

 
template metaprogramming(TMP 模板元编程)是编写template-based C++程序并执行于编译期的过程。
所谓TMP，指的是以C++写成、执行于C++编译器内的程序。一旦TMP程序结束执行，其输出，也就是template具现出的若干C++源码，便会一如既往地编译。

TMP的优点

 
TMP有两大优点：

1. 让某些事情变得容易，如果没有它，则可能无法完成某些任务。
2. 由于TMP执行于编译期，所以可以将工作从运行期转移到编译期。这直接导致了运行期的错误可以提前到编译期。另外，程序的每一个方面效率都得到了提高（较小的执行文件、较短的运行期、较少的内存）。然而缺点是编译时间变得很长。

TMP实例

 
上一节所描述的traits解法就是TMP，它引发编译期发生于类型身上的if…else条件判断。traits-based TMP解法是针对不同类型执行不同代码，每个函数所使用的操作都确保可以实行于其类型。

TMP已被证明是图灵完备的，你可以使用它声明变量、执行循环、编写调用函数等等。但你写出来的东西肯定明显和正常的c++不同，我们之前那一张用TMP写出来的ifelse就是如此（重载），不过那毕竟是汇编语言层级的TMP。

为了大致地描述一下TMP的工作方式，我们首先看看循环操作。TMP没有循环构件，所以循环效果藉由递归完成。TMP主要是一个函数式语言，因此使用递归也十分自然。但是，TMP的递归也并非我们所熟知的递归，因为它并不涉及递归函数调用，而是涉及“递归模板具现化”。

TMP版阶乘计算

通过实现阶乘计算，我们来示范以“递归模板具现化”实现循环，以及创建使用变量。

1
2
3
4
5
6
7
8

template<unsigned n>
struct Factorial{
    enum {value = n*Factorial<n-1>::value};
};
template<>
struct Factorial<0>{
    enum{value =1};//递归基
}

TMP可以达成的目标

1. 确保量度单位正确。
   在使用TMP时可以保证在编译期程序中所有量度单位的组合都正确，不论其计算多么复杂，这也就是为何TMP可被用来进行早期错误侦测。
2. 优化矩阵运算。
   比如五个矩阵的连乘会创建四个临时矩阵，甚至产生了四个作用于矩阵元素身上的循环。如果采用高级TMP技术，就能够削减内存消耗并合并循环，加速计算。
3. 生成客户定制的设计模式。
   将各种设计模式的某些特性加以整合，设计出独有的特性。这项技术已经超越了编程工艺领域如设计模式与智能指针，更广义地成为了generative programming的一个基础。

总结

1. TMP可将工作由运行期移到编译期，因而得以较早完成错误侦测和高效运行。
2. TMP可以定制设计模式，也可以规避某些并不适合特殊类型的代码。

前言

 
多态的本质在于：通过操作指向bc对象的指针或引用来操作dc对象，这样子引用或指针看起来就如同有多种类型。数组也可以使用多态，但其结果几乎不可能与你的预期结果一致。

问题实例

 
假设有一个类BST（比如是搜索树对象）和继承自BST类的派生类BalancedBST：

1
2

class BST { ... };
class BalancedBST: public BST { ... };

1
2
3
4
5

void printBSTArray(ostream& s,const BST array[],int numElements){
    for (int i = 0; i < numElements;++i) {
        s << array[i];
    }
}

1
2

BalancedBST bBSTArray[10];
printBSTArray(cout, bBSTArray, 10);

问题剖析

 
原因很简单：

1
2
3

for (int i = 0; i < numElements;++i) {
    s << array[i];
}

删除数组

 
如果我们试图通过一个bc指针去删除dc数组，那么结果也会崩溃，有实例如下：

1
2
3
4
5
6

void deleteArray(BST array[]){
    delete [] array;
}
BalancedBST *balTreeArray = new BalancedBST[50];
...
deleteArray(balTreeArray);

1
2
3

while(...)
    array[i].BST::~BST(); 
}

总结

 
简单的说，多态和指针算术不能混用.又由于数组总是会牵扯一些指针算术，所以多态和数组也不能混用。
一般而言，如果你尽量“不用一个具体类继承自另一个具体类”，那你应该会很少犯这种错误。

问题描述

 
STL主要由“容器、迭代器、算法”的templates构成，但也覆盖了若干工具性templates，其中有一个名为advance，用来将迭代器移动若干距离：

1
2

template<typename IterT,typename Dist>
void advance(IterT& iter,DistT d);

迭代器分类

 
我们首先回顾一下STL中迭代器的分类：

1. input与output迭代器
   它们只能向前移动，一次一步，用户只能读取/涂写它们所指的东西，显然这是在模仿输入输出文件的读写指针。istream_iterator与ostream_iterator是这一类迭代器的代表。
   由于这两类都只能向前移动，并且最多读写一次，所以他们只适合“一次性操作算法”。
2. forward迭代器
   这类迭代器能完成input与output迭代器所做的任何事，并且可以读或写其所指物一次以上。所以它们可执行多次性算法。STL并未提供SingleLinked List，但不难想象，这类容器的迭代器就是forward迭代器。
3. Bidirection迭代器
   比上一类更加强大，支持双向移动。STL中list,map,set(以及它们的multi版本）的迭代器就属于这一分类。
4. random access迭代器
   在Bidirection迭代器的基础上支持了算术操作，也就是说可以在常量时间内前后移动任意距离。这种操作类似于指针算术，而它也确实以内置指针为榜样。vector，deque，string的迭代器便是这种类型。

对于这5种分类，C++标准程序库分别提供专属的卷标结构（tag struct）加以确认：

1
2
3
4
5

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag:public input_iterator_tag {};
struct bidirectional_iterator_tag:public forward_iterator_tag {};
struct random_access_iterator_tag:public bidirection_iterator_tag {};

问题实例

 
将目光拉回至advance函数。既然不同的迭代器具有不同的性质，那我们自然会想到：针对不同的迭代器，advance内部执行不同的操作：

1
2
3
4
5
6
7
8
9

template<typename IterT,typename Dist>
void advance(IterT &it,Dist d){
    if(iter is random accesss iterator){
        it+=d;
    }
    else{
        while(...) ++it;
    }
}

Traits

 
Traits并非是c++的某个关键词或者一个事先定义好的构件；这是一种技术，也是c++程序员共同遵循的协议。其内置要求之一是：对于内置类型与用户自定义类型的表现必须一样好。举例而言，即如果上述advance接受的是一个指针与一个int参数，它必须仍然可以有效运作。

Traits的实现

Traits必须可以施加于内置类型，表明我们不应该使用“在自定义类型里附加信息”的技术，因为原始指针无法附加信息。
标准技术是把它放进一个template及一个或者多个特化版本中。针对迭代器的版本名为iterator_traits:

1
2

template<typename IterT> 
struct iterator_traits;//处理迭代器分类信息

Traits的运作方式

仍以迭代器为例，iterator_traits的运作机理是，针对每一个类型IterT，在struct iterator_traits中必然声明了某个typedef名为iterator_category.这个typedef用来确认IterT的迭代器分类。

实现iterator_traits

自定义用户类型

iterator_traits以两个部分来实现上述要求。
首先，它要求每个“用户自定义的迭代器类型”必须嵌套一个typedef，名为iterator_category，用以确认当前的卷标结构。举例而言，deque的迭代器可能如下：

1
2
3
4
5
6
7
8

template<...> 
class deque{
public:
    class iterator{
    public:
        typedef random_access_iterator_tag iterator_category;
    };
};

1
2
3
4
5
6
7
8

template<...> 
class list{
public:
    class iterator{
    public:
        typedef bidirectional_iterator_tag iterator_category；
    };
};

1
2
3
4

template<typename IterT>
struct iterator_traits{
    typedef typename IterT::iterator_category iterator_category;
}

指针类型

上述设计对自定义类型而言没问题，但对指针则行不通，因为指针不可能嵌套typedef，因此iterators_traits为指针类型提供了一个偏特化版本，如下所示：

1
2
3
4

template<typename IterT>
struct iterator_traits<IterT *>{//偏特化
    typedef random_access_iterator_tag iterator_cagetory;
}

总结

设计一个traits classes需要以下步骤：

1. 确认若干个你希望将来可以取得的信息（例如对迭代器的分类category）
2. 为该信息提供名称（如iterator_category）
3. 提供一个template与一组特化版本

解决方案

有了iterator_traits后我们似乎可以执行先前的伪代码了：

1
2
3
4
5
6

template<typename IterT,typename Dist>
void advance(IterT& it,Dist d){
    if(typeid(typename std::iterator_traits<IterT>::iterator_cagetory)==
        typeid(std::random_access_iterator_tag))
    ...
}

我们所需要的是一个能在编译期完成if…else操作的条件式，C++恰巧有某种特性支持这种行为：重载。

当我们重载某个函数f，我们必须详细叙述各个重载件的参数类型。当你调用f，编译期便根据实参选择最恰当的重载件。这简直为我们的问题量身定制。针对advance函数，我们所需要做的就是产生两版重载函数，内含advance的真正操作，但各自接受不同类型的iterator_category对象。具体如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

template<typename IterT,typename Dist>
void doadvance(IterT &iter,Dist d,std::random_access_iterator_tag){
    iter+=d;
}
template<typename IterT,typename Dist>
void doadvance(IterT &iter,Dist d,std::bidirectional_iterator_tag){
    if(d>=0) {
        while(d--) ++iter;
    }
    else{
        while(d++) --iter;
    }
}
template<typename IterT,typename Dist>
void doadvance(IterT &iter,Dist d,std::input_iterator_tag){
    if(d>=0) {
        throw std::out_of_range("Negative distance");
    }
    else{
        while(d--) ++iter;
    }
}

最终，advance函数的实现如下所示：

1
2
3
4

template<typename IterT,typename Dist>
void advance(IterT &iter,Dist d){
    doadvance(iter,d,typename std::iterator_traits<IterT>::iterator_category());
}

如何使用traits classes

1. 建立一组重载函数或函数模板（doadvance），彼此之间的差异仅在于各自的traits参数，令每个函数实现码与其接受的traits信息相匹配。
2. 建立一个控制函数或函数模板（advance），它调用上述函数并传递traits class所提供的信息。

总结

1. traits class使得“类型相关信息”在编译期可用，它们以templates和偏特化完成实现。
2. 整合重载技术后我们可以在编译期执行ifelse测试。