C++标准库学习2：顺序容器part 1

C++标准库学习笔记：顺序容器part 1（顺序容器概述、容器库概览、顺序容器操作）

顺序容器（sequential container）为程序员提供了控制元素存储和访问顺序的能力。

存储策略的tradeoff：
向容器中添加或从容器中删除元素的代价 v.s 非顺序访问容器中元素的代价

· string和vector将元素保存在连续的内存空间中 -> 下标计算地址迅速，但在每次插入或删除时需移动插入/删除位置后的所有元素
· list和forward_list不支持元素的随机访问 -> 为了访问一个元素需要遍历整个容器 -> 额外内存开销也很大
· deuqe支持快速的随机访问，中间位置添加或删除元素的代价（可能）很高，但在其两端添加或删除元素都是很快的。
· array：大小固定，不支持添加和删除元素以及改变容器大小的操作，且比内置数组更安全

确定使用哪种容器：在不确定的情况下只使用vector和list
公共的操作：使用迭代器，不使用下标操作，避免随机访问。

1. 常见容器操作：
   A. 类型别名
   iterator: 此容器类型的迭代器类型
   const_iterator: 可以读取元素，但不能修改元素的迭代器类型
   size_type: 无符号整数类型，足够保存此种容器类型最大可能容器的大小
   defference_type: 带符号整数类型，足够保存两个迭代器之间的距离
   value_type: 元素类型
   reference: 元素的左值类型，与value_type&含义相同
   const_reference: 元素的const左值类型（const value_type&）
   B. 构造函数
   C c; 默认构造函数，构造空容器
   C c1(c2); 构造c2的拷贝c1
   C c(b,e); 构造c，将迭代器b和e指定的范围内的元素拷贝到c（array不支持）
   C c{a, b, c}; 列表初始化c
   C. 赋值与swap
   c1 = c2 将c1中的元素替换为c2中元素
   c1 = {a, b, c, …} 将c1中的元素替换为列表中元素(不适用于array)
   a.swap(b) 交换a和b的元素
   swap(a, b) 与a.swap(b)等价
   D.大小
   c.size() c中元素的数目(不支持forward_list)
   c.max_size() c可保存的最大元素数目
   c.empty() 若c中存储了元素，返回false，否则返回true
   E.添加/删除元素
   c.insert(args) 将args中的元素拷贝进c
   c.emplace(inits) 使用inits构造c中的一个元素
   c.erase(args) 删除args指定的元素
   c.clear() 删除c中的所有元素，返回void
   关系运算符：
   ==, != 所有容器都支持相等（不等）运算符
   <, <=, >, >= 关系运算符（无序关联容器不支持）
   F.获取迭代器
   c.begin(), c.,end() 返回指向c的首元素与尾元素之后位置的迭代器
   c.cbegin(), c.cend() 返回const_iterator
   G.反向容器的额外成员（不支持forward_list）
   reverse_iterator() 按逆序寻址元素的迭代器
   const_reverse_iterator 不能修改元素的逆序迭代器
   c.rbegin(), c.rend() 返回指向c的尾元素和首元素之前位置的迭代器
   c.crbegin(), c.crend() 返回const_reverse_iterator

2. 迭代器
   与容器一样，迭代器有着公共的接口：如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。
   迭代器范围：由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置，这两个迭代器分别称为begin和end -> 左闭合区间 [begin, end)
   对构成范围的迭代器的要求：如果满足如下条件，两个迭代器begin和end构成一个迭代器范围 – 条件一：它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置；条件二：我们可以通过反复递增begin来到达end。
   tips: begin和end的判断使用==和!=，不使用<和>。

3. 容器类型成员【size_type、iterator、const_iterator】
   例子：
   A. 索引int的vector元素：vector size_type
   B. 读取string的list中的元素：list::const iterator
   C. 写入list：list::iterator

4. begin和end成员
   可以将一个普通的iterator转换成对应的const_iterator。

lista = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin();  //list::iterator
auto it2 = a.rbegin();  //list::reverse_iterator
auto it3 = a.cbegin();  //list::const_iterator
auto it4 = a.crbegin();  //list::const_reverse_iterator

5. 容器定义和初始化
   
   note：当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。
   note2：使用迭代器拷贝时，只要求元素类型相同，不要求容器类型相同。

list anthors = {"Milton", "Shakespeare", "Austen"};
vector articles = {"a", "an", "the"};

list list2(authors);  //正确：类型匹配
deque authList(authors);  //错误：容器类型不匹配
vector words(articles);   //错误：容器类型必须匹配

// 正确：可以将const char*元素转换成string
forward_list words(articles.begin(), articles.end());

两个迭代器表示一个范围，可以拷贝范围内的子序列：

// 拷贝元素，直到（但不包括）it指向的元素
deque authList(authors.begin(), it);

顺序容器提供接受一个容器大小和一个（可选的）元素初始值：

vector ivec(10, -1);   //10个int元素，每个都初始化为-1
list svec(10, "hi!");   //10个string;每个都初始化为“hi!"
forward_list ivec(10);   //10个元素，每个都初始化为0
deque svec(10);   //10个元素，每个都是空string

标准库array具有固定大小：

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

相较于内置数组，array在初始值的类型与创建的容器类型相同时可以对其进行拷贝和赋值操作。

6. 赋值和swap
   
   除array外，swap不对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间内完成：除string外指向容器的迭代器、引用和指针在swap操作后都不会失效；对一个string调用swap会导致迭代器、引用和指针失效。
   swap两个array会真正交换它们的元素，因此交换两个array所需的时间与array中元素的数量成正比。

7. 容器大小操作：size, empty, max_size【forward_list支持max_size和empty，但不支持size】

8. 关系运算符：
   

1. 向顺序容器添加元素
   

push_back的使用：

//从标准输入读取数据，将每个单词放到容器末尾
string word;
while (cin >> word)
	container.push_back(word);

//string是字符容器，因此也可以用push_back在string末尾添加字符
void pluralize(size_t cnt, string &word)
{
	if (cnt > 1)
		word.push)back('s');   //等价于word += 's'
}

push_front的使用[list、forward_list、deque]：

list ilist;
for (size_t ix = 0; ix != 4; ++ix)
	ilist.push_front(ix);

insert的使用->在容器中的特定位置添加元素[vector、deque、list、string]：

vector svec;
list slist;

// insetr函数接受一个迭代器作为其第一个参数
slist.insert(slist.begin(), "Hello!");  //等价于调用slist.push_front("Hello!")

//vector不支持push_front, 但我们可以插入到begin()之前
svec.insert(svec.begin(), "Hello!");

vector v = {"quasi", "simba", "frollo", "scar"};
//将v的最后两个元素添加到slist的开始位置
slist.insert(slist.begin(), v.end() - 1, v.end());
slist.insert(slist.end(), {"these", "words", "will", "go"});
slist.insert(slist.begin(), slist.begin(), slist.end());  //运行时错误:迭代器表示要拷贝的范围，不能指向与目的位置相同的容器

//insetr返回的迭代器指向新元素
//下面的代码可以在容器中一个特定位置反复插入新元素
list lst;
auto iter = lst.begin();
while (cin >> word)
	iter = lst.insert(iter, word);  //等价于调用push_front

emplace操作 – emplace_front、emplace和emplace_back【对应push_front、insert和push_back】-- 这些操作构造而不是拷贝元素
emplace函数直接在容器中构造元素，传递给emplace函数的参数必须与元素类型的构造函数相匹配。

2. 访问元素
   

// 在解引用一个迭代器或调用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不支持
}

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

if (c.empty()) {
	c.front() = 42;
	auto &v = c.back();   //获得指向最后一个元素的引用
	v = 1024;             //改变c中的元素
	auto v2 = c.back();   //v2不是一个引用，它是c.back()的一个拷贝
	v2 = 0;               //未改变c中的元素
}

下标操作和安全的随机访问：

vector svec;  //空vector
cout << svec[0];   //运行时错误：svec中没有元素
cout << svec.at(0);  //抛出一个out_of_range异常

删除元素：删除元素的成员函数并不检查其参数，在删除元素之前，程序员必须确保它(们)是存在的

note：注意成员函数有无返回值，返回值是什么 -> 可能有用

//删除一个list中的所有奇数元素
list lst = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto it = lst.begin();
while (it != lst.end())
	if (*it % 2)               //若元素为奇数
		it = lst.erase(it);    //删除此元素
	else
		++it;

//删除多个元素
elem = slist.erase(elem1, elem2);  //删除两个迭代器表示的范围内的元素，返回指向最后一个被删元素之后位置的迭代器,删除元素的范围[elem1, elem2),调用后elem1 = elem2

//删除一个容器中的所有元素
slist.clear();  //删除容器中所有元素
slist.erase(slist.begin(), slist.end());  //等价调用

3. 特殊的forward_lst操作
   

4. 改变容器大小
   

5. 容器操作可能使迭代器失效

在向容器添加元素后：
·如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用都将会失效。
·对于deque，插入到除首尾位置之后元素的迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
·对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
删除一个元素后：
对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素之外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不受影响。
对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。
当我们删除元素时，尾后迭代器总是会失效。

编写改变容器的循环顺序：
添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题，使用insert或erase来更新迭代：

iter = v1.insert(iter, *iter);   //将iter位置的元素插入到iter之前, iter指向插入的元素
iter = v1.erase(iter);   //删除元素，iter指向我们删除的元素之后的元素

不要保存end返回的迭代器：
如果在一个循环中插入/删除deque、string或vector中的元素，不要缓存end返回的迭代器。

1. C++ primer. 第五版.