顺序容器

容器是C++标准库中用于存储和管理数据集合的重要工具。顺序容器允许程序员控制元素的存储和访问顺序，这个顺序完全取决于元素被放入容器的位置，而不是元素本身的值。

顺序容器类型概览

C++提供了多种顺序容器，每种都有其独特的性能特点。这些容器在以下方面存在差异：

• 添加或删除元素的成本
• 非顺序访问元素的成本

主要顺序容器类型

除了array这种固定大小的容器外，其他容器都提供了高效、灵活的内存管理。我们可以添加和删除元素，使容器的大小动态增长或缩小。容器存储元素的策略对这些操作的效率有着根本性的影响。

string和vector将元素存储在连续的内存中。由于元素是连续的，通过索引计算元素地址非常快。 但是，在这些容器的中间位置添加或删除元素需要时间：插入或删除位置之后的所有元素都必须移动以保持连续性。 此外，添加元素有时需要分配额外的存储空间，在这种情况下，每个元素都必须移动到新的存储位置。

list和forward_list容器设计用于在任何位置快速添加或删除元素。 作为交换，这些类型不支持元素的随机访问：我们只能通过遍历容器来访问元素。 此外，与vector、deque和array相比，这些容器的内存开销通常很大。

deque是一个更复杂的数据结构。像string和vector一样，deque支持快速随机访问。与string和vector类似，在deque中间添加或删除元素是一个（潜在的）昂贵的操作。 但是，在deque两端添加或删除元素是一个快速操作，与在list或forward_list中添加元素相当。

forward_list和array类型是由新标准添加的。array是内置数组的更安全、更易用的替代品。 像内置数组一样，库数组具有固定大小。因此，array不支持添加和删除元素或调整容器大小的操作。 forward_list旨在与最佳的手写单向链表相媲美。 因此，forward_list没有size操作，因为存储或计算其大小与手写链表相比会产生开销。对于其他容器，size保证是一个快速的、常数时间的操作。

现代C++程序应该使用库容器而不是更原始的结构如数组，因为库容器几乎肯定比最精心制作的替代方案表现更好。

如何选择顺序容器

通常，除非有充分的理由选择其他容器，否则最好使用vector。

选择顺序容器时，通常应优先使用vector，因为它是最通用且高效的容器。 只有在有特殊需求时才考虑其他容器：如果需要频繁在容器中间插入或删除元素，可以选择list或forward_list，但要注意它们的空间开销较大，不适合存储大量小元素； 如果需要高效的随机访问，则应选择vector或deque；若程序需要在容器两端频繁插入或删除元素而不涉及中间操作，deque是更好的选择。

对于输入阶段需要在中间插入元素且后续需要随机访问的场景，通常建议先将数据追加到vector，输入结束后再排序；如果确实需要在输入时中间插入，可以先用list存储，输入完成后再拷贝到vector中。 总之，应根据访问和修改元素的主要方式、空间效率和操作效率综合考虑容器类型。

如果程序既需要随机访问，又需要在容器中间插入和删除元素，这个决定将取决于在list或forward_list中访问元素的相对成本与在vector或deque中插入或删除元素的成本。 通常，应用程序的主要操作（是更多访问还是更多插入或删除）将决定容器类型的选择。在这种情况下，可能需要使用两种容器对应用程序进行性能测试。

如果不确定使用哪种容器，编写代码时只使用vector和list都支持的操作：使用迭代器而不是下标，避免随机访问元素。这样，在需要时很容易使用vector或list。

容器库

C++容器库的操作形成了一个层次结构：某些操作是所有容器类型都提供的通用操作，其他操作则是特定类型容器（如顺序容器、关联容器或无序关联容器）所特有的，还有一些操作只适用于容器的较小子集。

通常，每个容器都在与类型同名的头文件中定义。例如，deque在deque头文件中，list在list头文件中，以此类推。

容器是类模板，就像vector一样，我们必须提供额外的信息来生成特定的容器类型。对于大多数容器，我们必须提供的信息是元素类型：

|
list<Book>          // 存储Book对象的list
deque<int>          // 存储整数的deque

几乎任何类型都可以用作顺序容器的元素类型。特别是，我们可以定义一个元素类型本身就是另一个容器的容器。 我们定义这样的容器与定义任何其他容器类型完全相同：在尖括号内指定元素类型（在这种情况下是容器类型）：

|
vector<vector<int>> matrix;  // 二维整数矩阵

这里matrix是一个元素为整数vector的vector，可以用来表示二维矩阵。 较老的编译器可能需要在尖括号之间加空格，例如vector<vector<int> >。

虽然我们可以在容器中存储几乎任何类型，但某些容器操作对元素类型有自己的要求。 我们可以为不支持特定操作要求的类型定义容器，但只有当元素类型满足该操作的要求时，我们才能使用该操作。

例如，接受大小参数的顺序容器构造函数使用元素类型的默认构造函数。某些类没有默认构造函数。我们可以定义包含此类对象的容器，但不能仅使用元素计数来构造此类容器：

|
// 假设ComplexNumber是没有默认构造函数的类型
vector<ComplexNumber> v1(5, ComplexNumber(1, 2));  // 正确：提供了元素初始化器
vector<ComplexNumber> v2(5);                       // 错误：必须提供元素初始化器

在描述容器操作时，我们会注意每个容器操作对元素类型施加的额外约束（如果有的话）。

容器操作概览

迭代器

与容器类似，迭代器也具有统一的接口：如果一个迭代器提供了某个操作，那么所有提供该操作的迭代器都以相同的方式支持这个操作。 例如，所有标准容器类型的迭代器都允许我们访问容器中的元素，它们都通过提供解引用运算符来实现这一点。同样，库容器的迭代器都定义了递增运算符来从一个元素移动到下一个元素。

迭代器范围的概念是标准库的基础。迭代器范围由一对迭代器表示，每个迭代器都引用同一容器中的元素，或者引用最后一个元素之后的位置。这两个迭代器通常称为begin和end，或者（有些误导性地）称为first和last，它们标记了容器中元素的范围。 last这个名称虽然常用，但有些误导性，因为第二个迭代器从不引用范围的最后一个元素。相反，它引用的是最后一个元素之后的一个位置。范围中的元素包括first引用的元素以及从first开始到但不包括last的每个元素。

这个元素范围称为左闭区间。这种范围的标准数学符号是：

|
[ begin, end )

表示范围从begin开始，到end结束但不包括end。迭代器begin和end必须引用同一个容器。迭代器end可以等于begin，但不能引用begin引用的元素之前的元素。

库使用左闭区间[begin, end)是因为这样的范围具有三个便利的属性。假设begin和end表示有效的迭代器范围，那么：

• 如果begin等于end，则范围为空
• 如果begin不等于end，则范围中至少有一个元素，且begin引用该范围中的第一个元素
• 我们可以递增begin若干次直到begin == end

这些属性意味着我们可以安全地编写如下循环来处理元素范围：

|
while (begin != end) {
    *begin = value;  // 正确：范围不为空，所以begin引用一个元素
    ++begin;         // 推进迭代器到下一个元素
}

给定begin和end形成有效的迭代器范围，我们知道如果begin == end，则范围为空。在这种情况下，我们退出循环。 如果范围非空，我们知道begin引用这个非空范围中的一个元素。因此，在while循环体内，我们知道解引用begin是安全的， 因为begin必须引用一个元素。最后，因为循环体递增begin，我们也知道循环最终会终止。

begin和end成员

begin和end操作产生引用容器中第一个元素和最后一个元素之后位置的迭代器。这些迭代器最常用于形成包含容器中所有元素的迭代器范围。

begin和end有几个版本：

• 带有r的版本返回反向迭代器
• 以c开头的版本返回相关迭代器的const版本

|
list<string> authors = {"李白", "杜甫", "白居易"};
auto it1 = authors.begin();   // list<string>::iterator
auto it2 = authors.rbegin();  // list<string>::reverse_iterator
auto it3 = authors.cbegin();  // list<string>::const_iterator
auto it4 = authors.crbegin(); // list<string>::const_reverse_iterator

不以c开头的函数是重载的。也就是说，实际上有两个名为begin的成员。一个是const成员，返回容器的const_iterator类型。 另一个是非const的，返回容器的iterator类型。rbegin、end和rend也是如此。 当我们在非const对象上调用这些成员之一时，我们得到返回iterator的版本。只 有当我们对这些函数调用const对象时，我们才得到迭代器的const版本。与指向const的指针和引用一样，我们可以将普通迭代器转换为相应的const_iterator，但不能反向转换。

c版本是由新标准引入的，以支持将auto与begin和end函数一起使用。在过去，我们别无选择，只能说明我们想要哪种类型的迭代器：

|
// 显式指定类型
list<string>::iterator it5 = authors.begin();

顺序容器的操作

顺序容器与关联容器在元素组织方式上存在本质差异，这种差异直接影响着元素的存储、访问、添加和删除方式。 在掌握了所有容器都支持的通用操作之后，我们需要深入学习顺序容器特有的操作，这些操作为我们提供了更加灵活和高效的数据管理能力。

添加元素到顺序容器

除了固定大小的array之外，标准库提供的所有容器都支持灵活的内存管理机制。我们可以在运行时动态地添加或删除元素，从而改变容器的大小。这种动态特性是现代C++编程的重要优势。

在使用这些添加元素的操作时，我们必须理解不同容器采用的分配策略对性能的影响。向vector或string的中间位置添加元素，或者向deque的非两端位置添加元素，都需要移动其他元素。 特别是向vector或string添加元素时，可能会导致整个容器的重新分配，这涉及到分配新内存并将现有元素移动到新位置的过程。

使用push_back在容器末尾添加元素

push_back操作是我们最常用的元素添加方法，它将新元素追加到容器的末尾。除了array和forward_list之外，所有顺序容器都支持这个操作。

让我们通过一个读取学生姓名的例子来理解push_back的使用：

|
// 从标准输入读取学生姓名，添加到容器末尾
vector<string> students;
string name;
while (cin >> name) {
    students.push_back(name);
}

这段代码每次读取一个学生姓名，然后将其添加到students容器的末尾。push_back操作会在容器末尾创建一个新元素，将容器大小增加1，新元素的值是name的副本。

由于string本质上是字符的容器，我们也可以使用push_back向字符串末尾添加字符：

|
void addSuffix(size_t count, string &filename) {
    if (count > 1) {
        filename.push_back('_');  // 等同于 filename += '_'
        filename.append(to_string(count));
    }
}

使用push_front在容器前端添加元素

除了push_back之外，list、forward_list和deque容器还支持push_front操作，它在容器的前端插入新元素。让我们看一个创建任务队列的例子：

|
deque<string> taskQueue;
// 添加高优先级任务到队列前端
for (int priority = 1; priority <= 3; ++priority) {
    string task = "优先级" + to_string(priority) + "任务";
    taskQueue.push_front(task);
}

执行这段代码后，任务队列的顺序将是："优先级3任务"、"优先级2任务"、"优先级1任务"。这是因为每次插入都是在当前首元素之前进行的，所以最后插入的元素成为了新的首元素。

需要注意的是，虽然deque和vector都提供快速随机访问，但vector不支持push_front操作。deque能够保证在容器两端进行常数时间的插入和删除操作，而在其他位置的插入可能相对昂贵。

在指定位置插入元素

insert系列操作为我们提供了在容器任意位置插入元素的能力。所有insert函数都以迭代器作为第一个参数，该迭代器指示插入位置。元素将被插入到该迭代器指向位置的前面。

考虑一个管理课程列表的场景：

|
vector<string> courses = {"数学", "物理", "化学"};
auto pos = courses.begin() + 1;  // 指向"物理"
courses.insert(pos, "计算机科学");  // 在"物理"前插入"计算机科学"
// 现在courses为：{"数学", "计算机科学", "物理", "化学"}

即使某些容器不支持push_front操作，我们也可以通过insert在容器开头插入元素：

|
vector<string> subjects;
// vector没有push_front，但可以在begin()位置插入
subjects.insert(subjects.begin(), "语文");

虽然在vector、deque或string的任意位置插入都是合法的，但这可能是一个昂贵的操作，特别是对于vector而言。

插入多个元素

insert操作的强大之处在于它能够一次插入多个元素。我们可以插入指定数量的相同元素：

|
vector<string> schedule;
// 在末尾插入5个"空闲时间"
schedule.insert(schedule.end(), 5, "空闲时间");

我们也可以插入另一个容器中的元素范围：

|
vector<string> requiredCourses = {"高等数学", "线性代数", "概率论", "统计学"};
vector<string> electiveCourses = {"机器学习", "数据结构"};
// 将必修课的后两门插入到选修课开头
electiveCourses.insert(electiveCourses.begin(), 
                      requiredCourses.end() - 2, requiredCourses.end());

我们还可以使用初始化列表插入多个元素：

|
vector<string> weekdays = {"周一", "周二"};
weekdays.insert(weekdays.end(), {"周三", "周四", "周五"});

利用insert的返回值

在新标准中，insert操作会返回一个指向第一个新插入元素的迭代器。这个特性让我们能够连续在同一位置插入多个元素：

|
list<string> todoList;
auto insertPos = todoList.begin();
string task;
while (cin >> task) {
    insertPos = todoList.insert(insertPos, task);  // 相当于push_front
}

这个循环的效果等同于反复调用push_front。每次插入后，insertPos都指向新插入的元素，而新元素总是在列表的最前面。

emplace操作：就地构造元素

C++11引入了emplace_front、emplace和emplace_back三个新操作，它们的优势在于直接在容器管理的内存空间中构造元素，而不是先构造临时对象再复制。

假设我们有一个存储学生信息的容器，Student类有一个接受姓名和年龄的构造函数：

|
class Student {
public:
    Student(const string& name, int age) : name_(name), age_(age) {}
    // 其他成员...
private:
    string name_;
    int age_;
};
 
vector<Student> students;
// 使用emplace_back直接构造Student对象
students.emplace_back("张三", 20);
 
// 错误：push_back不能直接接受构造函数参数

emplace操作的参数必须与元素类型的某个构造函数参数匹配。它们直接在容器中构造元素，避免了不必要的复制或移动操作。

访问容器中的元素

顺序容器提供了多种访问元素的方法。需要强调的是，如果容器为空，所有的访问操作都是未定义的行为。

每个顺序容器都有front成员函数，除了forward_list之外的所有容器还有back成员函数。这些操作分别返回对第一个和最后一个元素的引用：

|
vector<int> scores = {85, 92, 78, 96, 88};
if (!scores.empty()) {
    int firstScore = scores.front();   // 获取第一个成绩
    int lastScore = scores.back();     // 获取最后一个成绩
    
    // 也可以通过迭代器访问
    int firstByIter = *

在调用front或back之前，我们必须确保容器不为空。对空容器调用这些函数会导致严重的程序错误。

访问操作返回引用

容器的访问成员函数返回的是引用。如果容器是const对象，返回const引用；如果容器不是const，返回普通引用，我们可以用它来修改获取的元素：

|
vector<int> grades = {80, 90, 70};
if (!grades.empty()) {
    grades.front() = 85;        // 修改第一个元素
    auto& lastGrade = grades.back();  // 获取最后一个元素的引用
    lastGrade = 95;             // 修改最后一个元素
    
    auto copyGrade = grades.

使用auto时，如果我们想要修改元素，必须明确声明为引用类型。

下标操作和安全的随机访问

提供快速随机访问的容器（string、vector、deque和array）都支持下标运算符。下标必须在有效范围内，即大于等于0且小于容器大小。程序员有责任确保下标有效，下标运算符不会检查范围：

|
vector<string> cities = {"北京", "上海", "广州"};
cout << cities[0];     // 正确：输出"北京"
cout << cities[10];    // 运行时错误：下标越界！

如果我们想要确保下标有效，可以使用at成员函数。at的行为类似下标运算符，但如果下标无效，at会抛出out_of_range异常：

|
vector<string> cities;  // 空容器
try {
    cout << cities.at(0);  // 抛出out_of_range异常
} catch (const out_of_range& e) {
    cout << "访问越界：" << e.what() << endl;
}

删除容器中的元素

与添加元素类似，删除元素的操作也有多种方式。需要强调的是，删除操作不会检查其参数，程序员必须确保要删除的元素确实存在。

pop_front和pop_back操作

pop_front和pop_back函数分别删除第一个和最后一个元素。就像没有push_front的vector和string也没有pop_front一样，forward_list没有pop_back。这些操作返回void，如果需要删除前的值，必须先保存：

|
queue<string> messageQueue = {"消息1", "消息2", "消息3"};
while (!messageQueue.empty()) {
    string currentMsg = messageQueue.front();  // 保存要处理的消息
    processMessage(currentMsg);                // 处理消息
    messageQueue.pop_front();                  // 删除已处理的消息
}

erase操作：删除指定位置的元素

erase操作可以删除迭代器指定的单个元素，或者删除迭代器对指定的元素范围。两种形式的erase都返回指向被删除元素之后位置的迭代器：

|
list<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
auto iter = numbers.begin();
while (iter != numbers.end()) {
    if (*iter % 2 == 0) {

我们也可以删除元素范围：

|
vector<string> words = {"hello", "world", "cpp", "programming", "fun"};
// 删除中间三个元素
auto first = words.begin() + 1;
auto last = words.begin() + 4;
words.erase(first, last);  // 删除"world", "cpp", "programming"
// 现在words包含：{"hello", "fun"}

要删除容器中的所有元素，我们可以调用clear或向erase传递begin和end迭代器：

|
vector<int> data = {1, 2, 3, 4, 5};
data.clear();  // 删除所有元素
// 或者
// data.erase(data.begin(), data.end());  // 等价操作

forward_list的特殊操作

forward_list作为单向链表，在删除或添加元素时需要访问前驱节点以更新链接。由于单向链表无法轻易访问前驱节点，forward_list提供了特殊的操作：insert_after、emplace_after和erase_after。

为了支持这些操作，forward_list还提供了before_begin函数，它返回一个指向首元素之前不存在位置的迭代器：

|
forward_list<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
auto prev = numbers.before_begin();  // 指向首元素前的位置
auto curr = numbers.begin();         // 指向首元素
 
while (curr != numbers.end()) {

调整容器大小

除了array之外，我们可以使用resize操作来增大或缩小容器。如果当前大小大于请求的大小，元素将从容器末尾删除；如果当前大小小于新大小，元素将添加到容器末尾：

|
vector<int> scores(10, 100);  // 10个元素，每个都是100
scores.resize(15);            // 添加5个值为0的元素
scores.resize(20, 90);        // 添加5个值为90的元素
scores.resize(8);             // 删除末尾12个元素

resize操作可以接受一个可选的元素值参数，用于初始化添加的元素。如果未提供此参数，添加的元素将进行值初始化。

容器操作对迭代器的影响

添加或删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。使用失效的指针、引用或迭代器是严重的编程错误，可能导致程序崩溃。

当我们向容器添加元素时，不同容器的行为不同。对于vector或string，如果发生重新分配，所有迭代器都会失效；如果没有重新分配，插入位置之前的迭代器保持有效，之后的失效。对于deque，如果在两端添加元素，迭代器会失效但引用和指针保持有效；在其他位置添加会使所有迭代器、引用和指针失效。对于list或forward_list，所有迭代器、引用和指针都保持有效。

删除元素时，被删除元素的迭代器显然会失效。对于list或forward_list，其他所有迭代器、引用和指针保持有效。对于deque，如果删除两端的元素，其他迭代器、引用和指针不受影响；删除其他位置的元素会使所有迭代器、引用和指针失效。对于vector或string，删除位置之前的迭代器、引用和指针保持有效。

编写改变容器的循环

当我们编写添加或删除vector、string或deque元素的循环时，必须考虑迭代器可能失效的问题。程序必须确保在每次改变容器的操作后适当地刷新迭代器：

|
vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9};
auto iter = data.begin();
while (iter != data.end()) {
    if (*iter % 2 == 1) {

避免保存end返回的迭代器

在添加或删除vector或string的元素，或者添加元素到deque或删除deque中除首元素外的任何元素时，end返回的迭代器总是会失效。因此，改变容器的循环应该总是调用end而不是使用保存的副本：

|
// 危险的做法
auto begin = data.begin();
auto end = data.end();  // 保存end迭代器是危险的
while (begin != end) {  // 如果容器改变，end可能失效
    // 修改容器的操作...
}
 
// 安全的做法
while (begin != data.end()) {  // 每次都重新获取end
    // 修改容器的操作...
}

这种设计考虑也是C++标准库通常将end()实现为非常快速操作的原因之一。

vector的增长机制

为了支持快速的随机访问，vector的元素在内存中是连续存储的，每个元素都紧挨着前一个元素。通常情况下，我们不需要关心标准库类型的具体实现方式，只需要知道如何使用它们即可。然而，对于vector和string而言，实现的某些细节会影响到它们的接口设计。

既然元素必须连续存储，而容器的大小又是可变的，那么当我们向vector或string添加元素时会发生什么呢？如果没有足够的空间容纳新元素，容器不能简单地在内存中的其他地方添加元素，因为这会破坏连续性要求。相反，容器必须分配新的内存空间来容纳现有元素加上新元素，将元素从旧位置移动到新空间，添加新元素，然后释放旧内存。如果vector在每次添加元素时都进行这样的内存分配和释放操作，性能将会不可接受地缓慢。

为了避免这种开销，标准库的实现者采用了能够减少容器重新分配次数的分配策略。当需要获取新内存时，vector和string的实现通常会分配超出当前需要的容量。容器将这些存储空间保留在备用状态，并在添加新元素时使用它们。这样，就不需要为每个新元素都重新分配整个容器。

这种分配策略比每次添加元素都重新分配容器要高效得多。实际上，其性能好到足以使vector在实践中通常比list或deque增长得更高效，尽管vector在每次重新分配内存时都必须移动所有元素。

容量管理的成员函数

vector和string类型提供了一些成员函数，让我们能够与实现的内存分配部分进行交互。capacity操作告诉我们容器在必须分配更多空间之前能够容纳多少个元素。reserve操作让我们可以告诉容器应该准备容纳多少个元素。

调用reserve只有在请求的空间超过当前容量时才会改变vector的容量。如果请求的大小大于当前容量，reserve会分配至少与请求数量相等的空间（可能会分配更多）。

如果请求的大小小于或等于现有容量，reserve什么也不做。特别地，用小于当前容量的大小调用reserve不会导致容器释放内存。因此，调用reserve后，容量将大于或等于传递给reserve的参数。

结果是，调用reserve永远不会减少容器使用的空间大小。同样，resize操作只改变容器中元素的数量，而不改变其容量。我们不能使用resize来减少容器保留的内存。

在新标准下，我们可以调用shrink_to_fit来请求deque、vector或string释放不需要的内存。这个函数表示我们不再需要任何多余的容量。但是，实现可以自由地忽略这个请求，不保证调用shrink_to_fit会释放内存。

理解容量和大小的区别

理解容量和大小之间的区别是非常重要的。容器的大小是它已经持有的元素数量；容器的容量是在必须分配更多空间之前它能够容纳的元素数量。

让我们通过一个学生成绩管理的例子来说明大小和容量之间的相互作用：

|
vector<int> scores;
// 大小应该为0；容量由实现定义
cout << "scores: 大小: " << scores.size() 
     << " 容量: " << scores.capacity() << endl;
 
// 添加15个成绩
for (int i = 1; i <= 15; ++i) {
    scores.push_back(80 + i);  // 成绩从81到95
}

当我们运行这段代码时，可能会得到类似这样的输出：

|
scores: 大小: 0 容量: 0
scores: 大小: 15 容量: 16

我们知道空vector的大小为0，显然我们的标准库实现也将空vector的容量设置为0。当我们向vector添加元素时，大小等于我们添加的元素数量。容量必须至少与大小一样大，但可以更大。分配多少额外容量的具体细节因标准库的实现而异。在这个实现中，逐个添加15个元素导致容量为16。

我们可以形象地将当前scores的状态想象为：

|
81 82 83 ... 95 [预留容量]
     scores.size()
         ↑
       scores.capacity()
           ↑

现在我们可以预留一些额外的空间：

|
scores.reserve(30);  // 将容量设置为至少30，可能更多
cout << "scores: 大小: " << scores.size() 
     << " 容量: " << scores.capacity() << endl;

输出表明reserve调用分配了我们请求的确切空间：

|
scores: 大小: 15 容量: 30

接下来我们可能会用完这些预留的容量：

|
// 添加元素直到用完多余的容量
while (scores.size() != scores.capacity()) {
    scores.push_back(60);  // 添加一些较低的成绩
}
 
cout << "scores: 大小: " << scores.size() 
     << " 容量: " << scores.capacity() << endl;

输出表明此时我们已经用完了预留的容量，大小和容量相等：

|
scores: 大小: 30 容量: 30

因为我们只使用了预留的容量，vector不需要进行任何分配。实际上，只要没有操作超过vector的容量，vector就不能重新分配其元素。

如果我们现在再添加一个元素，vector将不得不重新分配：

|
scores.push_back(95);  // 再添加一个高分成绩
cout << "scores: 大小: " << scores.size() 
     << " 容量: " << scores.capacity() << endl;

这部分程序的输出：

|
scores: 大小: 31 容量: 60

表明这个vector实现似乎遵循每次必须分配新存储时将当前容量翻倍的策略。

我们可以调用shrink_to_fit来请求将超出当前大小需要的内存返回给系统：

|
scores.shrink_to_fit();  // 请求释放内存
cout << "scores: 大小: " << scores.size() 
     << " 容量: " << scores.capacity() << endl;

调用shrink_to_fit只是一个请求，不保证标准库会释放内存。

分配策略的保证

每个vector实现都可以选择自己的分配策略，但是它们在被迫进行分配之前不能分配新内存。只有当用户在大小等于容量时执行插入操作，或者调用resize或reserve且值超过当前容量时，vector才可能重新分配。分配超出指定数量的内存大小由实现决定。

每个实现都必须遵循一种策略，确保使用push_back向vector添加元素是高效的。从技术上讲，通过在最初为空的vector上调用push_back n 次来创建 n 元素vector的执行时间永远不能超过 n 的常数倍。

string的额外操作

string类型提供了许多超越顺序容器通用操作的额外功能。这些额外操作主要是为了支持string类与C风格字符数组之间的密切交互，或者提供使用索引替代迭代器的版本。 string库定义了大量的函数，幸运的是，这些函数使用重复的模式。

string的其他构造方式

除了我们之前介绍的构造函数以及string与其他顺序容器共享的构造函数之外，string类型还支持三种额外的构造函数。

这些接受字符串或const char*的构造函数接受额外的可选参数，让我们可以指定要复制的字符数。当我们传递一个字符串时，还可以指定开始复制的索引位置：

|
const char *greeting = "你好，世界！"; // 以null结尾的数组
char noNull[] = {'C', '+', '+'};     // 不以null结尾
string s1(greeting);                 // 复制到greeting中的null，s1 == "你好，世界！"
string s2(noNull, 3);                // 从noNull复制3个字符，s2 == "C++"
string s3(noNull);                   // 未定义：noNull不以null结尾
string s4

通常，当我们从const char*创建字符串时，指针指向的数组必须以null结尾；字符被复制直到遇到null。 如果我们还传递了一个计数，数组就不必以null结尾。如果我们没有传递计数且没有null，或者给定的计数大于数组的大小，操作是未定义的。

当我们从字符串复制时，可以提供可选的起始位置和计数。起始位置必须小于或等于给定字符串的大小。如果位置大于大小，构造函数会抛出out_of_range异常。 当我们传递计数时，从给定位置开始复制那么多字符。无论我们要求多少字符，库最多复制到字符串的大小。

substr操作

substr操作返回一个字符串，它是原始字符串的部分或全部副本。我们可以向substr传递可选的起始位置和计数：

|
string message("学习C++编程");
string s2 = message.substr(0, 2);    // s2 = "学习"
string s3 = message.substr(2);       // s3 = "C++编程"
string s4 = message.substr(2, 3);    // s4 = "C++"
string s5 = message.substr(15);      // 抛出out_of_range异常

如果位置超过字符串的大小，substr函数会抛出out_of_range异常。如果位置加上计数大于大小，计数会被调整为只复制到字符串的末尾。

改变string的其他方式

string类型支持顺序容器的赋值运算符以及assign、insert和erase操作。它还定义了insert和erase的额外版本。

除了接受迭代器的insert和erase版本之外，string还提供接受索引的版本。索引指示要删除的起始元素或在其之前插入给定值的位置：

|
string text = "Hello";
text.insert(text.size(), 3, '!');    // 在text末尾插入3个感叹号
text.erase(text.size() - 3, 3);      // 从text删除最后3个字符

string库还提供接受C风格字符数组的insert和assign版本。例如，我们可以使用以null结尾的字符数组作为要插入或赋值到字符串中的值：

|
const char *title = "C++程序设计教程";
string book;
book.assign(title, 3);               // book == "C++"
book.insert(book.size(), title + 3); // book == "C++程序设计教程"

这里我们首先通过调用assign替换book的内容。我们赋值到book中的字符是从title指向的字符开始的3个字符。我们请求的字符数必须小于或等于title指向的数组中的字符数（不包括null结尾符）。

我们也可以指定要插入或赋值的字符来自另一个字符串或其子字符串：

|
string course = "数据结构", textbook = "算法导论";
course.insert(0, textbook);          // 在位置0之前插入textbook的副本
course.insert(0, textbook, 0, textbook.size()); // 等价的调用

append和replace函数

string类定义了两个额外的成员append和replace，它们可以改变字符串的内容。append操作是在末尾插入的简写方式：

|
string book("C++基础教程"), book2 = book;
book.insert(book.size(), " 第五版");  // book == "C++基础教程 第五版"
book2.append(" 第五版");              // 等价：向book2追加" 第五版"

replace操作是调用erase和insert的简写方式：

|
// 将"第五版"替换为"第六版"的等价方法
book.erase(6, 3);                    // book == "C++基础教程 版"
book.insert(6, "第六");               // book == "C++基础教程 第六版"
// 从位置6开始，删除3个字符，然后插入"第六"
book2.replace(6, 3, "第六");          // 等价：book == book2

在replace调用中，我们插入的文本恰好与删除的文本大小相同。我们可以插入更大或更小的字符串：

|
book.replace(6, 3, "最新");           // book == "C++基础教程 最新版"

在这个调用中，我们删除了3个字符但插入了2个字符。

string搜索操作

string类提供了六种不同的搜索函数，每种都有四个重载版本。每个搜索操作都返回一个string::size_type值，表示匹配发生的索引。 如果没有匹配，函数返回一个名为string::npos的静态成员。库将npos定义为用值-1初始化的const string::size_type。 因为npos是无符号类型，这个初始化器意味着npos等于任何字符串可能拥有的最大可能大小。

find函数执行最简单的搜索。它寻找其参数并返回找到的第一个匹配的索引，如果没有匹配则返回npos：

|
string student("张三李四王五");
auto pos1 = student.find("李四");     // pos1 == 1

返回1，这是在"张三李四王五"中找到子字符串"李四"的索引。

搜索（和其他字符串操作）是区分大小写的。当我们在字符串中查找值时，大小写很重要：

|
string name("Hello");
pos1 = name.find("hello");          // pos1 == npos

这段代码会将pos1设置为npos，因为"Hello"不匹配"hello"。

一个稍微复杂的问题需要查找与搜索字符串中任何字符的匹配。例如，以下代码定位学号中的第一个数字：

|
string digits("0123456789"), studentId("s2021001");
// 返回1，即studentId中第一个数字的索引
auto pos = studentId.find_first_of(digits);

我们可以调用find_first_not_of来查找不在搜索参数中的第一个位置，而不是寻找匹配。例如，要查找字符串的第一个非数字字符，我们可以写：

|
string code("2021abc");
// 返回4，即字符'a'的索引
auto pos = code.find_first_not_of(digits);

指定搜索的起始位置

我们可以向查找操作传递可选的起始位置。这个可选参数指示从哪个位置开始搜索。默认情况下，该位置设置为零。一个常见的编程模式使用这个可选参数循环遍历字符串查找所有出现：

|
string::size_type pos = 0;
string data("a1b2c3d4"), numbers("0123456789");
// 每次迭代找到data中的下一个数字
while ((pos = data.find_first_of(numbers, pos)) != string::npos) {
    cout << "在索引" << pos << "处找到数字: " << data[pos] << endl;
    ++pos; // 移动到下一个字符
}

while条件中将pos重置为从pos当前值开始遇到的第一个数字的索引。只要find_first_of返回有效索引，我们就打印当前结果并递增pos。

如果我们忽略递增pos，循环将永远不会终止。为了理解原因，考虑如果我们不进行递增会发生什么。在循环的第二次遍历中，我们从pos索引的字符开始查找。该字符将是一个数字，所以find_first_of会（重复地）返回pos！

反向搜索

到目前为止我们使用的查找操作从左到右执行。库提供了从右到左搜索的类似操作。rfind成员搜索指定子字符串的最后一次（即最右边的）出现：

|
string text("数学物理数学");
auto first_pos = text.find("数学");     // 返回0
auto last_pos = text.rfind("数学");     // 返回2

find返回索引0，指示第一个"数学"的开始，而rfind返回索引2，指示最后一次出现"数学"的开始。

类似地，find_last函数的行为类似find_first函数，除了它们返回最后一个匹配而不是第一个。

compare函数

除了关系运算符之外，string库还提供了一组类似于C库strcmp函数的compare函数。与strcmp一样，s.compare根据s是等于、大于还是小于从给定参数形成的字符串，返回零、正值或负值。

有六个版本的compare。参数根据我们是比较两个字符串还是比较字符串和字符数组而变化。在两种情况下，我们都可以比较整个字符串或其一部分。

数值转换

字符串经常包含表示数字的字符。例如，我们用两个字符表示数值15，字符'1'后跟字符'5'。一般来说，数字的字符表示与其数值不同。存储在16位short中的数值15具有位模式0000000000001111，而表示为两个字符的字符串"15"具有不同的位模式。

新标准引入了几个在数值数据和库字符串之间转换的函数：

|
int score = 95;
string scoreStr = to_string(score);  // 将int类型的score转换为字符表示
double average = stod(scoreStr);     // 将字符串scoreStr转换为浮点数

这里我们调用to_string将95转换为其对应的字符串表示，然后调用stod将该字符串转换为浮点数。

要转换为数值的字符串中的第一个非空白字符必须是可以出现在数字中的字符：

|
string formula = "圆周率 = 3.14159";
// 转换formula中从数字开始的第一个子字符串，d = 3.14159
double pi = stod(formula.substr(formula.find_first_of("+-.0123456789")));

在这个stod调用中，我们调用find_first_of来获取formula中可能是数字一部分的第一个字符的位置。我们将从该位置开始的formula子字符串传递给stod。stod函数读取给定的字符串，直到找到不能成为数字一部分的字符。然后它将找到的数字的字符表示转换为相应的双精度浮点值。

要转换的字符串中的第一个非空白字符必须是符号（+或-）或数字。字符串可以以0x或0X开头表示十六进制。对于转换为浮点的函数，字符串也可以以小数点（.）开头，并可能包含e或E来指定指数。

如果字符串不能转换为数字，这些函数会抛出invalid_argument异常。如果转换生成无法表示的值，它们会抛出out_of_range异常。

容器适配器

除了顺序容器之外，标准库还定义了三种容器适配器：stack、queue和priority_queue。适配器是标准库中的一个通用概念。有容器适配器、迭代器适配器和函数适配器。本质上，适配器是使一种事物表现得像另一种事物的机制。容器适配器接受一个现有的容器类型，使其表现得像不同的类型。例如，stack适配器接受一个顺序容器（除了array或forward_list），使其操作起来像一个栈。

定义适配器

每个适配器都定义了两个构造函数：创建空对象的默认构造函数，以及接受容器并通过复制给定容器来初始化适配器的构造函数。例如，假设deq是一个deque<int>，我们可以使用deq来初始化一个新的栈：

|
deque<int> scores = {85, 92, 78, 96, 88};
stack<int> scoreStack(scores);  // 将scores中的元素复制到scoreStack中

默认情况下，stack和queue都是基于deque实现的，priority_queue是基于vector实现的。我们可以通过在创建适配器时将顺序容器命名为第二个类型参数来覆盖默认的容器类型：

|
// 基于vector实现的空栈
stack<string, vector<string>> stringStack;
// stringStack2基于vector实现，最初保存names的副本
stack<string, vector<string>> stringStack2(names);

对于给定的适配器，使用哪些容器有约束。所有适配器都要求能够添加和删除元素的能力。因此，它们不能建立在array上。同样，我们不能使用forward_list，因为所有适配器都需要添加、删除或访问容器中最后一个元素的操作。stack只需要push_back、pop_back和back操作，所以我们可以将任何剩余的容器类型用于stack。queue适配器需要back、push_back、front和push_front，所以它可以建立在list或deque上，但不能建立在vector上。priority_queue除了front、push_back和pop_back操作外还需要随机访问；它可以建立在vector或deque上，但不能建立在list上。

stack适配器

stack类型在stack头文件中定义。下面的程序说明了stack的使用：

|
stack<int> examScores;  // 空栈
// 填充栈
for (int score = 60; score <= 100; score += 10) {
    examScores.push(score);  // examScores保存60, 70, 80, 90, 100
}
 
while (!examScores.empty()) {  // 当examScores中还有值时
    int topScore = examScores.top();
    cout << "当前最高分: " <<

声明stack<int> examScores;定义examScores为一个保存整数元素的空栈。for循环添加五个元素，将每个初始化为下一个分数值。while循环遍历整个栈，检查顶部值并将其从栈中弹出，直到栈为空。

每个容器适配器根据底层容器类型提供的操作定义自己的操作。我们只能使用适配器操作，不能使用底层容器类型的操作。例如，虽然stack是使用deque实现的，我们没有对deque操作的直接访问。我们不能在栈上调用push_back；相反，我们必须使用名为push的栈操作。

queue适配器

queue和priority_queue适配器在queue头文件中定义。

标准库queue使用先进先出（FIFO）的存储和检索策略。进入队列的对象被放在后面，离开队列的对象从前面移除。餐厅按照客人到达的顺序安排座位就是FIFO队列的例子。

priority_queue让我们在队列中保存的元素之间建立优先级。新添加的元素被放在所有优先级较低的元素之前。餐厅根据客人的预订时间安排座位，而不管他们何时到达，这是优先队列的例子。默认情况下，库使用元素类型上的<运算符来确定相对优先级。

练习

现在让我们通过一些简单的练习题来巩固本章学到的知识。每道题都涵盖了STL容器的核心概念，请先尝试独立完成，然后再查看答案。

练习 1：vector的基本使用

编写一个程序，使用vector存储5个整数（1, 2, 3, 4, 5），然后使用迭代器遍历并输出所有元素。

|
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    
    // 使用迭代器遍历
    cout << "使用迭代器遍历：" << endl;
    for (auto it = v.begin

练习 2：容器的选择

根据以下场景，选择合适的容器类型并说明理由：

• 需要频繁在中间插入和删除元素
• 需要快速随机访问元素
• 需要从两端添加和删除元素

|
#include <iostream>
#include <vector>
#include <list>
#include <deque>
using namespace std;
 
int main() {
    // 场景1：频繁在中间插入删除 -> 使用list
    list<int> lst = {1, 2, 3, 4, 5};
    auto it = lst.begin();
    advance(it, 

练习 3：map的使用

编写一个程序，使用map存储学生的姓名和成绩，然后查找并输出某个学生的成绩。

|
#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main() {
    map<string, int> scores;  // 键是姓名，值是成绩
    
    // 添加学生成绩
    scores["张三"] = 85;
    scores["李四"] = 90;
    scores["王五"] = 78;

练习 4：stack的使用

使用stack实现一个简单的括号匹配检查器，检查字符串中的括号是否匹配。

|
#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
bool checkParentheses(const string& str) {
    stack<char> s;
    
    for (char c : str) {
        if (c == '(' || c == '[' || c == '{') {

练习 5：综合应用——简单的学生管理系统

使用vector和map实现一个简单的学生管理系统，可以添加学生、查找学生、计算平均成绩。

|
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
 
class StudentManager {
private:
    map<string, vector<int>> students;  // 姓名 -> 成绩列表
    
public:
    // 添加学生
    void addStudent(const string& name) {
        if (students.find(name) 

vector是最常用的顺序容器，支持随机访问和动态扩容。迭代器提供了统一的访问方式，范围for循环是C++11引入的语法糖，让遍历更加简洁。

选择容器的原则：

• vector：适合随机访问，末尾插入删除效率高
• list：适合频繁在中间插入删除，但不支持随机访问
• deque：适合需要从两端操作的情况，支持随机访问但效率略低于vector

map是关联容器，存储键值对。它根据键自动排序，查找效率为O(log n)。使用find()方法查找元素，如果找不到会返回end()迭代器。pair.first是键，pair.second是值。

stack是后进先出（LIFO）的容器适配器，非常适合处理需要"最近匹配"的问题，如括号匹配、表达式求值等。遇到左括号就入栈，遇到右括号就检查栈顶是否匹配。

这个例子综合运用了vector和map。map用于快速查找学生，vector用于存储每个学生的多门课程成绩。这种组合可以高效地处理键值对和列表数据。