【C++Primer笔记】第九章顺序容器

Myth丶恋晨 2022-10-30 14:24 147阅读 0赞

（本章笔记作为编程参考）

> 一个容器就是一些特定类型对象的集合。
> 
> 顺序容器的存储访问与加入容器时的位置对应；有序和无序关联容器则根据关键字的值来存储元素。

### 文章目录 ###

*   *  顺序容器概述
     *   *  选择容器的基本原则
     *  容器库概览
     *   *  容器公共操作
         *  迭代器
         *  容器定义和初始化
         *  赋值和swap
     *  顺序容器操作
     *   *  添加元素
         *  访问元素
         *  删除元素
         *  特殊的forward\_list操作
         *  改变容器大小
         *  容器操作可能使迭代器失效
     *  额外的string操作
     *   *   *  构造string的其他方法
             *  改变string的其他方法
             *  string搜索操作
             *  compare函数
             *  数值转换
     *  容器适配器
     *   *   *  容器适配器都支持的操作和类型
             *  定义一个适配器
             *  栈适配器
             *  队列适配器

## 顺序容器概述 ##

回顾数据结构，每个顺序容器（顺序表、队列、链表等）都有利有弊：是否支持随机访问、插入元素是否快速。

*  `vector`：可变大小数组，支持快速随机访问。**在尾部之外的位置插入或删除元素可能很慢**
 *  `deque`：双端队列，支持快速随机访问。**在头尾位置插入/删除速度很快**
 *  `list`：双向链表，**只支持双向顺序访问**，在`list`中任意位置进行插入/删除都很快（链表有额外内存开销）
 *  `forward_list`：单向链表，**只支持单向顺序访问**，在链表任何位置进行插入/删除都很快，不能使用`size`
 *  `array`：固定大小数组，支持快速随机访问，**不能添加或者删除元素**。相比于内置数组，是**更安全、更易使用**的数组类型
 *  `string`：**和`vector`相似**，但只用于保存字符，随机访问快，在尾部插入/删除速度快

### 选择容器的基本原则 ###

*  除非你有很好的理由选择其他容器，否则使用`vector`是最好的选择
 *  如果你的程序有很多很小的元素，且空间的额外开销很重要，那么不要使用`list`和`forward_list`
 *  如果程序要求随机访问元素，那么使用`vector`和`deque`
 *  如果程序要求在容器的中间插入或者删除元素，应使用`list`或`forward_list`
 *  如果程序只需要在头尾位置插入或者删除元素，但不会在中间位置进行插入或删除操作，则使用`deque`
 *  如果程序只有在读取输入时才需要在容器中间插入元素，那么你有两种做法：一是使用`vector`添加元素，然后调用标准库的`sort`重排；二是在输入阶段使用`list`，一旦输入完成，将`list`中的内容拷贝到一个`vector`中

## 容器库概览 ##

每个容器都定义在同名头文件中。

如果我们定义一个容器，其元素类型是另一个类型，要注意特殊操作是否能使用（如`vector<noDefault> v(10);`中，如果noDefault没有默认构造函数，将是不合法的）。

### 容器公共操作 ###

**类型别名**（必须使用作用域运算符，如`vector<int>difference_type count`）

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

**构造函数**

C c; //默认构造函数, 构造空容器
    C c(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中的元素替换为列表中元素（array不可）
    swap(a, b); //交换a和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.clear(); //删除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.crbegin(), c.crend() //返回const_reverse_iterator

### 迭代器 ###

容器迭代器都支持解引用、递增、递减（除`forward_list`外）、相等/不等运算。

只有`vector`、`deque`、`array`、`string`支持加减（加/减上一个整数或一个迭代器）算术运算和不等号比较。

一个**迭代器范围**由一对迭代器（`begin`和`end`）表示。该范围包含：从`begin`开始到`end`之前的一个元素，即：\[begin, end).

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

当不需要写访问时，应该使用`cbegin`和`cend`。

### 容器定义和初始化 ###

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。**不过当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，新容器内的元素类型只要能转换成初始化容器的元素类型即可**。

list<string> authors = {"Milton", "Shakespeare", "Austen"};
    vector<const char*> articles = {"a", "an", "the"};
    
    // 拷贝方式一：直接拷贝整个容器, 要求容器类型和元素类型都必须相同
    list<string> list2(authors);    // 正确: 类型匹配
    vector<string> words(articles); // 错误: 类型不匹配
    
    // 拷贝方式二：传递迭代器参数来拷贝一个范围
    // 正确: 可以将const char* 元素转换为string
    forward_list<string> words(articles.begin(), articles.end());

只有顺序容器才支持大小参数，关联容器不支持：

C seq(n)    // seq包含n个元素, 这些元素进行了值初始化; 此构造函数是explicit的(string不适用)
    C seq(n,t)  // seq包含n个初始化为t值得元素

定义一个`array`时，除了制定元素类型，还要指定容器大小：

array<int, 10> ia1;   // 10个默认初始化的int
    array<int, 10> ia2 = {42}; // ia3[0]为42, 剩余元素为0
    ia2 = {0}; //错误，不允许将花括号列表赋值array（见下）

虽然我们不能对内置数组赋值或拷贝，但是`array`并无此限制。

### 赋值和swap ###

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

## 顺序容器操作 ##

### 添加元素 ###

*  `c.push_back(t), c.emplace_back(args)`：在`c`的尾部创建一个值为`t`或者由`args`创建的元素
 *  `c.push_front(t), c.emplace_front(args)`：在`c`的头部创建一个值为`t`或者由`args`创建的元素（`vector`和`string`不支持）
 *  `c.insert(p,t), c.emplace(p, args)`：\*\*在迭代器`p`指向的元素之前\*\*创建一个值为`t`或由`args`创建的元素。**返回指向新添加的元素的迭代器**
 *  `c.insert(p,n,t)`：在迭代器`p`指向的元素之前插入`n`个值为`t`的元素，返回指向新添加的**第一个元素**的迭代器
 *  `c.insert(p,b,e)`：将迭代器`b`和`e`指定范围内的元素插入到迭代器`p`指向的元素之前，返回指向新添加的**第一个元素**的迭代器
 *  `c.insert(p,il)`：将花括号包起来的元素值列表插入到迭代器`p`指向的元素之前，返回新添加的第一个元素的迭代器

当调用`push`或者`insert`成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个`emplace`成员函数时，则是将参数传递给元素类型的构造函数。**`emplace`成员使用这些参数在容器管理的内存空间中直接构造元素**。

注意：

*  将元素插入到`vector`、`deque`和`string`的任何位置都是合法的，但是会很**耗时**
 *  向`vector`、`deque`和`string`插入元素会使所有指向容器的迭代器、指针、引用失效
 *  使用`insert`的返回值：
    
        list<string> lst;
        auto iter = lst.begin();
        while (cin >> word)
            iter = lst.insert(iter, word); //等价于push_front

### 访问元素 ###

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

可以用迭代器解引用访问元素，也可以直接用`front`和`back`。注意：`end`迭代器指向的是尾后元素，要解引用必须先`--`。

**在调用`front`和`end`之前，必须确保容器非空！！**

以下都是返回引用（容器是`const`对象则返回`const`的引用）：

*  `c.back()`：返回`c`中尾元素的引用, 如果`c`为空则函数行为未定义
 *  `c.front()`：返回`c`中首元素的引用, 如果`c`为空则函数行为未定义
 *  `c[n]`：返回第`n`个元素的引用, 如果`n>=c.size()`则函数行为未定义（链表不可随机访问）
 *  `c.at(n)`：返回第`n`个元素（从0开始）的引用, 如果下标越界则抛出`out_of_range`异常（链表不可随机访问）

使用`auto`时记得加上`&`。

### 删除元素 ###

*  `c.pop_back()`：删除`c`中尾元素, 若`c`为空则函数行为未定义，返回`void`
 *  `c.pop_front()`：删除`c`中首元素, 若`c`为空则函数行为未定义返回`void`（`vector`和`string`不支持）
 *  `c.erase(p)`：删除迭代器`p`指向的元素, **返回一个指向被删元素之后元素的迭代器**
 *  `c.erase(b,e)`：删除迭代器`b`和`e`所指定范围内的元素, 返回一个指向最后一个被删除元素之后元素的迭代器
 *  `c.clear()`：删除`c`中所有元素

### 特殊的forward\_list操作 ###

在链表中添加或删除元素（不适用于`array`），是通过改变给定元素之后的元素来完成的。所以`forward_list`返回首前迭代器。

*  `lst.before_begin(), lst.cbefore_begin()`：返回指向链表首元素之前不存在的元素的迭代器，此迭代器不能解引用
 *  `lst.insert_after(p,t),lst.insert_after(p,n,t),lst.insert_after(p,b,e),lst.insert_after(p,il)`：在迭代器`p`之后的位置插入元素，返回一个指向最后一个插入元素的迭代器
 *  `emplace_after(p,args)`：使用`args`在`p`指定的位置之后创建一个元素，返回一个指向这个新元素的迭代器
 *  `lst.erase_after(p), lst.erase_after(b,e)`：删除元素，返回一个指向被删元素之后元素的迭代器

### 改变容器大小 ###

除了`array`外我们可以使用`resize()`来增加或者缩小容器（不适用于`array`）。如果当前大小小于所要求的大小，容器后面的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部。

*  `c.resize(n)`和`c.resize(n,t)`

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

**保证每次改变容器的操作后都正确地重新定位迭代器！！**（尤其是对于`vector`、`deque`、`string`）

不要在循环开始前保存`end`迭代器。

**容器大小管理操作**：

*  `c.shrink_to_fit()`：将`capacity()`减少为与`size()`相同大小（只适用于`vector`、`string`和`deque`）
 *  `c.capacity()`：不重新分配内存空间的话，`c`可以保存多少元素（只适用于`vector`、`string`）
 *  `c.reserve(n)`：分配至少能容纳`n`个元素的内存空间（永远不会减少空间）（只适用于`vector`、`string`）

和`resize`区别：只改变容量，不改变元素个数。

## 额外的string操作 ##

> 本节初次阅读可能令人感到心烦，读者只需快速浏览。

#### 构造string的其他方法 ####

*  `string s(cp,n)`：`s`是`cp`指向的数组前`n`个字符的拷贝，此数组至少应该包含`n`个字符
 *  `string s(s2,pos2)`：`s`是`string s2`从下标`pos2`开始的字符的拷贝
 *  `string s(s2,pos2,len)`：`s`是`sting s2`从下标`pos2`开始`len2`个字符的拷贝
 *  `s.substr(pos,n)`：返回一个`string`，包含`s`中从`pos`开始的`n`个字符的拷贝

#### 改变string的其他方法 ####

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

*  `s.insert(pos,args)`：在`pos`之前插入`args`指定的字符，`pos`可以是一个下标或一个迭代器，接受下标的版本返回一个指向`s`的引用，接受迭代器的版本返回指向第一个插入字符的迭代器
 *  `s.erase(pos,len)`：删除从`pos`位置开始的`len`个字符，返回指向`s`的引用
 *  `s.append(args)`：将`s`中的字符替换为`args`的字符，返回一个指向`s`的引用
 *  `s.replace(range,args)`： 删除`s`中范围`range`内的字符，替换为`args`指定的字符。`range`或者是一个下标和一个长度，或者是一对指向`s`的迭代器。返回`s`的引用

上面提到的`args`可以是一下形式之一：

*  `str`：字符串`str`
 *  `str,pos,len`：`str`从`pos`开始最多`len`个字
 *  `cp,len`：从`cp`指向的字符数组的前（最多）`len`个字符
 *  `cp`：`cp`指向的以空字符结尾的字符数组
 *  `n,c`：`n`个字符`c`
 *  `b,e`：迭代器`b`和`e`指定的范围内的字符
 *  `初始化列表`：花括号包围的，以逗号分割的字符列表

注意：

*  `assign`总是**替换**`string`中的所有内容
 *  `append`总是将新字符**追加**到`string`的末尾
 *  `replace`函数提供了两种指定删除元素范围的方式：即可以通过一个位置和一个长度来指定范围，也可以通过一个迭代器范围来指定
 *  `insert`函数允许我们使用两种方式来指定插入点：用一个下标或者一个迭代器，两种方式下新元素都会插入到给定下标之前的位置

#### string搜索操作 ####

`string`类提供了`6`个不同的搜索函数，每个搜索操作返回一个`string::size_type`值，表示匹配发生位置的下标。如果搜索失败则返回一个名为`string::npos`的`static`成员。搜索操作包括：

*  `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`风格字符串，`pos`默认为`0`
 *  `cp,pos,n`：从`s`中位置`pos`开始查找指针`cp`指向的数组的前`n`个字符, `pos`和`n`无默认值

#### compare函数 ####

类似于`strcmp`函数，根据`s`是等于、大于还是小于参数指定的字符串，`s.compare`返回`0`、正数或者负数。根据我们是要比较两个`string`还是一个`string`与一个字符数组，我们可以将`compare`划分为`6`个版本：

*  `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`中第一个非空白符必须是数值中可能出现的字符，如果`string`不能转换为一个数值，否则这些函数会抛出一个`invalid_argument`的异常。

*  `to_string(val)`：一组重载函数，返回数值`val`的`string`表示。
 *  `stoi(s,p,b),stol(s,p,b),stoul(s,p,b),stoll(s,p,n),stoull(s,p,b)`：返回`s`的起始子串（表示整数内容）的数值，返回值分别是`int`、`long`、`unsigned long`、`long long`、`unsigned long long`。`b`表示转换所用的基数，默认值为`10`。`p`是`size_t`指针，用来保存`s`中第一个非数值字符的下标，默认为`0`，即不保存下标
 *  `stof(s,p),stod(s,p),stold(s,p)`：返回`s`的起始子串（表示浮点数）的数值，返回值类型分别是`float`、`double`或者`long double`。参数`p`的作用同上

## 容器适配器 ##

标准库定义了三个顺序容器适配器：`stack`、`queue`和`priority_queue`。例如`stack`适配器接收一个顺序容器（除`array`或`forward_list`外），并使其操作起来像一个`stack`一样。

#### 容器适配器都支持的操作和类型 ####

*  `size_type`：一种类型，足以保存当前类型的最大对象的大小
 *  `value_type`：元素类型
 *  `container_type`：实现适配器的底层容器类型
 *  `A a`：创建一个名为`a`的空适配器
 *  `A a(c)`：创建一个名为`a`的适配器，带有容器`c`的一个拷贝
 *  `关系运算符`：每个适配器都支持所有关系运算符`==, !=, <, <=, >, >=`
 *  `a.empty()`：判断`a`是否包含元素
 *  `a.size()`：返回`a`的元素数目
 *  `swap(a,b), a.swap(b)`：交换`a`和`b`的内容，`a`和`b`必须有相同类型，包括底层容器类型也必须相同

#### 定义一个适配器 ####

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，或接受一个容器的构造函数拷贝该容器来初始化适配器。默认情况下，`stack`和`queue`是基于`deque`实现的，`priority_queue`是基于`vector`实现的。但我们也可以通过在创建一个适配器时将一个命名的顺序容器作为第二个类型参数来重载默认容器类型。

//在vector上实现的空栈
    stack<string, vector<string>> str_stk;
    //str_stk2在vector上实现，初始化时保存svec的拷贝
    stack<string, vecotr<string>> str_stk2(svec);

#### 栈适配器 ####

> 栈默认基于`deque`实现，也可以再`list`或者`vecotr`上实现

*  `s.pop()`：删除栈顶元素，但不返回该元素值
 *  `s.push(item)`：创建一个新元素压入栈顶，通过拷贝或者移动`item`而来
 *  `s.emplace()`：创建一个新元素压入栈顶，该元素通过`args`构造
 *  `s.top()`：返回栈顶元素，但不将该元素弹出栈

#### 队列适配器 ####

> `queue`默认基于`deque`实现，也可以用`list`和`vecotr`实现。`priority_queue`默认基于`vector`实现，也可以用`deque`实现。

*  `q.pop()`：删除`queue`的首元素或`priority_queue`的最高优先级元素，但不返回此元素
 *  `q.front()`：返回首元素，但不删除此元素
 *  `q.back()`：只适用于`queue`，返回尾元素
 *  `q.top()`：返回最高级元素，但不删除该元素，只适用于`priority_queue`
 *  `q.push(item), q.emplace(args)`：在`queue`末尾或`priority_queue`中恰当的位置创建一个元素，其值为`item`，或者由`args`构造