《C++ Primer》笔记第9章顺序容器 / 开普饭

顺序容器类型

类型	解释
vector	可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
deque	双端队列。支持快速随机访问。在头尾位置插入、删除速度很快
list	双向链表。只支持双向顺序访问。在list中任何位置进行插入、删除操作速度都很快
forward_list	单向链表。只支持单向顺序访问。在链表任何位置进行插入、删除操作速度都很快
array	固定大小数组。支持快速随机访问。不能添加或删除元素
string	与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入、删除速度快。

string和vector将元素保存在连续的内存空间中。由元素的下标来计算其地址是非常快速的，但在中间位置添加或删除元素就会非常耗时。list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速，作为代价，这两个容器不支持元素的随机访问，并且相比vector、deque、array，这两个容器的额外内存开销也很大。deque支持快速的随机访问，在deque的两端添加或删除元素都是很快的，与list或forward_list添加删除元素的速度相当。array对象的大小是固定的。因此，array不支持添加和删除元素以及改变容器大小的操作。forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size保证是一个快速的常量时间的操作。
以下是一些选择容器的基本原则：
- 除非你有很好的理由选择其他容器，否则应使用vector。
- 如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list。
- 如果程序要求随机访问元素，应使用vector或deque。
- 如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。
- 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque。
- 如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
  - 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。
  - 如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。
如果你不确定应该使用哪种容器，那么可以在程序中只使用vector和list公共的操作：使用迭代器，不使用下标操作，避免随机访问。这样，在必要时选择使用vector或list都很方便。
容器类型上的操作形成了一种层次：
- 某些操作是所有容器类型都提供的。
- 另外一些操作仅针对顺序容器、关联容器或无序容器。
- 还有一些操作只适用于一小部分容器。
顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：
```
  // 假定noDefault是一个没有默认构造函数的类型
  vector<noDefault> v1(10, init); // 正确：提供了元素初始化器
  vector<noDefault> v2(10); // 错误：必须提供一个元素初始化器
```
容器操作：

类型别名	解释
iterator	此容器类型的迭代器类型
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足够保存此种容器类型最大可能容器的大小
difference_type	带符号整数类型，足够保存两个迭代器之间的距离
value_type	元素类型
reference	元素的左值类型；与`value_type&`含义相同
const_reference	元素的const左值类型（即，`const value_type&`）

构造函数	解释
C c;	默认构造函数，构造空容器
C c1(c2);	构造c2的拷贝c1
C c(b,e);	构造c，将迭代器b和e指定的范围内的元素内的元素拷贝到c
C c{a,b,c...};	列表初始化c

赋值与swap	解释
c1=c2	将c1中的元素替换为c2中元素
c1={a,b,c...}	将c1中的元素替换为列表中元素
a.swap(b)	交换a和b的元素
swap(a,b)	与a.swap(b)等价

大小	解释
c.size()	c中元素的数目
c.max_size()	c可保存的最大元素数目
c.empty()	若c中储存了元素，返回false，否则返回true

添加、删除元素	解释
c.insert(args)	将args中的元素拷贝进c
c.emplace(inits)	使用inits构造c中的一个元素
c.erase(args)	删除args指定的元素
c.clear()	删除c中的所有元素，返回void

关系运算符	解释
==，!=	所有容器都支持相等（不等）运算符
<，<=，>，>=	删除c中的所有元素，返回void

获取迭代器	解释
c.begin()，c.end()	返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin()，c.cend()	返回const_iterator

反向容器的额外成员（不支持forward_list）	解释
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin()，c.rend()	返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin()，c.crend()	返回const_reverse_iterator

forward_list迭代器不支持递减运算符（--）。
一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置。
迭代器范围中的元素包含first所表示的元素以及从first开始直至last（但不包含last）之间的所有元素。左闭合区间：[left, right)。
如果满足如下条件，两个迭代器begin和end构成一个迭代器范围：
- 它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置，且
- 我们可以通过反复递增begin来到达end。换句话说，end不在begin之前。
标准库使用左闭合范围是因为这种范围有三种方便的性质。假定begin和end构成一个合法的迭代器范围，则
- 如果begin与end相等，则范围为空
- 如果begin与end不等，则范围至少包含一个元素，且begin指向该范围中的第一个元素
- 我们可以对begin递增若干次，使得begin==end

这些性质意味着我们可以用循环来处理一个元素范围。

while (begin != end)
{
    *begin = val; // 正确：范围非空，因此begin指向一个元素
    // 在while循环中，可以安全地解引用begin，因为begin必然指向一个元素。
    ++begin; // 移动迭代器，获取下一个元素
}

反向迭代器就是一种反向遍历容器的迭代器，与正向迭代器相比，各种操作的含义也都发生了颠倒。例如，对一个反向迭代器执行++操作，会得到上一个元素。
begin和end有多个版本：带r的版本返回反向迭代器；以c开头的版本则返回const迭代器；不以c开头的函数都是被重载过的。一个是const成员，返回容器的const_iterator类型；另一个是非常量成员，返回容器的iterator类型。当我们对一个非常量对象调用这些成员时，得到的是返回iterator的版本。只有在对一个const对象调用这些函数时，才会得到一个const版本。与const指针和引用类似，可以将一个普通的iterator转换为对应的const_iterator，但反之不行。
当auto与begin或end结合使用时，获得的迭代器类型依赖于容器类型，与我们想要如何使用迭代器毫不相干。但以c开头的版本还是可以获得const_iterator的，而不管容器的类型是什么。当不需要写访问时，应该使用cbegin和cend。
容器定义和初始化

方法	解释
C c;	默认构造函数。如果c是一个array，则c中元素按默认方式初始化；否则c为空
C c1(c2)	c1初始化为c2的拷贝。c1和c2必须是相同类型（即，它们必须是相同的容器类型，且保存的是相同的元素类型；对于array类型，两者还必须具有相同大小）
C c{a,b,c...}或C c={a,b,c...}	c初始化为初始化列表中元素的拷贝。列表中元素的类型必须与c的元素类型相容。对于array类型，列表中元素数目必须等于或小于array的大小，任何遗漏的元素都进行值初始化
C c(b,e)	c初始化为迭代器b和e指定范围中的元素的拷贝。范围中元素的类型必须与C的元素的类型相容（array不适用）
——	只有顺序容器（不包括array）的构造函数才能接受大小参数
C seq(n)	seq包含n个元素，这些元素进行了值初始化；此构造函数是explicit的。（string不适用）
C seq(n,t)	seq包含n个初始化为值t的元素

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。但当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换为要初始化的容器的元素类型即可（构造函数只是读取范围中的元素并进行拷贝）。

// 每个容器有三个元素，用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors); // 正确：类型匹配
deque<string> authList(authors); // 错误：容器类型不匹配
vector<string> words(articles); // 错误：容器类型必须匹配
// 正确：可以将const char*元素转换为string
forward_list<string> words(articles.begin(),articles.end());

如果元素类型是内置类型或者是具有默认构造函数的类类型，可以只为构造函数提供一个容器大小参数。如果元素类型没有默认构造函数，除了大小参数外，还必须指定一个显示的元素初始值。

#include <iostream>
#include <vector>
using namespace std;

class A
{
private:
    vector<int> data;

public:
    A(vector<int>::iterator beg, vector<int>::iterator end)
    {
        data.assign(beg, end);
    }
    void display()
    {
        for (auto i : data)
            cout << i << " ";
        cout << endl;
    }
};

int main()
{
    vector<int> iv{1, 2, 3};
    vector<A> one(5, A(iv.begin(), iv.end()));
    for (auto i : one)
        i.display();
    cout << endl;
    return 0;
}

只有顺序容器的构造函数才接受大小参数，关联容器并不支持。

标准库array的大小也是类型的一部分。当定义一个array时，除了指定元素类型，我们必须同时指定元素类型和大小。

array<int, 42> // 类型为：保存42个int的数组
array<string, 10> // 类型为：保存10个string的数组

array<int, 10>::size_type i; // 数组类型包括元素类型和大小
array<int>::size_type j; // 错误：array<int>不是一个类型

一个默认构造的array是非空的：它包含了于其大小一样多的元素。这些元素都被默认初始化，就像一个内置数组中的元素那样。如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小。如果初始值数目小于array的大小，则它们被用来初始化array中靠前的元素，所有剩余元素都会进行值初始化。在这两种情况下，如果元素类型是一个类类型，那么该类必须有一个默认构造函数，以使值初始化能够进行。
```
array<int, 10> ia1; // 10个默认初始化的int
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // 列表初始化
array<int, 10> ia3 = {42}; // ia3[0]为42，剩余元素为0

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; // 错误：内置数组不支持拷贝或赋值
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; // 正确：只要数组类型匹配即合法
```
与其他容器一样，array也要求初始值的类型必须与要创建的容器类型相同。此外，array还要求元素类型和大小也都一样，因为大小是array类型的一部分。
与赋值相关的运算符可用于所有容器。赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝。如果两个容器原来大小不同，赋值运算后两者的大小都与右边容器的原大小相同。
```
c1 = c2; // 将c1的内容替换为c2中元素的拷贝
c1 = {a,b,c}; // 赋值后，c1大小为3
```
与内置数组不同，标准库array类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型。由于右边运算对象的大小可能与左边运算对象的大小不同，因此array类型不支持assign，也不允许用花括号包围的值列表进行赋值。
```
array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0}; // 所有元素值均为0
a1 = a2; // 替换a1中的元素
a2 = {0}; // 错误：不能将一个花括号列表赋予数组
```

容器赋值运算	解释
c1=c2	将c1中的元素替换为c2中元素的拷贝。c1和c2必须具有相同的类型
c={a,b,c...}	将c1中元素替换为初始化列表中元素的拷贝（array不适用）
swap(c1,c2)	交换c1和c2中的元素。c1和c2必须具有相同的类型。swap通常比从c2向c1拷贝元素快得多
——	assign操作不适用于关联容器和array
seq.assign(b,e)	将seq中的元素替换为迭代器b和e所表示的范围中的元素。迭代器b和e不能指向seq中的元素
seq.assign(il)	将seq中的元素替换为初始化列表il（initializer_list）中的元素
seq.assign(n,t)	将seq中的元素替换为n个值为t的元素

赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效（容器类型为array和string的情况除外）。
顺序容器的assign成员允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。assign操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。
```
list<string> names;
vector<const char*> oldstyle;
names = oldstyle; // 错误：容器类型不匹配
// 正确：可以将const char*转换为string
names.assign(oldstyle.cbegin(), oldstyle.cend());
```
由于其旧元素被替换，因此传递给assign的迭代器不能指向调用assign的容器。
除array外，swap不对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间内完成。
除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。它们仍指向swap操作之前所指向的那些元素。但是，在swap之后，这些元素已经属于不同的容器了。对一个string调用swap会导致迭代器、引用和指针失效。
swap两个array会真正交换它们的元素。因此，交换两个array所需的时间与array中元素的数目成正比。
对于array，在swap操作之后，指针、引用和迭代器所绑定的元素保持不变，但元素值已经与另一个array中对应元素进行了交换。
在标准库中，容器既提供成员函数版本的swap，也提供非成员版本的swap。非成员版本的swap在泛型编程中是非常重要的。统一使用非成员版本的swap是一个好习惯。
成员函数size返回容器中元素的数目；empty当size为0时返回布尔值true，否则返回false；max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。forward_list支持max_size和empty，但不支持size。
每个容器类型都支持相等运算符（==和!=）；除了无序关联容器都支持关系运算符（>、>=、<、<=）。关联运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。
比较两个容器实际上是进行元素的逐对比较。这些运算符的工作方式与string的关系运算类似。
- 如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等；否则两个容器不等。
- 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
- 如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不相等的元素的比较结果。
只有当其元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。
容器的相等运算符实际上是使用元素的==运算符实现比较的，而其他关系运算符是使用元素的<运算符。如果元素类型不支持所需运算符，那么保存这种元素的容器就不能使用相应的关系运算。

向顺序容器添加元素的操作	解释
——	这些操作会改变容器的大小；array不支持这些操作
——	forward_list有自己专有版本的insert和emplace
——	forward_list不支持push_back和emplace_back
——	vector和string不支持push_front和emplace_front
c.push_back(t)或c.emplace_back(args)	在c的尾部创建一个值为t或由args创建的元素。返回void
c.push_front(t)或c.emplace_front(args)	在c的头部创建一个值为t或由args创建的元素。返回void
c.insert(p,t)或c.emplace(p,args)	在迭代器p指向的元素之前创建一个值为t或由args创建的元素。返回指向新添加的元素的迭代器
c.insert(p,n,t)	在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器；若n为0，则返回p
c.insert(p,b,e)	将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素（insert会破坏迭代器）。返回指向新添加的第一个元素的迭代器；若范围为空，则返回p
c.insert(p,il)	il是一个花括号包围的元素值列表（initializer_list）。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器；若列表为空，则返回p

向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效。
不同容器使用不同的策略来分配元素空间，而这些策略直接影响性能。
当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象的一个拷贝，而不是对象本身。就像我们将一个对象传递给非引用参数一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。

通过使用insert的返回值，可以在容器中一个特定位置反复插入元素：

list<string> lst;
auto iter = lst.begin();
while (cin >> word)
iter = lst.insert(iter, word); // 等价于调用push_front

emplace_front、emplace和emplace_back这些操作构造而不是拷贝元素。

emplace函数在容器中直接构造元素。传递给emplace函数的参数必须与元素类型的构造函数相匹配。

#include <iostream>
#include <vector>
using namespace std;

class A
{
private:
    vector<int> data;

public:
    A(vector<int>::iterator beg, vector<int>::iterator end)
    {
        data.assign(beg, end);
    }
    void display()
    {
        for (auto i : data)
            cout << i << " ";
        cout << endl;
    }
};

int main()
{
    vector<int> iv{1, 2, 3};
    vector<A> one(5, A(iv.begin(), iv.end()));
    for (auto i : one)
        i.display();
    cout << endl;

    vector<int> ivv{2, 3, 6};
    one.emplace_back(ivv.begin(), ivv.end());
    one.back().display();
    return 0;
}

包括array在内的每个顺序容器都有一个front成员函数，而除forward_list之外的所有顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用：

// 在解引用一个迭代器或调用front或back之前检查是否有元素
if (!c.empty())
{
// val和val2是c中第一个元素值的拷贝
auto val = *c.begin(), val2 = c.front();
// val3和val4是c中最后一个元素值的拷贝
auto last = c.end();
auto val3 = *(--last); // forward_list迭代器不能执行--操作
auto val4 = c.back(); // forward_list不支持
}

在调用front和back（或解引用begin和end返回的迭代器）之前，要确保c非空。如果容器为空，if中操作的行为将是未定义的。

在顺序容器中访问元素的操作	解释
——	at和下标操作只适用于string、vector、deque和array
——	back不适用于forward_list
c.back()	返回c中尾元素的引用。若c为空，函数行为未定义。
c.front()	返回c中首元素的引用。若c为空，函数行为未定义。
c[n]	返回c中下标为n的元素的引用，n是一个无符号整数。若n>=c.size()，则函数行为未定义
c.at(n)	返回下标为n的元素的引用。类似下标运算符，但如果下标越界，则抛出一`out_of_range`异常

对一个空容器调用front和back，就像使用一个越界的下标一样，是一种严重的程序设计错误。

在容器中访问元素的成员函数（即，front、back、下标和at）返回的都是引用。如果容器是一个const对象，则返回值是const的引用。如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的值：

if (!c.empty())
{
c.front() = 42; // 将42赋予c中的第一个元素
auto &v = c.back(); // 获得指向最后一个元素的引用
v = 1024; // 改变c中的元素
auto v2 = c.back(); // v2不是一个引用，它是c.back()的一个拷贝
v2 = 0; // 未改变c中的元素
    // 如果我们使用auto变量来保存这些函数的返回值，并且希望使用此变量来改变元素的值，必须记得将变量定义为引用类型
}

顺序容器的删除操作	解释
——	这些操作会改变容器的大小，所以不适用于array
——	forward_list有特殊版本的erase
——	forward_list不支持pop_back；vector和string不支持pop_front
c.pop_back()	删除c中尾元素。若c为空，则函数行为未定义。函数返回void
c.pop_front()	删除c中首元素。若c为空，则函数行为未定义。函数返回void
c.erase(p)	删除迭代器p所指定的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返回尾后迭代器。若p是尾后迭代器，则函数行为未定义
c.erase(b,e)	删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删元素之后元素的迭代器，若e本身就是尾后迭代器，则函数也返回尾后迭代器（总之返回e）
c.clear()	删除c中的所有元素。返回void

删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。
删除元素的成员函数并不检查其参数。在删除元素之前，程序员必须确保它（们）是存在的。
在一个单向链表中，没有简单的办法来获取一个元素的前驱。因此，在一个forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。为了支持这些操作，forward_list也定义了before_begin，它返回一个首前迭代器（允许我们添加删除链表首元素）

在forward_list中插入或删除元素的操作	解释
lst.before_begin()或lst.cbefore_begin()	返回指向链表首元素之前不存在的元素的迭代器。此迭代器不能解引用。`cbefore_begin()`返回一个`const_iterator`
lst.insert_after(p,t)或lst.insert_after(p,n,t)或lst.insert_after(p,b,e)或lst.insert_after(p,il)	在迭代器p之后的位置插入元素。t是一个对象，n是数量，b和e是表示范围的一对迭代器（b和e不能指向lst内），il是一个花括号列表（`initializer_list`）。返回一个指向最后一个插入元素的迭代器。如果范围为空，则返回p。若p为尾后迭代器，则函数行为未定义
emplace_after(p,args)	使用args在p指定的位置之后创建一个元素。返回一个指向这个新元素的迭代器。若p为尾后迭代器，则函数行为未定义
lst.erase_after(p)或lst.erase_after(b,e)	删除p指向的位置之后的元素，或删除从b之后直到（但不包含）e之间的元素。返回一个指向被删元素之后元素的迭代器，若不存在这样的元素，则返回尾后迭代器。如果p指向lst的尾元素或者是一个尾后迭代器，则函数行为未定义

// 示例代码：
forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // 表示flst的“首前元素”
auto curr = flst.begin(); // 表示flst中的第一个元素
while (curr != flst.end()) // 仍有元素要处理
{
if (*curr % 2) // 若元素为奇数，也可以用*curr & 1
curr = flst.erase_after(prev); // 删除它并移动curr
else
{
prev = curr; // 移动迭代器curr，指向下一个元素，prev指向
++curr; // curr之前的元素
}
}

顺序容器大小操作	解释
——	resize不适用于array
c.resize(n)	调整c的大小为n个元素。若n<c.size()，则多出的元素被丢弃。若必须添加新元素（n>c.size()），对新元素进行值初始化。
c.resize(n,t)	调整c的大小为n个元素。任何新添加的元素都初始化为值t

如果resize缩小容器，则指向被删除元素的迭代器、引用和指针都会失效；对vector、string或deque进行resize可能导致迭代器、指针和引用失效。
容器操作可能使迭代器失效。使用失效的迭代器、指针或引用是严重的运行时错误。
- 在向容器添加元素后：
  - 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
  - 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
  - 对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
- 当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用一定会失效，毕竟，这些元素都已经被销毁了。当我们删除一个元素后：
  - 对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
  - 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用和指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
  - 对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。
当你使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好的办法。由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对vector、string和deque尤为重要。

程序必须保证每个循环布中都更新迭代器、引用和指针：

// 傻瓜循环，删除偶数元素，复制每个奇数元素
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin(); // 调用begin而不是cbegin，因为我们要改变vi
while (iter != vi.end())
{
if (*iter % 2)
{
iter = vi.insert(iter, *iter); // 复制当前元素
iter += 2; // 向前移动迭代器，跳过插入到它之前的元素以及当前元素
}
else
{
iter = vi.erase(iter); // 删除偶数元素
// 不应向前移动迭代器，iter指向我们删除的元素之后的元素
}
}

不要保存end返回的迭代器。当我们添加、删除vector或string的元素后，或在deque中首元素之外任何位置添加、删除元素后，原来end返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用。

容器大小管理操作	解释
——	shrink_to_fit只适用于vector、string和deque
——	capacity和reserve只适用于vector和string
c.shrink_to_fit()	请将capacity()减少为与size()相同大小（具体的实现可以选择忽略此请求，即，调用shrink_to_fit并不保证一定退回内存空间）
c.capacity()	不重新分配内存空间的话，c可以保存多少元素
c.reserve(n)	分配至少能容纳n个元素的内存空间

reserve并不改变容器中元素的数量，它仅影响vector预先分配多大的内存空间。只有当需要的内存空间超过当前容量时，reserve调用才会改变vector的容量，如果需求大小大于当前容量，reserve至少分配与需求一样大的内存空间（可能更大）。如果需求大小小于或等于当前容量，reserve什么也不做。特别是，当需求大小小于当前容量时，容器不会退回内存空间。因此，在调用reserve之后，capacity将会大于或等于传递给reserve的参数。这样，调用reserve永远也不会减少容器占用的内存空间。类似的，resize成员函数只能改变容器中元素的数目，而不是容器的容量。我们同样不能使用resize来减少容器预留的内存空间。
每个vector实现都可以选择自己的内存分配策略。但是必须遵守的一条原则是：只有当迫不得已（在执行insert操作时size与capacity相等，或者调用resize或reserve时给定的大小超过当前capacity）时才可以分配新的内存空间。

构造string的其他方法	解释
——	n、len2和pos2都是无符号值
string s(cp,n)	s是cp指向的数组中前n个字符的拷贝。此数组至少应该包含n个字符
string s(s2,pos2)	s是string s2从下标pos2开始的字符的拷贝。若pos2>s2.size()，构造函数的行为未定义
string s(s2,pos2,len2)	s是string s2从下标pos2开始len2个字符的拷贝。若pos2>s2.size()，构造函数的行为未定义。不管len2的值是多少，构造函数至多拷贝s2.size()-pos2个字符。

子字符串操作	解释
s.substr(pos,n)	返回一个string，包含s中从pos开始的n个字符的拷贝。pos的默认值为0.n的默认值为s.size()-pos，即拷贝从pos开始的所有字符

在c++11中，vector 增加了data()的用法，它返回内置vecotr所指的数组内存的第一个元素的指针。

修改string的操作	解释
s.insert(pos,args)	在pos之前插入args指定的字符。pos可以是一个下标或一个迭代器。接受下标的版本返回一个指向s的引用；接受迭代器的版本返回指向第一个插入字符的迭代器
s.erase(pos,len)	删除从位置pos开始的len个字符。如果len被省略，则删除从pos开始直至s末尾的所有字符。返回一个指向s的引用
s.assign(args)	将s中的字符替换为args指定的字符。返回一个指向s的引用
s.append(args)	将args追加到s。返回一个指向s的引用
s.replace(range,args)	删除s中范围range内的字符，替换为args指定的字符。range或者是一个下标和一个长度，或者是一对指向s的迭代器。返回一个指向s的引用
——	args可以是下列形式之一；append和assign可以使用所有形式
——	str不能与s相同，迭代器b和e不能指向s
str	字符串str
str,pos,len	str中从pos开始最多len个字
cp,len	从cp（char pointer）指向的字符数组的前（最多）len个字符
n,c	n个字符c
b,e	迭代器b和e指定的范围内的字符
初始化列表	花括号包围的，以逗号分隔的字符列表
——	*replace和insert所允许的args形式依赖于range和pos是如何指定的*

replace(pos,len,args)	replace(b,e,args)	insert(pos,args)	insert(iter,args)	args可以是
是	是	是	否	str
是	否	是	否	str,pos,len
是	是	是	否	cp,len
是	是	否	否	cp
是	是	是	是	n,c
否	是	否	是	b2,e2
否	是	否	是	初始化列表

string搜索函数返回string::size_type值，该类型是一个unsigned类型。因此，用一个int或其他带符号类型来保存这些函数的返回值不是一个好主意。

string搜索操作	解释
——	搜索操作返回指定字符出现的下标，如果未找到则返回npos
s.find(args)	查找s中args第一次出现的位置
s.rfind(args)	查找s中args最后一次出现的位置
s.find_first_of(args)	在s中查找args中任何一个字符第一次出现的位置
s.find_last_of(args)	在s中查找args中任何一个字符最后一次出现的位置
s.find_first_not_of(args)	在s中查找第一个不在args中的字符
s.find_last_not_of(args)	在s中查找最后一个不在args中的字符
——	args必须是以下形式之一
c,pos	从s中位置pos开始查找字符c。pos默认为0
s2,pos	从s中位置pos开始查找字符串s2。pos默认为0
cp,pos	从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串
cp,pos,n	从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和n无默认值

指定在哪里开始搜索：

string numbers("0123456789"), name("r2d2");
string::size_type pos = 0;
// 每步循环查找name中下一个数
while ((pos = name.find_first_of(numbers, pos)) != string::npos)
{
cout << "found number at index: " << pos
<< " element is " << name[pos] << endl;
++pos; // 移动到下一个字符
}

s.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个字符进行比较

string和数值之间的转换	解释
to_string(val)	一组重载函数，返回数值val的string表示。val可以是任何算术类型。对每个浮点类型和int或更大的整型，都有相应版本的to_string。与往常一样，小整型会被提升
stoi(s,p,b)或stol(s,p,b)或stoul(s,p,b)或stoll(s,p,b)或stoull(s,p,b)	返回s的起始子串（表示整数内容）的数值，返回值类型分别是int、long、unsigned long、long long、unsigned long long。b表示转换所用的基数，默认值为10。p是size_t指针，用来保存s中第一个非数值字符的下标，p默认为0，即，函数不保存下标
stof(s,p)或stod(s,p)或stold(s,p)	返回s的起始子串（表示浮点数内容）的数值，返回值类型分别是float、double、或long double。参数p的作用与整数转换函数中一样
——	string参数中第一个非空白符必须是符号（+或-）或数字。它可以以0x或0X开头来表示十六进制数。对那些将字符串转换为浮点值的函数，string参数也可以以小数点（.）开头，并可以包含e或E来表示指数部分。对于那些将字符串转换为整型值的函数，根据基数不同，string参数可以包含字母字符，对应大于数字9的数。
——	如果string不能转换为一个数值，这些函数抛出一个`invalid_argument`异常。如果转换得到的数值无法用任何类型来表示，则抛出一个`out_of_range`异常。

适配器是标准库中的一个通用概念。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，是其行为看起来像一种不同的类型。

所有容器适配器都支持的操作和类型	解释
size_type	一种类型，足以保存当前类型的最大对象的大小
value_type	元素类型
container_type	实现适配器的底层容器类型
A a;	创建一个名为a的空适配器
A a(c);	创建一个名为a的适配器，带有容器c的一个拷贝
关系运算符	每个适配器都支持所有关系运算符：==、!=、<、<=、>、>=。这些运算符返回底层容器的比较结果
a.empty()	若a包含任何元素，返回false，否则返回true
a.size()	返回a中的元素数目
swap(a,b)	交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同

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

// 从deq拷贝元素到stk
stack<int> stk(deq);
// 在vector上实现的空栈
stack<string, vector<string>> str_stk;
// str_stk2在vector上实现，初始化时保存svec的拷贝
stack<string, vector<string>> str_stk2(svec); // svec是vector<string>类型

额外的栈操作	解释
——	栈默认基于deque实现，也可以在list或vector之上实现。
s.pop()	删除栈顶元素，但不返回该元素值
s.push(item)	创建一个新元素压入栈顶，该元素通过拷贝或移动item而来，或者由args构造
s.top()	返回栈顶元素，但不将元素弹出栈

额外的queue和priority_queue操作	解释
——	queue默认基于deque实现，priority_queue默认基于vector实现
——	queue也可以用list或vector实现，priority_queue也可以用deque实现
q.pop()	弹出queue的首元素或priority_queue的最高优先级的元素，但不返回此元素
q.front()	返回首元素或尾元素，但不删除此元素
q.back()	只适用于queue
q.top()	返回最高优先级元素，但不删除该元素
q.push(item)或q.emplace(args)	在queue末尾或priority_queue中恰当的位置创建一个元素，其值为item，或者由args构造

deque支持在容器头尾位置的快速插入和删除，而且在两端插入或删除元素都不会导致重新分配空间。

《C++ Primer》笔记 第9章 顺序容器

相关推荐

《C++ Primer》笔记第9章顺序容器