9.1 顺序容器概述

容器类型

操作

vector

可变大小数组，支持快速随机访问，尾部插入/删除速度较快，其他尾置插入/删除速度可能很慢

deque

双端队列，支持快速随机访问，头尾插入/删除都很快

list

双向链表，支持双向顺序访问，任意位置插入/删除都很快

forward_list

单向链表，只支持单向顺序访问，任意位置插入/删除都很快

array

固定大小数组，支持快速随机访问，不能添加/删除元素

string

仅用于保存字符，支持快速随机访问，在尾部插入/删除速度较快

1. vector/deque/array/string都是顺序存储，而forward_list/list是链式存储，两类都是顺序容器

2. 新标准库容器的性能与同类手写数据结构的性能相比，至少持平或更好，所以建议C++程序最好使用C++标准库容器

3. 容器选择：

a) 无特殊理由，使用vector最优

b) 如果有很多小的元素，且空间额外开销很重要，则不要使用list或forward_list

c) 有随机访问容器元素需求，使用vector或deque

d) 有容器头尾插入/删除元素需求，使用deque

e) 如果只在读取输入时需要在中间位置插入，而后随机访问：

i. 可以先向vector尾部追加，再调用标准库的sort函数重排元素，从而避免在中间位置插入元素

ii. 如果必须在中间位置插入，可以在输入阶段使用list，输入完成后，将list中的内容拷贝至vector中

f) 不确定使用哪种容器时，可以先只使用vector和list的公共操作：使用迭代器，不使用下标，避免随机访问。然后在必要时选择vector或者list

9.2 容器库概览

类型别名

含义

iterator

此容器的迭代器类型

const_iterator

此容器的常量迭代器类型，即对该迭代器指向的元素只有读权限，没有写权限

size_type

无符号整型数，保存这种容器最大可能的dsize

difference_type

有符号整型，保存两个迭代器间的距离

value_type

容器中元素的类型

reference

容器元素的左值类型，等价于value_type&

const_reference

元素的常左值类型，等价于const value_type&

构造函数

含义

C c

默认构造函数，构造空容器

C c1(c2)

拷贝构造函数，容器类型与元素类型都必须相同

C c(b, e)

迭代器范围初始化，要求两种元素类型可以转换即可

C c{a, b, c…}

列表初始化c

C c(n)

接受大小参数的初始化方式，只有顺序容器能用，且string类型不能用

C c(n, v)

接受大小和每个元素值的初始化方式，只有顺序容器能用

赋值与swap

含义

c1 = c2

用容器c2里的值替换容器c1里的值，两种容器/元素类型必须相同

c1 = {a, b, c, …}

用列表中的元素替换c1中的元素，对于array不适用

a.swap(b)

把中元素交换为b中元素，如果b为空，则意味着将a置空

swap(a. b)

与a.swap(b)等价

大小

含义

c.size()

c中元素个数，对forward_list不适用

c.max_size()

c能承载的最大元素的个数

c.empty()

判断c是否为空

添加/移除元素(对于array无效)

含义

c.insert(args)

将args指代的元素拷贝到c中

c.emplace(inits)

用inits创建c中一个元素

c.erase(args)

将args指代的元素从c中移除

c.clear()

从c中移除所有元素，返回void

比较操作

含义

==, !=

比较两个容器对象是否相同，所有容器都支持

<, <=, >, >=

关系，对无序关联容器不适用

获取迭代器

含义

c.begin(), c.end()

指向容器首元素和尾后元素

c.cbegin(), c.cend()

返回容器的const_iterator

可逆容器的增量成员

含义

reverse_iterator

用来逆序访问容器元素的迭代器

const_reverse_iterator

用来逆序访问容器元素的只读迭代器

c.rbegin(), c.rend()

返回容器最后一个元素/首前元素的迭代器

c.crbegin(), c.crend()

返回const_reverse_iterator，即只读

9.2.1 迭代器

1. 一个迭代器范围通常由begin和end表示，begin指向首元素，end指向尾后元素（最后一个元素的后面），这种元素范围称为左闭合区间，用数学描述形式为[begin, end)

2. begin和end相当时，容器为空，所有迭代器都可以递增，但是forward_list的迭代器不可以递减

while (begin != end){    *begin = value;    ++begin;}

如果需要元素类型，可以使用容器的value_type。如果需要元素类型的引用，可以使用reference或const_reference

9.2.3 begin和end成员

1. begin和end有多个版本，带r的返回反向迭代器，带c的返回const迭代器；对非常量对象调用这些成员时，返回普通迭代器，对const对象调用时，返回const迭代器。但调用以c开头的版本与容器是否是常量无关，都返回const迭代器

2. 当程序不需要改写容器时，应使用cbegin和cend

9.2.4 容器定义和初始化

构造函数

含义

C c

默认构造函数，若C是std::array类型，则元素执行默认初始化

C c1(c2)

拷贝或赋值构造函数，容器类型与元素类型都必须相同，对于std::array类型，容器大小也必须相同

C c1 = c2

C c(b, e)

迭代器范围初始化，要求两种元素类型可以转换即可，对于std::array类型不适用

C c{a, b, c…}

列表初始化c

C seq(n)

接受大小参数的初始化方式，只有顺序容器能用，且string类型不能用

C seq(n, v)

接受大小和每个元素值的初始化方式，只有顺序容器能用

1. 将一个容器初始化为另一容器的拷贝时，两个容器的容器类型和元素类型都必须相同，传递迭代器参数来拷贝一个范围时，不要求容器类型相同，也不要求容器内元素类型完全相同，但是要能进行类型转换

std::list<std::string> fruits = {"apple", "pear", "orange"};std::vector<const char*> alpha = {"a", "an", "the"};std::list<std::string> list2(fruits); // okstd::deque<std::string> deq(fruits); // error，容器类型不匹配std::vector<std::string> words(alpha); // error，容器类型不匹配std::forward_list<std::string> words(alpha.begin(), alpha.end()); //ok，虽然容器类型不同，但是元素类型可以由const char *转换成std::string类型

2. C++11及以后可以用{ }列表初始化容器

3. 定义和使用std::array类型时，必须同时指定元素类型和容器大小，且初始值数量不能大于array大小，否则只初始化前面的元素

4. 注意，可以对std::array类型进行拷贝或赋值，但是内置数组类型不允许

9.2.5 赋值和swap

操作

含义

c1 = c2

用c2中的元素替换c1中的元素，c1 c2容器和元素类型必须相同

c = {a, b, c...}

用列表中的元素替换c中元素，对于array类型不适用

swap(c1, c2)

二者等价，交换c1和c2中的元素，如果想把c2的元素拷贝到c1，用swap的方式要比直接拷贝快的多

c1.swap(c2)

seq.assign(b, e)

用b e代表的区间内的元素初始化seq，注意，这里是左闭右开区间

seq.assign(li)

用list li中的元素初始化seq

seq.assign(n, v)

用n个相同的值v初始化seq

1. 赋值运算符两侧的运算对象必须类型相同。assign允许用类型不同但可以进行转换的类型赋值，或者用容器的子序列赋值

std::list<std::string> names;std::vector<const char*> cstyle;names = cstyle; // error: 容器类型不同names.assign(cstyle.cbegin(), cstyle.cend()); //ok，const char *可以转换成std::string

2. 传递给assign的迭代器不能指向调用assign的容器本身

3. swap交换两个相同类型容器的内容（容器大小可以不同），除array外，swap不对任何元素进行拷贝、删除或插入操作，只交换两个容器的内部数据结构，因此可以保证快速完成

4. 赋值运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap操作交换容器内容，不会导致迭代器、引用和指针失效（但array和string除外），即指针、引用和迭代器在swap操作后仍指向操作前的元素，但这些元素已经属于不同的容器了

5. array类型不支持assign，也不允许用花括号进行列表赋值（初始化除外），用花括号圈起来的列表为array对象赋值属于undefined behavior

6. C++11及以后的标准库同时提供了成员和非成员函数版本的swap。非成员版本的swap在泛型编程中非常重要，建议统一使用非成员版本的swap

9.2.6 容器大小操作

size成员返回容器中元素的数量；empty当size为0时返回true，否则返回false；max_size返回一个大于或等于该类型容器所能容纳的最大元素数量的值。forward_list支持max_size和empty，但不支持size

9.2.7 关系运算符

两个容器的比较实际上是元素的逐对比较，其工作方式与string的关系运算符类似：

1) 如果两个容器大小相同且所有元素对应相等，则这两个容器相等

2) 如果两个容器对应元素都相等，但长度不同，则较小容器小于较大容器

3) 如果两个元素对应元素也不想等，则比较结果取决于第一个不等元素的比较结果

9.3 顺序容器操作

注意：以下提到的所有添加和删除元素操作，希望读者都自动感知将array排除在外

9.3.1 添加元素

除array外，其他标准库容器都提供灵活的内存管理，能够动态添加或删除元素

操作

含义

c.push_back(t)

在容器尾部添加一个值为t的元素或用args构造的对象

c.emplace_back(args)

c.push_front(t)

在容器头部添加一个值为t的元素或用args构造的对象

c.emplace_front(args)

c.insert(p, t)

在迭代器p指定的位置前面添加一个值为t的元素或用args构造的对象

c.emplace(p, args)

c.insert(p, n, t)

在迭代器p指定的位置前面插入n个值为t的元素，返回指向插入的第一个元素的迭代器，如果n为0，返回p

c.insert(p, b, e)

在迭代器p指定的位置前面插入一串元素，这串元素由迭代器b和e指定，返回指向插入的第一个元素的迭代器，如果b e相等，则意味着没插入元素，返回p

c.insert(p, li)

在迭代器p指定的位置前面插入一个{ }圈起来的列表，返回指向插入的第一个元素的迭代器，如果列表为空，返回p

Note:向vector/string/deque中插入元素会使所有指向容器的迭代器/引用/指针失效

1. 特例汇总：

a) vector和string不支持push_front和emplace_front，对于不支持之类操作的容器，可以使用insert将元素插入开始位置；

b) forward_list不支持push_back和emplace_back

c) forward_list有特殊版本的insert和emplace操作

2. 向vecotr/deque/string的任意位置插入都可以，但是可能会很耗时，所以不推荐

3. C++11及以后新增了三个直接构造而不是拷贝元素的操作：emplace_front, emplace_back和emplace，其分别对应push_front, push_back和insert，当调用push或insert时，元素对象被拷贝到容器中，而调用emplace时，则是将参数传递给元素类型的构造函数，直接在容器的内存空间中构造元素

// 用带有三个参数的 Sales_data 的构造函数c.emplace_back("978-0590353403", 25, 15.99); //okc.push_back("978-0590353403", 25, 15.99); //error, push_back不支持直接构造对象c.push_back(Sales_data("978-0590353403", 25, 15.99)); //ok, 用三个参数构造临时对象

1. 每个顺序容器都有一个front成员，且除了forward_list，都有一个back成员，分别返回容器的首尾元素，调用这二者之前，要确保容器非空

操作

含义

c.back()

返回容器c的尾元素的引用，程序员保证容器非空

c.front()

返回容器c的首元素的引用，程序员保证容器非空

c[n]

反馈容器中第n（n从0开始）个元素的引用，如果n越界，属于undefined behavior

c.at(n)

与c[n]等价，但越界时会抛出out_of_range异常

Note: 保证下标有效是程序员的责任，也是好的习惯

1. 以上成员函数返回的都是引用（若容器尾const对象，则返回const引用）

2. string/vector/deque/array都提供了下标运算，建议使用at来访问

9.3.3 删除元素

操作

含义

c.pop_back()

移除c中最后一个元素，返回void，程序员必须保证容器非空

c.pop_front()

移除c中首元素，返回void，程序员必须保证容器非空

c.erase(p)

移除c中由迭代器p指向的元素，返回指向p后面元素的迭代器

c.erase(b, e)

移除由迭代器b e指向的范围内的元素，返回指向被删除的最后一个元素后面的那个元素的迭代器，不要忘了，b e仍然是左闭右开区间

c.clear()

清除c中所有元素，返回void

1. 删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。删除vector或string的元素后，指向删除点之后位置的迭代器、引用和指针也都会失效

2. vector和string类型不支持pop_front，forward_list类型不支持pop_back

9.3.4 特殊的forward_list操作

forward_list是单向链表，添加和删除操作都会同时改变前驱和后继节点，因此一般添加和删除操作对forward_list都不适用，其定义了自身的添加和删除操作

操作

含义

lst.before_begin()/lst.cbefore_begin()

指向首元素之前位置的迭代器

lst.insert_after(p, t)

在迭代器p指向的元素后面添加值为t的元素，返回指向插入的元素的迭代器

lst.insert_after(p, n, t)

在迭代器p指向的元素后面添加值n个为t的元素，返回指向插入的最后一个元素的迭代器

lst.insert_after(p, b, e)

在迭代器p指向的元素后面添加由迭代器b e指定的范围的元素，返回指向插入的最后一个元素的迭代器

lst.insert_after(p, li)

在迭代器p指向的元素后面添加由{ }圈起来的元素列表，返回指向插入的最后一个元素的迭代器

lst.emplace_after(p, args)

用args构造一个元素，并将其插到迭代器p指向的元素后面，返回指向新插入的元素的迭代器

lst.erase_after(p)

移除迭代器p指向的元素的下一个元素

lst.erase_after(b, e)

移除从迭代器b指向的下一个元素开始，一直到e指向的前一个元素，返回指向（最后一个被删除元素）的下一个元素的迭代器

1. 向forward_list尾插元素，必须通过遍历找到尾前元素，然后再在尾前元素上调用insert_after方法

9.3.5 改变容器大小

操作

含义

c.resize(n)

resize c，使c用有n个元素的空间，若n小于c的size，则多余元素会被忽略，若n大于c的size，则新加进来的元素会被默认初始化

c.resize(n, t)

resize c，使c拥有n个元素空间，且每个值都是t

1. 如果容器保存的是类类型元素，且resize向容器添加新元素，则必须提供初始值，或元素类型提供默认构造函数

9.3.6 容器操作可能使迭代器失效

1. 向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素，使用它们是一种严重错误

2. 向容器中添加元素后：

a) 如果容器是vector或string类型，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用都会失效

b) 如果容器是deque类型，添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置，则迭代器会失效，而指针和引用不会失效

c) 如果容器是list或forward_list类型，指向容器的迭代器、指针和引用仍然有效。

3. 从容器中删除元素后，指向被删除元素的迭代器、指针和引用失效：

a) 如果容器是list或forward_list类型，指向容器其他位置的迭代器、指针和引用仍然有效

b) 如果容器是deque类型，删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素，则尾后迭代器失效，其他迭代器、指针和引用不受影响。如果删除首元素，这些也不会受影响

c) 如果容器是vector或string类型，指向删除位置之前元素的迭代器、指针和引用仍然有效，但尾后迭代器总会失效

4. 必须保证在每次改变容器后都重定位（更新）迭代器

5. 不要保存end函数返回的迭代器

a) push/pop/emplace_back/emplace_front都会改变尾后迭代器

b) for循环判断条件中的end()每次迭代都会重新获取迭代器进行判断，因此速度也会略慢

9.4 vector对象如何增长

1. vector和string的实现通常会分配比新空间需求更大的内存空间，容器预留这些空间作为备用，可用来保存更多新元素

操作

含义

c.shrink_to_fit()

减小capacity()，使之等于size()，只有vector/string/deque能用

c.capacity()

不重新扩充内存空间的情况下c中能存储的最多元素的个数，只有vector/string能用

c.reserve(n)

分配至少n个元素的空间，只有vector/string能用

2. reserve函数告知容器应该准备保存多少元素，它并不改变容器中元素的数量，仅影响容器预先分配的内存空间大小，只有当需要的内存空间超过当前容量时，reserve才会真正改变容器容量，分配不小于需求大小的内存空间。当需求小于当前容量时，reserve什么都不做

3. c.shrink_to_fit()只是一个请求，实现时标准库可能会不执行

9.5 额外的string操作9.5.1 构造string的其他方法

操作

含义

string s(cp, n)

将cp指向的aray的前n个字符拷贝给s，此时cp为const char *类型

string s(s2, pos)

将string s2从pos开始的所有字符拷贝给s，由程序员保证pos有效

string s(s2, pos, len)

将string s2从pos开始，长度为len的子串拷贝给s，不管len多大，最多拷贝到s2的尾部

s.substr(pos, n)

返回s中从pos开始，长度为n的子串，pos默认从0开始，len默认为从pos开始到s结尾的长度，由程序员保证pos有效

9.5.2 改变string的其他方法

操作

含义

s.insert(pos, args)

在pos之前插入由args构造的字符序列，pos可以是一个索引值或迭代器，pos是索引值时，返回对s的引用；pos是迭代器时，返回指向插入的第一个字符的迭代器

s.erase(pos, len)

从pos开始移除长度为s的子串，如果不传len参数，则一直移除到末尾，返回对s的引用

s.assign(args)

用args替换s中的字符，返回对s的引用

s.append(args)

在s末尾添加args构造的字符，返回对s的引用

s.replace(range, args)

用args替换s中range代表的范围中的字符，range可以由index和长度组成，也可以由一对儿迭代器组成，返回对s的引用

replace中的args可以是如下中的一种

str

string对象str

str, pos, len

从string对象str的pos开始截取长度为len的字符

cp, len

从cp指向的const char *截取长度为len的字符

cp

由cp指向的以Null结尾的字符

n, c

n个相同的字符c

b, e

由b和e两个迭代器指向的范围

initializer list

由{ }圈起来的字符列表

注意：

1. insert的所有版本都是第一部分参数为pos，后面的参数为待插入字符

2. erase的所有版本都是第一部分参数是pos，pos代表起始位置

3. replace的所有版本的参数都是第一部分为要删除的范围，第二部分为要插入的字符

string s("C++ Primer"), s2 = s;s.insert(s.size(), " 4th Ed."); //实际上是在末尾插入s2.append(" 4th Ed."); // 在s2末尾追加s.erase(11, 3); // s == "C++ Primer  Ed."s.insert(11, "5th"); // s == "C++ Primer 5th Ed."s2.replace(11, 3, "5th"); //从位置11开始，移除3个字符，然后插入"5th"

1. string的搜索操作都返回一个string::size_type值，表示位置的下标。如果搜索失败，则返回一个名为string::npos的static成员。npos为const string::size_type类型，并初始化为-1

操作

含义

s.find(args)

找到s中args第一次出现的位置

s.rfind(args)

找到s中args最后一次出现的位置

s.find_first_of(args)

找到args中任意一个字符在s中第一次出现的位置

s.find_last_of(args)

找到args中任意一个字符在s中最后一次出现的位置

s.find_first_not_of(args)

找到s中（不存在于args中的字符）第一次出现的位置

s.find_last_not_of(args)

找到s中（不存在于args中的字符）最后一次出现的位置

args必须是以下其中一种

c, pos

从s中的pos位置开始查找字符c

s2, pos

从s中的pos位置开始查找字符串s2

cp, pos

从s中的pos位置开始查找cp指向的C-style字符串

cp, pos, n

从s中的pos位置开始查找cp指向的C-style字符串的前n个字符

9.5.4 compare函数

string类型提供了一组compare函数进行字符串比较操作，类似C标准库的strcmp函数。

compare函数的几种参数形式

操作

含义

s2

把s和s2比较

pos1, n1, s2

把s中从pos1开始的n1个字符和s2进行比较

pos1, n1, s2, pos2, n2

把s中从pos1开始的n1个字符和s2中从pos2开始的n2个字符进行比较

cp

把s和cp指向的字符数组相比较

pos1, n1, cp

把s中从pos1开始的n1个字符和cp指向的字符数组相比较

pos1, n1, cp, n2

把s中从pos1开始的n1个字符和cp指向的字符数组中前n2个字符相比较

9.5.5 数值转换

C++11增加了string和数值之间的转换函数

操作

含义

to_string(val)

将val表示的数值转换成字符串，val可以是任意数值类型

stoi(s, p, b)

将s转换为b进制的int/long/unsigned long/long long/unsigned long long类型，到p停止，即p指向第一个非数值型字符

stol(s, p, b)

stoul(s, p, b)

stoll(s, p, b)

stoull(s, p, b)

stof(s, p)

将s转换为float/double/long double类型，到p停止，即p指向s中第一个非数值型字符

stod(s, p)

stold(s, p)

进行数值转换时，string参数的第一个非空白字符必须是符号（+或-）或数字。它可以以0x或0X开头来表示十六进制数。对于转换目标是浮点值的函数，string参数也可以以小数点开头，并可以包含e或E来表示指数部分。

如果给定的string不能转换为一个数值，则转换函数会抛出invalid_argument异常。如果转换得到的数值无法用任何类型表示，则抛出out_of_range异常

9.6 容器适配器

1. 标准库定义了stack、queue和priority_queue三种容器适配器。容器适配器可以改变已有容器的工作机制

2. 所有容器适配器都支持的操作和类型

操作或类型

含义

size_type

能够承载当前类型的size的最大值

value_type

元素类型

container_type

当前适配器所依赖的容器的类型

A a

构造一个空适配器

A a(c)

用容器c的备份构造一个新的适配器

relational operator

每个适配器都支持所有关系运算符：==, !=, <, <=, >, >=

a.empty()

判断a是否为空

a.size()

a中元素个数

swap(a, b)

交换a和b的内容，ab必须具有相同类型，包括适配器依赖的容器类型也必须相同

3. 默认情况下，stack和queue是基于deque实现的，priority_queue是基于vector实现的。可以在创建适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型

4. 所有适配器都要求容器具有添加和删除元素的能力，因此适配器不能构造在array上。适配器还要求容器具有添加、删除和访问尾元素的能力，因此也不能用forward_list构造适配器

5. 栈适配器stack定义在头文件stack中，其支持的操作如下

操作

含义

s.pop()

从栈中移除栈顶元素

s.push(item)

以拷贝的方式构造一个新的栈顶元素

s.emplace(item)

以移动的方式构造一个新的栈顶元素

s.top()

返回栈顶元素

6. 队列适配器queue和priority_queue定义在头文件queue中，其支持的操作如下

操作

含义

q.pop()

从priority_queue中移除highest-priority元素

q.front()

返回q的首元素

q.back()

返回q的尾元素，只对queue有效

q.push(item)

在queue尾以拷贝的方式构建新元素

q.emplace(item)

在queue尾以移动的方式构建新元素

7. queue使用先进先出（first-in，first-out，FIFO）的存储和访问策略。进入队列的对象被放置到队尾，而离开队列的对象则从队首删除