C++Primer笔记-第九章：顺序容器

前言

该系列是《C++Primer第五版》的笔记，包含本人认为值得记录和整理的主要的知识点，并不是全部内容，也不是具体的内容。
该系列文章的作用应该是作为复习或预习的参考，有哪些知识点忘记或想学，可以大致浏览下该文章，然后再去书中寻找详细解答。（本系列文章基本是按书本顺序罗列的知识点，便于大家去书中寻找）
所以看该文章前，需要有一定的C++基础，否则阅读起来可能有困难。

本文大致整理了第九章的知识点，涉及到C++关于顺序容器类的重要知识，属于STL中比较基础的部分，需要重点掌握。

链接目录

• 第二章：变量与基本类型
• 第三章：字符串、向量和数组
• 第四章：表达式
• 第五章：语句
• 第六章：函数
• 第七章：类
• 第八章：IO库
• 第九章：顺序容器
• 第十章：泛型算法
• 第十一章：关联容器
• 第十二章：动态内存
• 第十三章：拷贝控制
• 第十四章：重载运算与类型转换
• 第十五章：面向对象程序设计
• 第十六章：模板与泛型编程
• 第十七章：标准库特殊设施
• 第十八章：用于大型程序的工具
• 第十九章：特殊工具与技术

顺序容器库概述

通常vector是最好的选择，除非有很好的理由选择其他容器。

容器均为模板类，必须提供额外信息(类型信息)来生成特定的容器类型。

对容器可以保存的元素类型的限制：

• 对于某些没有默认构造函数的类

//noDefault没有默认构造函数，此时构造vector不能只提供元素数目参数
vector<noDefault> v1(10, init);//正确，init是元素初始化器
vector<noDefault> v2(10);//错误，必须提供初始化

这里罗列了部分常用的容器类操作，更详细的表格在书中有，这里就不展开了。

顺序容器的迭代器

需要注意迭代器的范围
迭代器范围：[begin, end)

容器定义和初始化

将一个容器初始化为另一个容器的拷贝：

• 两个容器的类型及其元素类型必须匹配。
• 当传递迭代器参数来拷贝时，可以不同。

list<string> authors = {"M", "S", "A"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors);
deque<string> authList(authors);//错误：容器类型不匹配怕
//正确，元素类型可转换
forward_list<string> words(articles.begin(), articles.end());

标准库array具有固定大小：

array<int, 42> arr;//类型为int的含有42个元素的数组

array<int, 42> arr2 = arr;//正确，数组类型匹配，但内置数组不支持

赋值和swap

c1 = c2;//将c1的内容替换为c2中元素的拷贝
c1 = {a, b, c};//赋值后c1的大小为3

//对array特殊，因为大小不可改变
array<int, 3> a1 = {1, 2, 3};
a1 = {0};//数组成员全为0
a1 = {4};//数组成员为4、0、0

容器赋值运算：

使用assign：相比用=赋值，assign允许类型不同但能转换的类型进行赋值。

list<string> names;
vector<const char*> old;
names = old;//错误，类型不匹配
names.assign(old.cbegin(), old.cend());//正确

使用swap：元素本身并未交换，实际交换指针，不进行拷贝删除或插入操作，所以使用swap能够节省复制的开销。

vector<string> vec1(10);
vector<string> vec2(24);
swap(vec1, vec2);//交换后vec1包含24个string，vec2包含10个

向顺序容器添加元素

insert函数返回新插入的第一个元素的迭代器。

注意！向一个vector、string或deque插入元素可能会使所有指向容器的迭代器、引用和指针失效。

• push_back：除了array和forwar_list外，每个顺序容器都支持。
• push_front：list、forward_list和deque支持，将元素插入容器头部。

在容器特定位置添加元素：

//在vec.begin()之前插入"hello"
vec.insert(vec.begin(), "hello");
//在vec.end()之前插入十个"hello"
vec.insert(vec.end(), 10, "hello");
//将后两个迭代器范围内的元素插入到第一个迭代器之前
//后两个迭代器不能是要插入容器自身的迭代器
vec.insert(vec.begin(), vec2.begin(), vec2.end());
//在迭代器前插入列表元素
vec.insert(vec.begin(), {"a", "b"});

使用insert的返回值：返回插入新元素的迭代器。

while(cin >> word){
	iter = lst.insert(iter, word);
}

使用emplace操作：直接在容器的内存空间中构造对象而不是拷贝对象。

//参数列表是构造容器c中类型的参数
c.emplace_back("999", 25, 16.6);
c.emplace_back();//调用容器元素类型的默认构造函数
c.emplace(iter, args);//第一个参数是迭代器，后续参数是构造函数所需的参数
c.emplace_front();

访问元素

访问前需要确保容器内有元素，否则访问结果是未定义的。

if(!c.empty()){
	auto val = *c.begin;
}

访问成员函数返回的是引用。

删除元素

注意：删除元素的函数并不检查参数，必须确保被删元素是存在的。

特殊的forward_list操作

改变容器大小

容器操作可能导致迭代器失效

添加元素后：

• 如果容器是vector或string，且存储空间被重新分配，则之前的迭代器、指针和引用都会失效。如果存储空间未重新分配，则只有插入位置之后的元素的迭代器、指针和引用失效。
• 对于deque，插入到除首位位置之外的位置都会导致迭代器、指针和引用失效。如果在首位置添加元素，迭代器失效，指针和引用不失效。
• 对于list和forward_list，指向容器的迭代器、指针和引用都有效。

删除元素后：

• 对于list和forward_list，指向容器其他位置的迭代器、引用和指针都有效。
• 对于deque，如果在首位之外的位置删除元素，则迭代器、引用和指针都失效。如果删除尾元素，除尾后迭代器外，其他迭代器、引用和指针不受影响，如果是首元素，都不受影响。
• 对于vector和string，被删元素之前的迭代器、引用和指针都有效。

不要保存end返回的迭代器：end返回的迭代器极容易失效，应该在循环步内更新end迭代器。

vector对象是如何增长的

vector和string通常会分配比现有元素所需更大的内存空间作为备用。当持有的内存空间不够时，会进行扩张，重新分配内存空间，此时迭代器、引用和指针会失效。

只有当当前内存空间不足以存储时，reserve调用才会改变vector的容量。当需求大小小于当前容量时，并不会退回内存空间。另外resize只改变容器中元素的数量，并不会改变容器的容量。shrink_to_fit也只是请求退回内存空间，但具体执行不确定。

capacity和size：capacity为当前容器的容量，size为当前容器中元素的数量。

额外的string操作

构造string的其他方法：

以上操作不能越界，否则行为未定义。对于通过const char*的构造，越界未定义，对于通过string的构造，越界抛出out_of_range异常。

substr操作：不带参数n默认读取到尾。

• s.substr(pos, n)：返回一个string，包含s从pos开始的n个字符的拷贝

改变string的其他方法：

s.insert(s.size(), 5, '!');//在s的末尾插入5个!
s.erase(s.size() - 5, 5);//删除s末尾5个字符
s.append("!!!");//追加!!!到末尾
s.replace(3, 3, "!!!");//从位置3开始删除3个字符，再插入!!!

string搜索操作：

string name("AnnaBelle");
auto pos1 = name.find("Anna");//find函数返回位置下标pos1 == 0

string numbers("0123456789"), name("r2d2");
auto pos = name.find_first_of(numbers);//在name中寻找与numbers中任一字符第一个匹配的位置
auto pos2 = name.find_first_not_of(numbers);//第一个不匹配的

数值转换

int i = 42;
string s = to_string(i);
double d = stod(s);

容器适配器

• stack：将容器表现为栈的特性
• queue：将容器表现为队列的特性
• priority_queue：将容器表现为优先队列的特性

所有容器适配器都支持的操作和类型：

//在vector上实现的空栈
stack<string, vector<string>> str_stk;

stack栈适配器：默认基于deque实现，也可以在list或vector上实现。

queue队列适配器：queue默认基于deque实现，priority_queue默认基于vector实现。queue也可以用list或vector实现，priority_queue也可以用deque实现。

---