MSVC

在编译std::list的时候,MSVC 2012会存储链表的长度。除此以外,它的实现方法和GCC基本一致。这就是说,内置函数.size()只需要从内存中读取一个值就可以返回函数结果,其速度相当快。不过,这也意味着每次添增/删除节点的时候都需要调整这个值。

MSVC的链存储结构也和GCC有所区别:

4801-3

可见,GCC构造的虚节点在链尾,而MSVC构造的虚节点在链首。

使用MSVC 2012(启用/Fa2.asm/GS-/Ob1选项)编译上述程序,可得到:

指令清单51.31 MSVC 2012带参数/Fa2.asm/GS-/Ob1优化的程序

_l$ = -16 ; size = 8
_t1$ = -8 ; size = 8
_main     PROC
    sub   esp, 16
    push  ebx
    push  esi
    push  edi
    push  0
    push  0
    lea   ecx, DWORD PTR _l$[esp+36]
    mov   DWORD PTR _l$[esp+40], 0
    ; allocate first "garbage" element
    call  ?_Buynode0@?$_List_alloc@$0A@U?$_List_base_types@Ua@@V? ↙
    ↘ $allocator@Ua@@@std@@@std@@@std@@QAEPAU?$_List_node@Ua@@PAX@2@PAU32@0@Z ; std:: ↙
    ↘ _List_alloc<0,std::_List_base_types<a,std::allocator<a> > >::_Buynode0
    mov   edi, DWORD PTR __imp__printf
    mov   ebx, eax
    push  OFFSET $SG40685 ; '* empty list:'
    mov   DWORD PTR _l$[esp+32], ebx
    call  edi ; printf
    lea   eax, DWORD PTR _l$[esp+32]
    push  eax
    call  ?dump_List_val@@YAXPAI@Z ; dump_List_val
    mov   esi, DWORD PTR [ebx]
    add   esp, 8
    lea   eax, DWORD PTR _t1$[esp+28]
    push  eax
    push  DWORD PTR [esi+4]
    lea   ecx, DWORD PTR _l$[esp+36]
    push  esi
    mov   DWORD PTR _t1$[esp+40], 1 ; data for a new node
    mov   DWORD PTR _t1$[esp+44], 2 ; data for a new node
    ; allocate new node
    call  ??$_Buynode@ABUa@@@?$_List_buy@Ua@@V?$allocator@Ua@@@std@@@std@@QAEPAU? ↙
    ↘ $_List_node@Ua@@PAX@1@PAU21@0ABUa@@@Z ; std::_List_buy<a,std::allocator<a> >::_Buynode<a ↙
    ↘ const &>
    mov   DWORD PTR [esi+4], eax
    mov   ecx, DWORD PTR [eax+4]
    mov   DWORD PTR _t1$[esp+28], 3 ; data for a new node
    mov   DWORD PTR [ecx], eax
    mov   esi, DWORD PTR [ebx]
    lea   eax, DWORD PTR _t1$[esp+28]
    push  eax
    push  DWORD PTR [esi+4]
    lea   ecx, DWORD PTR _l$[esp+36]
    push  esi
    mov   DWORD PTR _t1$[esp+44], 4 ; data for a new node
    ; allocate new node
    call  ??$_Buynode@ABUa@@@?$_List_buy@Ua@@V?$allocator@Ua@@@std@@@std@@QAEPAU? ↙
    ↘ $_List_node@Ua@@PAX@1@PAU21@0ABUa@@@Z ; std::_List_buy<a,std::allocator<a> >::_Buynode<a  ↙
    ↘ const &>
    mov   DWORD PTR [esi+4], eax
    mov   ecx, DWORD PTR [eax+4]
    mov   DWORD PTR _t1$[esp+28], 5 ; data for a new node
    mov   DWORD PTR [ecx], eax
    lea   eax, DWORD PTR _t1$[esp+28]
    push  eax
    push  DWORD PTR [ebx+4]
    lea   ecx, DWORD PTR _l$[esp+36]
    push  ebx
    mov   DWORD PTR _t1$[esp+44], 6 ; data for a new node
    ; allocate new node
    call  ??$_Buynode@ABUa@@@?$_List_buy@Ua@@V?$allocator@Ua@@@std@@@std@@QAEPAU? ↙
    ↘ $_List_node@Ua@@PAX@1@PAU21@0ABUa@@@Z ; std::_List_buy<a,std::allocator<a> >::_Buynode<a  ↙
    ↘ const &>
    mov   DWORD PTR [ebx+4], eax
    mov   ecx, DWORD PTR [eax+4]
    push  OFFSET $SG40689 ; '* 3-elements list:'
    mov   DWORD PTR _l$[esp+36], 3
    mov   DWORD PTR [ecx], eax
    call  edi ; printf
    lea   eax, DWORD PTR _l$[esp+32]
    push  eax
    call  ?dump_List_val@@YAXPAI@Z ; dump_List_val
    push  OFFSET $SG40831 ; 'node at .begin:'
    call  edi ; printf
    push  DWORD PTR [ebx] ; get next field of node l variable points to
    call  ?dump_List_node@@YAXPAUList_node@@@Z ; dump_List_node
    push  OFFSET $SG40835 ; 'node at .end:'
    call  edi ; printf
    push  ebx ; pointer to the node $l$ variable points to!
    call  ?dump_List_node@@YAXPAUList_node@@@Z ; dump_List_node
    push  OFFSET $SG40839 ; '* let''s count from the begin:'
    call  edi ; printf
    mov   esi, DWORD PTR [ebx] ; operator++: get ->next pointer
    push  DWORD PTR [esi+12]
    push  DWORD PTR [esi+8]
    push  OFFSET $SG40846 ; '1st element: %d %d'
    call  edi ; printf
    mov   esi, DWORD PTR [esi] ; operator++: get ->next pointer
    push  DWORD PTR [esi+12]
    push  DWORD PTR [esi+8]
    push  OFFSET $SG40848 ; '2nd element: %d %d'
    call  edi ; printf
    mov   esi, DWORD PTR [esi] ; operator++: get ->next pointer
    push  DWORD PTR [esi+12]
    push  DWORD PTR [esi+8]
    push  OFFSET $SG40850 ; '3rd element: %d %d'
    call  edi ; printf
    mov   eax, DWORD PTR [esi] ; operator++: get ->next pointer
    add   esp, 64
    push  DWORD PTR [eax+12]
    push  DWORD PTR [eax+8]
    push  OFFSET $SG40852 ; 'element at .end(): %d %d'
    call  edi ; printf
    push  OFFSET $SG40853 ; '* let''s count from the end:'
    call  edi ; printf
    push  DWORD PTR [ebx+12] ; use x and y fields from the node l variable points to
    push  DWORD PTR [ebx+8]
    push  OFFSET $SG40860 ; 'element at .end(): %d %d'
    call  edi ; printf
    mov   esi, DWORD PTR [ebx+4] ; operator--: get ->prev pointer
    push  DWORD PTR [esi+12]
    push  DWORD PTR [esi+8]
    push  OFFSET $SG40862 ; '3rd element: %d %d'
    call  edi ; printf
    mov   esi, DWORD PTR [esi+4] ; operator--: get ->prev pointer
    push  DWORD PTR [esi+12]
    push  DWORD PTR [esi+8]
    push  OFFSET $SG40864 ; '2nd element: %d %d'
    call  edi ; printf
    mov   eax, DWORD PTR [esi+4] ; operator--: get ->prev pointer
    push  DWORD PTR [eax+12]
    push  DWORD PTR [eax+8]
    push  OFFSET $SG40866 ; '1st element: %d %d'
    call  edi ; printf
    add   esp, 64
    push  OFFSET $SG40867 ; 'removing last element...'
    call  edi ; printf
    mov   edx, DWORD PTR [ebx+4]
    add   esp, 4

    ; prev=next?
    ; it  is the only element, "garbage one"?
    ; if  yes, do not delete it!
    cmp   edx, ebx
    je    SHORT $LN349@main
    mov   ecx, DWORD PTR [edx+4]
    mov   eax, DWORD PTR [edx]
    mov   DWORD PTR [ecx], eax
    mov   ecx, DWORD PTR [edx]
    mov   eax, DWORD PTR [edx+4]
    push  edx
    mov   DWORD PTR [ecx+4], eax
    call  ??3@YAXPAX@Z ; operator delete
    add   esp, 4
    mov   DWORD PTR _l$[esp+32], 2
$LN349@main:
    lea   eax, DWORD PTR _l$[esp+28]
    push  eax
    call  ?dump_List_val@@YAXPAI@Z ; dump_List_val
    mov   eax, DWORD PTR [ebx]
    add   esp, 4
    mov   DWORD PTR [ebx], ebx
    mov   DWORD PTR [ebx+4], ebx
    cmp   eax, ebx
    je    SHORT $LN412@main
$LL414@main:
    mov   esi, DWORD PTR [eax]
    push  eax
    call  ??3@YAXPAX@Z ; operator delete
    add   esp, 4
    mov   eax, esi
    cmp   esi, ebx
    jne   SHORT $LL414@main
$LN412@main:
    push  ebx
    call  ??3@YAXPAX@Z ; operator delete
    add   esp, 4
    xor   eax, eax
    pop   edi
    pop   esi
    pop   ebx
    add   esp, 16
    ret   0
_main ENDP

在构造数据链的时候,MSVC通过“Buynode”函数分配了虚节点的空间;此后,这个函数同样用于分配其他节点的存储空间。相比之下,GCC则会在局部栈里存储链表的第一个节点。

指令清单51.32 整个程序的输出

* empty list:
_Myhead=0x003CC258, _Mysize=0
ptr=0x003CC258 _Next=0x003CC258 _Prev=0x003CC258 x=6226002 y=4522072
* 3-elements list:
_Myhead=0x003CC258, _Mysize=3
ptr=0x003CC258 _Next=0x003CC288 _Prev=0x003CC2A0 x=6226002 y=4522072
ptr=0x003CC288 _Next=0x003CC270 _Prev=0x003CC258 x=3 y=4
ptr=0x003CC270 _Next=0x003CC2A0 _Prev=0x003CC288 x=1 y=2
ptr=0x003CC2A0 _Next=0x003CC258 _Prev=0x003CC270 x=5 y=6
node at .begin:
ptr=0x003CC288 _Next=0x003CC270 _Prev=0x003CC258 x=3 y=4
node at .end:
ptr=0x003CC258 _Next=0x003CC288 _Prev=0x003CC2A0 x=6226002 y=4522072
* let's count from the begin:
1st element: 3 4
2nd element: 1 2
3rd element: 5 6
element at .end(): 6226002 4522072
* let's count from the end:
element at .end(): 6226002 4522072
3rd element: 5 6
2nd element: 1 2
1st element: 3 4
removing last element...
_Myhead=0x003CC258, _Mysize=2
ptr=0x003CC258 _Next=0x003CC288 _Prev=0x003CC270 x=6226002 y=4522072
ptr=0x003CC288 _Next=0x003CC270 _Prev=0x003CC258 x=3 y=4
ptr=0x003CC270 _Next=0x003CC258 _Prev=0x003CC288 x=1 y=2

C++11 std::forward_list单向链表

std::forward_list和std::list的结构基本相同,只是它是单向链,它的迭代器(链域)只有”next”字段而没有”prev”字段。虽然这种链表的内存开销变小了,但是无法进行逆向遍历。

51.4.3 std::vector标准向量

我们将std::vector标准向量称为PODT[4]C数组的安全封装容器。其内部结构和标准字符串std::string十分相似(参见51.4.1节)。它有一个数据缓冲区的专用指针,一个指向数组尾部的专用指针,以及一个指向分配缓冲区尾部的专用指针。

这种数组采取的各个元素以彼此相邻的方式存储于内存之中,这点和常规数组没什么区别(参见第18章)。新推出的C++11标准,为其定义了内置函数.data()。std::vector的.data()的作用就和std::string中的.c_str()一样,用于返回缓冲区的地址。

这种数据结构使用堆/heap来存储数据缓冲区,而堆的空间消耗可能会比数组本身还大。

MSVC和GCC的实现机理基本相同,只是结构体的变量名称稍微有些不同。因此,所以这里使用同一个例子进行说明。下述源程序用于遍历std::vector的数据结构。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

struct vector_of_ints
{
    // MSVC names:
    int *Myfirst;
    int *Mylast;
    int *Myend;

    // GCC structure is the same, but names are: _M_start, _M_finish, _M_end_of_storage
};

void dump(struct vector_of_ints *in)
{
    printf ("_Myfirst=%p, _Mylast=%p, _Myend=%p\n", in->Myfirst, in->Mylast, in->Myend);
    size_t size=(in->Mylast-in->Myfirst);
    size_t capacity=(in->Myend-in->Myfirst);
    printf ("size=%d, capacity=%d\n", size, capacity);
    for (size_t i=0; i<size; i++)
        printf ("element %d: %d\n", i, in->Myfirst[i]);
};

int main()
{
    std::vector<int> c;
    dump ((struct vector_of_ints*)(void*)&c);
    c.push_back(1);
    dump ((struct vector_of_ints*)(void*)&c);
    c.push_back(2);
    dump ((struct vector_of_ints*)(void*)&c);
    c.push_back(3);
    dump ((struct vector_of_ints*)(void*)&c);
    c.push_back(4);
    dump ((struct vector_of_ints*)(void*)&c);
    c.reserve (6);
    dump ((struct vector_of_ints*)(void*)&c);
    c.push_back(5);
    dump ((struct vector_of_ints*)(void*)&c);
    c.push_back(6);
    dump ((struct vector_of_ints*)(void*)&c);
    printf ("%d\n", c.at(5)); // with bounds checking
    printf ("%d\n", c[8]); // operator[], without bounds checking
};

下面是采用MSVC编译后的程序输出。

_Myfirst=00000000, _Mylast=00000000, _Myend=00000000
size=0, capacity=0
_Myfirst=0051CF48, _Mylast=0051CF4C, _Myend=0051CF4C
size=1, capacity=1
element 0: 1
_Myfirst=0051CF58, _Mylast=0051CF60, _Myend=0051CF60
size=2, capacity=2
element 0: 1
element 1: 2
_Myfirst=0051C278, _Mylast=0051C284, _Myend=0051C284
size=3, capacity=3
element 0: 1
element 1: 2
element 2: 3
_Myfirst=0051C290, _Mylast=0051C2A0, _Myend=0051C2A0
size=4, capacity=4
element 0: 1
element 1: 2
element 2: 3
element 3: 4
_Myfirst=0051B180, _Mylast=0051B190, _Myend=0051B198
size=4, capacity=6
element 0: 1
element 1: 2
element 2: 3
element 3: 4
_Myfirst=0051B180, _Mylast=0051B194, _Myend=0051B198
size=5, capacity=6
element 0: 1
element 1: 2
element 2: 3
element 3: 4
element 4: 5
_Myfirst=0051B180, _Mylast=0051B198, _Myend=0051B198
size=6, capacity=6
element 0: 1
element 1: 2
element 2: 3
element 3: 4
element 4: 5
element 5: 6
6
6619158

从程序中我们可以看到,当主函数main()开始运行后并没有立即分配数据缓冲区。在第一次调用push_back()函数之后,它才分配了缓冲区。此后,每调用一次push_back()函数,数组的空间和size(capacity)都增大一次。不仅空间容量逐渐增长,而且缓冲区的地址也会同期改变。这是因为每次调用push_back()函数时,都会在堆里重新分配空间。所以这种操作的时间开销很大。要想提高效率,就必须预测数组的大小并使用.reserve()方式为其预留存储空间。

最后一个数值是随机的噪音。它不属于链表的某个节点,只是一个随机数。从这一点我们可以看出,std::vector(标准向量)的下标运算符“[]”不会检测索引值是否超越下标界限。要进行这种数组边界检查,可以使用内置函数.at()。虽然.at()方法的运行速度较慢,但是它能在下标越 std::out_of_range (越界)的错误提示。

我们来看它的汇编指令。使用MSVC 2012(启用 /GS- /Ob1选项)编译上述源程序,可得到:

指令清单51.33 MSVC 2012 /GS- /Ob1

$SG52650 DB '%d', 0aH, 00H
$SG52651 DB '%d', 0aH, 00H

_this$ = -4 ; size = 4
__Pos$ = 8  ; size = 4
?at@?$vector@HV?$allocator@H@std@@@std@@QAEAAHI@Z PROC ; std::vector<int,std::allocator<int> ↙
    ↘ >::at, COMDAT
; _this$ = ecx
    push  ebp
    mov   ebp, esp
    push  ecx
    mov   DWORD PTR _this$[ebp], ecx
    mov   eax, DWORD PTR _this$[ebp]
    mov   ecx, DWORD PTR _this$[ebp]
    mov   edx, DWORD PTR [eax+4]
    sub   edx, DWORD PTR [ecx]
    sar   edx, 2
    cmp   edx, DWORD PTR __Pos$[ebp]
    ja    SHORT $LN1@at
    push  OFFSET ??_C@_0BM@NMJKDPPO@invalid?5vector?$DMT?$DO?5subscript?$AA@
    call  DWORD PTR __imp_?_Xout_of_range@std@@YAXPBD@Z
$LN1@at:
    mov   eax, DWORD PTR _this$[ebp]
    mov   ecx, DWORD PTR [eax]
    mov   edx, DWORD PTR __Pos$[ebp]
    lea   eax, DWORD PTR [ecx+edx*4]
$LN3@at:
    mov   esp, ebp
    pop   ebp
    ret   4
?at@?$vector@HV?$allocator@H@std@@@std@@QAEAAHI@Z ENDP ; std::vector<int,std::allocator<int>  ↙
    ↘ >::at

_c$ = -36 ; size = 12
$T1 = -24 ; size = 4
$T2 = -20 ; size = 4
$T3 = -16 ; size = 4
$T4 = -12 ; size = 4
$T5 = -8  ; size = 4
$T6 = -4  ; size = 4
_main PROC
    push  ebp
    mov   ebp, esp
    sub   esp, 36
    mov   DWORD PTR _c$[ebp], 0 ; Myfirst
    mov   DWORD PTR _c$[ebp+4], 0 ; Mylast
    mov   DWORD PTR _c$[ebp+8], 0 ; Myend
    lea   eax, DWORD PTR _c$[ebp]
    push  eax
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    mov   DWORD PTR $T6[ebp], 1
    lea   ecx, DWORD PTR $T6[ebp]
    push  ecx
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?push_back@?$vector@HV?$allocator@H@std@@@std@@QAEX$$QAH@Z ; std::vector<int,std:: ↙
    ↘ allocator<int> >::push_back
    lea   edx, DWORD PTR _c$[ebp]
    push  edx
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    mov   DWORD PTR $T5[ebp], 2
    lea   eax, DWORD PTR $T5[ebp]
    push  eax
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?push_back@?$vector@HV?$allocator@H@std@@@std@@QAEX$$QAH@Z ; std::vector<int,std:: ↙
    ↘ allocator<int> >::push_back
    lea   ecx, DWORD PTR _c$[ebp]
    push  ecx
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    mov   DWORD PTR $T4[ebp], 3
    lea   edx, DWORD PTR $T4[ebp]
    push  edx
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?push_back@?$vector@HV?$allocator@H@std@@@std@@QAEX$$QAH@Z ; std::vector<int,std:: ↙
    ↘ allocator<int> >::push_back
    lea   eax, DWORD PTR _c$[ebp]
    push  eax
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    mov   DWORD PTR $T3[ebp], 4
    lea   ecx, DWORD PTR $T3[ebp]
    push  ecx
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?push_back@?$vector@HV?$allocator@H@std@@@std@@QAEX$$QAH@Z ; std::vector<int,std:: ↙
    ↘ allocator<int> >::push_back
    lea   edx, DWORD PTR _c$[ebp]
    push  edx
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    push  6
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?reserve@?$vector@HV?$allocator@H@std@@@std@@QAEXI@Z ; std::vector<int,std::allocator< ↙
    ↘ int> >::reserve
    lea   eax, DWORD PTR _c$[ebp]
    push  eax
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    mov   DWORD PTR $T2[ebp], 5
    lea   ecx, DWORD PTR $T2[ebp]
    push  ecx
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?push_back@?$vector@HV?$allocator@H@std@@@std@@QAEX$$QAH@Z ; std::vector<int,std:: ↙
    ↘ allocator<int> >::push_back
    lea   edx, DWORD PTR _c$[ebp]
    push  edx
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    mov   DWORD PTR $T1[ebp], 6
    lea   eax, DWORD PTR $T1[ebp]
    push  eax
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?push_back@?$vector@HV?$allocator@H@std@@@std@@QAEX$$QAH@Z ; std::vector<int,std:: ↙
    ↘ allocator<int> >::push_back
    lea   ecx, DWORD PTR _c$[ebp]
    push  ecx
    call  ?dump@@YAXPAUvector_of_ints@@@Z ; dump
    add   esp, 4
    push  5
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?at@?$vector@HV?$allocator@H@std@@@std@@QAEAAHI@Z ; std::vector<int,std::allocator<int ↙
    ↘ > >::at
    mov   edx, DWORD PTR [eax]
    push  edx
    push  OFFSET $SG52650 ; '%d'
    call  DWORD PTR __imp__printf
    add   esp, 8
    mov   eax, 8
    shl   eax, 2
    mov   ecx, DWORD PTR _c$[ebp]
    mov   edx, DWORD PTR [ecx+eax]
    push  edx
    push  OFFSET $SG52651 ; '%d'
    call  DWORD PTR __imp__printf
    add   esp, 8
    lea   ecx, DWORD PTR _c$[ebp]
    call  ?_Tidy@?$vector@HV?$allocator@H@std@@@std@@IAEXXZ  ; std::vector<int,std::allocator<int ↙
    ↘ > >::_Tidy
    xor   eax, eax
    mov   esp, ebp
    pop   ebp
    ret   0
_main ENDP

从中我们可以看到.at()方法检查下标边界以及异常处理的详细细节。最后一个输出值是printf()函数直接从内存中提取的数值。它在提取数值的时候没有做任何越界检查。

有读者可能会问了,为什么标准向量的数据结构为什么不像标准函数std::string中的那样、单独用一个字段记录size(大小)和capacity(体积)这类的信息呢?虽然笔者无法查证,但是笔者相信大概是.at()在进行边界检查时效率更好吧。

GCC生成的汇编指令也十分雷同,不过它以内联函数的形式实现.at()。

指令清单51.34 GCC 4.8.1 –fno –inline –small –functions –O1编译

main proc  near
     push  ebp
     mov   ebp, esp
     push  edi
     push  esi
     push  ebx
     and   esp, 0FFFFFFF0h
     sub   esp, 20h
     mov   dword ptr [esp+14h], 0
     mov   dword ptr [esp+18h], 0
     mov   dword ptr [esp+1Ch], 0
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   dword ptr [esp+10h], 1
     lea   eax, [esp+10h]
     mov   [esp+4], eax
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _ZNSt6vectorIiSaIiEE9push_backERKi ; std::vector<int,std::allocator<int>>::push_back( ↙
    ↘ int const&)
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   dword ptr [esp+10h], 2
     lea   eax, [esp+10h]
     mov   [esp+4], eax
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _ZNSt6vectorIiSaIiEE9push_backERKi ; std::vector<int,std::allocator<int>>::push_back( ↙
     ↘ int const&)
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   dword ptr [esp+10h], 3
     lea   eax, [esp+10h]
     mov   [esp+4], eax
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _ZNSt6vectorIiSaIiEE9push_backERKi ; std::vector<int,std::allocator<int>>::push_back( ↙
    ↘ int const&)
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   dword ptr [esp+10h], 4
     lea   eax, [esp+10h]
     mov   [esp+4], eax
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _ZNSt6vectorIiSaIiEE9push_backERKi  ; std::vector<int,std::allocator<int>>::push_back( ↙
    ↘ int  const&)
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   ebx, [esp+14h]
     mov   eax, [esp+1Ch]
     sub   eax, ebx
     cmp   eax, 17h
     ja    short loc_80001CF
     mov   edi, [esp+18h]
     sub   edi, ebx
     sar   edi, 2
     mov   dword ptr [esp], 18h
     call  _Znwj            ; operator new(uint)
     mov   esi, eax
     test  edi, edi
     jz    short loc_80001AD
     lea   eax, ds:0[edi*4]
     mov   [esp+8], eax     ; n
     mov   [esp+4], ebx     ; src
     mov   [esp], esi       ; dest
     call  memmove

loc_80001AD: ; CODE XREF: main+F8
     mov   eax, [esp+14h]
     test  eax, eax
     jz    short loc_80001BD
     mov   [esp], eax       ; void *
     call  _ZdlPv           ; operator delete(void *)

loc_80001BD: ; CODE XREF: main+117
     mov   [esp+14h], esi
     lea   eax, [esi+edi*4]
     mov   [esp+18h], eax
     add   esi, 18h
     mov   [esp+1Ch], esi

loc_80001CF: ; CODE XREF: main+DD
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   dword ptr [esp+10h], 5
     lea   eax, [esp+10h]
     mov   [esp+4], eax
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _ZNSt6vectorIiSaIiEE9push_backERKi ; std::vector<int,std::allocator<int>>::push_back( ↙
    ↘ int const&)
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   dword ptr [esp+10h], 6
     lea   eax, [esp+10h]
     mov   [esp+4], eax
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _ZNSt6vectorIiSaIiEE9push_backERKi ; std::vector<int,std::allocator<int>>::push_back( ↙
    ↘ int const&)
     lea   eax, [esp+14h]
     mov   [esp], eax
     call  _Z4dumpP14vector_of_ints ; dump(vector_of_ints *)
     mov   eax, [esp+14h]
     mov   edx, [esp+18h]
     sub   edx, eax
     cmp   edx, 17h
     ja    short loc_8000246
     mov   dword ptr [esp], offset aVector_m_range ; "vector::_M_range_check"
     call  _ZSt20__throw_out_of_rangePKc ; std::__throw_out_of_range(char const*)

loc_8000246:                            ; CODE XREF: main+19C
     mov   eax, [eax+14h]
     mov  [esp+8], eax
     mov   dword ptr [esp+4], offset aD ; "%d\n"
     mov   dword ptr [esp], 1
     call  __printf_chk
     mov   eax, [esp+14h]
     mov   eax, [eax+20h]
     mov   [esp+8], eax
     mov   dword ptr [esp+4], offset aD ; "%d\n"
     mov   dword ptr [esp], 1
     call  __printf_chk
     mov   eax, [esp+14h]
     test  eax, eax
     jz    short loc_80002AC
     mov   [esp], eax        ; void *
     call  _ZdlPv            ; operator delete(void *)
     jmp   short loc_80002AC

     mov   ebx, eax
     mov   edx, [esp+14h]
     test  edx, edx
     jz    short loc_80002A4
     mov   [esp], edx        ; void *
     call  _ZdlPv            ; operator delete(void *)

loc_80002A4: ; CODE XREF: main+1FE
     mov   [esp], ebx
     call  _Unwind_Resume


loc_80002AC: ; CODE XREF: main+1EA
             ; main+1F4
     mov   eax, 0
     lea   esp, [ebp-0Ch]
     pop   ebx
     pop   esi
     pop   edi
     pop   ebp

locret_80002B8: ; DATA XREF: .eh_frame:08000510
                ; .eh_frame:080005BC
     retn
main endp

编译器也对.reserve()函数进行了内联处理。如果缓冲区不大,程序会调用new()方法分配缓冲区的存储空间;使用memmove()方法来复制缓冲区中的内容;最后通过delete()方法来释放缓冲区空间。

如果采用GCC编译的话,编译程序的输出为:

_Myfirst=0x(nil), _Mylast=0x(nil), _Myend=0x(nil)
size=0, capacity=0
_Myfirst=0x8257008, _Mylast=0x825700c, _Myend=0x825700c
size=1, capacity=1
element 0: 1
_Myfirst=0x8257018, _Mylast=0x8257020, _Myend=0x8257020
size=2, capacity=2
element 0: 1
element 1: 2
_Myfirst=0x8257028, _Mylast=0x8257034, _Myend=0x8257038
size=3, capacity=4
element 0: 1
element 1: 2
element 2: 3
_Myfirst=0x8257028, _Mylast=0x8257038, _Myend=0x8257038
size=4, capacity=4
element 0: 1
element 1: 2
element 2: 3
element 3: 4
_Myfirst=0x8257040, _Mylast=0x8257050, _Myend=0x8257058
size=4, capacity=6
element 0: 1
element 1: 2
element 2: 3
element 3: 4
_Myfirst=0x8257040, _Mylast=0x8257054, _Myend=0x8257058
size=5, capacity=6
element 0: 1
element 1: 2
element 2: 3
element 3: 4
element 4: 5
_Myfirst=0x8257040, _Mylast=0x8257058, _Myend=0x8257058
size=6, capacity=6
element 0: 1
element 1: 2
element 2: 3
element 3: 4
element 4: 5
element 5: 6
6
0

从程序我们可以看到,GCC的缓冲区buffer的增长方式与MSVC不同。具体来说,通过一个简单的例子实践可以看到:由MSVC编译的程序每次会把缓冲区增加50%;而由GCC编译的程序则会将缓冲区扩张100%——也就是翻倍。

51.4.4 std::map()和std::set()

“二叉树”是另外一种常见的基础数据结构。二叉树是每个节点最多有两个子树的有序树,每个节点都有自己的关键字(key)-值(value)。

二叉树通常会用于构造联合数组(associative arrays)。联合数组又称为词典(dictionary)或 hash 表,它由一系列的“关键字-值”构成。

二叉制树最少具备三个重要的特性:

现在开始举例说明:我们将存储数列0, 1, 2, 3, 5, 6, 9, 10, 11, 12, 20, 99, 100, 101, 107, 1001, 1010,并形成下述二叉树结构:

从下面的图中,我们很容易发现这样一个规律:所有左边节点的值都比其右边节点的值小,而所有右边节点的值都比左边的节点的值大。

在遵守以上规则的前提下,我们做起查询算法来就相对简单了。我们只需要关注当前节点的数值以及我们要查询的值,将这两者进行比较,当前者比后者小时,那么我们只需要向右搜索对比查找;反之,当前者比后者大时,我们就会向左搜索对比查找。一直到找到节点的值与要搜索的值相等为止。这就是为什么刚才说只需要一个对比函数即可进行节点数或者字符串对比。

4801-4

所有的键都有一个唯一的值,不能重复。

我们可以计算需要花费的步数,公式大约为:log2nn是二进制树中键的个数),这个公式计算的是我们要找到一个平衡树的搜索步数。这就意味着在一个1000个键的二进制树中,通过大约10步我们就能找到需要的值;而10000个键的二进制树中则需要13步。看起来还是很不错的。树总是需要像这样平衡一下,也就是说,键必须在所有水平上平衡分布。插入和移除一些节点可能都需要保持树的平衡状态。

有几个可用的流行平衡算法,包括AVL树和红黑树。后面的算法采用的办法是将每个节点标注为red(红)或者black(黑),以简化结点的平衡过程。

不管是GCC还是MSVC的模板函数std::map()和std::set()都使用了红黑树(red-black)的算法。

在std::set()中只含有键,而std::map()中除了键(std::set)还有相应的每个节点的数值。

MSVC

#include <map>
#include <set>
#include <string>
#include <iostream>

// structure is not packed!
struct tree_node
{
    struct tree_node *Left;
    struct tree_node *Parent;
    struct tree_node *Right;
    char Color; // 0 - Red, 1 - Black
    char Isnil;
    //std::pair Myval;
    unsigned int first; // called Myval in std::set
    const char *second; // not present in std::set
};

struct tree_struct
{
    struct tree_node *Myhead;
    size_t Mysize;
};

void dump_tree_node (struct tree_node *n, bool is_set, bool traverse)
{
    printf ("ptr=0x%p Left=0x%p Parent=0x%p Right=0x%p Color=%d Isnil=%d\n",
            n, n->Left, n->Parent, n->Right, n->Color, n->Isnil);
    if (n->Isnil==0)
    {
        if (is_set)
            printf ("first=%d\n", n->first);
        else
            printf ("first=%d second=[%s]\n", n->first, n->second);
    }

    if (traverse)
    {
        if (n->Isnil==1)
            dump_tree_node (n->Parent, is_set, true);
        else
        {
            if (n->Left->Isnil==0)
                dump_tree_node (n->Left, is_set, true);
            if (n->Right->Isnil==0)
                dump_tree_node (n->Right, is_set, true);
        };
    };
};
const char* ALOT_OF_TABS="\t\t\t\t\t\t\t\t\t\t\t";

void dump_as_tree (int tabs, struct tree_node *n, bool is_set)
{
    if (is_set)
        printf ("%d\n", n->first);
    else
        printf ("%d [%s]\n", n->first, n->second);
    if (n->Left->Isnil==0)
    {
        printf ("%.*sL-------", tabs, ALOT_OF_TABS);
        dump_as_tree (tabs+1, n->Left, is_set);
    };
    if (n->Right->Isnil==0)
    {
        printf ("%.*sR-------", tabs, ALOT_OF_TABS);
        dump_as_tree (tabs+1, n->Right, is_set);
    };
};

void dump_map_and_set(struct tree_struct *m, bool is_set)
{
    printf ("ptr=0x%p, Myhead=0x%p, Mysize=%d\n", m, m->Myhead, m->Mysize);
    dump_tree_node (m->Myhead, is_set, true);
    printf ("As a tree:\n");
    printf ("root----");
    dump_as_tree (1, m->Myhead->Parent, is_set);
};

int main()
{
    // map

    std::map<int, const char*> m;

    m[10]="ten";
    m[20]="twenty";
    m[3]="three";
    m[101]="one hundred one";
    m[100]="one hundred";
    m[12]="twelve";
    m[107]="one hundred seven";
    m[0]="zero";
    m[1]="one";
    m[6]="six";
    m[99]="ninety-nine";
    m[5]="five";
    m[11]="eleven";
    m[1001]="one thousand one";
    m[1010]="one thousand ten";
    m[2]="two";
    m[9]="nine";
    printf ("dumping m as map:\n");
    dump_map_and_set ((struct tree_struct *)(void*)&m, false);

    std::map<int, const char*>::iterator it1=m.begin();
    printf ("m.begin():\n");
    dump_tree_node ((struct tree_node *)*(void**)&it1, false, false);
    it1=m.end();
    printf ("m.end():\n");
    dump_tree_node ((struct tree_node *)*(void**)&it1, false, false);

    // set

    std::set<int> s;
    s.insert(123);
    s.insert(456);
    s.insert(11);
    s.insert(12);
    s.insert(100);
    s.insert(1001);
    printf ("dumping s as set:\n");
    dump_map_and_set ((struct tree_struct *)(void*)&s, true);
    std::set<int>::iterator it2=s.begin();
    printf ("s.begin():\n");
    dump_tree_node ((struct tree_node *)*(void**)&it2, true, false);
    it2=s.end();
    printf ("s.end():\n");
    dump_tree_node ((struct tree_node *)*(void**)&it2, true, false);
};

指令清单51.35 MSVC 2012

dumping m as map:
ptr=0x0020FE04, Myhead=0x005BB3A0, Mysize=17
ptr=0x005BB3A0 Left=0x005BB4A0 Parent=0x005BB3C0 Right=0x005BB580 Color=1 Isnil=1
ptr=0x005BB3C0 Left=0x005BB4C0 Parent=0x005BB3A0 Right=0x005BB440 Color=1 Isnil=0
first=10 second=[ten]
ptr=0x005BB4C0 Left=0x005BB4A0 Parent=0x005BB3C0 Right=0x005BB520 Color=1 Isnil=0
first=1 second=[one]
ptr=0x005BB4A0 Left=0x005BB3A0 Parent=0x005BB4C0 Right=0x005BB3A0 Color=1 Isnil=0
first=0 second=[zero]
ptr=0x005BB520 Left=0x005BB400 Parent=0x005BB4C0 Right=0x005BB4E0 Color=0 Isnil=0
first=5 second=[five]
ptr=0x005BB400 Left=0x005BB5A0 Parent=0x005BB520 Right=0x005BB3A0 Color=1 Isnil=0
first=3 second=[three]
ptr=0x005BB5A0 Left=0x005BB3A0 Parent=0x005BB400 Right=0x005BB3A0 Color=0 Isnil=0
first=2 second=[two]
ptr=0x005BB4E0 Left=0x005BB3A0 Parent=0x005BB520 Right=0x005BB5C0 Color=1 Isnil=0
first=6 second=[six]
ptr=0x005BB5C0 Left=0x005BB3A0 Parent=0x005BB4E0 Right=0x005BB3A0 Color=0 Isnil=0
first=9 second=[nine]
ptr=0x005BB440 Left=0x005BB3E0 Parent=0x005BB3C0 Right=0x005BB480 Color=1 Isnil=0
first=100 second=[one hundred]
ptr=0x005BB3E0 Left=0x005BB460 Parent=0x005BB440 Right=0x005BB500 Color=0 Isnil=0
first=20 second=[twenty]
ptr=0x005BB460 Left=0x005BB540 Parent=0x005BB3E0 Right=0x005BB3A0 Color=1 Isnil=0
first=12 second=[twelve]
ptr=0x005BB540 Left=0x005BB3A0 Parent=0x005BB460 Right=0x005BB3A0 Color=0 Isnil=0
first=11 second=[eleven]
ptr=0x005BB500 Left=0x005BB3A0 Parent=0x005BB3E0 Right=0x005BB3A0 Color=1 Isnil=0
first=99 second=[ninety-nine]
ptr=0x005BB480 Left=0x005BB420 Parent=0x005BB440 Right=0x005BB560 Color=0 Isnil=0
first=107 second=[one hundred seven]
ptr=0x005BB420 Left=0x005BB3A0 Parent=0x005BB480 Right=0x005BB3A0 Color=1 Isnil=0
first=101 second=[one hundred one]
ptr=0x005BB560 Left=0x005BB3A0 Parent=0x005BB480 Right=0x005BB580 Color=1 Isnil=0
first=1001 second=[one thousand one]
ptr=0x005BB580 Left=0x005BB3A0 Parent=0x005BB560 Right=0x005BB3A0 Color=0 Isnil=0
first=1010 second=[one thousand ten]
As a tree:
root----10 [ten]
        L-------1 [one]
                L-------0 [zero]
                R-------5 [five]
                        L-------3 [three]
                                L-------2 [two]
                        R-------6 [six]
                                R-------9 [nine]
        R-------100 [one hundred]
                L-------20 [twenty]
                        L-------12 [twelve]
                                L-------11 [eleven]
                        R-------99 [ninety-nine]
                R-------107 [one hundred seven]
                        L-------101 [one hundred one]
                        R-------1001 [one thousand one]
                                R-------1010 [one thousand ten]
m.begin():
ptr=0x005BB4A0 Left=0x005BB3A0 Parent=0x005BB4C0 Right=0x005BB3A0 Color=1 Isnil=0
first=0 second=[zero]
m.end():
ptr=0x005BB3A0 Left=0x005BB4A0 Parent=0x005BB3C0 Right=0x005BB580 Color=1 Isnil=1

dumping s as set:
ptr=0x0020FDFC, Myhead=0x005BB5E0, Mysize=6
ptr=0x005BB5E0 Left=0x005BB640 Parent=0x005BB600 Right=0x005BB6A0 Color=1 Isnil=1
ptr=0x005BB600 Left=0x005BB660 Parent=0x005BB5E0 Right=0x005BB620 Color=1 Isnil=0
first=123
ptr=0x005BB660 Left=0x005BB640 Parent=0x005BB600 Right=0x005BB680 Color=1 Isnil=0
first=12
ptr=0x005BB640 Left=0x005BB5E0 Parent=0x005BB660 Right=0x005BB5E0 Color=0 Isnil=0
first=11
ptr=0x005BB680 Left=0x005BB5E0 Parent=0x005BB660 Right=0x005BB5E0 Color=0 Isnil=0
first=100
ptr=0x005BB620 Left=0x005BB5E0 Parent=0x005BB600 Right=0x005BB6A0 Color=1 Isnil=0
first=456
ptr=0x005BB6A0 Left=0x005BB5E0 Parent=0x005BB620 Right=0x005BB5E0 Color=0 Isnil=0
first=1001
As a tree:
root----123
        L-------12
                L-------11
                R-------100
        R-------456
                R-------1001
s.begin():
ptr=0x005BB640 Left=0x005BB5E0 Parent=0x005BB660 Right=0x005BB5E0 Color=0 Isnil=0
first=11
s.end():
ptr=0x005BB5E0 Left=0x005BB640 Parent=0x005BB600 Right=0x005BB6A0 Color=1 Isnil=1

因为结构设计得并不紧密,所以2个char型值各占用了4字节空间。

对于std::map结构来说,first和second的数据数据组合可被视为std::pair的一个数据元素。而std::set的每个节点则只有1个值。

51.4.2节介绍过,MSVC编译器在构造std::list的时候会保链表的长度信息。我们可以在程序看到它也存储了这种数据类型的具体尺寸。

这两种数据结构和std::list的相同之处是,迭代器都是指向节点的指针。.begin()迭代函数指向最小的键。实际上,整个数据结构里都没有最小键的指针(和链表的情况一样)每当程序调用这个迭代器的时候,它就遍历所有键、查找出最小值。单目递增运算符operator --和单目递减运算符operator++可将指针指向树里的前一个或后一个节点。MIT出版社出版的《Introduction to Algorithms, Third Edition》(Thomas H. Cormen等人著)介绍了这两个运算符的具体算法。

迭代器.end()指向了一个隐蔽的虚节点。其Isnil为1,即是说它没有对应的关键字(key)或值(value)、不是真正意义上的数据结点,仅是一个存储控制信息的容器。这个虚节点的父节点是真正的根节点的指针,也就是整个信息树的顶点。