本章和后面四章介绍C++标准库的容器和算法部分（通常称为STL）。本章和后面两张的重点是最常用、最有用的STL容器——向量的设计和实现。

17.1 引言

C++标准库中最有用的容器是vector。vector提供了给定类型的元素序列。标准库vector是一个方便、灵活、（时间和空间上）高效、静态类型安全的元素容器。

在本章和后面两章中，我们将展示如何用基本语言功能来构建vector，从而说明有用的概念和编程技术，并通过C++语言特性表达出来。我们在实现vector中遇到的语言功能和编程技术是通用并且被广泛使用的。

我们通过一系列逐渐复杂的vector实现来接近标准库vector。

17.2 vector基础

首先考虑vector的一个非常简单的用法：

vector<double> age(4); // a vector with 4 elements of type double
age[0]=0.33;
age[1]=22.0;
age[2]=27.2;
age[3]=54.2;

这段代码创建了一个有四个double类型元素的向量，并给四个元素分别赋值为0.33、22.0、27.2和54.2。这四个元素编号为0、1、2、3。C++标准库容器中的元素编号始终从0开始。 向量中的元素个数称为大小(size)，元素编号（索引）从0到size-1。可以用下图来表示age：

如何在计算机内存中实现这种“图形化设计”？显然，我们需要定义一个类vector，它需要一个存储大小的数据成员和一个存储元素的数据成员。但是如何表示一组数量可变的元素？我们需要第一个元素的内存地址。在C++中，可以存储地址的数据类型称为指针(pointer)。

于是，可以定义我们自己的第一个版本的vector类：

// a very simplified vector of doubles
class vector {int sz;        // the sizedouble* elem;  // pointer to the first element (of type double)
public:vector(int s); // constructor: allocate s doubles,// let elem point to them// store s in szint size() const { return sz; }  // the current size
};

在进行vector的设计之前，首先学习“指针”和与它紧密相关的“数组”的概念——这是C++“内存”概念的关键。

17.3 内存、地址和指针

计算机内存是一个字节序列，这些字节从0开始编号。用于指示内存位置的编号称为地址(address)。地址本质上就是一个整数。例如，可以将1 MB (= 2¹⁰ KB = 2²⁰ B)内存可视化为以下图形：

其中每个方格表示一个字节（内存单元），这些字节的编号（地址）依次为0, 1, 2, …, 2²⁰-1。

内存中的任何对象都有一个地址。例如：

int var = 17;

该语句为var分配了一块“int大小”（通常是4字节）的内存空间，并将值17放入这块内存。保存地址的对象称为指针(pointer)，在语法上T*是“指向T的指针”。例如：

int* ptr = &var;  // ptr holds the address of var

取地址(address of)运算符&用于获得对象的地址。在这里ptr是指向var的指针，其值是var的地址。假设var的地址是4096，则ptr的值为4096：

注：假设一个int占4字节，则var实际上占用了4096~4099连续的4个字节，对象的地址是首字节的地址。

解引用(dereference)运算符*用于访问指针指向的对象。例如：

cout << "pi==" << pi << "; contents of pi==" << *pi << "\\n";

可能的输出为

pi==0x649ff8b4; contents of pi==17

pi的值取决于编译器在内存中为变量var分配的地址（每次运行程序都会变化）。指针的值（地址）通常用十六进制表示。

解引用运算符也可以用于赋值运算符的左侧（pi是指针本身，*pi是指针指向的对象）：

*pi = 27;  // OK: you can assign 27 to the int pointed to by pi

注意，即使指针的值可以被打印为一个整数，但指针不是int，二者不能混淆：

int i = pi;  // error: can't assign an int* to an int
pi = 7;     // error: can't assign an int to an int*

不同类型的指针也不能混用。例如，指向char的指针不能指向int：

char* pc = pi;  // error: can't assign an int* to a char*
pi = pc;        // error: can't assign a char* to an int*

另见：《C程序设计语言》笔记 第5章 指针与数组

17.3.1 sizeof运算符

运算符sizeof用于获取对象或类型的大小（占用的内存字节数）：

void sizes(char ch, int i, int* pi) {cout << "the size of char is " << sizeof(char) << ' ' << sizeof(ch) << '\\n';cout << "the size of int is " << sizeof(int) << ' ' << sizeof(i) << '\\n';cout << "the size of int* is " << sizeof(int*) << ' ' << sizeof(pi) << '\\n';
}

sizeof可用于类型名或表达式。sizeof的结果是一个正整数，单位是sizeof(char)（定义为1）。

试一试

C++基本类型的长度如下表所示：

类型	长度	指针类型	指针长度
bool	1	bool*	4或8
char	1	char*	4或8
short	2	short*	4或8
int	2或4	int*	4或8
long	4或8	long*	4或8
long long	8	long long*	4或8
float	4	float*	4或8
double	8	double*	4或8

注：

• C++标准规定int类型的大小至少是2字节，在不同的机器上可能是2字节或4字节；类似地，long类型的长度可能是4字节或8字节。详见Fundamental types “Integer types” 一节。
• 标准库头文件<cstdint>定义了一组固定宽度整数类型（别名），例如int32_t、int64_t等。
• 对于指针类型，在32位系统上是4字节，在64位系统上是8字节（指针的大小只与内存地址空间的大小有关，与实际类型无关）。

一个vector占用多少内存？尝试

cout << "the size of vector<int>(10) is " << sizeof(vector<int>(10)) << '\\n';
cout << "the size of vector<int>(100) is " << sizeof(vector<int>(100)) << '\\n';
cout << "the size of vector<int>(1000) is " << sizeof(vector<int>(1000)) << '\\n';

输出为

the size of vector<int>(10) is 24
the size of vector<int>(100) is 24
the size of vector<int>(1000) is 24

看过本章和下一章后，这个解释将会变得很明显，但显然sizeof不计入向量元素。

注：vector对象本身只包含大小和指向元素的指针等成员，元素不属于vector对象的一部分，否则vector对象的大小将是不确定的。

17.4 自由存储和指针

C++程序的内存布局(memory layout)如下图所示：

整个内存空间被划分为四部分：

• 代码段(code segment)：也称为文本段(text segment)，包含由代码编译生成的机器指令。
• 数据段(data segment)：也称为静态存储(static storage)，包含全局变量和静态变量。
• 栈(stack)：也称为自动存储(automatic storage)，包含局部变量和函数参数。
• 堆(heap)：也称为自由存储(free storage)，可以通过new运算符动态分配的内存。

参考：Memory Layout of C Programs

注：栈内存中的变量离开作用域时自动释放内存，而堆内存必须手动释放，否则将导致内存泄露。

例如：

double* p = new double[4];  // allocate 4 doubles on the free store

该语句在自由存储中分配4个double大小（32字节）的内存空间，并返回指向首地址的指针（假设为850），如下图所示：

17.4.1 自由存储分配

new运算符从自由存储中分配内存，返回首字节的地址（指向它创建的对象或数组首元素的指针）。如果对象的类型是T，则返回的指针类型是T*。

new运算符可以为单个对象或数组分配内存。例如：

int* pi = new int            // allocate one int
int* qi = new int[4];        // allocate 4 ints (an array of 4 ints)double* pd = new double;     // allocate one double
double* qd = new double[n];  // allocate n doubles (an array of n doubles)

注意分配的元素个数可以是变量，这允许我们在运行时指定分配多少个对象。

17.4.2 通过指针访问

除了在指针上使用解引用运算符*，还可以使用下标运算符[]，这两个运算符既可用于读也可用于写。例如：

double* p = new double[4];  // allocate 4 doubles on the free store
double x = *p;              // read the (first) object pointed to by p
double y = p[2];            // read the 3rd object pointed to by p*p = 7.7;                   // write to the (first) object pointed to by p
p[2] = 9.9;                 // write to the 3rd object pointed to by p

当用于指针时，[]运算符将内存视为一系列对象（类型由指针声明指定）。p[i]等价于*(p+i)。

注：只有当指针指向数组中的元素时，使用[]运算符才有意义。

17.4.3 范围

指针的主要问题是指针并不“知道”它指向多少个元素（甚至不知道它指向单个对象还是数组中的某个元素）。例如：

double* p = new double;        // allocate a double
double* q = new double[1000];  // allocate 1000 doubles
q[700] = 7.7;       // fine
q = p;              // let q point to the same as p
double d = q[700];  // out-of-range access!

其中第二个q[700]（也就是p[700]）是越界(out-of-range)访问，p[700]这个内存位置可能是其他对象的一部分。越界访问是一个典型的灾难性错误：“灾难性”表现为“程序神秘地崩溃”或者“程序给出错误的输出”。越界访问是特别令人讨厌的。越界读取会得到一个“随机”值，这取决于某些完全无关的对象；而越界写入可能会给某些对象意外的错误值。

我们必须保证这种越界访问不会发生。 我们使用vector而不是直接使用new分配的内存的原因之一是vector知道它的大小，因此可以很容易地避免越界访问。

17.4.4 初始化

我们希望确保指针及其指向的对象都是被初始化的。考虑：

double* p0;                    // uninitialized: likely trouble
double* p1 = new double;       // get (allocate) an uninitialized double
double* p2 = new double(5.5);  // get a double initialized to 5.5
double* p3 = new double[5];    // get (allocate) 5 uninitialized doubles

未初始化的指针是野指针(wild pointer)，例如上面的p0。由于其值是随机的，使用未初始化的指针必定导致越界访问。

对于内置类型，new分配的内存是未初始化的，例如p1。可以使用()或{}来初始化，例如p2。

new创建的数组默认也是未初始化的。可以指定初始化列表（此时可以省略元素个数）：

double* p4 = new double[5]{0, 1, 2, 3, 4};
double* p5 = new double[]{0, 1, 2, 3, 4};

注：如果指定了元素个数，但初始化列表中初始值个数少于元素个数，则剩余元素将被默认初始化。

对于自定义类型可以更好地控制初始化。如果类型X有默认构造函数，则未指定初始值时将使用默认构造：

X* px1 = new X;      // one default-initialized X
X* px2 = new X[17];  // 17 default-initialized Xs

如果类型Y有构造函数，但没有默认构造函数，则必须显式地初始化：

Y* py1 = new Y;      // error: no default constructor
Y* py2 = new Y(13);  // OK: initialized to Y(13)
Y* py3 = new Y[17];  // error: no default constructor
Y* py4 = new Y[17]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};

当数组只有几个元素时，初始值列表将会很方便。

17.4.5 空指针

如果没有可用的值来初始化指针，则使用空指针(null pointer)，nullptr：

double* p = nullptr;  // the null pointer

空指针的值为0，通常用于测试一个指针是否有效（例如是否指向某个对象），例如if (p != nullptr)，等价于if (p)。注意，对于未初始化的指针，这个测试是没有意义的。

注：

• 空指针可用于函数返回值表示异常情况，例如“未找到”或“发生了错误”。
• nullptr是C++11引入的关键字，可以隐式转换为任意类型的指针。旧的代码使用0或NULL表示空指针。

17.4.6 自由存储释放

由于一台计算机的内存是有限的，因此在使用结束后应当将内存释放回自由存储，从而自由存储可以将这些内存重新用于新的分配。对于大型程序和长时间运行的程序（例如操作系统、嵌入式系统）来说，这种释放内存并重新使用是很重要的。

如果使用new分配的内存没有被释放，并且离开了保存其地址的指针的作用域，则会发生内存泄露(memory leak)（因为之后再也没有机会去释放）。例如：

double* calc(int res_size, int max) {double* p = new double[max];  // leaks memorydouble* res = new double[res_size];// use p to calculate results to be put in resreturn res;
}double* r = calc(100,1000);

每次调用calc()会“泄露”分配给p的double数组所占用的内存（如果调用者不释放r，同样会造成内存泄露）。

将内存释放回自由存储的运算符是delete，用于new返回的指针。有两种形式的delete：

• delete p释放由new分配的单个对象的内存。
• delete[] p释放由new分配的数组的内存。

上面的例子修正后变为

double* calc(int res_size, int max) {// the caller is responsible for the memory allocated for resdouble* p = new double[max];double* res = new double[res_size];// use p to calculate results to be put in resdelete[] p;  // we don't need that memory anymore: free itreturn res;
}double* r = calc(100,1000);
// use r
delete[] r;  // we don't need that memory anymore: free it

这个例子说明了使用自由存储的一个主要原因：我们可以在一个函数中创建对象，并将其返回给调用者（来避免值拷贝）。

注：

• 如果函数返回了由new返回的指针，则调用者负责释放该内存，否则会发生内存泄露。
• C++11引入了智能指针shared_ptr和unique_ptr，能够自动释放内存，定义在头文件<memory>中。
• C++17引入了拷贝消除(copy elision)/返回值优化(return value optimization, RVO)特性：在特定情况下，即使函数返回值是值类型也不会发生值拷贝。

删除一个对象两次是一个严重的错误。 例如：

int* p = new int(5);
delete p;  // fine: p points to an object created by new
// ... no use of p here ...
delete p;  // error: p points to memory owned by the free-store manager

第二次delete p时，你已不再拥有p指向的内存，自由存储管理器可能已经将其回收并分配给其他对象，删除该对象（由程序的其他部分拥有）会引起程序错误。

删除空指针不会做任何事，因此删除空指针是无害的。

实际上，编译器可以知道我们什么时候不再需要一块内存，并在没有人为干预的情况下回收它。这叫做自动垃圾收集(garbage collection, GC)。然而自动垃圾收集并不是无代价的，也不是对所有应用都是理想的。在C++中，（通过new使用自由存储时）程序员必须自己处理“垃圾”。

注：

• Java、Python等语言内置了垃圾收集器，能够自动管理内存。
• 在C++中可以通过标准库容器、智能指针等工具来简化垃圾收集工作。

17.5 析构函数

现在可以用自由存储分配实现17.2节中vector的构造函数：

vector(int s) :sz(s), elem(new double[s]{0}) {}

构造函数分配了s个double，并全部初始化为0。

然而，这个vector会泄露内存，因为在构造函数中使用new分配的内存没有被释放。考虑：

void f(int n) {vector v(n);  // allocate n doubles// ... use v ...
}

当函数f()返回时，v在自由存储中分配的内存没有被释放。我们可以为vector定义一个clean_up()并调用它：

void f2(int n) {vector v(n);   // allocate n doubles// ... use v ...v.clean_up();  // clean_up() deletes elem
}

这是可以的。但是，关于自由存储的一个最常见的问题是人们忘记delete。clean_up()也有同样的问题：人们可能忘记调用它。更好的做法是使编译器知道一个与构造函数具有相反功能的函数——析构函数(destructor)（如9.4.2节所述，使用构造函数来避免忘记调用初始化函数）。当一个类的对象被创建时构造函数将被隐式调用，同样，当一个对象离开作用域时析构函数将被隐式调用。构造函数确保对象被正确地创建和初始化，相反，析构函数确保对象被正确地销毁（释放了该释放的“资源”）。

类T的析构函数名为~T。例如：

// destructor: free memory
~vector() {delete[] elem;
}

这样就可以写出：

void f3(int n) {double* p = new double[n];  // allocate n doublesvector v(n);  // the vector allocates n doubles// ... use p and v ...delete[ ] p;  // deallocate p's doubles
}  // vector automatically cleans up after v

显然，delete[]相当繁琐并且容易出错。有了vector，就没有必要再使用new分配内存，并记得用delete释放。vector已经做了，而且做得更好。

注：对于new创建的单个对象，可以用智能指针来代替。

每个拥有资源（自由存储、文件、缓冲区、线程、锁等）的类都需要析构函数，在构造函数中获取资源，在析构函数中释放资源。vector的构造函数/析构函数处理自由存储内存就是一个典型的例子。

17.5.1 生成的析构函数 析构顺序

如果一个类没有定义析构函数，则编译器会自动生成一个析构函数（相当于函数体为空）。

无论是自定义的还是生成的析构函数，在执行完函数体之后，编译器还会调用数据成员的析构函数和基类的析构函数。“析构函数应该被调用”这一保证就是这样实现的。

注：这一规则保证了析构顺序和构造顺序是相反的

• 构造顺序：基类 → 成员（按照声明顺序） → 自身
• 析构顺序：自身 → 成员（按照声明相反顺序） → 基类

例如：

struct Customer {string name;vector<string> addresses;
};void some_fct() {Customer fred;// initialize fred// use fred
}

当退出some_fct()后，fred将被销毁，name和addresses的析构函数将被调用。

所有的规则可以总结为：当对象被销毁时（离开作用域、delete等），析构函数被调用。

17.5.2 析构函数和自由存储 虚析构函数

考虑一个自由存储和类层次结构结合使用的例子：

Shape* fct() {Text tt(Point(200, 200), "Annemarie");// ...Shape* p = new Text(Point(100, 100), "Nicholas");return p;
}void f() {Shape* q = fct();// ...delete q;
}

在函数fct()中，Text对象tt在离开fct()时被销毁，tt及其成员和基类Shape的析构函数将被调用。但是，对于从fct()返回的由new创建的Text对象，调用函数f()不知道q指向一个Text，那么delete q是如何调用Text的析构函数的？

在14.2.1节，我们略过了一个事实：Shape有一个虚析构函数，这正是问题的关键。当执行delete q时，delete会查看q的类型以确定是否需要调用析构函数，如果是则调用。因此delete q调用Shape的析构函数~Shape()。而~Shape()是虚函数，根据虚函数调用机制，实际会调用派生类的析构函数，在这里是~Text()（之后又自动调用了~Shape()）。如果~Shape()不是虚函数，则~Text()将不会被调用，Text的string成员将不会被正确销毁。

经验法则：如果一个类作为基类，则需要虚析构函数。 否则当通过基类指针delete一个由new创建的派生类对象时，派生类的析构函数不会被调用，从而派生类对象不会被正确销毁。

试一试

17.6 访问元素

为了读写向量元素，我们提供简单的get()和set()成员函数：

double get(int n) { return elem[n]; }       // access: read
void set(int n, double v) { elem[n] = v; }  // access: write

这里在elem指针上使用[]运算符访问元素，如17.4.2节所述。

现在可以这样使用vector：

vector v(5);
for (int i = 0; i < v.size(); ++i) {v.set(i, 1.1*i);cout << "v[" << i << "]==" << v.get(i) << '\\n';
}

与常用的下标符号相比，使用get()和set()的代码很丑陋。18.4节将为vector定义[]运算符。

当前版本的vector：简单向量v1

17.7 指向类对象的指针

“指针”的概念是通用的，可以指向内存中的任何对象。例如，可以使用vector的指针：

vector* f(int s) {vector* p = new vector(s);  // allocate a vector on free store// fill *preturn p;
}void ff() {vector* q = f(4);// use *qdelete q;  // free vector on free store
}

请记住：位于构造函数之外的new会带来忘记delete它所创建的对象的机会。除非你有一个好的删除对象的策略（例如Vector_ref），否则尽量将new放在构造函数中、delete放在析构函数中。

给定一个对象名，可以使用.运算符访问成员：

vector v(4);
int x = v.size();
double d = v.get(3);

类似地，给定一个对象指针，可以使用->运算符访问成员：

vector* p = new vector(4);
int x = p–>size();
double d = p–>get(3);

p->m等价于(*p).m。

.和->通常称为成员访问运算符(member access operators)。

17.8 类型混用：void*和类型转换

偶尔，我们不得不放弃类型系统的保护（例如，与不知道C++类型的其他语言交互，与没有按照静态类型安全设计的旧代码交互）。在这种情况下，我们需要两样东西：

• 一种指针，指向不知道保存的是何种对象的内存
• 一种操作，告诉编译器这种指针指向的是哪种类型（未经证实）

类型void*的含义是“指向编译器不知道类型的内存的指针”。当我们想在代码之间传递不知道实际类型的地址时，就需要使用void*。例如回调函数的“地址”参数（16.3.1节），以及最底层的内存分配器（例如new运算符的实现）。

void用于表示“没有返回值”，不存在void类型的对象，因此void*指针不能被解引用。任何类型的指针都可以赋值给void*指针，反之则必须用static_cast进行显式类型转换(explicit type conversion)或者称为转换(cast)。例如：

void* pv = new int;  // OK: int* converts to void*
void* pv2 = pv;      // copying is OK (copying is what void*s are for)
double* pd = pv;     // error: cannot convert void* to double*
*pv = 7;             // error: cannot dereference a void* (we don't know what type of object it points to)
pv[2] = 9;           // error: cannot subscript a void*
int* pi = static_cast<int*>(pv);  // OK: explicit conversion

C++提供的显式类型转换运算符：

• static_cast：将一种类型转换为另一种相关的类型（例如int和double、void*和double*）。
• dynamic_cast：将基类指针/引用转换为派生类指针/引用（反之不需要转换）。如果转换失败，对于指针类型返回空指针，对于引用类型抛出std::bad_cast异常。
• const_cast：移除const属性。
• reinterpret_cast：在两个不相关的类型之间转换，例如int和double*。

只有在完全有必要时才使用static_cast，而const_cast和reinterpret_cast是两个更危险的转换。不要期望使用reinterpret_cast的代码可以移至。

17.9 指针和引用

引用可以看作是一种自动解引用的、不可变的指针，或者是对象的别名。指针和引用的区别：

• 指针可以不初始化（野指针），也可以不指向任何对象（空指针），而引用必须初始化。
• 给指针赋值会改变指针本身的值，使其指向其他对象；而引用在初始化之后不能引用其他对象，给引用赋值改变的是被引用的对象的值。
• 指针通过new或&获取，使用*或[]解引用；引用通过对象名获取，不需要解引用。

注：

• 指针的const属性分为指针本身和被指向的对象：

类型	p可变	*p可变
T*	是	是
const T* （等价于T const*）	是	否
T* const	否	是
const T* const	否	否

• 在const属性方面，T&相当于T* const，const T&相当于const T* const。

例如：

int x = 10;
int* p = &x;    // you need & to get a pointer
*p = 7;         // use * to assign to x through p
int x2 = *p;    // read x through p
int* p2 = &x2;  // get a pointer to another int
p2 = p;         // p2 and p both point to x
p = &x2;        // make p point to another object

对应的引用的例子如下：

int y = 10;
int& r = y;    // the & is in the type, not in the initializer
r = 7;         // assign to y through r (no * needed)
int y2 = r;    // read y through r (no * needed)
int& r2 = y2;  // get a reference to another int
r2 = r;        // the value of y is assigned to y2
r = &y2;       // error: you can't change the value of a reference// (no assignment of an int* to an int&)

注意：

• r2 = r相当于*p2 = *p，而不是p2 = p。
• r = &y2是类型错误，不存在给引用本身赋值使其引用另一个对象的操作。

指针和引用都是使用内存地址实现的，只是在用法上稍有不同。

17.9.1 指针参数和引用参数

当你希望将一个变量的值改为由函数计算的结果时，有三种选择：返回值、指针参数和引用参数。例如：

int incr_v(int x) { return x+1; }  // compute a new value and return it
void incr_p(int* p) { ++*p; }      // pass a pointer (dereference it and increment the result)
void incr_r(int& r) { ++r; }       // pass a reference

每种方法各有利弊，需要根据具体的函数及其用法决定。使用指针参数会提醒程序员参数可能被修改，但需要判断空指针；相反，引用参数“看起来很无辜”（看不出参数会被修改），但可以确保引用了一个对象。

因此，答案是“取决于函数的性质”：

• 对于小的对象，使用传值。
• 对于“没有对象”（用空指针表示）是合法参数的函数，使用指针参数（记得判断空指针）。
• 否则，使用引用参数。

另见8.5.6节。

17.9.2 指针、引用和继承

如14.4节所述，派生类可以被用在需要其公有基类的地方（接口继承）。对于指针或引用，这一思想表达为：如果B是D的公有基类，则D*可以被隐式转换为B*，D&可以被隐式转换为B&。例如：

void rotate(Shape* s, int n);  // rotate *s n degreesShape* p = new Circle(Point(100, 100), 40);
Circle c(Point(200, 200), 50);
rotate(p, 35);
rotate(&c, 45);

对于引用是类似的：

void rotate(Shape& s, int n);  // rotate s n degreesShape& r = c;
rotate(r, 55);
rotate(*p, 65);
rotate(c, 75);

这对于大多数面向对象编程技术来说至关重要。

17.9.3 示例：链表

17.9.4 链表操作

17.9.5 链表的使用

17.10 this指针

17.10.1 更多用法