以上图表采用了偏移量与对应变量的方式展现3个类对象的内存存储结构。图中一共出现了4个变量,即长width、高height、宽depth以及密度density。

体积函数get_volume()的代码如下所示。

指令清单51.15 带/Ob0参数的MSVC 2008优化程序

?get_volume@box@@QAEHXZ PROC ; box::get_volume, COMDAT
; _this$ = ecx
    mov   eax, DWORD PTR [ecx+8]
    imul  eax, DWORD PTR [ecx+4]
    imul  eax, DWORD PTR [ecx]
    ret   0
?get_volume@box@@QAEHXZ ENDP ; box::get_volume

密度函数get_density()的代码如下所示。

指令清单51.16 带/Ob0参数的MSVC 2008优化程序

?get_density@solid_object@@QAEHXZ PROC ; solid_object::get_density, COMDAT
; _this$ = ecx
    mov  eax, DWORD PTR [ecx]
    ret  0
?get_density@solid_object@@QAEHXZ ENDP ; solid_object::get_density

最有意思的是solod_box::get_weight()重量函数。

指令清单51.17 带/Ob0参数的MSVC 2008优化程序

?get_weight@solid_box@@QAEHXZ PROC ; solid_box::get_weight, COMDAT
; _this$ = ecx
    push  esi
    mov   esi, ecx
    push  edi
    lea   ecx, DWORD PTR [esi+12]
    call  ?get_density@solid_object@@QAEHXZ ; solid_object::get_density
    mov   ecx, esi
    mov   edi, eax
    call  ?get_volume@box@@QAEHXZ ; box::get_volume
    imul  eax, edi
    pop   edi
    pop   esi
    ret   0
?get_weight@solid_box@@QAEHXZ ENDP ; solid_box::get_weight

函数get_weight()(计算重量)只调用了两个方法。在调用get_volume()(计算体积)时,它传递了this指针。而在调用get_density()(密度)函数时,它传递的地址是“this指针+12个字节”。后面这个地址对应的是solid_box类的solid_object字段。

因此,solid_object::get_density()方法认为,它处理的是常规的solid_object类,而box::get_volume()则可以正常访问原有数据类型的3个变量,如同直接操作box类一样。

因此,我们可以相信:继承了其他的、多个类而生成的类对象,在内存之中就是一种联合体型的数据结构。它继承了原有父类的全部字段和方法。在这种继承类对象调用某个具体方法时,它传递的是与该方法原有基类相对地址相应的this指针。

51.1.5 虚拟方法

我们再来看看一个简单点的例子:

#include <stdio.h>

class object
{
    public:
        int color;
        object() { };
        object (int color) { this->color=color; };
        virtual void dump()
        {
            printf ("color=%d\n", color);
        };
};

class box : public object
{
    private:
        int width, height, depth;
    public:
        box(int color, int width, int height, int depth)
        {
            this->color=color;
            this->width=width;
            this->height=height;
            this->depth=depth;
        };
        void dump()
        {
            printf ("this is box. color=%d, width=%d, height=%d, depth=%d\n", color, width, height, depth);
        };
};

class sphere : public object
{
    private:
        int radius;
    public:
        sphere(int color, int radius)
        {
            this->color=color;
            this->radius=radius;
        };
        void dump()
        {
            printf ("this is sphere. color=%d, radius=%d\n", color, radius);
        };
};

int main()
{
    box b(1, 10, 20, 30);
    sphere s(2, 40);

    object *o1=&b;
    object *o2=&s;

    o1->dump();
    o2->dump();
    return 0;
};

类object定义一个虚拟函数dump(),它被继承类box和sphere中的同名函数覆盖了。

在调用虚拟函数时,编译器阶段可能无法确定对象的类型情况。当类中含有虚函数时,其基类的指针就可以指向任何派生类的对象,这时就有可能不知道基类指针到底指向的是哪个对象的情况。这时就要根据实时类型信息,确定应当调用的相应函数。

在启用优化编译选项/Ox和/Ob0后,我们再用MSVC 2008编译主函数main():

_s$ = -32 ; size = 12
_b$ = -20 ; size = 20
_main PROC
    sub   esp, 32
    push  30
    push  20
    push  10
    push  1
    lea   ecx, DWORD PTR _b$[esp+48]
    call  ??0box@@QAE@HHHH@Z ; box::box
    push  40
    push  2
    lea   ecx, DWORD PTR _s$[esp+40]
    call  ??0sphere@@QAE@HH@Z ; sphere::sphere
    mov   eax, DWORD PTR _b$[esp+32]
    mov   edx, DWORD PTR [eax]
    lea   ecx, DWORD PTR _b$[esp+32]
    call  edx
    mov   eax, DWORD PTR _s$[esp+32]
    mov   edx, DWORD PTR [eax]
    lea   ecx, DWORD PTR _s$[esp+32]
    call  edx
    xor   eax, eax
    add   esp, 32
    ret   0
_main ENDP

指向dump()函数的函数指针应当位于类对象object中的某个地方。我们在哪里去找新方法的函数地址呢?它必定由构造函数定义: main()函数没用调用其他函数,因此这个指针肯定由构造函数定义。

box类实例的构造函数为:

??_R0?AVbox@@@8 DD FLAT:??_7type_info@@6B@ ; box 'RTTI Type Descriptor'
    DD     00H
    DB     '.?AVbox@@', 00H

??_R1A@?0A@EA@box@@8 DD FLAT:??_R0?AVbox@@@8 ; box::'RTTI Base Class Descriptor at (0,-1,0,64)'
    DD     01H
    DD     00H
    DD     0ffffffffH
    DD     00H
    DD     040H
    DD     FLAT:??_R3box@@8

??_R2box@@8 DD     FLAT:??_R1A@?0A@EA@box@@8 ; box::'RTTI Base Class Array'
    DD     FLAT:??_R1A@?0A@EA@object@@8

??_R3box@@8 DD     00H ; box::'RTTI Class Hierarchy Descriptor'
    DD     00H
    DD     02H
    DD     FLAT:??_R2box@@8

??_R4box@@6B@ DD 00H ; box::'RTTI Complete Object Locator'
    DD     00H
    DD     00H
    DD     FLAT:??_R0?AVbox@@@8
    DD     FLAT:??_R3box@@8

??_7box@@6B@ DD     FLAT:??_R4box@@6B@ ; box::`vftable'
    DD     FLAT:?dump@box@@UAEXXZ

_color$ = 8    ; size = 4
_width$ = 12   ; size = 4
_height$ = 16  ; size = 4
_depth$ = 20   ; size = 4
??0box@@QAE@HHHH@Z PROC ; box::box, COMDAT
; _this$ = ecx
    push  esi
    mov   esi, ecx
    call  ??0object@@QAE@XZ ; object::object
    mov   eax, DWORD PTR _color$[esp]
    mov   ecx, DWORD PTR _width$[esp]
    mov   edx, DWORD PTR _height$[esp]
    mov   DWORD PTR [esi+4], eax
    mov   eax, DWORD PTR _depth$[esp]
    mov   DWORD PTR [esi+16], eax
    mov   DWORD PTR [esi], OFFSET ??_7box@@6B@
    mov   DWORD PTR [esi+8], ecx
    mov   DWORD PTR [esi+12], edx
    mov   eax, esi
    pop   esi
    ret   16
??0box@@QAE@HHHH@Z ENDP ; box::box

它的内存布局略有不同:第一个字段是某个box::’vftable’(虚拟函数表)的指针(具体名称由MSVC编译器设置)。

在这个表中,我们看到一个指向数据表box::RTTI Complete Object Locator的链接和一个指向类成员函数box::dump()的链接。它们的正规名称分别是虚拟方法表和RTTI[3]。虚拟方法表存储着各方法的地址,RTTI表存储着类型的信息。另外,RTTI表为C++程序提供了“强制转换运算符”dynamic_cast (将基类类型的指针或引用安全地转换为派生类型的指针或引用)和“类型查询操作符”typeid。在上述指令调用类成员函数时,它所使用的类名称仍然是文本型字符串。基于代码中dump()函数的实例情况可知,在通过调用指向基类的指针(或引用)调用其虚拟函数(类实例::虚方法)时,指针最终会指向派生类实例的同名虚拟方法——构造函数会把指针实际指向的对象实例的类型信息存储在数据结构之中。

在内存数据表里检索虚拟方法的内存地址必定要消耗额外的CPU时间。因此虚拟方法的运行速度比一般的方法要慢一些。

在GCC生成的相应代码中,RTTI表的构造稍微有些不同。

51.2 ostream输出流

我们来看一个经典的例子“hello world!”,这里我们试图采用输出流的方式重新实现它。

#include <iostream>

int main()
{
    std::cout << "Hello, world!\n";
}

几乎所有的教科书都写明,运算重载符“<<”的作用是“重载”其他类型的数据,主要用于对象之间的运算。我们来看看操作符“<<”的输出流用法。

指令清单51.18 精简版的MSVC 2012的程序代码

$SG37112 DB 'Hello, world!', 0aH, 00H

_main PROC
    push OFFSET $SG37112
    push OFFSET ?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::cout
    call ??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU? ↙
    ↘ $char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char> >
    add   esp, 8
    xor   eax, eax
    ret   0
_main ENDP

我们把源程序稍微修改一下:

#include <iostream>

int main()
{
    std::cout << "Hello, " << "world!\n";
}

教科书都说这种运算会从左至右依次进行。实际上确实如此:

指令清单51.19 MSVC 2012下的程序实现

$SG37112 DB 'world!', 0aH, 00H
$SG37113 DB 'Hello, ', 00H

_main PROC
    push OFFSET $SG37113 ; 'Hello, '
    push OFFSET ?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::cout
    call ??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU? ↙
    ↘ $char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char> >
    add  esp, 8

    push OFFSET $SG37112 ; 'world!'
    push eax             ; result of previous function execution
    call ??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU? ↙
    ↘ $char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char> >
    add  esp, 8

    xor  eax, eax
    ret  0
_main ENDP

如果我们用f()函数来表示“<<”的运算功能的话,那么上述程序就可以表示为:

f(f(std::cout, "Hello, "), "world!");

GCC生成的代码 和MSVC生成的代码基本一样。

51.3 引用

C++中,引用也是指针(可以参考本书第10章),但是调用其是安全的,因为在编译它们时,是很难出现失误的(参见ISO13,p.8.3.2)。比如说,引用永远指向某个类型的既定对象,而且引用不可以是空(参见Cli,p.8.6)。更进一步讲,引用不能改变指向,不可能把某个引用重新指向其他的对象(参见Cli,p.8.5)。

接下来,我们稍微改写一下第10章的第一个源程序,把f1函数的指针全部替换为引用:

void f2 (int x, int y, int & sum, int & product)
{
        sum=x+y;
        product=x*y;
};

我们可以看到编译之后的代码和那个使用指针的代码完全一样(参见第10章)。

指令清单51.20 采用MSVC 2010优化的程序代码

_x$ = 8                                              ; size = 4
_y$ = 12                                             ; size = 4
_sum$ = 16                                           ; size = 4
_product$ = 20                                       ; size = 4
?f2@@YAXHHAAH0@Z PROC                                ; f2
        mov     ecx, DWORD PTR _y$[esp-4]
        mov     eax, DWORD PTR _x$[esp-4]
        lea     edx, DWORD PTR [eax+ecx]
        imul eax, ecx
        mov ecx, DWORD PTR _product$[esp-4]
        push esi
        mov     esi, DWORD PTR _sum$[esp]
        mov     DWORD PTR [esi], edx
        mov     DWORD PTR [ecx], eax
        pop     esi
        ret     0
?f2@@YAXHHAAH0@Z ENDP                                ; f2

至于为什么这里的程序使用了一些奇怪的名字,可以参见本书的51.1.1节。

51.4 STL/标准模板库(Standard Template Library)

请注意:本书仅保证本节内容在32位系统里有效,未对x64系统做过验证。

51.4.1 std::string(字符串)

内部

多数字符串库(Yur13,p.2.2)都把std::string定义为以下几个组件:缓冲区指针、字符串缓冲区、当前字符串的长度(便于函数操作;请参阅[Yur13]的2.2.1节)以及当前缓冲区的容量。在缓冲区里,字符串通常用0作字符串结束符,以兼容常规的C语言ASCIIZ字符串格式。

C++的标准ISO13没有定义std::string 的实现方法。然而,它们通常用上述方法定义的这种数据结构。

在C++的标准数据结构中,字符串不是类对象(不像Qt那样,把QString声明为标准类)。它把字符串定义为模板型数据(基本字符串basic_string)。这是为了兼容各种类型的字符元素。现在,它至少支持char(标准字符)以及wchar_t(宽字符)。

因此,std::string是以8位字符char为基本类型的类,而std::wstring则是以16/32位宽字符wchar_t为基本类型的类。

MSVC

当字符串长度在16字符以内时,MSVC将字符串数据直接存储在缓冲区里,不再使用“指针+缓冲区”的复杂结构。

这就意味着;在32位系统里,字符串最少会占用24(16+4+4=24)个字节;而在64位环境下,字符串至少占用32(16+8+8=32)个字节。如果字符串的长度超过16个字符的话,这16个字节空间就算白白浪费了。

指令清单51.21 MSVC的例子程序

#include <string>
#include <stdio.h>

struct std_string
{
    union
    {
        char buf[16];
        char* ptr;
    } u;
    size_t size;      // AKA 'Mysize' in MSVC
    size_t capacity;  // AKA 'Myres' in MSVC
};

void dump_std_string(std::string s)
{
    struct std_string *p=(struct std_string*)&s;
    printf ("[%s] size:%d capacity:%d\n", p->size>16 ? p->u.ptr : p->u.buf, p->size, p-> capacity);
};

int main()
{
    std::string s1="short string";
    std::string s2="string longer that 16 bytes";

    dump_std_string(s1);
    dump_std_string(s2);

    // that works without using c_str()
    printf ("%s\n", &s1);
    printf ("%s\n", s2);
};

源代码的功能应当不需要解释。

需要注意的有以下几点:

只要字符串长度没有超过16个字符,编译器就不会使用堆(heap)存储字符串的缓冲区。在实际的程序中,多数字符串确实是短字符串。很明显,微软研发人员将16字符串作为长短字符串的分割点。

虽然我们没有在主程序main()的最后调用成员函数c_str(),但是这个程序可以通过编译,也能在屏幕上显示出字符串的内容。

这就是为什么这个程序能运转起来。

第一个例子的字符串不足16个字符,因此它会被保存到字符串缓冲区。这个缓冲区实际位于std:string对象的起始地址(可视为结构体型数据)。这个区域里的数据,采取了标准的ASCIIZ的数据结构。因此printf()函数在处理指针时直接处理了相应的ASCIIZ字符串。所以,源程序可以显示第一个字符串的内容。

第二个字符串的长度大于16字节,更危险。编程人员很容易在此疏忽大意、忘记此时应当使用string对象的成员函数c_str()。之所以本例这样还能正常工作,是因为指向缓冲区的指针正好位于结构体的开始部分。某些人可能在相当长的时间里一直这么写代码,而一直不觉得会有问题;直到他们遇到超长字符串引发程序崩溃的时候,他们才会开始意识到问题的存在。

GCC

GCC在实现std::string的时候使用了MSVC里没有的变量——reference count。

另外一个有趣的事情是:指向std::string实例的指针,并不是指向结构体的起始地址,而是指向了字符串缓冲区的指针。文件libstdc++-v3/include/bits/ basic_string.h 解释了这一问题。它说,这是为了便于调试程序:

* The reason you want _M_data pointing to the character %array and
* not the _Rep is so that the debugger can see the string
* contents. (Probably we should add a non-inline member to get
* the _Rep for the debugger to use, so users can check the actual
* string length.)

有兴趣的读者可以下载看看:http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a010 68.html

考虑到有关问题之后,我们调整了上一个小节使用的源程序:

指令清单51.22 GCC例子

#include <string>
#include <stdio.h>

struct std_string
{
    size_t length;
    size_t capacity;
    size_t refcount;
};

void dump_std_string(std::string s)
{
    char *p1=*(char**)&s; // GCC type checking workaround
    struct std_string *p2=(struct std_string*)(p1-sizeof(struct std_string));
    printf ("[%s] size:%d capacity:%d\n", p1, p2->length, p2->capacity);
};

int main()
{
    std::string s1="short string";
    std::string s2="string longer that 16 bytes";

    dump_std_string(s1);
    dump_std_string(s2);

    // GCC type checking workaround:
    printf ("%s\n", *(char**)&s1);
    printf ("%s\n", *(char**)&s2);
};

因为GCC的类型检查规则更为苛刻,所以我们不得不做很多针对性的修改。即使这个程序的printf()函数同样可以在不依赖c_str()函数的情况下打印字符串内容。

一个更加复杂的例子

#include <string>
#include <stdio.h>

int main()
{
    std::string s1="Hello, ";
    std::string s2="world!\n";
    std::string s3=s1+s2;

    printf ("%s\n", s3.c_str());
}

指令清单51.23 MSVC 2012编译的程序

$SG39512 DB 'Hello, ', 00H
$SG39514 DB 'world!', 0aH, 00H
$SG39581 DB '%s', 0aH, 00H

_s2$ = -72 ; size = 24
_s3$ = -48 ; size = 24
_s1$ = -24 ; size = 24
_main PROC
    sub  esp, 72

    push 7
    push OFFSET $SG39512
    lea  ecx, DWORD PTR _s1$[esp+80]
    mov  DWORD PTR _s1$[esp+100], 15
    mov  DWORD PTR _s1$[esp+96], 0
    mov  BYTE PTR _s1$[esp+80], 0
    call ?assign@?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@QAEAAV12@PBDI@Z ; ↙
    ↘std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign

    push 7
    push OFFSET $SG39514
    lea  ecx, DWORD PTR _s2$[esp+80]
    mov  DWORD PTR _s2$[esp+100], 15
    mov  DWORD PTR _s2$[esp+96], 0
    mov  BYTE PTR _s2$[esp+80], 0
    call ?assign@?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@QAEAAV12@PBDI@Z ; ↙
    ↘ std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign

    lea  eax, DWORD PTR _s2$[esp+72]
    push eax
    lea  eax, DWORD PTR _s1$[esp+76]
    push eax
    lea  eax, DWORD PTR _s3$[esp+80]
    push eax
    call ??$?HDU?$char_traits@D@std@@V?$allocator@D@1@@std@@YA?AV?$basic_string@DU? ↙
    ↘ $char_traits@D@std@@V?$allocator@D@2@@0@ABV10@0@Z ; std::operator+<char,std::char_traits< ↙
    ↘ char>,std::allocator<char> >

    ; inlined c_str() method:
    cmp  DWORD PTR _s3$[esp+104], 16
    lea  eax, DWORD PTR _s3$[esp+84]
    cmovae eax, DWORD PTR _s3$[esp+84]

    push eax
    push OFFSET $SG39581
    call _printf
    add  esp, 20

    cmp  DWORD PTR _s3$[esp+92], 16
    jb   SHORT $LN119@main
    push DWORD PTR _s3$[esp+72]
    call ??3@YAXPAX@Z              ; operator delete
    add  esp, 4
$LN119@main:
    cmp  DWORD PTR _s2$[esp+92], 16
    mov  DWORD PTR _s3$[esp+92], 15
    mov  DWORD PTR _s3$[esp+88], 0
    mov  BYTE PTR _s3$[esp+72], 0
    jb   SHORT $LN151@main
    push DWORD PTR _s2$[esp+72]
    call ??3@YAXPAX@Z               ; operator delete
    add  esp, 4
$LN151@main:
    cmp  DWORD PTR _s1$[esp+92], 16
    mov  DWORD PTR _s2$[esp+92], 15
    mov  DWORD PTR _s2$[esp+88], 0
    mov  BYTE PTR _s2$[esp+72], 0
    jb   SHORT $LN195@main
    push DWORD PTR _s1$[esp+72]
    call ??3@YAXPAX@Z               ; operator delete
    add  esp, 4
$LN195@main:
    xor  eax, eax
    add  esp, 72
    ret  0
_main ENDP

编译器没有采用原有模式构建字符串。使用堆来存储字符串缓冲区,数据结构自然就完全不同。ASCIIZ字符串通常存储于程序的数据段,在执行程序的时候,assign方式会构造字符串s1和s2。而后程序通过运算符“+”构造s3。

请注意此处没有调用字符串的c_str()方式。因为代码很紧凑,所以编译器把c_str()的代码内联(内嵌)到了此处:如果字符串的长度不足16个字符,那么EAX寄存器将保留缓冲区的指针;否则它将提取堆里那个存储字符串的缓冲区指针。

最后,程序调用了3个析构函数,用于释放长字符串(长度大于16个字符的字符串)占用的堆空间。如果字符串长度小于16,那么std::string对象全部存储于数据栈,会随函数结束而自动释放。

就性能而言,短字符串的处理速度更快,因为访问堆的操作要少一些。

GCC的处理方式更为简单。GCC不会把短字符串的文本缓冲区直接存储到string结构体里。

使用GCC\ 4.8.1编译上述程序,可得到:

指令清单51.24 GCC 4.8.1下的程序编译

.LC0:
    .string "Hello, "
.LC1:
    .string "world!\n"
main:
    push  ebp
    mov   ebp, esp
    push  edi
    push  esi
    push  ebx
    and   esp, -16
    sub   esp, 32
    lea   ebx, [esp+28]
    lea   edi, [esp+20]
    mov   DWORD PTR [esp+8], ebx
    lea   esi, [esp+24]
    mov   DWORD PTR [esp+4], OFFSET FLAT:.LC0
    mov   DWORD PTR [esp], edi

    call  _ZNSsC1EPKcRKSaIcE

    mov   DWORD PTR [esp+8], ebx
    mov   DWORD PTR [esp+4], OFFSET FLAT:.LC1
    mov   DWORD PTR [esp], esi

    call  _ZNSsC1EPKcRKSaIcE

    mov   DWORD PTR [esp+4], edi
    mov   DWORD PTR [esp], ebx

    call  _ZNSsC1ERKSs

    mov   DWORD PTR [esp+4], esi
    mov   DWORD PTR [esp], ebx

    call  _ZNSs6appendERKSs

    ; inlined c_str():
    mov   eax, DWORD PTR [esp+28]
    mov   DWORD PTR [esp], eax

    call  puts

    mov   eax, DWORD PTR [esp+28]
    lea   ebx, [esp+19]
    mov   DWORD PTR [esp+4], ebx
    sub   eax, 12
    mov   DWORD PTR [esp], eax
    call  _ZNSs4_Rep10_M_disposeERKSaIcE
    mov   eax, DWORD PTR [esp+24]
    mov   DWORD PTR [esp+4], ebx
    sub   eax, 12
    mov   DWORD PTR [esp], eax
    call  _ZNSs4_Rep10_M_disposeERKSaIcE
    mov   eax, DWORD PTR [esp+20]
    mov   DWORD PTR [esp+4], ebx
    sub   eax, 12
    mov   DWORD PTR [esp], eax
    call  _ZNSs4_Rep10_M_disposeERKSaIcE
    lea   esp, [ebp-12]
    xor   eax, eax
    pop   ebx
    pop   esi
    pop   edi
    pop   ebp
    ret

可见,传递给析构函数的指针不是对象的指针,而是指向string对象之前12个字节的地址的指针——那才是结构体真正的起始地址。

全局变量std::string

虽然资深的C++编程人员都不会把std::string当作全局变量使用,但实际上由STL定义的数据类型都可以用作全局变量,

确实如此,我们来看下面这段程序:

#include <stdio.h>
#include <string>

std::string s="a string";

int main()
{
    printf ("%s\n", s.c_str());
};

实际上,在主函数main()启动之前,全局变量就已经完成初始化操作了。

指令清单 51.25 MSVC 2012(这里我们可以看到这个全局变量是
如何构造的以及一个析构体是如何注册的)

??__Es@@YAXXZ PROC
    push 8
    push OFFSET $SG39512 ; 'a string'
    mov  ecx, OFFSET ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A ; s
    call ?assign@?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@QAEAAV12@PBDI@Z ; ↙
    ↘ std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign
    push OFFSET ??__Fs@@YAXXZ ; `dynamic atexit destructor for 's''
    call _atexit
    pop  ecx
    ret  0
??__Es@@YAXXZ ENDP

指令清单51.26 MSVC 2012(从这个程序我们可以看到,
主函数main()是如何使用一个全局变量的)

$SG39512 DB 'a string', 00H
$SG39519 DB '%s', 0aH, 00H

_main PROC
    cmp   DWORD PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A+20, 16
    mov   eax, OFFSET ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A ; s
    cmovae eax, DWORD PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A
    push  eax
    push  OFFSET $SG39519 ; '%s'
    call  _printf
    add   esp, 8
    xor   eax, eax
    ret   0
_main ENDP

指令清单51.27 MSVC 2012在退出之前,析构函数的调用过程

??__Fs@@YAXXZ PROC
    push  ecx
    cmp   DWORD PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A+20, 16
    jb    SHORT $LN23@dynamic
    push  esi
    mov   esi, DWORD PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A
    lea   ecx, DWORD PTR $T2[esp+8]
    call  ??0?$_Wrap_alloc@V?$allocator@D@std@@@std@@QAE@XZ
    push  OFFSET ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A ; s
    lea   ecx, DWORD PTR $T2[esp+12]
    call  ??$destroy@PAD@?$_Wrap_alloc@V?$allocator@D@std@@@std@@QAEXPAPAD@Z
    lea   ecx, DWORD PTR $T1[esp+8]
    call  ??0?$_Wrap_alloc@V?$allocator@D@std@@@std@@QAE@XZ
    push  esi
    call  ??3@YAXPAX@Z ; operator delete
    add   esp, 4
    pop   esi
$LN23@dynamic:
    mov   DWORD PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A+20, 15
    mov   DWORD PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A+16, 0
    mov   BYTE PTR ?s@@3V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@A, 0
    pop   ecx
    ret   0
??__Fs@@YAXXZ ENDP

实际上,主函数main()没有调用那个创建全局变量的构造函数,这部分任务是CRT在启动main()函数之前就已经完成的操作。不止如此,全局变量的析构函数由stdlib声明的atexit()函数提供,只有在main结束之后才会被调用。

GCC的处理方法十分相似。经GCC 4.8.1编译上述源程序,可得到:

指令清单51.28 GCC 4.8.1函数

main:
    push  ebp
    mov   ebp, esp
    and   esp, -16
    sub   esp, 16
    mov   eax, DWORD PTR s
    mov   DWORD PTR [esp], eax
    call  puts
    xor   eax, eax
    leave
    ret
.LC0:
    .string "a string"
_GLOBAL__sub_I_s:
    sub   esp, 44
    lea   eax, [esp+31]
    mov   DWORD PTR [esp+8], eax
    mov   DWORD PTR [esp+4], OFFSET FLAT:.LC0
    mov   DWORD PTR [esp], OFFSET FLAT:s
    call  _ZNSsC1EPKcRKSaIcE
    mov   DWORD PTR [esp+8], OFFSET FLAT:__dso_handle
    mov   DWORD PTR [esp+4], OFFSET FLAT:s
    mov   DWORD PTR [esp], OFFSET FLAT:_ZNSsD1Ev
    call  __cxa_atexit
    add   esp, 44
    ret
.LFE645:
    .size  _GLOBAL__sub_I_s, .-_GLOBAL__sub_I_s
    .section .init_array,"aw"
    .align 4
    .long  _GLOBAL__sub_I_s
    .globl s
    .bss
    .align 4
    .type  s, @object
    .size  s, 4
s:
    .zero 4
    .hidden __dso_handle

但是GCC没有单独建立一个专用函数,而是把每个析构函数逐一传递给atexit()函数。

51.4.2 std::list

std::list是众所皆知的双向链表的容器类,它的每个数据元素可通过链表指针(链域)串接成逻辑意义上的线性表。这种数据结构的每个元素都有2个指针,一个指针指向前一个元素,另一个指针指向后一个元素。

链域的存在决定了,每个节点要比单纯的节点数据元素多占用2个words的空间,即32位系统下要多占用8个字节,而64位系统下会多占用16个字节。

C++的标准模板库只是给现有结构体扩充了“next”“previous”指针,使之形成语意上的有序序列。

我们以2个变量组成的结构体为例,演示std::list的链结构。

虽然C++标准(ISO/IEC 14882:2011 (C++ 11 standard))没有明确这种数据结构的具体实现方法,但是MSVC编译器和GCC编译器不约而同地选择几乎一致的实现方法。我们就以下源程序为例进行说明:

#include <stdio.h>
#include <list>
#include <iostream>

struct a
{
    int x;
    int y;
};

struct List_node
{
    struct List_node* _Next;
    struct List_node* _Prev;
    int x;
    int y;
};

void dump_List_node (struct List_node *n)
{
    printf ("ptr=0x%p _Next=0x%p _Prev=0x%p x=%d y=%d\n",
        n, n->_Next, n->_Prev, n->x, n->y);
};

void dump_List_vals (struct List_node* n)
{
    struct List_node* current=n;

    for (;;)
    {
        dump_List_node (current);
        current=current->_Next;
        if (current==n) // end
            break;
    };
};

void dump_List_val (unsigned int *a)
{
#ifdef _MSC_VER
    // GCC implementation does not have "size" field
    printf ("_Myhead=0x%p, _Mysize=%d\n", a[0], a[1]);
#endif
    dump_List_vals ((struct List_node*)a[0]);
};

int main()
{
    std::list<struct a> l;

    printf ("* empty list:\n");
    dump_List_val((unsigned int*)(void*)&l);

    struct a t1;
    t1.x=1;
    t1.y=2;
    l.push_front (t1);
    t1.x=3;
    t1.y=4;
    l.push_front (t1);
    t1.x=5;
    t1.y=6;
    l.push_back (t1);

    printf ("* 3-elements list:\n");
    dump_List_val((unsigned int*)(void*)&l);

    std::list<struct a>::iterator tmp;
    printf ("node at .begin:\n");
    tmp=l.begin();
    dump_List_node ((struct List_node *)*(void**)&tmp);
    printf ("node at .end:\n");
    tmp=l.end();
    dump_List_node ((struct List_node *)*(void**)&tmp);

    printf ("* let's count from the begin:\n");
    std::list<struct a>::iterator it=l.begin();
    printf ("1st element: %d %d\n", (*it).x, (*it).y);
    it++;
    printf ("2nd element: %d %d\n", (*it).x, (*it).y);
    it++;
    printf ("3rd element: %d %d\n", (*it).x, (*it).y);
    it++;
    printf ("element at .end(): %d %d\n", (*it).x, (*it).y);

    printf ("* let's count from the end:\n");
    std::list<struct a>::iterator it2=l.end();
    printf ("element at .end(): %d %d\n", (*it2).x, (*it2).y);
    it2--;
    printf ("3rd element: %d %d\n", (*it2).x, (*it2).y);
    it2--;
    printf ("2nd element: %d %d\n", (*it2).x, (*it2).y);
    it2--;
    printf ("1st element: %d %d\n", (*it2).x, (*it2).y);

    printf ("removing last element...\n");
    l.pop_back();
    dump_List_val((unsigned int*)(void*)&l);
};

GCC

我们首先讲解GCC编译器的编译方式。

运行上述程序时,将会得到很多输出数据。我们进行分段解说:

* empty list:
ptr=0x0028fe90 _Next=0x0028fe90 _Prev=0x0028fe90 x=3 y=0

此时它还是个空链。虽然我们还未对其进行赋值操作,但是变量x和变量y已经有数据了(也就是常人所说的虚结点/dummy node)。而且,“next”“prev”指针都指向该节点自己。

4801-1

在这个时候,迭代器.begin(开始)和.end(结束)值相等。

然后程序创建了3个节点,此后整个链表的内部数据将会变为:

* 3-elements list:
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
ptr=0x00034988 _Next=0x00034b40 _Prev=0x000349a0 x=1 y=2
ptr=0x00034b40 _Next=0x0028fe90 _Prev=0x00034988 x=5 y=6
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034b40 x=5 y=6

最后一个元素的地址还是刚才的0x0028fe90。实际上在释放结构体之前它的地址不会发生变化。而且这个节点的两个字段xy仍然还是随机的噪音数据,这时它们的值分别是5和6。碰巧的是,这些值和最后一个元素的值相同。只是这种巧合并不会一直持续下去。

此时,这3个节点存储过程和内存分布结构如下所示。

4801-1z

变量l总是指向第一个节点。

实际上迭代器.begin()(开始)和.end()(结束)不是变量而是函数,它们的返回值是相应节点的指针。

双向链表通常都会采用这种虚节点(英文别称是sentinel node/岗哨节点)的实现方法。这种节点具有简化链结构和提升操作效率的作用。

迭代器其实就是一个指向节点的指针,而list.begin()和list.end()分别返回首/尾节点的指针。

node at .begin:
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
node at .end:
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034b40 x=5 y=6

事实上,最后一个节点的Next指针指向的第一个节点,而第一个元素的Prev指针指向的是最后一个元素。因此我们很容易就能想到这是一个循环链。

所以,可利用指向第一个节点的指针(即本例的实例l)顺藤摸瓜地找到序列的最后一个节点,而不必遍历整个链。利用这种结构,我们还可毫不费力的在链尾之后插入其他节点。

运算符“++”、“--”就是把迭代器的值设为[当前节点->prev]或[当前节点->next]的值。逆向迭代器(reverse iterators,即.rbegin和.rend)的作用几乎相同,只是方向相反。

迭代器的运算符“*”用于返回节点结构体的指针,即自定义的数据结构体的启始地址,换句话说是节点第一项数据(本例中是x)的指针。

在链表里插入和删除节点时,我们只需要分配(或释放)节点的存储空间,,然后再更新所有的链域指针、即可保障整个链的有效性。

在删除节点之后,相邻节点的迭代器(链域)可能依然指向被删除的无效节点,此时迭代器就会失效。指向无效结点的迭代器又叫做“迷途指针”和“悬空指针”(dangling pointer)。当然,这种指针就不能再使用了。

在GCC(以4.8.1版为例)编译std::list的实例时,它不会存储链中的节点总数。这就意味着内置函数.size()的运行速度十分缓慢,因为它必须遍历完整个数据链才能返回节点个数。因此,那些与节点总数有关的所有函数(例如O(n))的时间开销都和链表长度成正比。

指令清单51.29 GCC4.8.1带参数-fno内置小函数的优化

main proc near
    push  ebp
    mov   ebp, esp
    push  esi
    push  ebx
    and   esp, 0FFFFFFF0h
    sub   esp, 20h
    lea   ebx, [esp+10h]
    mov   dword ptr [esp], offset s ; "* empty list:"
    mov   [esp+10h], ebx
    mov   [esp+14h], ebx
    call  puts
    mov   [esp], ebx
    call  _Z13dump_List_valPj ; dump_List_val(uint *)
    lea   esi, [esp+18h]
    mov   [esp+4], esi
    mov   [esp], ebx
    mov   dword ptr [esp+18h], 1 ; X for new element
    mov   dword ptr [esp+1Ch], 2 ; Y for new element
    call  _ZNSt4listI1aSaIS0_EE10push_frontERKS0_ ; std::list<a,std::allocator<a>>::push_front(a ↙
    ↘ const&)
    mov   [esp+4], esi
    mov   [esp], ebx
    mov   dword ptr [esp+18h], 3 ; X for new element
    mov   dword ptr [esp+1Ch], 4 ; Y for new element
    call  _ZNSt4listI1aSaIS0_EE10push_frontERKS0_ ; std::list<a,std::allocator<a>>::push_front(a ↙
    ↘ const&)
    mov   dword ptr [esp], 10h
    mov   dword ptr [esp+18h], 5 ; X for new element
    mov   dword ptr [esp+1Ch], 6 ; Y for new element
    call  _Znwj ; operator new(uint)
    cmp   eax, 0FFFFFFF8h
    jz    short loc_80002A6
    mov   ecx, [esp+1Ch]
    mov   edx, [esp+18h]
    mov   [eax+0Ch], ecx
    mov   [eax+8], edx

loc_80002A6: ; CODE XREF: main+86
    mov   [esp+4], ebx
    mov   [esp], eax
    call  _ZNSt8__detail15_List_node_base7_M_hookEPS0_ ; std::__detail::_List_node_base::_M_hook ↙
    ↘ (std::__detail::_List_node_base*)
    mov   dword ptr [esp], offset a3ElementsList ; "* 3-elements list:"
    call  puts
    mov   [esp], ebx
    call  _Z13dump_List_valPj ; dump_List_val(uint *)
    mov   dword ptr [esp], offset aNodeAt_begin ; "node at .begin:"
    call  puts
    mov   eax, [esp+10h]
    mov   [esp], eax
    call  _Z14dump_List_nodeP9List_node ; dump_List_node(List_node *)
    mov   dword ptr [esp], offset aNodeAt_end ; "node at .end:"
    call  puts
    mov   [esp], ebx
    call  _Z14dump_List_nodeP9List_node ; dump_List_node(List_node *)
    mov   dword ptr [esp], offset aLetSCountFromT ; "* let's count from the begin:"
    call  puts
    mov   esi, [esp+10h]
    mov   eax, [esi+0Ch]
    mov   [esp+0Ch], eax
    mov   eax, [esi+8]
    mov   dword ptr [esp+4], offset a1stElementDD ; "1st element: %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   esi, [esi] ; operator++: get ->next pointer
    mov   eax, [esi+0Ch]
    mov   [esp+0Ch], eax
    mov   eax, [esi+8]
    mov   dword ptr [esp+4], offset a2ndElementDD ; "2nd element: %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   esi, [esi] ; operator++: get ->next pointer
    mov   eax, [esi+0Ch]
    mov   [esp+0Ch], eax
    mov   eax, [esi+8]
    mov   dword ptr [esp+4], offset a3rdElementDD ; "3rd element: %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   eax, [esi] ; operator++: get ->next pointer
    mov   edx, [eax+0Ch]
    mov   [esp+0Ch], edx
    mov   eax, [eax+8]
    mov   dword ptr [esp+4], offset aElementAt_endD ; "element at .end(): %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   dword ptr [esp], offset aLetSCountFro_0 ; "* let's count from the end:" ↙
    ↘ call puts
    mov   eax, [esp+1Ch]
    mov   dword ptr [esp+4], offset aElementAt_endD ; "element at .end(): %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+0Ch], eax
    mov   eax, [esp+18h]
    mov   [esp+8], eax
    call  __printf_chk
    mov   esi, [esp+14h]
    mov   eax, [esi+0Ch]
    mov   [esp+0Ch], eax
    mov   eax, [esi+8]
    mov   dword ptr [esp+4], offset a3rdElementDD ; "3rd element: %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   esi, [esi+4] ; operator--: get ->prev pointer
    mov   eax, [esi+0Ch]
    mov   [esp+0Ch], eax
    mov   eax, [esi+8]
    mov   dword ptr [esp+4], offset a2ndElementDD ; "2nd element: %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   eax, [esi+4] ; operator--: get ->prev pointer
    mov   edx, [eax+0Ch]
    mov   [esp+0Ch], edx
    mov   eax, [eax+8]
    mov   dword ptr [esp+4], offset a1stElementDD ; "1st element: %d %d\n"
    mov   dword ptr [esp], 1
    mov   [esp+8], eax
    call  __printf_chk
    mov   dword ptr [esp], offset aRemovingLastEl ; "removing last element..."
    call  puts
    mov   esi, [esp+14h]
    mov   [esp], esi
    call  _ZNSt8__detail15_List_node_base9_M_unhookEv   ; std::__detail::_List_node_base:: ↙
    ↘ _M_unhook(void)
    mov   [esp], esi ; void *
    call  _ZdlPv ; operator delete(void *)
    mov   [esp], ebx
    call  _Z13dump_List_valPj ; dump_List_val(uint *)
    mov   [esp], ebx
    call  _ZNSt10_List_baseI1aSaIS0_EE8_M_clearEv ; std::_List_base<a,std::allocator<a>>:: ↙
    ↘ _M_clear(void)
    lea   esp, [ebp-8]
    xor   eax, eax
    pop   ebx
    pop   esi
    pop   ebp
    retn
main endp

运行上面这个由GCC编译的程序,可以得到如下数据:

指令清单51.30 整个输出

* empty list:
ptr=0x0028fe90 _Next=0x0028fe90 _Prev=0x0028fe90 x=3 y=0
* 3-elements list:
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
ptr=0x00034988 _Next=0x00034b40 _Prev=0x000349a0 x=1 y=2
ptr=0x00034b40 _Next=0x0028fe90 _Prev=0x00034988 x=5 y=6
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034b40 x=5 y=6
node at .begin:
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
node at .end:
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034b40 x=5 y=6
* let's count from the begin:
1st element: 3 4
2nd element: 1 2
3rd element: 5 6
element at .end(): 5 6
* let's count from the end:
element at .end(): 5 6
3rd element: 5 6
2nd element: 1 2
1st element: 3 4
removing last element...
ptr=0x000349a0 _Next=0x00034988 _Prev=0x0028fe90 x=3 y=4
ptr=0x00034988 _Next=0x0028fe90 _Prev=0x000349a0 x=1 y=2
ptr=0x0028fe90 _Next=0x000349a0 _Prev=0x00034988 x=5 y=6