C++Primer——第九章(顺序容器)

• 迭代器范围：begin到end，即第一个元素到最后一个元素的后面一个位置。
• 左闭合区间：[begin, end)

int main() {
	list<string> a = { "aaa","bbb","ccc" };
	const list<string> b = { "AAA","BBB","CCC" };

	auto itl = 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

	auto it5 = a.begin();       // list::iterator  
	auto it6 = b.begin();       // list::const_iterator
}

• 直接复制：将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
• 使用迭代器复制：不要求容器类型相同，容器内的元素类型也可以不同，只要能将 要拷贝的元素类型 转换为 要初始化的容器的元素类型 即可。
• 只有顺序容器的构造函数 才接受大小参数，关联容器并不支持。
• array具有固定大小。（当定义一个array时 除了指定元素类型，还要指定容器大小）
• 和其他容器不同，默认构造的array是非空的，它包含了 与其大小一样多 的元素，这些元素都被默认初始化。

int main() {
	list<string> lst = { "aaa","bbb","ccc" };
	deque<const char*> deq = { "AAA","BBB","CCC" };
	
	list<string> lst1(lst);       // 正确: 容器类型和元素类型 都相同
	list<string> lst2(deq);       // 错误: 容器类型和元素类型 都不相同
	list<string> lst3(lst.begin(), lst.end());       // 正确
	list<string> lst4(deq.begin(), deq.end());       // 正确: const char*可以转换成string

	
	vector<string> vec(5);        // 正确
	set<string> vec(5);           // 错误: 只有顺序容器的构造函数 才接受大小参数，关联容器并不支持。


	array<int> arr1;               // 错误: 当定义一个array时 除了指定元素类型，还要指定容器大小
	array<int,5> arr2;             // 正确: arr2包含了 与其大小一样多 的元素，这些元素都被默认初始化
	array<int,10> arr3 = arr2;     // 错误: 大小不匹配（大小和类型都要匹配）
	array<int,5> arr4 = arr2;      // 正确
}

• 统一使用 非成员版本的swap 是一个好习惯。（swap通常比从c2向c1拷贝元素快得多）
• 交换两个容器内容的操作会很快——元素本身并未被交换，非成员版本的swap 只是交换了两个容器的内部数据结构。（除了array，swap两个array会真正交换它们的元素）
• 因此元素不会被移动，这意味着 指向窗口的迭代器、引用和指针在 非成员版本swap操作之后都不会失效。它们仍指向swap操作之前 所指向的那些元素，只是这些元素已经属于不同的容器了。（除了string，对一个string调用swap会导致迭代器、引用和指针失效。）
• assign操作不适用于 关联容器和array

int main() {
	vector<int> v1 = { 1,2,3,4,5 };
	vector<int> v2 = { 1,2,5 };
	vector<int> v3 = { 1,2,3,4 };
	vector<int> v4 = { 1,2,3,4,5 };

	v1 < v2;      // ture: v1和v2在元素[2]处不同，v1[2]小于v2[2] 
    v1 > v3;      // ture: 所有元素都相等，但v1中元素数目更多
	v1 == v4;     // true: 每个元素都相等，且v1和v4大小相同
	v1 == v3;     // false: v1元素数目比v3多

	vector<Demo> d1;
	vector<Demo> d2;
	d1 == d2;     // 如果Demo没有定义 比较运算符，则不能使用 关系运算符==比较两个容器
}

• 当我们用一个对象 去初始化容器或者将对象插入到容器时，实际上放入的是对象的拷贝。
• 因为这些操作会改变大小，因此不适用于array。
• forward_list有自己专有版本的 insert和emplace。forward_list不支持 push_back和emplace_back。
• emplace开头的函数是新标准引入的，这些操作是 构造而不是拷贝元素。传递给emplace的参数 必须和元素类型的构造函数相匹配。

int main() {
	vector<Sales_data> vec;

	vec.pop_back("978-0590353403"，25， 15.99);          // 错误: 没有接受三个参数的push_ back版本
	vec.emplace_back("978-0590353403"，25， 15.99);      // 正确: 使用三个参数的Sales data构造函数

	vec.push_back(Sales_ data("978-0590353403"，25， 15.99));      // 正确: 创建一个临时的Sales_ data对象传递给push_ back
}

• at和下标操作只适用于string、vector、deque、array。
• back不适用于forward_list。
• 访问成员函数返回的是引用。
• 如果希望下标是合法的，可以使用at函数。（at成员函数类似下标运算符，但如果下标越界，at会抛出一个out_of_range 异常）

int main() {
	vector<int> vec = { 1,2,3 };

	if (!vec.empty()) {
		vec.front() = 10;          // 将10赋予vec中的第一个元素vec[0]

		auto& v1 = vec.back();     // 获得指向最后一个元素的引用
		v1 = 10;                   // 将vec中的元素vec[2]的值改为10
		auto v2 = vec.back();      // v2不是一个引用，它是c.back()的一个拷贝（auto根据编译器 计算变量初始值推断类型，会忽略&）
		v2 = 10;                   // 未改变vec中的元素
	}
}

• 会改变容器大小，不适用于array。
• forward_list有特殊版本的erase，forward_list不支持pop_back。
• vector和string不支持pop_front。

• 链表在删除元素时需要 修改前置节点的内容，双向链表结点 有前驱的指针，但是单向链表结点 没有，出于这个原因，在一个forward list 中添加或删除元素的操作是通过 改变给定元素之后的元素 来完成的。
• forward_list定义了before_begin，即首前迭代器，允许我们再在首元素之前添加或删除元素。

int main() {
    list<int> lst(10, 1);   // 10个int，每个的值都是1
    
    lst.resize(15);         // 将5个值为0的元素 添加到lst的末尾
    lst.resize(20, -1);     // 将5个值为-1的元素 添加到lst的末尾
    lst.resize(5);          // 从lst末尾删除15个元素
}

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

• 对于list和forward_list，指向容器其他位置的迭代器、引用和指针仍然有效。
• 对于deque，如果在首尾之外的任何位置 删除元素，那么指向被删除元素外 其他元素的迭代器、指针、引用都会失效；如果是删除deque的尾元素，则尾后迭代器会失效，但其他不受影响；如果删除的是deque的头元素，这些也不会受影响。
• 对于vector和string，指向被删元素之前 的迭代器、引用、指针仍然有效。

• 元素类型必须支持 赋值运算；
• 元素类型的对象必须 可以复制。
• 除了输入输出标准库类型外，其他所有标准库类型 都是有效的容器元素类型。

• shrink_to_fit 只适用于vector、string、deque。
• capacity和reverse 只适用于vector、string。

• 只有当需要的内存空间 超过当前容量时，reserve调用才会改变vector的容量。如果需求大小大于当前容量，reserve至少分配 与需求一样大的内存空间 (可能更大)。
• 我们可以调用shrink_to_fit 来要求 deque. vector或string 退回不需要的任何多余的内存空间。但是，具体的实现可以选择忽略此请求。(调用shrink_to_fit 并不保证一定退回内存空间）
• 只有在执行insert操作时 size与capacity相等，或者调用resize或reserve时 给定的大小超过当前capacity，vector才可能重新分配内存空间。(会分配多少 超过给定容量的额外空间，取决于具体实现)

int main() {
	const char* cp = "Hello World!!!";    // 以空字符结束的数组
	char noNull[] = { 'H','i' };          // 不是以空字符结束的数组

	string s1(cp);             // 正确: 拷贝cp中的字符直到遇到空字符，s1 == "Hello World!! !"
	string s2(noNull);         // 错误:  noNull不是以空字符结束

	string s3(noNull, 2);      // 正确: 从noNull拷贝两个字符，s2 == "Hi"
	string s4(s1, 6);          // 正确: 从s1[6]开始拷贝,直至s1末尾; s6== "World!!!"
	string s5(cp + 6, 5);      // 正确: 从cp[6]开始拷贝5个字符，s4 == "World"
	string s6(s1, 16);         // 错误: 抛出一个out_ of_ range异常（16>=s1.size）

	string s7(s1, 6, 5);       // 正确: 从s1[6]开始拷贝5个字符，s5 == "World"
	string s8(s1, 6, 20);      // 正确: 从s1[6]开始拷贝,但只拷贝到s1末尾; s7 == "World!!!"
}

9.6 容器适配器

int main() {
	vector<string> vec = { "aaa","bbb","ccc" };

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

	str_stk1.size();     // 0
	str_stk2.size();     // 3
	std::swap(str_stk1, str_stk2);
	str_stk1.size();     // 3
	str_stk2.size();     // 0

	str_stk1.top();      // "ccc"
	str_stk1.pop();     
	str_stk1.top();      // "bbb"
	str_stk1.pop();
	str_stk1.top();      // "ccc"
	str_stk1.pop();

	str_stk1.size();     // 0
}

• stack适配器：要求push_back、pop_back、back。（因此可以使用除array和forward_ list之外的任何容器类型来构造stack）
• queue适配器：要求back、push_back、front、push_front。(因此它可以构造于list或deque之上，但不能基于vector构造 (vector不支持push_front))
• priority_queue适配器：要求front、push_ back、pop_ back、随机访问能力。(因此它可以构造于vector或deque之上，但不能基于list构造 (list不支持随机访问))