C++Primer学习笔记09.顺序容器
### -顺序容器主要靠刷题来熟悉容器的用法。
### 概述
所有顺序容器都提供了快速顺序访问元素的能力。
| 容器类型 | 说明 |
| -------------- | ----------------------------------------------------------------- |
| vector | 可变长数组，在尾部之外的位置插入、删除元素可能很慢。 |
| deque | 双端队列，支持快速随机访问。头尾插入删除元素很快。 |
| list | 双向链表，只支持顺序范围，说是说在任意位置插入删除都很快。 |
| forward_list | 单向链表，只支持单向顺序访问，说是说在任意位置插入删除都很快。|
| array | 固定大小数组。支持快速随机访问。 |
| string | 与 vector 相似，专门用于保存字符。随机访问快。尾部插入/删除快。 |
除了固定大小的 array 外，其他容器都提供高效、灵活的内存管理。我们可以添加和删除元素，扩张和收缩容器的大小。
<b>容器的选取</b>
- <span style="color:red">除非有很好的理由选择其他容器，否则应使用 vector。</span>
- 如果程序有很多小的元素，且空间的额外开销很重要，则不要使用 list 或 forward_list。
- 如果程序要求随机访问元素，应使用 vector 或 deque。
- 如果程序要求在容器的中间插入或删除元素，应使用 list 或 forward_list。
- 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用 deque。
<span style="color:red">如果你不确定应该使用哪种容器，那么可以在程序中只使用 vector 和 list 公共的操作：使用迭代器，不使用下标操作，避免随机访问。这样，在必要时选择使用 vector 或 list 都很方便。</span>
### 概览
大多数的容器都实现了某些通用的功能，少数方法是个别容器特有的。此处先介绍所有容器的通用功能。
<b>容器初始化的限制</b>
声明一个指定类型容器的大小时要确保该类型的对象可以被默认初始化，否则会报错。因为指定了容器大小时，需要用该类型的数据对容器进行填充。
```cpp
#include <iostream>
#include <vector>
using namespace std;
class noDefault {
public:
noDefault(int i) {
cout << "noDefault " << i << endl;
}
};
class Default {
public:
Default() = default;
};
void initVector() {
// 正确，指定初始大小为0，并给与默认值 0 填充。
vector<int> vec(10);
for (auto w: vec) {
cout << w << "\t";
}
// 错误，无法对 noDefault 进行默认初始化，它没有默认构造方法
// vector<noDefault> vecC(10);
// 正确，提供了noDefualt 构造方法需要的参数，可以进行隐式类型转换
vector<noDefault> vecC(10,10);
// 正确，可以对 Default 进行默认初始化，有默认构造方法
vector<Default> vecC2(10);
}
int main() {
initVector();
return 0;
}
```
<div align="center"><h6>容器的通用操作</h6></div>
| 类型别名 | 说明 |
| -------------------- | --------------------------------------------------------------------------------------------------------------------------- |
| iterator | 容器类型的迭代器类型 |
| const_iterator | 可读取元素，但是不可修改元素的迭代器 |
| size_type | 无符号整数，容器最大的大小 |
| difference_type | 带符号整数，保存两个迭代器直接的拒了 |
| value_type | 元素类型 |
| reference | 元素的左值；与 value_type 含义相同 |
| const_reference | 元素的 const 左值类型，即 const_value_type& |
| <b>构造函数</b> | <b>说明</b> |
| C c; | 默认构造函数，初始化一个空容器 |
| C c1(c2) | 用 c2 的元素初始化 c1，如果 c2 中的数据是对象，会触发对象的拷贝构造 |
| C c(b, e) | 将迭代器 begin 和 end 范围内的元素拷贝给 c |
| CC{a, b, c, ...} | 列表初始化，也会触发拷贝构造，如 vector\<Default\> v{Default()}; <br>会先构造出 Default 对象，再把 Default 对象拷贝给容器 |
| <b>赋值与 swap</b> | <b>说明</b> |
| c1 = c2 | 用容器 c2 中的元素初始化 c1，会触发拷贝构造 |
| c1 = {a, b, c}; | 列表初始化，会触发拷贝构造 |
| a.swap(b) | 交换容器 a 和 b 内部的数据结构，不会触发容器内元素的拷贝构造 |
| swap(a, b) | 同上 |
> 测试 vector 初始化、赋值、swap 的代码
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Default {
public:
Default() = default;
Default(const Default &obj) {
cout << "触发拷贝构造" << endl;
};
};
void initVector() {
vector<Default> vec1(2);
//触发拷贝构造
// vector<Default> vec2(vec1);
// 触发拷贝构造
vector<Default> vec3{Default()};
}
void swapVector(){
vector<Default> c1(1);
// 触发拷贝构造
// vector<Default> c2 = c1;
// 触发拷贝构造
// vector<Default> c3 = {Default()};
vector<Default>c4(2);
// 只是交换内部的数据结构，不会触发容器中对象的拷贝
c4.swap(c1);
cout<<c4.size()<<endl; //1
swap(c1,c4);
cout<<c4.size()<<endl; //1
}
int main() {
swapVector();
return 0;
}
```
| 添加/删除元素 | 说明 |
| ---------------------------- | ----------------------------------------------------------------------------------------------- |
| c.insert(position, args) | 将 args 拷贝</b>进 c<br>如果是对象的隐式类型转换<span style="color:red">会触发拷贝构造</span> |
| c.emplace(position, inits) | 将 inits 拷贝进 c<br>如果是对象的隐式类型转换<span style="color:red">不会触发拷贝构造</span>|
| c.erase(start, end) | 删除指定区间的元素，左闭右开 |
| c.clear() | 删除 c 中的所有元素，返回 void |
| <b>关系运算符</b> | <b>说明</b> |
| ==, != | 所有容器都支持 |
| <, <=, >, >= | 无需关联容器不支持 |
| <b>获取迭代器</b> | <b>说明</b> |
| c.begin(), c.end() | 指向首元素和尾部元素之后位置的迭代器 |
| c.cbegin(), c.cend() | 返回 const_iterator |
| <b>反向容器</b> | <b>说明，不支持 forward_list</b> |
| reverse_iterator | 按逆序寻址元素的迭代器 |
| const_reverse_iterator | const |
| c.rbegin(), c.rend() | 返回指向 c 的尾部元素和首元素之前位置的迭代器 |
| c.crbegin(), c.crend() | 返回 const_reverse_iterator |
> 测试添加删除元素的代码
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Default {
public:
Default() = default;
Default(int i) {}
Default(const Default &obj) {
cout << "触发拷贝构造" << endl;
};
~Default() {
cout << "析构" << endl;
}
};
void insertVector() {
vector<Default> c1(1);
vector<Default> c2(3);
// 触发两次拷贝构造
c1.insert(c1.end(), c2);
c1.emplace(c1.end(), c2);
cout << c1.size() << endl; // 3
cout << "=================" << endl;
// 左闭右开，触发了两个对象的析构
c1.erase(c1.begin(), c1.begin() + 2);
cout << "=================" << endl;
cout << c1.size() << endl; // 1
// 不触发拷贝构造
c1.emplace(c1.end(), 1);
c1.insert(c1.end(), 1);
cout << "=================" << endl;
// 触发三次析构，三个对象都被 delete 了
c1.clear();
cout << "=================" << endl;
}
int main() {
insertVector();
return 0;
}
```
#### 迭代器
用迭代器指定迭代范围时，遍历的区间是左闭右开。
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main() {
vector<int> vec{1, 2, 3, 4, 5, 6, 7};
vector<int>::iterator beg = vec.begin();
vector<int>::iterator end = vec.end();
cout << "==========" << endl;
// vector 的内存空间是连续的，没问题，但是不推荐
// 推荐用 beg!=end
while (beg < end) {
cout << *beg++ << endl;
}
cout << "===== != =====" << endl;
list<int> lst1;
auto liter1 = lst1.begin();
auto liter2 = lst1.end();
// 错误，list 的内存空间不是连续的，不能这样比较
// list 内部的迭代器无法用 < > 比较
while (liter1<liter2){
}
return 0;
}
```
除了迭代器，容器内部还有许多其他的类型成员：size_type, iterator, const_iterator, difference_type 等。
#### 容器定义和初始化
每个容器类型都定义了一个默认构造函数，除了 array 之外，其他容器的默认构造函数都会创建一个指定类型的空容器，而 array 创建时需要指定大小。
| 定义和初始化 | 说明 |
| ------------------ | --------------------------------------------------------------------------------------------------------------------------- |
| C c; | 默认构造函数，初始化一个空容器 |
| C c1(c2) | 用 c2 的元素初始化 c1，如果 c2 中的数据是对象，会触发对象的拷贝构造 |
| C c(b, e) | 将迭代器 begin 和 end 范围内的元素拷贝给 c |
| CC{a, b, c, ...} | 列表初始化，也会触发拷贝构造，如 vector\<Default\> v{Default()}; <br>会先构造出 Default 对象，再把 Default 对象拷贝给容器 |
| c1 = c2 | 用容器 c2 中的元素初始化 c1，会触发拷贝构造，array 还要求两个容器大小一样。 |
| c1 = {a, b, c};| 列表初始化，会触发拷贝构造 |
| C seq(n) | -- |
| C seq(n, t) | -- |
<b>array 具有固定的大小</b>
```cpp
array<int, 40> arr; // 容量为 40，保存 int 类型的数据
array<int, 40>::size_type; // array 的类型成员
array<int>::size_type; // 错误！需要指定容量！
```
<span style="color:red">容量大小是 array 的一部分。</span>
#### 赋值和swap
需要注意下 array 的赋值操作。
```cpp
array<int, 10> a1 = {0,1};
array<int, 10> a2 = {0};
a1 = a2; // 用 a2 的元素替换 a1 的元素
a2 = {0}; // 错误，不能将一个花括号列表赋予数组。测试了下，正常运行，，
```
> 容器赋值运算
由于右边运算对象的大小可能和左边运算对象的大小不一样，因此 array 类型不支持 assign，也不允许使用花括号包围的值列表进行赋值。<span style="color:orange">我本地测的是可以用花括号~的。不知是不是 C++ 版本的问题。</span>
```cpp
#include <iostream>
#include <array>
using namespace std;
int main() {
array<int, 8> a;
a = {1, 2, 3, 4, 5};
// 1 2 3 4 5 0 0 0
for (auto w: a) cout << w << "\t";
return 0;
}
```
| <b>赋值与 swap</b> | <b>说明</b> |
| -------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------- |
| c1 = c2 | 用容器 c2 中的元素初始化 c1，会触发拷贝构造 |
| c1 = {a, b, c}; | 列表初始化，会触发拷贝构造 |
| a.swap(b) | 交换容器 a 和 b 内部的数据结构，不会触发容器内元素的拷贝构造 |
| swap(a, b) | 同上 |
| seq.assign(b, e) | 将 seq 中的元素替换为迭代器 b 和 e 所表示的范围中的元素。b 和 e 不能指向 seq 中的元素。<span style="color:red">array 无 assign 方法。</span> |
| seq.assign(l1) | 将 seq 中的元素替换为 l1 中的元素 |
| seq.assign(n, t) | 将 seq 中的元素替换为 n 个值为 t 的元素 |
```cpp
#include <iostream>
#include <vector>
#include <list>
#include <array>
using namespace std;
int main() {
vector<int> vec{1, 2, 3, 4, 5};
array<int, 5> avec{11, 21, 31, 41, 51};
vec.assign(avec.begin(), avec.end());
// 11 21 31 41 51
for (auto w: vec) cout << w << "\t";
return 0;
}
```
swap 操作只是交换两个容器内部的数据结构，元素本身并未交换，因此速度非常快。<span style="color:orange">元素不会被移动意味着，指向容器的迭代器、引用和指针再 swap 操作后都不会失效，它们仍然指向之前的元素（失效只是说指针的指向改变了？）</span>
但是，swap 对 array 进行操作时，swap 会对元素进行拷贝、删除或插入！
> 书中的内容，目前不是很明白
元素不会被移动的事实意味着，除 string 外，指向容器的迭代器、引用和指针在 swap 操作之后都不会失效。它们仍指向 swap 操作之前所指向的那些元素。但是，在 swap 之后，这些元素已经属于不同的容器了。例如，假定 iter 在 swap 之前指向 svec1 的 string，那么在 swap 之后它指向 svec2 的元素。与其他容器不同，对一个 string 调用 swap 会导致迭代器、引用和指针失效。
与其他容器不同，swap 两个 array 会真正交换它们的元素。因此，交换两个 array 所需的时间与 array 中元素的数目成正比。
因此，对于 array，在 swap 操作之后，指针、引用和迭代器所绑定的元素保持不变，但元素值已经与另一个 array 中对应元素的值进行了交换。
页:
[1]