C++学习笔记：顺序容器

9. 顺序容器

容器	特点
vector	动态扩容，提供随机访问。在容器的末尾插入数据开销小，在中间和开头插入数据开销大。
string	类似vector，动态扩容，提供随机访问，存储字符。
deque	双端队列，动态扩容，提供随机访问。在容器开头和结尾插入数据开销小。
list	双端链表，动态扩容，提供顺序访问。在链表的任何位置插入开销都很小。
forward_list	单向链表，动态扩容，提供顺序访问。在链表的任何位置插入开销都很小。(只保留指向下一个元素指针)
array	数组，固定大小，提供随机访问。不能添加和删除元素。

对于容器的选择，应该根据容器的特性，总体来说，遵循以下原则：

• 不确定大小，且大多在末尾插入（删除），则选择vector，vector一般是容器的首选
• 随机访问，选择deque或vector，如果需要在开头插入（删除）则选择deque
• 中间插入与删除，则选择list或forward_list，更低的开销则可以选择forward_list
• 固定大小，不添加和删除元素和选择array

如果遇到"随机访问且中间插入（删除）"，则应该考虑应用中插入（删除）与访问的比重，如果业务更在意读取，则可以牺牲插入（删除）性能。

deque结构

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。

为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址。

也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间

9.1 容器通用特性

9.1.1 容器的定义和初始化

// 用vector做为讲解，其他容器也支持同样的操作
vector<int> vec; // 定义一个默认初始化的容器，比如int，则用0初始化
vector<int> vec1(vec2); // 等价于：vector vec1 = vec2; // vec2必须与vec1是相同类型
vector<int> vec1{1, 2, 3}; // 等价于：vector<int> vec1 = {1, 2, 3}; // 用列表进行初始化，array
vector<int> vec1(b, e); // 使用迭代器进行拷贝
vector<int> vec1(10, -1); // 将容器使用10个-1进行初始化

// array比较特殊，不仅指出元素类型，还得指出array的size
array<int, 10>; // array初始化为10个0

将容器A拷贝为容器B时，如果A与B类型相同，比如容器是vector，元素的类型都是int，则可以通过vector<int> vec1(vec2)直接拷贝，否则需要使用迭代器，例如const char *可以通过vector<string> vec1(b, end)。

区别于内置数组[]，std::array支持数组拷贝

array<int, 2> int_arr1{1, 2};
array<int, 2> int_arr2 = int_arr1; // 直接拷贝int_arr1

对std::array进行列表赋值，由于std::array固定长度，只会修改其中的元素。如果是vector、list、deque等变长的容器，则会将整个容器的值修改为右边的列表。

如下面的代码所示，values = {1}，只会使得values[0] = 1，因为其是std::array，所以也不支持assign操作。

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

int main()
{
    array<int, 100> values = {0};
    vector<int> values2 = {1,2,3};
    values2 = {4};
    values = {1};
    cout << "输出values：" << endl;
    for(auto i: values)
    {
        cout << i << " ";
    }
    cout << endl;
    cout << "输出values2：" << endl;
    for(auto i: values2)
    {
        cout << i << " ";
    }
    cout << endl;
}

输出结果：

输出values：
1 0 0 0 0 0 0 0 0 0 
输出values2：
4 

9.1.2 容器的成员

// 以vector举例，其他容器相同
vector<int>::iterator iter; // 迭代器
vector<int>::const_iterator c_iter; // 不可变的迭代器
vector<int>::reverse_iterator r_iter; // 逆序迭代器
vector<int>::const_reverse_iterator const_r_iter; 

vector<int>::size_type size; // 同size_t
vector<int>::value_type val_type; // 元素类型
vector<int>::reference ref; // 元素引用
vector<int>::const_reference ref; // 不可变的元素引用
vector<int>::diffrence_type diff_type; // 带符号的整数，保存两个迭代器距离

在泛型编程中作用很大。

9.1.3 容器的函数

迭代器

// 1. 迭代器
v.begin(); // 指向首元素的迭代器
v.cbegin(); // 指向首元素的const迭代器
v.end(); // 指向尾后（尾元素之后）的迭代器
v.cend(); // 指向尾后（尾元素之后）的const迭代器

// 逆序遍历
v.rbegin(); v.rend();
v.crbegin(); v.crend();

所有的顺序容器都实现了递增运算符：++，其中forward_list不支持--。

只有vector、deque、string和array实现了算术运算符：+=1 -=1，forward_list与list没有实现，所以不支持。

元素的遍历一般通过：begin() != end()进行。

赋值与swap

swap(v1, v2); // 交换两个容器的元素内容，等价于v1.swap(v2)，一般常用第一种形式
v1.assign(b, e); // 将v1使用迭代器b和e替换
v1.assign(il); // 使用初始化列表赋值
v1.assign(n, t); // 使用n个值为t的元素替换

使用swap进行交换，速度极快（array除外，其使用的是拷贝），其交换的是内部数据结构（指针）。使用swap之后，会导致string容器的指针、迭代器和引用失效，其他容器则不会。

容器大小相关

v.size(); // 容器当前的元素数量
v.max_size(); // 容器能容纳最大数量的元素
v.empty(); // 当size==0，则返回true
v.capacity(); // 返回内存占用，动态容器根据内存管理算法进行分配，会根据策略减少申请内存的次数

forward_list为了极致效率，不包含size()和empty()。

9.2 容器的操作

9.2.1 访问元素

v.front(); // 返回容器中的首元素引用。如果容器为空，则导致segmentation fault
v.back(); // 返回容器中的尾元素引用。如果容器为空，则导致segmentation fault。不支持forward_list
v[n]; v.at(n); // 下标与at相同，但at在越界时会返回out_of_range错误

在使用访问方式时，最好先加上v.empty()进行判断。

9.2.2 添加元素

v.push_back(t); // 在尾部添加一个元素，返回void
v.emplace_back(args); // 在尾部添加一系列参数，然后调用元素的class构造函数，再存放到v，返回void

v.push_front(t);
v.emplace_front(args);

v.insert(p, t); // 在迭代器p指向的元素之前，添加一个元素t，返回新添加元素的迭代器
v.emplace(p, args);

v.insert(p, n, t); // 添加n个t，返回指向第一个t的迭代器。如果n=0，则返回p
v.insert(p, b, e); // 使用另一个容器的迭代器进行添加。b和e不能指向v本身的元素，如果范围为空，则返回p
v.insert(p, il); // 使用列表进行添加

上述操作不支持array，因为array的元素和大小不可变。back类型的操作不支持forward_list，因为它是单项链表，不支持向后操作。使用insert或emplace进行添加时，会导致vector、string和deque的指针、引用、迭代器失效。

9.2.3 删除元素

c.pop_back(); // 删除尾元素，如果c为空则会segment fault。返回void
c.pop_front(); // 删除首元素，同上

c.erase(p); // 删除迭代器指向的元素，返回该元素的下一个元素的迭代器。尾元素被删除，则返回尾后迭代器。如果元素是尾后迭代器，则会segment fault
c.erase(b, e); // 删除迭代器b到e（范围：[b, e) 前开后闭）范围的元素，返回被删的最后一个元素的下一个元素。如果e是尾后迭代器，则也返回尾后迭代器

c.clear(); // 删除c中的所有元素，返回void

c.pop_front不支持vector，string；c.pop_back不支持forward_list，并且其具有特殊的erase操作。对

删除deque的首尾之外的任何元素都会导致，对其的引用，指针和迭代器失效。删除vector，string的元素，会导致指向被删除元素之后的指针、引用、迭代器失效。

9.2.4 forward_list特殊操作

forward_list操作逻辑与单向链表相同，需要知道本元素的信息与指向本元素的指针信息，才能添加和删除元素。

lst.before_begin(); // 指向首元素之前不存在的位置，因此该迭代器不能解引用。
lst.cbefore_begin(); // 返回 const_iterator

lst.insert_after(p, t); // 在 p 指向的元素之后插入 t，返回指向 t 的迭代器
lst.insert_after(p, n, t);
lst.insert(p, il);
lst.insert(p, b, e); 

// 同样，还有 emplace_after(p, args)

lst.erase_after(p); // 删除 p 指定元素之后的元素，如果 p 是尾后迭代器，则 segment fault
lst.erase_after(b, e);

对forward_list的添加元素和删除元素，则需要考虑到前一个指针和当前指针。

9.2.5 改变容器大小

v.resize(n); // n是大小，用于将容器的 size 设置为 n。如果 n 小于当前 size，则会删除多余元素，如果 n 大于当前 size，则会使用元素的默认构造器，添加到 v 中
v.resize(n, t); // 将v 的 size 设置为 n，如果 n 大于 size，则用元素 t 填充，如果 n 小于 size 则只发生删除

对容器进行 resize，可能会导致迭代器等失效。

9.3 string

数字与字符串可以转换，通过to_string(13)可以转换为string s("13")。字符串也可通过stoi(s, p, b)，p 代表迭代器，b 代表进制(10 进制默认，8 进制，16 进制等等) 转换为整数。对用的还有 long、unsigned long、longlong、usigned long long、float、double、long double，例如：stold代表转换为 long double。

9.3.1 string 的其他拷贝、构造方法

string s(cp, n); // n 是长度，cp 是字符数组。拷贝前 n 个字符
string s(s1, pos1); // 从 s1 的 pos1 位置拷贝字符到结束，pos1>s1.size()会 segment fault
string s(s1, pos1, len1); // 从 s1 的 pos1 位置拷贝 len1 个字符。pos1>s1.size()会 segment fault，最多拷贝|s1.size() - len1|个字符

s.substr(pos);
s.substr(pos, n); // 返回一个字符串，从 pos 开始，长度为 n

9.3.2 查找字符、字符串

// 如果未找到则返回 npos，string::npos==-1，类型是 string::size_type
size_t find (const string& str, size_t pos = 0) const noexcept;	
size_t find (const char* s, size_t pos = 0) const;
size_t find (const char* s, size_t pos, size_type n) const;
size_t find (char c, size_t pos = 0) const noexcept;

// 相似的函数还有以下 4 个，参数与上一致
find_first_of; // 查找 s 中 args 任何一个字符第一次出现的位置
find_first_not_of; // 查找 s 中第一个不在 args 中的字符
find_last_of; // 查找 s 中args 任何一个字符最后一次出现的位置
find_last_not_of; // 查找 s 中最后一个不在 args 中的字符

9.3.3 添加和替换

append返回一个指向字符串 s 的引用。

string& append (const string& str);
string& append (const string& str, size_t subpos, size_t sublen); // str中 pos 位置开始的 len 个字符，添加到 string
string& append (const char* s);
string& append (const char* s, size_t n);
string& append (size_t n, char c);
string& append (initializer_list<char> il);
string& append (InputIterator first, InputIterator last);

// replace的 args 部分的参数与 append 相同
s.replace(range, args); //将范围 range 的字符删除，替换为 args 指定的字符

由于标准库的 replace 不支持：replace("xxx", "xxxx")操作，所以需要自己写一个 replace_all函数。

void replaceAll(std::string& str, const std::string& from, const std::string& to) {
    size_t start_pos = 0;
    while ((start_pos = str.find(from, start_pos)) != std::string::npos) {
        str.replace(start_pos, from.length(), to);
        start_pos += to.length(); // 继续搜索下一个位置
    }
}

9.3.4 比较字符

s.compare函数返回 0，正数，负数之一，0 表示两个字符串比较的部分相同。

// s与 str 对比
int compare (const string& str) const noexcept; 

//s 从 pos 长度为 len的字符与 str 比
int compare (size_t pos, size_t len, const string& str) const; 

// s 从 pos 长度为 len的字符与 str 从 subpos 长度为 sublen 的字符比
int compare (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen) const;

// 与字符数组比
int compare (const char* s) const;int compare (size_t pos, size_t len, const char* s) const;

// 与字符数组开始位置，长度为 n 的字符
int compare (size_t pos, size_t len, const char* s, size_t n) const;

9.4 容器适配器

适配器(adaptor)是一种设计模式，可以将容器对象转换为客户端希望的另一个接口，例如：stack，从而获得标准的先进后出接口：push、pop等。

顺序容器拥有3个适配器：stack、queue和priority_queue。其中，stack和queue在默认构造函数下，是基于deque容器实现的，priority_queue是基于vector容器实现的。对于非默认实现的容器，需要在定义时，重载容器类型。

stack<int> int_stack; // 定义一个基于deque实现的空栈
stack<int> int_stack(v); // 定义一个基于deque的栈，使用容器deque<int> v填充
stack<int, vector<int>> int_stack(int_vector); // 定义一个基于vector的栈，使用vector<int> 填充

3个适配器默认支持以下类型和操作：

value_type;
size_type;
container_type; // 返回基于何种容器实现的
关系运算符：> < = != 等;
a.empty();
a.size();
swap(a, b); // 同 a.swap(b)

stack特有操作：

s.push(t);
s.emplace(args);
s.pop();
s.top();

queue 特有操作：

q.pop();
q.front();
q.back();
q.push(t);
q.emplace(args);

priority_queue 特有操作(基于vector实现，由于是优先级队列，在方法的定义上没有back())：

pq.pop();
pq.front();
pq.push(t); // 根据优先级放入到合适的位置
pq.emplace(args);
pq.top(); // 返回优先级最高的元素

由priority_queue可知，push的过程涉及到排序和重新插入，涉及到多次随机访问与更简化的内存管理，加之不需要两端操作，所以从内存的连续性和访问的随机性上来看，vector确实比deque更适合priority_queue。