X和Y是向量，最初保存在存储器中，a是标量。这个问题就是所谓的SAXPY或DAXPY循环，它们构成了Linpack基准测试的内层循环。SAXPY表示“单精度a × X加Y” (single- precision a x X plus Y)；DAXPY表示“双精度a × X加Y” (double precision a × X plus Y)。Linpack是一组线性代数例程，Linpack 基准测试包括执行高斯消去法的例程。
在VMIPS结构中，可寻址单位为1个字节，所以我们示例的步幅将为800。由于矩阵的大小在编译时可能是未知的，或者就像向量长度一样，在每次执行相同语句时可能会发生变化，所以必须对步幅值进行动态计算。向量步幅可以和向量起始地址一样，放在通用寄存器中。然后，VMIPS指令LVWS (load vector with stride)将向量提取到向量寄存器中。同样，在存储非单位步幅向量时，使用指令SVwS (store vector with stride)。为了支持大于1的步幅，会使存储器系统变得复杂。在引入非单位步幅之后，就有可能频繁访问同一个组。当多个访问对一个存储器组产生竞争时，就会发生存储器组冲突，从而使某个访问陷入停顿。如果满足以下条件则会产生组冲突，从而产生停顿。
如上所述，CUDA编程模型为每个循环迭代指定一个CUDA，为每个线程块指定一个唯一的识别编号(blockIdx)，也为块中的每个CUDA线程指定一个唯一识别编号(threadIdx)。因此，它创建8192个CUDA线程，并使用唯一编号完成数组中每个元素的寻址，因此，不存在递增和分支编码。前3条PTX指令在R8中计算出唯一的元素字节偏移，会将这一偏移量加到数组的基地址中。以下PTX指令载入两个双精度浮点操作数，对其进行相乘和相加，并存储求和结果。(下面将描述与CUDA代码if (i < n)相对应的PTX代码。)
假定L1和L2是直接映射的，L1的块大小为b个字节，L2的块大小为4b个字节。假定L1包含两个块，起始地址为x和x+b，且x mod 4b = 0,也就是说，x也是L2中一个块的起始地址；因此，L2中的单个块包含着L1块x、x+b、x+2b和x+3b。假定处理器生成一个对块y的引用，这个块对应于在两个缓存中都包含x的块，从而会产生缺失。由于L2产生缺失，所以它会提取4b个字节，并替换包含x、x+b、x+2b和x+3b的块，而L1取得b个字节，并替换包含x的块。由于L1仍然包含x+b，但L2不再包含，因此不再保持包含特性。
（2）存储器寻址。几乎所有桌面计算机和服务器计算机（包括80x86、ARM和MIPS）都使用字节寻址来访问存储器操作数。有些体系结构（像ARM和MIPS）要求操作对象必须是对齐的。一个大小为s的对象，其字节地址为A，如果A mod s = 0，则对这个对象的访问是对齐的。如果操作数是对齐的，访向速度通常会快一些。
/* 优化之后 */ for (jj = 0; jj < N; jj += B) for (kk = 0; kk < N; kk += B) for (i = 0; i < N; i ++) for (j = kk; j < min(jj+B, N); j ++) { r = 0; for (k = kk; k < min(kk+B, N); k ++) r = r + y[i][k] * z[k][j]; x[i][j] = r; }
在将DDR SDRAM封装为DIMM形式时，会用DIMM峰值带宽进行标记，这种标记方法很容易引起混淆。比如，之所得到PC2100这样一个DIMM名称，是源于133MHz x 2 x 8字节=2100MB/s，为了避免这种混淆，在对芯片本身进行标记时，给出的不是其时钟频率，而是每秒比特数，因此一个133MHz的DDR芯片被称为DDR266。表2-3给出了时钟频率、每芯片每秒钟的传送数目、芯片名称、DIMM带宽和DIMM名称之间的关系。
IBM 370体系结构在20世纪70年代添加了一个由VMM管理的迂回层，解决了页表问题。来宾操作系统和以前一样保存自己的页表，所以就不再需要影子页表。在许多RISC计算机中，为了实现TLB的虚拟化，VMM管理实际TLB，并拥有每个来宾VM的TLB内容副本。为实现这一功能，所有访问TLB的功能都必须被捕获。具有进程ID标记的TLB可以将来自不同VM与VMM的项目混合在一起，所以不需要在切换VM时刷新TLB。与此同时，VMM在后台支持VM的虚拟进程ID与实际进程ID之间的映射。
在实际程序中，人们通常不知道循环的上限。假定此上限为n，我们希望展开循环，制作循环体的k个副本。我们生成的是一对连续循环，而不是单个展开后的循环。第一个循环执行(n mod k)次，其主体就是原来的循环。第二个循环是由外层循环包围的展开循环，迭代(n/k)次。当n值较大时，大多数执行时间都花费在未展开的循环体上。在前面的例子中，通过展开消除了开销指令，尽管这样会显著增大代码规模，但却可以提高这一循环的性能。如果针对先前介绍的流水线来调度展开后的循环，它的执行情况又会如何呢?
IBM 360/91浮点单元使用一种支持乱序执行的高级方案。这一方案由Robert Tomasulo发明，它会跟踪指令的操作数何时可用，将RAW冒险降至最低，并在硬件中引入寄存器重命名功能，将WAW和WAR冒险降至最低。在现代处理器中存在这一方案的许多变体，但跟踪指令相关以允许在操作数可用时立即执行指令、重命名寄存器以避免WAR和WAW冒险，这些核心概念仍然是它们的共同特征。
Loop: LD R2,0(R1) ; R2=array element DADDIU R2,R2,#1 ; increment R2 SD R2,0(R1) ; store result DADDIU R1,R1,#8 ; increment poi nter BNE R2,R3, LOOP ;branch if not last element
（2）不必要的相关——在有无数个寄存器时，就可以消除真寄存器数据相关之外的所有其他数据相关。但是，由于递归或代码生成约定而造成的相关仍然会引入一些不必要的真数据相关。其中一个例子就是在一个简单的 for 循环中对于控制变量的相关。由于控制变量在每次循环迭代时都会递增，所以循环中包含至少一个相关。Wall 的研究中包含了数量有限的一些此类优化，但更积极地应用这些优化方式有可能增加ILP的数目。此外，特定的代码生成约定也会引入一些不必要的相关，特别是在使用返回地址窗口和栈指针寄存器时（它会在调用/返回序列中递增和递减）。Wall消除了返回地址寄存器的影响，但在链接约定中使用规模指针可能会导致“不必要的”相关。
图3-21对 ARM A8.上CPI各组成分量的估计值表明：流水线停顿是增大基本CPI的主要因素。eon值得专门一提，它完成基于整数的图形计算（光线跟踪），而且缓存缺失很少。由于大量使用乘法，计算非常密集，所以单个乘法流水线可能会成为主要瓶颈。这一估计值是利用L1和L2缺失率与代价来计算每个指令中因为L1和L2生成的停顿而获得的。从具体模拟器测得的CPI中减去这些估计值即可获得流水线停顿。流水线停顿包含所有这3种冒险再加上一些次要影响，比如路预测错误等
组态5__STL_CLASS_PARTIAL_SPECIALIZATION。如果编译器支持 partial specialization of class templates(模板类偏特化)就定义。在模板类一般化设计之外（全特化），针对某些template做特殊设计。“所谓的partial specialization的另一个意思是提供另一份template定义式,而其本身仍是templatized”。全特化就是所有的模板都为具体的类。T*特化允许用指针类型匹配的模式（也只能匹配指针类型）。const T*特化允许使用指向const的指针类型匹配（也只能匹配指向const的指针）。
const INT operator--(int) { INT temp=*this; --(*this); return temp; }
int& operator*() const { return (int&)m_i; } private: int m_i;
};
ostream& operator<<(ostream& os,const INT &i) { os<<'['<<i.m_i<<']'; return os; }
intmain() { INT I(5); cout<<I++; cout<<++I; cout<<I--; cout<<--I; cout<<*I; }
前闭后开区间表示法
任何一个STL算法，都需要获得由一对迭代器（泛型指针）所标示的区间，用以表示操作范围，这一对迭代器所标示的是个所谓的前闭后开区间，以[first,last)表示，也就是说，整个实际范围从first开始，直到last-1.迭代器last所指的是“最后一个元素的下一位置”。这种off by one（偏移一格，或说pass the end）的标示法，带来了很多方便，例如下面两个STL算法的循环设计，就显得干净利落：
第一级配置器直接使用malloc()，free()，realloc()等C函数执行实际的内存配置、释放、重配置操作，并实现出类似C++ new handler机制。它有独特的out-of-memory内存处理机制：在抛出std::bad_alloc异常之前，调用内存不足处理例程尝试释放空间，如果用户没有定义相应的内存不足处理例程，那么还是会抛出异常。
所谓C++ new handler机制是，你可以要求系统在内存配置要求无法被满足时，调用一个你所指定的函数。换句话说，一旦::operator new无法完成任务，在丢出std::bad_alloc异常状态之前，会先调用由客户端指定的处理例程，该处理例程通常即被称为new-handler。new-handler解决内存不足的做法有特定的模式。
template <bool threads, int inst> class__default_alloc_template {
private: // 實際上我們應該使用 static const int x = N // 來取代 enum { x = N }, 但目前支援該性質的編譯器還不多。 # ifndef __SUNPRO_CC enum {__ALIGN = 8}; enum {__MAX_BYTES = 128}; enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; # endif staticsize_tROUND_UP(size_t bytes){ return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1)); } __PRIVATE: unionobj { unionobj * free_list_link; char client_data[1]; /* The client sees this. */ }; private: # ifdef __SUNPRO_CC static obj * __VOLATILE free_list[]; // Specifying a size results in duplicate def for 4.1 # else static obj * __VOLATILE free_list[__NFREELISTS]; # endif staticsize_tFREELIST_INDEX(size_t bytes){ return (((bytes) + __ALIGN-1)/__ALIGN - 1); }
// Returns an object of size n, and optionally adds to size n free list. staticvoid *refill(size_t n); // Allocates a chunk for nobjs of size "size". nobjs may be reduced // if it is inconvenient to allocate the requested number. staticchar *chunk_alloc(size_t size, int &nobjs);
/* n must be > 0 */ staticvoid * allocate(size_t n) { obj * __VOLATILE * my_free_list; obj * __RESTRICT result;
if (n > (size_t) __MAX_BYTES) { return(malloc_alloc::allocate(n)); } my_free_list = free_list + FREELIST_INDEX(n); // Acquire the lock here with a constructor call. // This ensures that it is released in exit or during stack // unwinding. # ifndef _NOTHREADS /*REFERENCED*/ lock lock_instance; # endif result = *my_free_list; if (result == 0) { void *r = refill(ROUND_UP(n)); return r; } *my_free_list = result -> free_list_link; return (result); };
/* Returns an object of size n, and optionally adds to size n free list.*/ /* We assume that n is properly aligned. */ /* We hold the allocation lock. */ template <bool threads, int inst> void* __default_alloc_template<threads, inst>::refill(size_t n) { int nobjs = 20; //调用chunk_alloc()，尝试取得nobjs个区块作为free list的新节点，注意参数nobjs是pass by reference char * chunk = chunk_alloc(n, nobjs); obj * __VOLATILE * my_free_list; obj * result; obj * current_obj, * next_obj; int i;
if (1 == nobjs) return(chunk); my_free_list = free_list + FREELIST_INDEX(n);
/* We allocate memory in large chunks in order to avoid fragmenting */ /* the malloc heap too much. */ /* We assume that size is properly aligned. */ /* We hold the allocation lock. */ template <bool threads, int inst> char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs) { char * result; size_t total_bytes = size * nobjs; size_t bytes_left = end_free - start_free;
if (bytes_left >= total_bytes) { result = start_free; start_free += total_bytes; return(result); } elseif (bytes_left >= size) { nobjs = bytes_left/size; total_bytes = size * nobjs; result = start_free; start_free += total_bytes; return(result); } else { size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);//注意此处申请的空间的大小 // Try to make use of the left-over piece. if (bytes_left > 0) { obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj *)start_free) -> free_list_link = *my_free_list; *my_free_list = (obj *)start_free; } start_free = (char *)malloc(bytes_to_get); if (0 == start_free) { int i; obj * __VOLATILE * my_free_list, *p; // Try to make do with what we have. That can't // hurt. We do not try smaller requests, since that tends // to result in disaster on multi-process machines. for (i = size; i <= __MAX_BYTES; i += __ALIGN) { my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (0 != p) { *my_free_list = p -> free_list_link; start_free = (char *)p; end_free = start_free + i; return(chunk_alloc(size, nobjs)); // Any leftover piece will eventually make it to the // right free list. } } end_free = 0; // In case of exception. start_free = (char *)malloc_alloc::allocate(bytes_to_get); // This should either throw an // exception or remedy the situation. Thus we assume it // succeeded. } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; return(chunk_alloc(size, nobjs)); } }
与uninitialized_copy()一样，uninitialized_fill()必须具备“commit or rollback”语意，换句话说，它要么产生出所有必要元素，要么不产生任何元素，如果有任何一个copy constructor丢出异常（exception），uninitialized_fill()，必须能够将已产生的所有元素析构掉。
template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)； 参数: first, last 指出被复制的元素的区间范围[first，last). result 指出复制到目标区间的具体位置[result-(last-first),result) 返回值： 返回一个迭代器，指出已被复制元素区间的起始位置
stack是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口。stack允许新增元素，移除元素、取得最顶端元素，但不允许有遍历行为。若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。同时，也可以使用list作为底层实现，它也是具有双向开口的数据结构。由于stack系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter(配接器)。因此，STL stack往往不被称为container，而被归类为container adapter。
queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口。queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素，但不允许遍历行为，也不提供迭代器。若以deque为底部结构并封闭其头端入口和尾部出口，便轻而易举地形成了一个queue。同时，也可以使用list作为底层实现，它也是具有双向开口的数据结构。因为queue的所有元素的进出都必须符合“先进先出”的条件，queue不提供走访功能，也不提供迭代器。
template <classInputIterator, classForwardIterator> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2) { for ( ; first1 != last1; ++first1) for (ForwardIterator iter = first2; iter != last2; ++iter) if (*first1 == *iter) return first1; return last1; }
template <classInputIterator, classForwardIterator, classBinaryPredicate> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp) { for ( ; first1 != last1; ++first1) for (ForwardIterator iter = first2; iter != last2; ++iter) if (comp(*first1, *iter)) return first1; return last1; }
for_each
将仿函数施加于区间内的每个元素之上。不能够改变元素内容，返回值被忽略。可以用于打印元素的值等。
1 2 3 4 5 6
template <classInputIterator, classFunction> Function for_each(InputIterator first, InputIterator last, Function f){ for ( ; first != last; ++first) f(*first); return f; }
generate
将仿函数的运算结果赋值给区间内的每一个元素
1 2 3 4 5
template <classForwardIterator, classGenerator> voidgenerate(ForwardIterator first, ForwardIterator last, Generator gen){ for ( ; first != last; ++first) *first = gen(); }
generate_n
将仿函数的运算结果赋值给迭代器first开始的n个元素上
1 2 3 4 5 6
template <classOutputIterator, classSize, classGenerator> OutputIterator generate_n(OutputIterator first, Size n, Generator gen){ for ( ; n > 0; --n, ++first) *first = gen(); return first; }
template <classForwardIterator, classT> ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value){ first = find(first, last, value); ForwardIterator next = first; return first == last ? first : remove_copy(++next, last, first, value); }
template <classInputIterator, classOutputIterator, classT> OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value){ for ( ; first != last; ++first) if (*first != value) { *result = *first; ++result; } return result; }
remove_if
移除[first, last)区间内所有被仿函数pred核定为true的元素。它并不真正从容器中删除那些元素（换句话说，容器大小并未改变），每一个不符合pred条件的元素都会被轮番赋值给first之后的空间。返回值ForwardIterator标示出重新整理后的最后元素的下一位置，此算法会留有一些残余数据，如果要删除那些残余数据，可将返回的迭代器交给区间所在之容器的erase() member function。
1 2 3 4 5 6 7
template <classForwardIterator, classPredicate> ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred){ first = find_if(first, last, pred); ForwardIterator next = first; return first == last ? first : remove_copy_if(++next, last, first, pred); }
template <classBidirectionalIterator> void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) { while (true) if (first == last || first == --last) return; else iter_swap(first++, last); }
template <classRandomAccessIterator> void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { while (first < last) iter_swap(first++, --last); }
template <classBidirectionalIterator> inlinevoidreverse(BidirectionalIterator first, BidirectionalIterator last){ __reverse(first, last, iterator_category(first)); }
template <classRandomAccessIterator, classDistance> void __rotate(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Distance*, random_access_iterator_tag) { Distance n = __gcd(last - first, middle - first); while (n--) __rotate_cycle(first, last, first + n, middle - first, value_type(first)); }
template <classEuclideanRingElement> EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n) { while (n != 0) { EuclideanRingElement t = m % n; m = n; n = t; } return m; }
template <classForwardIterator, classT, classCompare, classDistance> ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp, Distance*, forward_iterator_tag) { Distance len = 0; distance(first, last, len); Distance half; ForwardIterator middle; while(len > 0) { half = len >> 1; middle = first; //对于前向迭代器才需要用这种方式寻找位置，对于随机访问迭代器可以直接+ first = advance(middle, half); if(*middle < value) { first = middle + 1; ++first; len = len - half - 1; } else//即使是相等，还需要迭代，因为要找出相等的元素中最前一个的位置 { len = half; } } return first; }
template <classRandomAccessIterator, classT, classCompare, classDistance> RandomAccessIterator __lower_bound(RandomAccessIterator first, RandomAccessIterator last, const T& value, Compare comp, Distance*, random_access_iterator_tag) { Distance len = last - first; Distance half; RandomAccessIterator middle;
while (len > 0) { half = len >> 1; middle = first + half; if (comp(*middle, value)) { first = middle + 1; len = len - half - 1; } else len = half; } return first; }
template <classForwardIterator, classT, classDistance> ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Distance*, forward_iterator_tag) { Distance len = 0; distance(first, last, len); Distance half; ForwardIterator middle;
while (len > 0) { half = len >> 1; middle = first; advance(middle, half); if (value < *middle) len = half; else { first = middle; ++first; len = len - half - 1; } } return first; }
template <classRandomAccessIterator, classT, classDistance> RandomAccessIterator __upper_bound(RandomAccessIterator first, RandomAccessIterator last, const T& value, Distance*, random_access_iterator_tag) { Distance len = last - first; Distance half; RandomAccessIterator middle;
while (len > 0) { half = len >> 1; middle = first + half; if (value < *middle) len = half; else { first = middle + 1; len = len - half - 1; } } return first; } template <classForwardIterator, classT, classCompare, classDistance> ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp, Distance*, forward_iterator_tag) { Distance len = 0; distance(first, last, len); Distance half; ForwardIterator middle;
while (len > 0) { half = len >> 1; middle = first; advance(middle, half); if (comp(value, *middle)) len = half; else { first = middle; ++first; len = len - half - 1; } } return first; }
template <classRandomAccessIterator, classT, classCompare, classDistance> RandomAccessIterator __upper_bound(RandomAccessIterator first, RandomAccessIterator last, const T& value, Compare comp, Distance*, random_access_iterator_tag) { Distance len = last - first; Distance half; RandomAccessIterator middle;
while (len > 0) { half = len >> 1; middle = first + half; if (comp(value, *middle)) len = half; else { first = middle + 1; len = len - half - 1; } } return first; }
template <classForwardIterator, classT> boolbinary_search(ForwardIterator first, ForwardIterator last, const T& value){ ForwardIterator i = lower_bound(first, last, value); return i != last && !(value < *i); }
template <classForwardIterator, classT, classCompare> boolbinary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp){ ForwardIterator i = lower_bound(first, last, value, comp); return i != last && !comp(value, *i); }
template <classBidirectionalIterator> boolnext_permutation(BidirectionalIterator first, BidirectionalIterator last){ if (first == last) returnfalse; BidirectionalIterator i = first; ++i; if (i == last) returnfalse; i = last; --i;
for(;;) { BidirectionalIterator ii = i; --i; if (*i < *ii) { BidirectionalIterator j = last; while (!(*i < *--j)); iter_swap(i, j); reverse(ii, last); returntrue; } if (i == first) { reverse(first, last); returnfalse; } } }
template <classBidirectionalIterator, classCompare> boolnext_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp){ if (first == last) returnfalse; BidirectionalIterator i = first; ++i; if (i == last) returnfalse; i = last; --i;
for(;;) { BidirectionalIterator ii = i; --i; if (comp(*i, *ii)) { BidirectionalIterator j = last; while (!comp(*i, *--j)); iter_swap(i, j); reverse(ii, last); returntrue; } if (i == first) { reverse(first, last); returnfalse; } } }
template <classBidirectionalIterator> boolprev_permutation(BidirectionalIterator first, BidirectionalIterator last){ if (first == last) returnfalse; BidirectionalIterator i = first; ++i; if (i == last) returnfalse; i = last; --i;
for(;;) { BidirectionalIterator ii = i; --i; if (*ii < *i) { BidirectionalIterator j = last; while (!(*--j < *i)); iter_swap(i, j); reverse(ii, last); returntrue; } if (i == first) { reverse(first, last); returnfalse; } } }
template <classBidirectionalIterator, classCompare> boolprev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp){ if (first == last) returnfalse; BidirectionalIterator i = first; ++i; if (i == last) returnfalse; i = last; --i;
for(;;) { BidirectionalIterator ii = i; --i; if (comp(*ii, *i)) { BidirectionalIterator j = last; while (!comp(*--j, *i)); iter_swap(i, j); reverse(ii, last); returntrue; } if (i == first) { reverse(first, last); returnfalse; } } }
template <classRandomAccessIterator, classDistance> void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last, Distance*) { if (first == last) return; for (RandomAccessIterator i = first + 1; i != last; ++i) #ifdef __STL_NO_DRAND48 iter_swap(i, first + Distance(rand() % ((i - first) + 1))); #else iter_swap(i, first + Distance(lrand48() % ((i - first) + 1))); #endif }
template <classRandomAccessIterator> inlinevoidrandom_shuffle(RandomAccessIterator first, RandomAccessIterator last){ __random_shuffle(first, last, distance_type(first)); }
template <classRandomAccessIterator, classRandomNumberGenerator> voidrandom_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand){ if (first == last) return; for (RandomAccessIterator i = first + 1; i != last; ++i) iter_swap(i, first + rand((i - first) + 1)); }
template <classRandomAccessIterator> void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) { if (first == last) return; for (RandomAccessIterator i = first + 1; i != last; ++i) __linear_insert(first, i, value_type(first)); }
template <classRandomAccessIterator, classCompare> void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { if (first == last) return; for (RandomAccessIterator i = first + 1; i != last; ++i) __linear_insert(first, i, value_type(first), comp); }
template <classRandomAccessIterator, classT> inlinevoid __linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*) { T value = *last; if (value < *first) { copy_backward(first, last, last + 1); *first = value; } else __unguarded_linear_insert(last, value); }
template <classRandomAccessIterator, classT, classCompare> inlinevoid __linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*, Compare comp) { T value = *last; if (comp(value, *first)) { copy_backward(first, last, last + 1); *first = value; } else __unguarded_linear_insert(last, value, comp); }
template <classRandomAccessIterator, classT> void __unguarded_linear_insert(RandomAccessIterator last, T value) { RandomAccessIterator next = last; --next; while (value < *next) { *last = *next; last = next; --next; } *last = value; }
template <classRandomAccessIterator, classT, classCompare> void __unguarded_linear_insert(RandomAccessIterator last, T value, Compare comp) { RandomAccessIterator next = last; --next; while (comp(value , *next)) { *last = *next; last = next; --next; } *last = value; }
template <classT> inlineconst T& __median(const T& a, const T& b, const T& c) { if (a < b) if (b < c) return b; elseif (a < c) return c; else return a; elseif (a < c) return a; elseif (b < c) return c; else return b; }
while (last - first >= two_step) { result = merge(first, first + step_size, first + step_size, first + two_step, result, comp); first += two_step; } step_size = min(Distance(last - first), step_size);
merge(first, first + step_size, first + step_size, last, result, comp); }
// 证同函数，任何函数经过后不会改变，用于set rb_tree keyOfValue op // identity is an extensions: it is not part of the standard. template <class_Tp> struct_Identity : public unary_function<_Tp,_Tp> { const _Tp& operator()(const _Tp& __x)const{ return __x; } }; template <class_Tp> structidentity : public _Identity<_Tp> {}; // 选择函数，返回pair第一元素，用于map rb_tree keyOfValue op // select1st and select2nd are extensions: they are not part of the standard. template <class_Pair> struct_Select1st : public unary_function<_Pair, typename _Pair::first_type> { consttypename _Pair::first_type& operator()(const _Pair& __x)const{ return __x.first; } }; // 选择函数，返回pair第二元素 template <class_Pair> struct_Select2nd : public unary_function<_Pair, typename _Pair::second_type> { consttypename _Pair::second_type& operator()(const _Pair& __x)const{ return __x.second; } }; template <class_Pair> structselect1st : public _Select1st<_Pair> {}; template <class_Pair> structselect2nd : public _Select2nd<_Pair> {}; // 传回一个忽略另一个 // project1st and project2nd are extensions: they are not part of the standard template <class_Arg1, class_Arg2> struct_Project1st : public binary_function<_Arg1, _Arg2, _Arg1> { _Arg1 operator()(const _Arg1& __x, const _Arg2&)const{ return __x; } }; template <class_Arg1, class_Arg2> struct_Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> { _Arg2 operator()(const _Arg1&, const _Arg2& __y)const{ return __y; } }; template <class_Arg1, class_Arg2> structproject1st : public _Project1st<_Arg1, _Arg2> {}; template <class_Arg1, class_Arg2> structproject2nd : public _Project2nd<_Arg1, _Arg2> {};
配接器
配接器（adapters）在 STL 组件的灵活组合运用功能上，扮演着轴承、转换器的角色。Adapter 这个概念，事实上是一种设计模式。《Design Patterns》一书提到 23 个最普及的设计模式，其中对 adapter 样式的定义如下：将一个 class 的接口转换为另一个 class 的接口，使原本因接口不兼容而不能合作的 classes，可以一起运作。
配接器之概观与分类
STL 所提供的各种配接器中，改变容器（containers）接口者，我们称为 container adapter，改变迭代器（iterators）接口者，我们称之为 iterator adapter，改变仿函数（functors）接口者，我们称为 function adapter。
template <classtype> classPoint3d { public: Point3d(type x = 0.0, type y = 0.0, type z = 0.0) : _x(x), _y(y), _z(z) {} type x(){return _x;} voidsetx(type xval){x = xval;} private: type _x; type _y; type _z; }
也可以坐标类型和坐标数目都参数化：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <classtype, int dim> classPoint { public: Point(); Point(type coords[dim]) { for (int index = 0; index < dim; index ++) _coords[index] = coords[index]; } type& operator[](int index) { assert(index < dim && index >= 0); return _coords[index]; } private: type _coords[dim]; }
加入封装后的布局成本
答案是并没有增加布局成本。就像C struct一样，data members直接在每一个object中，但是memeber functions虽然含在class的声明之内，却不出现在object中。每一个non-inline member function只会诞生一个函数实体。至于每一个拥有零个或一个定义的inline function则会在其每一个使用者(模块)身上产生一个函数实体。
表格驱动对象模型：把所有与members相关的信息抽取出来，放在一个data member table和一个member function table之中，class object本身则含有指向这两个表格的指针。member function table是一系列的slot，每一个slot指出一个member function，data member table则直接含有数据本身:
C++对象模型：nonstatic data members被配置于每一个class object之内，static data members则被存放在所有的class object之外。static和nonstatic function members也被放在所有的class object之外。
C++最初采用的继承模型并不运用任何间接性：base class subobject的data members被直接放置于derived class object中。这提供了对base class members最紧凑而且最有效率的存取。缺点是base class members的任何改变，包括增加、移除或改变类型等等，都使得所有用到此base class或其derived class的objects必须重新编译。
自c++ 2.0起才新导入的virtual base class，需要一些间接的base class表现方法。Virtual base class的原始模型是在class object中为每一个有关联的virtual base class加上一个指针。其它演化出来的模型则若不是导入一个virtual base class table，就是扩充原已存在的virtual table，以便维护每一个virtual base class的位置。
真正的问题并不在于所有“使用者自定义类型”的声明是否必须使用相同的关键词，问题在于使用class或struct关键词是否可以给予“类型的内部声明”以某种承诺。也就是说，如果struct关键词的使用实现了C的数据萃取观念，而class关键词实现的是C++的ADT (Abstract Data Type）观念，那么当然“不一致性”是一种错误的语言用法。就好像下面这种错误，一个object被矛盾地声明为static和extern:
面向对象模型（object-oriented model）。在此模型中有一些彼此相关的类型，通过一个抽象的 base class (用以提供共通接口）被封装起来。Library_materials class 就是一个例子，真正的 subtypes 例如 Book、Video、Compact_Disc、Puppet、Laptop 等等都可以从那里派生而来：
编译器必须确保如果一个object含有一个或一个以上的vptrs，那些vptrs的内容不会被base class object初始化或改变。OO 程序设计不支持对 object 的直接处理，考虑如下例子：
1 2 3 4 5 6 7
ZooAnimal za; ZooAnimal *pza;
Bear b; Panda *pp = new Panda;
pza = &b;
其内存布局可能如下：
将 za 或 b 的地址，或 pp 所含内容（也是地址）指定给 pza，显然没问题。一个 pointer 或一个 reference 之所以支持多态，是因为它们并不引发内存中任何“与类型有关的内存委托操作”，改变的只是他们所指向的内存的“大小和内容解释方式”。
任何企图改变 object za 大小的行为，都会违反其定义中的“资源需求量”，如：把整个 Bear object 指定给 za，那么就会溢出它所配置得到的内存。当一个 base class object 被指定为一个 derived class object 时，derived object 就会被切割，以塞入较小的 base type 内存中。derived type 将不会留下任何痕迹。
C++ 也支持 object-based（OB）风格（非 OO），区别是对象构建不需要 virtual 机制，编译时即可决定类型。例如String class，一种非多态的数据结构，String class可以展示封装的非多态形式，它提供一个public接口和一个private实作品，包括数据和算法，但是不支持类型的扩充，一个OB设计可能比一个对等的OO涉及速度更快而且空间更紧凑，速度快是因为所有函数引发操作都在编译期决定，对象构建起来不需要virtual机制，空间紧凑是因为每一个class object不需要负担传统上为了支持virtual机制而需要的额外负荷，不过OB设计没有弹性。
第二章 构造函数语意学
iostream 函数库的建筑师：Jerry Schwarz 早期意图支持一个 iostream class object 的纯测试量（scalar test)：
简单来说：如果一个 class 没有任何 constructor，但其内含一个 member object，而这个 member object 有 default constructor，那么编译器就会合成出一个“nontrivial default constructor”。举个例子：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classFoo { public: Foo(), Foo(int)... };
classBar { public: Foo foo; char *str; };
voidfoo_bar(){ Bar bar; // Bar::foo must be initialized here
if (str) { } ... }
这个程序当中，编译器会为 class Bar 合成一个 default constructor，因为在 foo_bar 中，声明了一个 Bar 对象，这时候就需要初始化其中的 member，其中 Bar::foo 就需要调用 Foo 的 default constructor 才能初始化，这里初始化 foo 就是编译器的责任，但是 Bar::str 的初始化，则还是程序员的责任。合成出的 default constructor 可能如下：
1 2 3 4 5 6
// possible synthesis of Bar default constructor // invoke Foo default constructor for member foo inlineBar::Bar(){ // Pseudo C++ Code foo.Foo::Foo(); }
现在程序的需求满足，但编译器的需求没有满足，还需要初始化 foo，但 default constructor 已经被程序员定义了，没法再合成一个了，那么编译器会按如下准则行动：“如果 class A 内含一个或一个以上的 member class objects，那么，class A 的每个 constructor 必须调用每一个 member class 的default constructor”。所以，编译器可能会将代码扩展成：
如果有多个 class member object 都需要进行初始化操作，那么编译器会按 member object 在 class 中的声明次序，一个个调用其 default constructors。这些代码都将被安插在 explicit user code（生成的代码是 implicit 的）之前。
“带有 Default Constructor”的 Base Class
如果一个没有任何 constructor 的 class 派生自一个“带有 default constructor”（包括自动生成的）的 base class，那么编译器就会为其生成一个 nontrivial default constructor，在其中调用 base class 的 default constructor。
如果程序员写了好几个 constructor，但就是没写 default constructor 呢？那么编译器就会扩张现有的每一个 constructor，将所需要调用的 base calss 的 default constructor 一个个加上去，但并不会为其合成新的 default constructor（因为程序员已经提供了 constructor，所以不会再合成了）。注意，如果还有上一小节说的 member class object，那么这些 object 的 default constructor 也会被安插进去，位置在 base class constructor 之后。
必须使virtual base class在其每一个derived class object中的位置，能够于执行期准备妥当，例如：
1 2 3 4 5 6 7 8 9 10 11 12
classX { public: int i;}; classA : publicvirtual X {public: int j;}; classB : publicvirtual X {public: double d;}; classA : public A, public B {public: int k;};
编译器无法固定住foo()之中“经由pa而存取的X::i”的实际偏移位置，因为pa的真正类型可以改变。编译器必须改变执行存取操作的那些码，使X::i可以延迟到执行的时候决定。所有经由reference或pointer来存取一个virtual base class的操作都可以通过相关指针完成，foo()可以被改写为：
1
voidfoo(const A* pa){ pa->__vbcX->i = 1024;}
其中__vbcX表示编译器所产生的指针。
因为 virtual base class 在内存中的位置也是由一个指针指示出的，所以编译器也会对每个 constructor 安插一些代码，用来支持 virtual base class，如果没有声明任何 constructor，那么编译器就会合成一个 default constructor。
小结
以上四种情况，编译器都会给未声明 constructor 的 class 合成一个 default constructor。C++ Standard 把这些合成物称为 implicit nontrivial default constructor。至于没有存在这四种情况下且没有声明 constructor 的 class，它们拥有的是 implicit trivial default constructor，且实际上并不会被合成出来。
在合成的 default constructor 中，只有 base class subobject 和 member class object 会被初始化，其他的 nonstatic data member 都不会被初始化，因为编译器不需要。
C++ 新手（我）一般有两个误解：
任何 class 如果没有定义 default constructor，就会被合成出一个来。
编译器合成出来的 default constructor 会明确设定 “class 内每一个 data member 的默认值”。
Word noun("block"); voidfoo(){ Word verb = noun; // ... }
很明显 verb 是根据 nonun 来初始化。如果 class Word 定义了一个 copy constructor，则 verb 的初始化操作会调用它，但如果没有，则编译器会先看看 Word 这个 class 是否展现了 “bitwise copy semantics”，然后再决定要不要合成一个 copy constructor。若 class Word 声明如下：
classZooAnimal { public: ZooAnimal(); virtual ~ZooAnimal(); virtualvoidanimate(); virtualvoiddraw(); // ... private: // data necessary for ZooAnimal's // version of animate() and draw() }; classBear : public ZooAnimal { public: Bear(); voidanimate(); voiddraw(); virtualvoiddance(); // ... private: // data necessary for Bear's version // of animate(), draw(), and dance() }; Bear yogi; Bear winnie = yogi;
ZooAnimal class object以另一个ZooAnimal class object作为初值可以直接靠bitwise copy semantics完成。
// simple bitwise copy is not sufficient // compiler must explicitly initialize little_critter's // virtual base class pointer/offset RedPanda little_red; Raccoon little_critter = little_red;
为了正确的 little_critter 初值设定，则必须合成一个 copy constructor，在其中会生成一些代码来设定 virtual base class pointer/offset 的初值（或只是简单的确定它没有被消除），对于其它 member 则执行必要的 memberwise 初始化操作。下图展示了 little_red 和 little_critter 的关系：
如果 class X 定义了一个 copy constructor，那么当 foo() 被调用时，保证该 copy constructor 也会被调用。
这两个假设都得视编译器所提供的进取性优化程度（degree of aggressive optimization）而定。在高品质的 C++ 编译器中，上述两点对于 class X 的 nontrivial definitions 都不正确。
明确的初始化操作（Explicit Initialization）
定义X x0;，有如下程序，每一个都明显地以x0来初始化其class object：
1 2 3 4 5 6
void foo_bar() { X x1(x0); X x2 = x0; X x3 = X(x0); // ... }
会有如下两个转化阶段：
重写每一个定义，其中的初始化操作会被删除。
class 的 copy constructor 调用操作会被安插进去。
在明确的双阶段转化后，foo_bar()转化后可能的样子：
1 2 3 4 5 6 7 8 9 10 11 12 13
// Possible program transformation // Pseudo C++ Code voidfoo_bar(){ X x1; X x2; X x3; // compiler inserted invocations // of copy constructor for X x1.X::X(x0); x2.X::X(x0); x3.X::X(x0); // ... }
其中的x1.X::X(x0)表现出对以下的copy constructor的调用：
1
X::X(const X& xx);
参数的初始化（Argument Initialization）
有如下函数定义：
1
voidfoo(X x0);
以下调用方式：
1 2 3
X xx; // ... foo(xx);
将会要求局部实体（local instance）x0以 memberwise 的方式将 xx 当作初值。编译器的一种策略如下，导入暂时性的 object，并调用 copy constructor 将其初始化：
1 2 3 4 5 6 7
// Pseudo C++ code // compiler generated temporary X __temp0; // compiler invocation of copy constructor __temp0.X::X(xx); // rewrite function call to take temporary foo(__temp0);
// function transformation to reflect // application of copy constructor // Pseudo C++ Code voidbar(X& __result){ // 这里多了一个参数哦 X xx; // compiler generated invocation // of default constructor xx.X::X(); // ... process xx // compiler generated invocation // of copy constructor __result.X::X(xx); return; }
现在编译器则会将如下调用操作：
1
X xx = bar();
转化为：
1 2 3
// note: no default constructor applied X xx; bar( xx );
而：
1
bar().memfunc(); // 执行 bar 函数返回的 object 的成员函数
则可能转化为：
1 2
X __temp0; (bar(__temp0), __temp0).memfunc();
函数指针的类型也会被转换：
1 2
X (*pf) (); pf = bar;
转化为：
1 2
void (*pf) (X&); pf = bar;
在使用者层面做优化（Optimization at the User Level）
对于如下函数，xx 会被拷贝到编译器所产生的__result之中：
1 2 3 4 5
X bar(const T &y, const T &z){ X xx; // ... process xx using y and z return xx; }
程序员可以换种形式编写，可以在 X 当中另外定义一个 constructor，接收 y 和 z 类型的值，直接计算xx，改写函数为：
1 2 3
X bar(const T &y, const T &z){ returnX(y, z); }
于是经过编译器转换后：
1 2 3 4 5
// Pseudo C++ Code voidbar(X &__result, const T &y, const T &z){ __result.X::X(y, z); return; }
__result直接被计算出来，而非经过 copy constructor 拷贝而得（本来应该是在 bar 中构造出 xx，然后用 copy constructor 把__result初始化为 xx 的值）。这种方法的优劣有待探讨。
在编译器层面做优化（Optimization at the Compiler Level）
有如下函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
X bar(){ X xx; // ... process xx return xx; } 所有的return指令传回相同的具名数值（named value），因此编译器可能会做优化，以`__result`参数代替 named return value： ```C++ voidbar(X &__result) { // default constructor invocation // Pseudo C++ Code __result.X::X(); // ... process in __result directly return; }
// Expansion of constructor // Pseudo C++ Code Shape::Shape() { // vptr must be set before user code executes __vptr__Shape = __vtbl__Shape; // oops: memset zeros out value of vptr memset(this, 0, sizeof(Shape)); };
这种优化会导致一些程序员坚持所有的 member 初始化操作必须在 member initialization list 中完成，即使是行为良好的 member 如 _cnt。
1
Word::Word() : _cnt(0), _name(0) {}
事实上，编译器会一个个操作 initialization list，以声明的次序，将代码安插在 constructor 内，并且是安插在 explicit user code 之前。下面这个初始化操作就会出错：
1 2 3 4 5 6 7 8
classX { int i; int j;
public: // oops! do you see the problem? X(int val) : j(val), i(j){}... };
程序员的本意是想把 j 用 val 先初始化，然后再用 j 把 i 初始化，而事实上，初始化的顺序是按照 member 的声明次序来的，所以会先用 j 初始化 i，而 i 目前是个随机值。建议把一个member的初始化操作和另一个放在一起，放在constructor中：
1 2 3
X::X(int val) :j(val) { i = j; }
另外，可以调用一个 member function 来设定一个 member 的初值。但这时候应该在 constructor 体内调用 member function 做初始化，而不是在 member initialization list 中，因为这时候，和此 object 相关的 this 指针已经准备好了，可以通过 this 指针调用 member function 了。
最后，用一个 derived class member function 的调用结果来初始化 base class constructor 会如何：
1 2 3 4 5 6 7 8 9 10 11 12
// is the invocation of FooBar::fval() ok? classFooBar : public X { // FooBar 继承自 X int _fval;
public: intfval(){ return _fval; } // 用成员函数 fval 的调用结果作为 base class constructor 的参数 FooBar(int val) : _fval(val), X(fval()){} ... };
编译器可能会将其扩张为：
1 2 3 4 5 6
// Pseudo C++ Code FooBar::FooBar( /* this pointer goes here */ ) { // Oops: definitely not a good idea X::X( this, this->fval() ); _fval = val; };
很显然，调用fval()回传的_fval还是个随机值。可能是由于 base class 必须在 initialization list 里面初始化，而之前那种情况可以在 constructor 函数体内初始化，这时候就可以将所需要的 member 先初始化好，再调用成员函数。
简略的说，编译器会对initialization list一一处理并可能重新排序，以反映出members的声明次序，它会安插一些代码到constructor体内，并置于任何explicit user code之前。
Data 语意学
有如下代码：
1 2 3 4
classX {}; classY : publicvirtual X {}; classZ : publicvirtual X {}; classA : public Y, public Z {};
一个空的 class 如上述 X，事实并非为空，它有一个隐晦的1 byte，是被编译器安插进去的char，使得这个 class 的两个 objects 可以在内存中分配独一无二的地址。
而 Y 和 Z 的大小和机器还有编译器有关，其受三个因素影响：
语言本身所造成的额外负担（overhead）：当语言支持 virtual base class 时，在 derived class 中，会有一个指针，指向 virtual base class subobject 或者是一个相关表格，表格中存放的是 virtual base class subobject 的地址或者是其偏移量（offset）。书中所用机器上，指针是 4 bytes（我的机器上是 8 bytes）。
编译器对于特殊情况所提供的优化处理：Virtual base class X subobject 的 1 bytes 大小也出现在 class Y 和 Z 身上。传统上它被放在 derived class 的尾端。某些编译器会对 empty virtual base class 提供特殊支持（看来我用的 gcc 7.4.0 有提供支持）。
Alignment 的限制：class Y 和 Z 的大小截至目前为 5 bytes。为了更有效率的在内存中存取，会有 alignment 机制。在书中所用机器上，alignment 是 4 bytes（我的机器上为 8 bytes），所以 class Y 和 Z 必须填补 3 bytes，最终结果为 8 bytes。下图表现了 X，Y，Z 对象布局：
有的编译器会将一个 empty virtual base class 视为最开头的部分，这样就不需要任何额外的空间了（比如我用的 gcc 7.4.0 上，Y 和 Z 的大小仅为一个指针的大小，无需额外空间），省下了上述第二点的 1 bytes，也就不再需要第三点所说的3bbytes的填补，只剩下第一点所说的额外负担，在此模型下Y和Z的大小都是4而不是8。侯捷所用的 vc++ 就是这样，其 X，Y，Z 的对象布局如下：
编译器之间的差异正说明了 C++ 对象模型的演化，这是一个例子，第二章的 NRV 优化也是一个例子。
Y 和 Z 的大小都是 8，而 A 的大小却是 12，分许一下即可，首先一个 virtual base class subobject 只会在 derived class 中存一份实体，所以：
被共享的一个 class X 实体，大小 1 bytes。
Base class Y 的大小本来还有个 virtual base class，现在减去 virtual base class 的大小，就是 4 bytes，Z 也是一样，这样加起来就是 8 bytes。
class A 大小 0 byte。
A 的 alignment 大小（如果有）。上述三项总和：9 bytes。然后 class A 必须对齐 4 bytes，所以填补 3 bytes，最后是 12 bytes。
如果编译器对empty virtual base class有所处理，那么 class X 的 1 bytes 就没有了，于是额外 3 bytes 的对齐也不需要了，所以只需 8 bytes 即可（侯捷的就是这样，我的也是这样，只不过我的一个指针大小 8 bytes，所以需要 16 bytes）。
在这一章中，class的data members以及class hierarchy是中心议题。一个 class的data members，一般而言，可以表现这个class在程序执行时的某种状态。Non-static data members放置的是个别的class object感兴趣的数据，static data members则放置的是整个class感兴趣的数据。
C++对象模型尽量以空间优化和存取速度优化的考虑来表现nonstatic data members，并且保持和C语言struct数据配置的兼容性。它把数据直接存放在每一个class object之中。对于继承而来的nonstatic data members（不管是virtual或 nonvirtual base class）也是如此。不过并没有强制定义其间的排列顺序。static data members则被放置在程序的一个global data segment中，不会影响个别的class object的大小。在程序之中，不管该class被产生出多少个objects（经由直接产生或间接派生），static data members永远只存在一份实体（译注：甚至即使该class没有任何object实体，其static data members也已存在）。但是一个template class的static data mnembers的行为稍有不同，7.1节有详细的讨论。
综上，一个 class object 的大小可能会受以下两个因素的影响：
由编译器自动加上的额外 data members，用来支持某些语言特性（如 virtual 特性）。
alignment 的需要。
Data Member 的绑定（The Binding of a Data Member）
有如下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// A third party foo.h header file // pulled in from somewhere externfloat x; // the programmer's Point3d.h file classPoint3d { public: Point3d(float, float, float); // question: which x is returned and set? floatX()const{ return x; } voidX(float new_x)const{ x = new_x; } // ... private: float x, y, z; };
Point3d::X()很显然会传回 class 内部的 x，而非外部（extern）那个 x，但并不总是这样！以前的编译器是会返回 global x 的。所以导致了两种防御性程序设计风格：
把所有的 data members 放在 class 声明的起头处，以确保正确的绑定。
把所有的 inline functions，不管大小都放在 class 声明之外。
这种风格现在依然存在。但它们的必要性从 C++ 2.0 之后就没了。后来的这种语言规则被称为member rewriting rule，大意是一个 inline 函数实体，在整个 class 未被完全看见之前，是不会被评估求值（evaluated）的。C++ Stantard 以member scope resolution rules来精炼这个rewriting rule：如果一个 inline 函数在 class 声明之后立刻被定义，那么就还是对其评估求值（evaluate）。
对member functions本身的分析会直到整个class的声明都出现了之后才开始。因此在一个inline member function躯体之内的一个data member绑定操作，会在整个 class 声明完成之后才发生。
然而，对于 member function 的 argument list 并不是这样，Argument list 中的名词还是会在第一次遇到时就被决议（resolved）完成。所以对于 nested type（typedef）的声明，还是应该放在 class 的起始处。例如在下边的程序中，length的类型在两个member function signatures中都决议为global typedef，也就是int，当后续再有length的nested typedef声明出现时，C++就把稍早的绑定标识为非法。
通过 member selection operaor（也就是 . 运算符）只不过是语法上的方便而已，member 并不在 class object 中。对于从复杂继承关系中继承而来的 static data member，也是一样，程序之中对于static members仍然只有一个唯一的实体，其存取路径仍然是那么直接。
若取一个 static data member 的地址，会得到一个指向其数据类型的指针，而不是一个指向其 class member 的指针，应为 static member 并不在 class object 中：
1
&Point3d::chunkSize;
会得到类型如下的内存地址：
1
constint*
如果有两个 class，声明了一个相同名字的 static member。那么编译器会给每个 static data member 编码（所谓的 name-mangling），以获得独一无二的程序识别代码，以免放在 data segment 中时导致名称冲突。
Nonstatic Data Members
Nonstatic data member 直接放在每个 class object 中，除非有一个 class object，不然无法直接存取。再 member function 中直接取一个 nonstatic data member 时，会有如下转换：
1 2 3 4 5
Point3d Point3d::translate( const Point3d &pt ){ x += pt.x; y += pt.y; z += pt.z; }
对于 x，y，z 的存取，实际上是由implicit class object（this 指针）完成的：
1 2 3 4 5 6
// internal augmentation of member function Point3d Point3d::translate( Point3d *constthis, const Point3d &pt ){ this->x += pt.x; this->y += pt.y; this->z += pt.z; }
要想对 nonstatic data member 进行存取，编译器需要把 class object 的起始地址加上一个 data member 的偏移量（offset）：
1
origin._y = 0.0;
那么地址&origin._y就等于：
1
&origin + (&Point3d::_y - 1);
注意 -1 操作。指向 data member 的指针，其 offset 值总是被加上 1，这样就可以使编译器区分出一个指向 data member 的指针，用以指出class 的第一个 member和一个指向 data member 的指针，没有指出任何 member两种情况。
每一个 nonstatic data member 的偏移量（offset）在编译时期即可获得，即使 member 数以 base class，所以，存取 nonstatic data member 的效率和存取一个 C struct member 是一样的。
若有虚拟继承，则存取虚拟继承的 base class 当中的 member 时，会有一层间接性：
1 2
Point3d *pt3d; pt3d->_x = 0.0;
如果_x是一个 virtual base class 的 member，存取速度则会变慢。
现在考虑本小节开始的问题，从 origin 存取和从 pt 存取有什么差异？答案是：当 Point3d 是一个 derived class ，并且继承结构中有一个 virtual base class，并且被存取的member是一个从该virtual base class继承而来的member时，就会有差异。这时候我们不知道 pt 到底指向哪一种类型（是 base class 类型还是 derived class 类型？），所以也就不知道 member 真正的 offset 位置，所以必须延迟至执行期才行，且需要一层间接引导。但是用origin就不会有这种问题，其类型无疑是Point3d class，而即使它继承自virtual base class，members的offset位置也在编译期间固定了。
继承与Data Member
C++ 继承模型里，一个 derived class object 是其自己的 member 加上其 base class member 的总和，至于 derived class member 和 base class member 的排列次序则无所谓。但大部分都是 base class member 先出现，有 virtual base class 的除外。
如果C++把derived class members和concrete1 subobject捆绑在一起，去除填补空间，上述那些语意就无法保留了，那么下边的指定操作：
1 2
pc1_1 = pc2; *pc1_2 = *pc1_1;
就会将被捆绑在一起、继承而得的members内容覆盖掉。
所以必须保持base class subobject 在 derived 中的原样性。
加上多态（Adding Polymorphism）
如果要处理一个坐标点，不论其是一个 Point2d 还是 Point3d 实例，那么，就需要提供 virtual function 接口：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classPoint2d { public: Point2d(float x = 0.0, float y = 0.0) : _x(x), _y(y){}; // access functions for x & y same as above // invariant across type: not made virtual
// add placeholders for z — do nothing ... virtualfloatz(){return0.0}; virtualvoidz(float){} // turn type explicit operations virtual virtualvoidoperator+=(const Point2d& rhs) { _x += rhs.x(); _y += rhs.y(); } // ... more members protected: float _x, _y; };
单一继承提供了一种自然多态（natural polymorphism）形式，是关于 class 体系中的 base type 和 derived type 之间的转换，它们的 base class 和 derived class 的 objects 都是从相同的地址开始，差异只在于，derived object 比较大，用来容纳它自己的 nonstatic data member。如以下操作：
1 2
Point3d p3d; Point2d *p = &p3d;
把一个 derived class object 指定给 base class 的指针或 reference，并不需要编译器去修改地址（因为它们的起始地址是相同的，指针的值无需改变，只是解释指针的方式改变了），提供了最佳执行效率。
如果把 vptr 放在 class object 的起始处，这时候，如果 base class 没有 virtual function 而 derived class 有，那么这种自然多态就会被打破，因为将 derived object 转换为 base 类型，需要编译器介入，用来调整地址（把 vptr 排除掉）。
classVertex3d : public Point3d, public Vertex { public: // ... protected: float mumble; }
所示的继承体系：
如图所示，多重继承的问题主要发生于 derived class object 和其第二或后继的 base class object 之间的转换，对一个多重派生对象，将其地址指定给最左端（也就是第一个）base class 的指针，情况和单一继承一样，因为它们有相同的地址。而第二或后继的 base class 起始的地址，则与 derived class 不同（可以在上图中看出，Vertex 在 Point3d 后面）。所以如下操作：
Class 如果含有一个或多个 virtual base class subobjects，将会被分割为两个部分：一个不变的局部和一个共享局部。不变局部不管后继如何演化，总是拥有固定的 offset，这一部分可以直接存取。而共享局部（就是 virtual base class subobject 的部分），这一部分会因为每次的派生操作而发生变化，所以会被间接存取。这时候各家编译器的实现就有差别了，下面是三种主流策略。
classVertex3d : public Vertex, public Point2d { public: ... protected: float mumble; };
一般的布局策略是先安排好 derived class 的不变部分，再建立其共享部分。cfront 编译器会在每一个 derived class object 中安插一些指针，每个指针指向一个 virtual base class，要存取继承来的 virtual base class member，可以用相关指针间接完成。
这样的模型有两个主要缺点：
每一个对象必须针对其每一个 virtual base class 背负一个额外的指针，然而我们希望 class object 有固定的负担，不会因为 virtual base class 的数目而有所变化。
由于虚拟机串链的加成，导致间接存取层次的增加，比如，如果有三层虚拟继承，我就需要三次间接存取（经过三个 virtual base class 指针），然而我们希望有固定的存取时间，而不会因为继承深度改变而改变。
第二个问题可以通过将所用的 virtual base class 指针拷贝到 derived class object 中来解决，这就付出了空间上的代价。下图为该方式的布局：
至于第一个问题，有两个解决办法。Microsoft 编译器引入所谓的 virtual base class table。每一个 class object 如果有一个或多个 virtual base class，则编译器会安插一个指针，指向 virtual base class table，真正的 virtual base class 指针则放在这个 table 中。第二个解决方法是在 virtual function table 中放置 virtual base class 的 offset（不是地址哦），下图显示了这种布局：
经由一个非多态的 class object 来存取一个继承而来的 virtual base class 的 member：
1 2 3
Point3d origin; ... origin._x;
可以被优化为一个直接存取操作，就好像一个经由对象调用的 virtual function 调用操作，可以在编译时期被决议（resolved）完成一样。这次存取以及下一次存取之间对象的类型不可改变。所以virtual base class subobjects的位置会变化的问题不再存在。
一般而言，virtual base class 最有效的运用形式是：一个抽象的 virtual base class，没有任何 data members。
指向 Data Members 的指针（Pointer to Data Members）
指向 data member 的指针可以用来调查 class member 的底层布局，比如 vptr 的位置。考虑下面的 Point3d 声明：
每个 Point3d class 有三个坐标值：x，y，z，以及一个 vptr，而 static data member origin 则被放在 class object 之外。唯一可能因编译器不同而不同的是 vptr 的位置。C++ Standard 对 vptr 的位置没有限制，但实际上不是在对象头部就是在对象尾部。
那么，取某个坐标成员的地址：
1
&Point3d::z;
实际上得到的是 z 坐标在 class object 中的偏移量（offset）。其最小值是 x 和 y 的大小总和，因为 C++ 要求同一个 access level 中的 member 的排列次序应该和其声明次序相同。
然而vptr的位置没有限制，实际上vptr不是放在对象的头部就是尾部，在一部32位的机器上，每一个float是4 bytes，所以应该期望刚才获得的值不是8就是12。如果 vptr 在对象的尾端，则三个坐标值的 offset 分别是 0，4，8。如果 vptr 在对象起头，则三个坐标值的 offset 分别是 4，8，12。然而若去取 data member 的地址，传回值总是多 1，也就是 1，6，9 或 5，9，13。这是为了区分一个没有指向任何 data member的指针和一个指向第一个 data member 的指针（gcc 7.4.0 将没有指向任何 data member的指针设为了 0xffffffffffffffff）。考虑如下例子：
1 2 3 4 5 6 7
float Point3d::*p1 = 0; float Point3d::*p2 = &Point3d::x; // oops: how to distinguish? if (p1 == p2) { cout << " p1 & p2 contain the same value — "; cout << " they must address the same member!" << endl; }
如果magnitude()声明为inline会更有效率。使用 class scope operator 明确的调用一个 virtual function，就和调用 nonstatic member function 的效果是一样的。通过一个 class object 调用一个 virtual function，也和调用 nonstatic member function 的效果一样：
在引入 static member function 之前，C++ 语言要求所有的 member function 必须由该 class 的 object 来调用，所以就有了下面奇特的写法：
1
((Point3d*)0)->object_count();
其中object_count()只是简单的回传_object_count这个 static data member。
实际上，只有当一个或多个nonstatic data members在member function中被直接存取时，才需要class object。 Class obect提供了this指针给这种形式的函数调用使用。这个this指针把在 member function中存取的nonstatic class members绑定于object内对应的 members之上。如果没有任何一个members被直接存取，事实上就不需要this指针，因此也就没有必要通过一个class object来调用一个member function。不过C++语言到当前为止并不能够识别这种情况。
这么一来就在存取static data members时产生了一些不规则性。如果class 的设计者把static data member声明为nonpublic（这一直被视为是一种好的习惯），那么他就必须提供一个或多个；member functions来存取该member。因此虽然你可以不靠class object来存取一个static member，但其存取函数却得绑定于一个class object之上。
C++ 中，多态（polymorphism）表示以一个 public base class 的指针（或 reference），寻址出一个 derived class object的意思。多态机制主要扮演一个输送机制经由它我们可以在程序的任何地方采用一组public derived类型，这种多态形式被称为是消极的。可以在编译时期完成。
在runtime type identification (RTTT）性质被引入C++语言之前，c++对“积极多态（active polymorphism)”的唯一支持，就是对于virtual function call的决议（resolution）操作。有了RTTI，就能够在执行期查询一个多态的pointer 或多态的reference了。
// hierarchy to illustrate MI complications // of virtual function support classBase1 { public: Base1(); virtual ~Base1(); virtualvoidspeakClearly(); virtual Base1 *clone()const;
其中，faddr为 virtual function 的地址，offset为 this 指针的调整值。这个做法的缺点就是对每个 virtual function 的调用操作都有影响，即使不需要 offset 的情况也是如此。比较有效率的方法是利用所谓的 thunk。所谓thunk是一小段assembly码，用来:
当一个 virtual base class 从另一个 virtual base class 派生而来，并且两者都支持 virtual function 和 nonstatic data member 时，情况过于复杂，不在此讨论，书中的建议是：不要在一个 virtual base class 中声明 nonstatic data member。
函数的效能
下面用 nonmember friend function、member function、virtual member function 的形式测试以下函数：
两种情况，其未优化的执行平均时间未 6.90 秒（和单一继承的 virtual function 效率相同）。
指向 Member Function 的指针（Pointer-to-Member Functions）
取一个 nonstatic data member 的地址，得到的是该 member 在 class 布局中的 bytes 位置（再加 1）。需要被绑定于某个 class object 的地址上，才能够被存取。
取一个 nonstatic member function 的地址，且该函数不是虚函数，则得到的结果是它在内存中真正的地址（我在 gcc 7.4.0 上得到所有的成员函数的地址都是一个相同的值，包括不同 class 的成员函数，不知道为什么）。但这个地址也需要被绑定到 class objet 才能使用，因为所有的 nonstatic member functions 都需要对象的地址才能使用 。
一个指向 member function 的指针，其声明语法如下：
1 2 3 4
double// return type (Point::* // class the function is member pmf) // name of pointer to member (); // argument list
然后这样使用：
1
double (Point::*coord)() = &Point::x;
也可以这样指定：
1
coord = &Point::y;
可以这样调用(origin是对象):
1
(origin.*coord)();
也可以这样调用(origin是指针):
1
(origin->*coord)();
调用操作会被转化为：
1
(coord)(&origin));
或：
1
(coord)(ptr);
使用“member function 指针”，如果不用于 virtual function、多重继承、virtual base class 等情况的话，并不会比使用一个“nonmember function 指针”的成本更高。
支持“指向 Virtual Members Functions”之指针
有如下程序片段：
1 2
float (Point::*pmf)() = &Point::z; Point *ptr = new Point3d;
继续看__mptr这个结构体，delta字段表示 this 指针的 offset 值，而 v_offset 字段放的是一个 virtual base class 或多重继承中的第二或后继的 base class 的 vptr 位置。如果 vptr 放在 class 对象的起始处，那么这个字段就不需要了，代价则是 C 对象的兼容性降低。这些字段（delta 和 v_offset）只有在多重继承或虚拟继承的情况下才需要。
许多编译器对不同的 class 的特性提供多种指向 member function 的指针形式，如 Microsoft 提供了：
一个单一继承实例（其中带有 vcall thunk 地址或函数地址）；
一个多重继承实例（其中带有 faddr 和 delta 两个member）；
一个虚拟继承实例（其中带有四个 member）。
“指向 Member Function 之指针”的效率
下面的测试中，cross_product()函数经由以下方式调用：
一个指向 nonmember function 的指针；
一个指向 class member function 的指针；
一个指向 virtual member function 的指针；
多重继承下的 nonvirtual 及 virtual member function call；
虚拟继承下的 nonvirtual 及 virtual member function call；
结果如下：
Inline Functions
关键词 inline（或 class declaration 中的 member function 或 friend function 的定义）只是一项请求，如果这项请求被接受，编译器就必须认为它可以用一个表达式（expression）合理地将这个函数扩展开。
要不要定义纯虚函数完全由 class 设计者决定，但有一个例外：class 的设计者必须定义 pure virtual destructor。因为每一个 derived class destructor 都会被编译器扩展，以静态调用的方式调用每一个基类的 destructor，因此，只要缺乏任何一个 base class destructor 的定义，就会导致链接失败。
当编译器遇到这样的定义：Point global;，程序的行为会和在 C 语言中表现一样（没有构造函数等东西），只有一点不一样：在 C 中，global 被视为临时性的定义，因为它没有明确的初始化操作，这种“临时性的定义”会被链接器折叠，只留下单独一个实体，放在程序 data segment 中一个特别保留给未初始化之 global objects 使用的空间，这块空间被称为BSS，是 Block Started by Symbol 的缩写。
而 C++ 并不支持“临时性的定义”，global 在 C++ 中被视为完全定义。C 和 C++ 的一个差异就在于，BSS data segment 在 C++ 中相对不重要。C++ 的所有全局对象都被当作“初始化过的数据”来对待。
每一个explicit constructor都会被扩充以调用其两个member class objects的constructors。如果定义constructor如下：
1
Line::Line(const Point &begin, const Point &end) : _end(end), _begin(begin) {}
它会被扩充为：
1 2 3 4 5
Line* Line::Line(Line *this, const Point &begin, const Point &end){ this->_begin.Point::Point(begin); this->_end.Point::Point(end); returnthis; }
当程序员写下：
1
Line a;
时，implicit Line destructor会被合成出来（如果Line派生自Point，那么合成出来的destructor将会是virtual。然而由于Line只是内带Point objects而非继承自Point，所以被合成出来的destructor只是nontrivial而已）。在其中，它的member class objects的destructors会被调用（以其构造的相反顺序）
// Psuedo C++ Code: // Constructor Augmentation with Virtual Base class Vertex3d* Vertex3d::Vertex3d( Vertex3d *this, bool __most_derived, float x, float y, float z ){ if ( __most_derived != false ) this->Point::Point( x, y); // invoke immediate base classes, // setting __most_derived to false this->Point3d::Point3d( false, x, y, z ); this->Vertex::Vertex( false, x, y ); // set vptrs // insert user code returnthis; }
所以，“virtual base class constructor 的被调用”有着明确的定义：只有当一个完整的 class object 被定义出来时，它才会被调用；如果 object 只是某个完整 object 的 subobject，它就不会被调用。
以这一点为杠杆，我们可以产生更有效率的constructors。某些新近的编译器把每一个constructor分裂为二，一个针对完整的object，另一个针对subobject。“完整object”版无条件地调用virtual base constructors，设定所有的vptrs等等。 “subobject”版则不调用virtual base constructors，也可能不设定vptrs等等。将在下一节讨论对vptr的设定。constructor的分裂可带来程序速度的提升。
vptr 初始化语义学（The Semantics of the vptr Initialization）
当我们定义一个 PVertex object 时，constructors 的调用顺序是：
1 2 3 4 5
Point(x, y); Point3d(x, y, z); Vertex(x, y, z); Vertex3d(x, y, z); PVertex(x, y, z);
假设这个继承体系中的每一个 class 都定义了一个 virtual function：size()，该函数负责传回 class 的大小。如果我们写：
1 2 3 4
PVertex pv; Point3d p3d;
Point *pt = &pv;
那么这个调用操作：
1
pt->size();
将传回PVertex的大小，而：
1 2
pt = &p3d; pt->size();
将传回Point3d的大小。
假设在继承体系中的每一个 constructor 内都带一个调用操作，比如：
1 2 3 4 5 6
Point3d::Point3d( float x, float y, float z ) : _x( x ), _y( y ), _z( z ) { if ( spyOn ) cerr << "within Point3d::Point3d()" << " size: " << size() << endl; }
事实是，在 Point3d constructor 中调用的size()函数，必须被决议为Point3d::size()。更一般地，在一个 class （Point3d）的 constructor 中，经由构造中的对象（PVertex）来调用一个 virtual function，其函数实体应该是在此 class 中有作用的那个（Point3d）。
Constructors的调用顺序是：由根源而末端（bottom up)，由内而外（inside out)。 当base class constructor执行时，derived实体还没有被构造出来。在PVertex constructor执行完毕之前，PVertex并不是一个完整的对象：Point3d constructor执行之后，只有Point3d subobject构造完毕。
这意味着，当每一个PVertex base class constructors被调用时，编译系统必须保证有适当的size()函数实体被调用。怎样才能办到这一点呢？如果调用操作限制必须在constructor（或destructor）中直接调用，那么答案十分明显：将每一个调用操作以静态方式决议之，千万不要用到虚拟机制。如果是在Point3d constructor中，就明确调用Point3d::size()。
在base class constructors调用操作之后，但是在程序员代码或是“member initialization list中所列的members初始化操作”之前。
在每一件事情发生之后。
答案是2，策略2解决了“在class中限制一组virtual functions名单”的问题。如果每一个constructor都一直等待到其base class constructors执行完毕之后才设定其对象的vptt，那么每次它都能够调用正确的virtual function实体。
令每一个base class constructor设定其对象的vptr，使它指向相关的virtual table之后，构造中的对象就可以严格而正确橄变成“构造过程中所幻化出来的每一个class的对象。一个PVertex对象会先形成一个Point对象、 一个Point3d对象、一个Vertex对象、一个Vertex3d对象，然后才成为一个PVertex对象。在每一个base class constructor中，对象可以与constructor’s class 的完整对象作比较。对于对象而言，“个体发生学”概括了“系统发生学”。constructor 的执行算法通常如下：
在derived class constructor中，“所有virtual base classes”及“上层base class”的constructors会被调用；
上述完成之后，对象的vptr(s)被初始化。指向相关的virtual table(s)
如果有member initialization list的话，将在constructor体内扩展开来。这必须在vptr被设定之后才进行，以免有一个virtual member function被调用。
如果我们声明一个PVertex对象，然后由于我们对其base class constructors的最新定义，其vptr将不再需要在每一个base class constructor中被设定。解决之道是把constructor分裂为一个完整的object实体和一个subobject实体。在subobject实体中，vptr的设定可以省略。
在class的constructor 的 member initialization list中调用该class的一个虚拟函数，安全吗？就实际而将该函数运行于其classs data member的初始化行动中，总是安全的。这是，正如我们所见，vptr保证能够在member initialization list被扩展之前，由编译器正确设定好。但是在语意上这可能是不安全的，因为函数本身可能还得依赖未被设立初值的members。所以我并不推荐这种做法。然而，从vptr的整体来看是安全的。
对象复制语义学（Object Copy Semantics）
当设计一个 class，并以一个 class object 指定给另一个 class object 时，有三种选择：
// Pseudo C++ Code: synthesized copy assignment operator inline Point3d& Point3d::operator=( Point3d *constthis, const Point3d &p ) { // invoke the base class instance this->Point::operator=( p ); // memberwise copy the derived class members _z = p._z; return *this; }
copy assignment operator 有一个不够理想、严谨的地方，那就是它缺乏一个 member assignment list（也就是类似于 member initialization list 的东西）。必须写成以下两种形式，才能调用 base class 的 copy assignment operator：
另一个方法是，编译器为 copy assignment operator 产生分化函数（split functions），用来支持这个 class 成为 most-derived class 或成为中间的 base class。（这里没有说具体如何做，不是很懂这个方法）
事实上，copy assignment operator 在虚拟继承情况下行为不佳，需要小心设计和说明。许多编译器甚至并不尝试取得正确的语义，导致 virtual base class copy assignment operator 多次被调用。
有一种方法可以保证 most-derived class 会完成 virtual base class subobject 的 copy 行为，就是在 derived class 的 copy assignment operator 函数实体的最后，明确调用那个 operator：
1 2 3 4 5 6 7 8 9
inline Vertex3d& Vertex3d::operator=( const Vertex3d &v ) { this->Point3d::operator=( v ); this->Vertex::operator=( v ); // must place this last if your compiler does // not suppress intermediate class invocations this->Point::operator=( v ); ... }
一个 complete 实体，总是设定好 vptr，并调用 virtual base class destructor。
一个 base class subobject 实体；除非在 destructor 函数中调用一个 virtual function，否则它绝不会调用 virtual base class destructor 并设定 vptr。
一个object的生命结束于其destructor开始执行之时。由于每一个base class destructor都轮番被调用，所以derived object实际变成了一个完整的object。例如一个PVertex对象归还其内存空间之前，会依次变成一个Vertex3d对象、一个Vertex对象、一个Point3d对象，最后成为一个Point对象。当我们在destructor中调用member functions时，对象的蜕变会因为vptr的重新设定（在每一个destructor中，在程序员所供应的码执行之前）而受到影响。在程序中施行destructors的真正语意将在第6章详述。
{ if ( cache ) // check cache; if match, return 1 return1; Point xx; // constructor goes here while ( cvs.iter( xx )) if ( xx == value ) goto found; // destructor goes here return0;
found: // cache item // destructor goes here return1; }
如果 Point 没有定义 constructor 和 destructor，那么只需配置足够的内存即可，不需要做其他事。
如果 Point 明确定义了 default constructor，那么 这个 constructor 必须轮流施行于每个元素之上。在 cfront 中，使用了一个名为vec_new()的函数产生出以 class object 构造而成的数组。函数类型通常如下：
1 2 3 4 5 6 7
void* vec_new { void *array, // address of start of array size_t elem_size, // size of each class object int elem_count, // number of elements in array void (*constructor)( void* ), void (*destructor)( void*, char ) }
Point knots[10]; vec_new(&knots, sizeof(Point), 10, &Point::Point, 0);
如果 Point 也定义了 destructor，那么当 knots 的生命结束时，destructor 会施行于那 10 个 Point 元素身上。这会经由类似的一个vec_delete()来完成，其函数类型通常如下：
1 2 3 4 5 6 7
void* vec_delete { void *array, // address of start of array size_t elem_size, // size of each class object int elem_count, // number of elements in array void (*destructor)( void*, char ) }
若程序员提供一个或多个初值给这个数组：
1 2 3 4 5
Point knots[10] = { Point(), Point(1.0, 1.0, 0.5), -1.0 };
// let arena be globally defined voidfooBar(){ Point2w *p2w = new (arena) Point2w; // ... do it ... // ... now manipulate a new object ... p2w = new (arena) Point2w; };
还有一个问题是：如何知道 arena 所指的内存区块是否需要先解构？这在语言层面上没有解答，合理的习俗是令执行 new 的这一端也要负责执行 destructor。
另一个问题是 arena 所表现的真正指针类型，它必须指向相同类型的 class，或者是一块“新鲜”的内存，足够容纳该类型的 object。注意，derived class 很明显不在被支持之列。对于一个derived class，或是其他没有关联的类型，其行为虽然并非不合法，却也未经定义。
新鲜额存储空间可以这样配置而来：
1
char *arena = newchar [ sizeof(Point2w) ];
相同类型的object则可以这样获得：
1
Point2w *arena = new Point2w;
不论哪一种情况，新的Point2w的储存空间的确是覆盖了arena的位置，而此行为已在良好控制之下。然而，一般而言，placement new operator并不支持多态（polymorphism）。被交给new的指针，应该适当地指向一块预先配置好的内存。如果derived class比其base class大，例如：
1
Point2w *p2w = new (arena) Point3w;
Poit3w的constructor将会导致严重的破坏。
Placement new perator被引入C++ 2.0时，最晦涩隐暗的问题就是下面这个：
1 2 3 4 5 6 7 8 9 10
strcut Base { int j; virtualvoidf(); }; structDerived : Base { voidf(); }
voidfooBar(){ Base b; b.f(); // Base::f()被调用 b.~Base(); new (&b) Derived; // 1 b.f(); // 哪一个f()被调用 }
上述两个classes有相同的大小，故把derived object放在为base class配置的内存中是安全的，然而，要支持这一点，或许必须放弃对于“经由object静态调用所有virtual function”通常都会有的优化处理。结果，placement new operator的这种使用方式在C++中未能获得支持。于是上述程序的行为没有定义，大部分编译器调用的是Base::f()。
一般而言，placement new operator 并不支持多态。被交给 new 的指针应该是预先配置好的。
当临时性对象是根据程序的执行期语意有条件地被产生出来时，临时性对象的生命规则就显得有些复杂了。举个例子，像这样的表达式：if (s + t || u + v)，其中的u + v子算式只有在s + t被评估为false时，才会开始被评估。与第二个子算式有关的临时性对象必须被摧毁。但是，很明显地，不可以被无条件地摧毁。也就是说，我们希望只有在临时性对象被产生出来的情况下才去摧毁它。
实际上，在 template 之中，对于一个 nonmember name 的决议结果，是根据这个 name 的使用是否与 template 的类型参数有关而决定的。如果互不相关，就以“scope of the template declaration”来决定 name。否则，以“scope of the template instantiation”来决定 name。
那么对于以下两个调用操作：
1 2
sr0.invariant(); sr0.type_dependent();
第一行的调用，invariant()中的foo()与用以具现 ScopeRules 的参数类型无关，_val的类型是int，是不会变的，此外，函数的决议结果只和函数的原型（signature）有关，与函数的返回值无关，所以_member的类型不影响哪个foo()实体被选中，foo()的调用与 template 参数毫无关联，所以必须根据“scope of the template declaration”来决议。
对于第二行的调用，很明显与 template 参数有关，template 参数将决定_member的真正类型。所以这一次foo()必须在“scope of the template instantiation”中决议，本例中，这个 scope 有两个foo()，所以如果_member的类型为 int，就会调用 int 版的foo()，如果是 double 则调用 double 版本的foo()，如果是 long，那么就会产生歧义了。
所以编译器必须保持两个 scope contexts：
“scope of the template declaration”，用以专注于一般的 template class。
“scope of the template instantiation”，用以专注于特定的实体。
Member Function 的具现行为（Member Function Instantiation）
下面是编译器设计者必须回答的三个主要问题：
编译器如何找出函数的定义？答案之一是包含template program text file，就好像它是个header文件一样。Borland编译器就是遵循这个策略。另一种方法是要求一个文件命名规则，例如，我们可以要求，在Point.h文件中发现的函数声明，其template program text一定要放置于文件Point.C或Point.cpp中，依此类推。cfront就是遵循这个策略。Edison Design Group编译器对此两种策略都支持。
当一个 exception 被丢出时，控制权会从函数调用中被释放，并寻找吻合的 catch 子句。如果都没有吻合者，那么默认的处理例程terminate()会被调用。当控制权被放弃后，堆栈中的每个函数调用就被推离。这个程序称为unwinding the stack。在每个函数被推离堆栈之前，函数的 local class objects 的 destructor 会被调用。
如果exception是在auto_ptr中被丢出的，那么就没有active local objects需要被EH机制摧毁。然而如果SMLock constructor中丢出一个exception，则auto_ptr object必须在“unwinding”之前先被摧毁。至于在第三个区段中，两个local objects当然必须被摧毁。
支持 EH，会使那些拥有 member class subobject 或 base class subobject 的 class 的 constructor 更复杂。一个 class 如果被部分构造，则其 destructor 必须只施行于那些已被构造的 subobject 和 member object 身上。这些事情都是编译器的责任。例如，假设class X有member objects A、B和C，都各有一对constructor和destructor，如果A的constructor丢出一个exception，不论A或B或C都不需要调用其destructor，如果B的constructor丢出一个exception，则A的destructor必须被调用，但C不用。
对于每一个被丢出来的exception，编译器必须产生一个类型描述器，对exception的类型进行编码。如果那是一个derived type，则编码内容必须包括其所有base class的类型信息。只编进public base class的类型是不够的，因为这个exception可能被一个member function捕捉，而在一个member function的范围（scope）之中，在derived class和nonpublic base class之间可以转换。
simplify_conv_op(ptype Pt) { //ok: conversion operators can only be fcts pfct pf = pfct(pt); // };
在const member functicns引入之前，这份码是正确的。请注意其中甚至有一个批注，说明这样的转型的安全。但是在const member functions引进之后，不论程序批注或程序代码都不对了。程序代码之所以失败，非常不幸是因为String class声明的改变．因为char * cnversion运算符现在被内部视为一个gen而不是一个fct。
C++ 的 RTTI 机制提供一个安全的 downcast 设备，但只对那些展现“多态”的类型有效。如何分辨一个 class 是否展现多态？ RTTI 所采用的策略是经由声明一个或多个 virtual function 来区别 class 声明，优点是透明化地将旧有程序转换过来，只要重新编译就好，缺点则是可能会将一个其实并非必要的virtual function强迫导入继承体系的base class身上。在 C++ 中，一个具备多态性质的 class 正是内含继承而来（或直接声明）的 virtual functions。
从编译器角度看，这个策略还有其他优点，就是大量降低额外负担。所有多态类的 object 都维护了一个指针，指向 virtual function table。只要把与该 class 相关的 RTTI object 地址放进 virtual table 中（通常放在第一个 slot），那么额外负担就降低为：每个 class object 只多花费一个指针。这个指针只需要被设定一次，他是被编译器静态设定而不是在执行期由class constructor设定。
Type-Safe Dynamic Cast（保证安全的动态转型）
dynamic_cast 运算符可以在执行期决定真正的类型。如果 downcast 是安全的（也就是 base type pointer 确实指向一个 derived class object），这个运算符会传回被适当转型过的指针。如果 downcast 不安全，则会传回 0。
type_info是 C++ 所定义的类型描述器的 class 名称，该 class 中放置着待索求的类型信息。virtual table 的第一个 slot 内含 type_info object 的地址。此type_info object与pt所指之class type有关。这两个类型描述器被交给一个runtime library函数，比较之后告诉我们是否吻合。很显然这比static cast昂贵得多，但却安全得多（如果我们把一个fct类型 “downcast”为一个gen类型的话）。
进程通过执行mknod()创建一个FIFO“设备文件”，参数为新FIFO的路径名以及S_IFIFO（0x10000）与该新文件的权限位掩码进行逻辑或的结果。 POSIX引入了一个名为mkfifo()的系统调用专门创建FIFO。该系统调用在Linux及 System V Release 4 中是作为调用mknod()的C库函数实现的。
为了把不正确地引用错误资源的风险降到最小，内核不会在IPC标识符一空闲就再利用它。相反，分配给资源的IPC标识符总是大于给同类型的前一个资源所分配的标识符（溢出例外）。每个IPC标识符都是通过结合使用与资源类型相关的位置使用序号s、已分配资源的任一位置索引i以及内核中可分配资源所选定的最大值M而计算出。0 <= i < M，则每个IPC资源的 ID 可按如下公式计算：IPC标识符 = s * M + i。
已链接的模块也可以导出自己的符号，这样其他模块就可以访问这些符号。模块符号部分表（module symbol table）保存在模块代码段的__ksymcab、__ksymtab_gpl和__kstrtab部分中。要从模块中导出符号的一个子集，程序员可以使用上面描述的EXPORT_SYMBOL和EXPORT_SYMBOL_GPL宏。当模块链接时，模块的导出符号被拷贝到两个内存数组中，而其地址保存在module对象的syms和gpl_syms字段中。
我们通过这个返回的句柄提升了进程的优先级，这样它就能从调度器那里获得更多的 CPU 时间。这里只是用于演示目的，并没什么实际的效应。重要的一点是：通过OpenProcess()打开的资源不需要显式的调用CloseHandle()来关闭。当然，应用程序终止时资源也会随之关闭。然而，在更加复杂的应用程序里，windows_handle类确保当一个资源不再使用时就能正确的关闭。某个资源一旦离开了它的作用域——上例中h的作用域在main()函数的末尾——它的析构函数会被自动的调用，相应的资源也就释放掉了。
本例中定义了2个共享指针i1和i2，它们都引用到同一个 int 类型的对象。i1通过new操作符返回的地址显示的初始化，i2通过i1拷贝构造而来。i1接着调用reset()，它所包含的整数的地址被重新初始化。不过它之前所包含的对象并没有被释放，因为i2仍然引用着它。智能指针boost::shared_ptr记录了有多少个共享指针在引用同一个对象，只有在最后一个共享指针销毁时才会释放这个对象。
在intrusive_ptr_add_ref()和intrusive_ptr_release()内部调用AddRef()和Release()这两个函数，来增加或减少相应 COM 对象的引用计数。这个例子中用到的 COM 对象名为'FileSystemObject'，在Windows上它是默认可用的。通过这个对象可以访问底层的文件系统，比如检查一个给定的目录是否存在。在上例中，我们检查C:\Windows目录是否存在。具体它在内部是怎么实现的，跟boost::intrusive_ptr的功能无关，完全取决于 COM。关键点在于一旦介入式指针 disp 离开了它的作用域——check_windows_folder()函数的末尾，函数intrusive_ptr_release()将会被自动调用。这将减少 COM 对象'FileSystemObject'的内部引用计数到0，于是该对象就销毁了。
虽然这个库的名字乍一看好象有点误导，但实际上并非如此。Boost.Signals所实现的模式被命名为信号至插槽(signal to slot)，它基于以下概念：当对应的信号被发出时，相关联的插槽即被执行。原则上，你可以把单词信号和插槽分别替换为事件和事件处理器。不过，由于信号可以在任意给定的时间发出，所以这一概念放弃了 ‘事件’ 的名字。
注意到本例并没有调用函数std::setlocale()。使用函数std::locale::global()设置全局区域设置后，也自动进行了 C 区域设置。实际上，C++ 程序几乎总是使用函数std::locale::global()进行全局区域设置，而不是像前面的例子那样使用函数std::setlocale()。
所有这些函数的共同点是均返回类型为boost::iterator_range类的一对迭代器。此类起源于Boost C++的Boost.Range库，它在迭代器的概念上定义了“范围”。因为操作符<<由boost::iterator_range类重载而来，单个搜索算法的结果可以直接写入标准输出流。以上程序将 Boris 作为第一个结果输出而第二个结果为空字符串。
voidrandom_number_generator() { init_number_generator(); int i = std::rand(); boost::lock_guard<boost::mutex> lock(mutex); std::cout << i << std::endl; }
intmain() { boost::thread t[3];
for (int i = 0; i < 3; ++i) t[i] = boost::thread(random_number_generator);
voidinit_number_generator() { static boost::thread_specific_ptr<bool> tls; if (!tls.get()) tls.reset(newbool(false)); if (!*tls) { *tls = true; std::srand(static_cast<unsignedint>(std::time(0))); } }
boost::mutex mutex;
voidrandom_number_generator() { init_number_generator(); int i = std::rand(); boost::lock_guard<boost::mutex> lock(mutex); std::cout << i << std::endl; }
intmain() { boost::thread t[3];
for (int i = 0; i < 3; ++i) t[i] = boost::thread(random_number_generator);
如果remove()没有被调用, 那么，即使进程终止，共享内存还会一直存在，而不论共享内存的删除是否依赖底层操作系统。多数Unix操作系统，包括Linux，一旦系统重新启动，都会自动删除共享内存，在Windows或 Mac OS X上，remove()必须调用，这两种系统实际上将共享内存存储在持久化的文件上，此文件在系统重启后还是存在的。
Windows 提供了一种特别的共享内存，它可以在最后一个使用它的应用程序终止后自动删除。为了使用它，提供了boost::interprocess::windows_shared_memory类，定义在boost/interprocess/windows_shared_memory.hpp文件中。
boost::filesystem::space()用于取回磁盘的总空间和剩余空间。它返回一个boost::filesystem::space_info类型的对象，其中定义了三个公有属性：capacity，free和available。这三个属性的类型均为boost::uintmax_t，该类型定义于Boost.Integer库，通常是unsigned long long的typedef。磁盘空间是以字节数来计算的。
格里历是教皇 Gregory XIII 在1582年颁发的。严格来说，Boost.DateTime支持由1400年至9999年的历法日期，这意味着它支持1582年以前的日期。因此，Boost.DateTime可用于任一历法日期，只要该日期在转换为格里历后是在1400年之后。如果需要更早的年份，就必须使用其它库来代替。
这个例子使用了boost::gregorian::day_clock类，它是一个返回当前日期的时钟类。方法universal_day()返回一个与时区及夏时制无关的 UTC 日期。UTC 是世界时(universal time)的国际缩写。boost::gregorian::day_clock还提供了另一个方法local_day()，它接受本地设置。要取出本地时区的当前日期，必须使用local_day()。
名字空间boost::gregorian中包含了许多其它自由函数，将保存在字符串中的日期转换为boost::gregorian::date类型的对象。这个例子实际上是通过boost::gregorian::date_from_iso_string()函数对一个以 ISO 8601 格式给出的日期进行转换。还有其它相类似的函数，如boost::gregorian::from_simple_string()和boost::gregorian::from_us_string()。
要创建一个boost::local_time::posix_time_zone类型的对象，就要将一个描述该时区的字符串作为单一参数传递给构造函数。以上例子指定了欧洲中部时区：CET 是欧洲中部时间(Central European Time)的缩写。由于 CET 比 UTC 早一个小时，所以时差以 +1 表示。Boost.DateTime并不能解释时区的缩写，也就不知道 CET 的意思。所以，必须以小时数给出时差；传入 +0 表示没有时差。
在执行时，该程序将打印2009-Jan-05 12:00:00，2009-Jan-05 13:00:00 CET，2009-Jan-05 13:00:00和 CET 到标准输出流。用以初始化boost::posix_time::ptime和boost::local_time::local_date_time类型的值缺省总是与 UTC 时区相关的。只有当一个boost::local_time::local_date_time类型的对象被写出至标准输出流时，或者调用local_time()方法时，才使用时差来计算本地时间。
星期几和月份的名字可以通过分别传入两个数组给boost::date_time::date_facet类的long_month_names()和long_weekday_names()方法来修改，这两个数组分别包含了相应的名字。以上例子现在将打印Mittwoch, 07. Januar 2009到标准输出流。
Boost C++ 的序列化库允许将C++应用程序中的对象转换为一个字节序列，此序列可以被保存，并可在将来恢复对象的时候再次加载。各种不同的数据格式，包括 XML，只要具有一定规则的数据格式，在序列化后都产生一个字节序列。所有Boost.Serialization支持的格式，在某些方面来说都是专有的。比如 XML 格式不同用来和不是用 C++ Boost.Serialization库开发的应用程序交换数据。所有以 XML 格式存储的数据适合于从之前存储的数据上恢复同一个C++对象。XML 格式的唯一优点是序列化的C++对象容易理解，这是很有用的，比如说在调试的时候。
键值提取器boost::multi_index::identity（定义在boost/multi_index/identity.hpp中）可以使用容器中的数据类型作为键值。示例中，就需要 person 类是可排序的，因为它已经作为了接口boost::multi_index::ordered_unique的键值。在示例里，它是通过重载operator<()操作符来实现的。
如果使用Boost 1.36.0，并且用Visual Studio 2008在Windows XP环境下编译以上应用程序将不断产生错误代码14（没有足够的存储空间以完成操作）。即使函数boost::asio::ip::host_name()成功决定了计算机名，也会报出错误代码14。事实上这是因为函数boost::asio::ip::host_name()的实现有问题。
在save_configuration_data()的catch句柄中，通过获取tag_errmsg以创建一个对象，它通过字符串saving configuration data failed进行初始化，以便通过operator<<()操作符向异常boost::exception中加入更多信息。然后这个异常被相应的重新抛出。
通过使用宏BOOST_THROW_EXCEPTION替代throw，如函数名、文件名、行数之类的附加信息将自动被添加到异常中。但这仅仅在编译器支持宏的情况下有效。当通过C++标准定义__FILE__和__LINE__之类的宏时，没有用于返回当前函数名的标准化的宏。由于许多编译器制造商提供这样的宏，BOOST_THROW_EXCEPTION试图识别当前编译器，从而利用相对应的宏。使用 Visual C++ 2008 编译时，以上应用程序显示以下信息：
1 2 3 4
.\main.cpp(31): Throw in function class boost::shared_array<char> __cdecl allocate(unsigned int) Dynamic exception type: class boost::exception_detail::clone_impl<struct boost::exception_detail::error_info_injector<class allocation_failed> > std::exception::what: allocation of 2000 bytes failed [struct tag_errmsg *] = saving configuration data failed
intmain() { int i = 0x10000; short s = i; std::cout << s << std::endl; }
由于从int到short的类型转换自动产生，所以本例编译没有错误。虽然本例可以运行，但结果由于依赖具体的编译器实现而结果无法预期。数字0x10000对于变量i来说太大而不能存储在short类型的变量中。依据C++标准，这个操作的结果是实现定义的(“implementation defined”)。用Visual C++ 2008编译，应用程序显示的是0。s的值当然不同于i的值。
SYSENTER_RETURN: popl %ebp popl %edx popl %ecx ret
参数传递
系统调用的输入/输出参数可能是：
实际的值
用户态进程地址空间的变量
指向用户态函数的指针的数据结构地址
因为system_call()和sysenter_entry()是 Linux 中所有系统调用的公共入口点，因此每个系统调用至少有一个参数，即通过eax寄存器传递进来的系统调用号。
普通C函数的参数传递时通过把参数值写入活动的程序栈（用户态栈或内核态栈）实现的。而系统调用是一种横跨用户和内核的特殊函数，所以既不能使用用户态栈也不能使用内核态栈。在发出系统调用前，系统调用的参数被写入 CPU 寄存器，然后再调用系统调用服务例程前，内核再把存放在 CPU 中的参数拷贝到内核态堆栈中，因为系统调用服务例程是普通的 C 函数。
static __always_inline int __vfs_follow_link(struct nameidata *nd, constchar *link) { int res = 0; char *name; if (IS_ERR(link)) goto fail;
if (*link == '/') { path_release(nd); if (!walk_init_root(link, nd)) /* weird __emul_prefix() stuff did it */ goto out; } res = link_path_walk(link, nd); out: if (nd->depth || res || nd->last_type!=LAST_NORM) return res; /* * If it is an iterative symlinks resolution in open_namei() we * have to copy the last component. And all that crap because of * bloody create() on broken symlinks. Furrfu... */ name = __getname(); if (unlikely(!name)) { path_release(nd); return -ENOMEM; } strcpy(name, nd->last.name); nd->last.name = name; return0; fail: path_release(nd); return PTR_ERR(link); }
/* NB: we're sure to have correct a_ops only after f_op->open */ if (f->f_flags & O_DIRECT) { if (!f->f_mapping->a_ops || ((!f->f_mapping->a_ops->direct_IO) && (!f->f_mapping->a_ops->get_xip_page))) { fput(f); f = ERR_PTR(-EINVAL); } }
/** * kmap_high - map a highmem page into memory * @page: &struct page to map * * Returns the page's virtual memory address. * * We cannot call this from interrupts, as it may block. */ void *kmap_high(struct page *page) { unsignedlong vaddr; lock_kmap();
for (i = 0; (z = zonelinst->zones[i]) != NULL; i ++) { if (zone_watermark_of(z, order, ...)) { page = buffered_rmqueue(z, order, gfp_mask); if (page) return page; } }
int ret = 0; for (i = pgd_index(address); i < pgd_index(end-1); i++) { pud_t *pud = pud_alloc(&init_mm, pgd, address); ret = -ENOMEM; if (!pud) break; next = (address + PGDIR_SIZE) & PGDIR_MASK; if (next < address || next > end) next = end; if (map_area_pud(pud, address, next, prot, pages)) break; address = next; pgd++; ret = 0; } spin_unlock(&init_mm.page_table_lock); flush_cache_vmap((unsignedlong)area->addr, end); return ret;
Linux 2.6 还特别提供了一个vmap()函数，它将映射非连续内存区中已经分配的页框：本质上，该函数接收一组指向页描述符的指针作为参数，调用get_vm_area()得到一个新vm_struct描述符，然后调用map_vm_area()来映射页框。因此该函数与vmalloc()相似，但是它不分配页框。
if (mm) { /* Check the cache first. */ /* (Cache hit rate is typically around 35%.) */ vma = mm->mmap_cache; if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) { structrb_node * rb_node;
写时复制（Copy On Write，COW）的思想相当简单：父进程和子进程共享页框而不是复制页框。然后只要页框被共享，它们就不能被修改。无论父进程还是子进程何时试图写一个共享的页框，就产生一个异常，这是内核就把这个页复制到一个新的页框中并标记可写。原来的页框仍然是写保护的：当其他进程试图写入时，内核检查写进程是否是这个页框的唯一属主，如果是，就把这个页框标记为对这个进程可写。
\
