C++ Primer 顺序容器

顺序容器概述

存储策略的影响容器选择原则 容器库概览（适用于所有容器的 *** 作）

定义 *** 作迭代器容器类型成员begin和end成员容器定义和初始化赋值和swap 顺序容器 *** 作

添加元素访问元素删除元素特殊的forward_list *** 作改变容器大小容器 *** 作可能使迭代器失效 容器适配器

定义一个适配器适配器限制栈适配器队列适配器

string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，根据下标来计算地址是很快速的。然而，这样会导致在删除或插入除尾部以外的元素时，需要移动插入/删除之后的所有元素来保证连续存储。更糟糕的是，这样可能会需要分配额外的存储空间。list和forward_list两个容器的设计目的是令容器任何位置的添加和删除 *** 作都很快速。作为代价，这两个容器不支持元素的随机访问。这两个容器的额外内存开销也很大（记录元素之外还需要记录地址）。deque是一个复杂的数据结构。与string和vector类似，deque支持快速的随机访问。与string和vector一样，在deque的中间位置添加或删除元素的代价很高。但是，在deque的两端添加和删除元素都很快，与list或forward_list添加元素的速度相当。

除非有很好的理由选择其他容器，否则使用vector。如果程序有很多小的元素，且空间的额外开销很重要，那么不要使用list或forward_list。如果程序要求随机访问元素，应使用vector或deque。如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除 *** 作，则使用deque。如果程序只有在读取输入时才需要在容器的中间位置插入元素，随后需要随机访问元素。考虑两个方面：这个需求是否是真的？比如可以通过vector的push_back()与sort函数避免在中间位置添加元素；如果需求是真的，可以先采用list再拷贝给vector。

我们需要更加添加/删除元素的需求、访问顺序的需求以及空间开销的需求灵活选择容器。

每个容器都定义在同名头文件中；定义时，需要在尖括号中指定元素的类型。

说明：

不适用于array；在不同容器中， *** 作的接口不同（对应的函数名称不一样，但功能大体一致）。

迭代器范围由一对迭代器表示。

end表示的迭代器不会指向最后一个元素，而是指向尾元素之后的位置。

迭代器范围中的元素包含first所表示的元素以及first开始直至last(但不包含last)之间的所有元素。这种元素范围被称为左闭合区间 [ b e g i n , e n d ) [begin,end) [begin,end)。

要求：begin和end必须指向相同的容器；end和begin可以指向相同的位置，但不能指向begin之前的位置。

这样一种左闭合范围蕴含的性质是：如果begin==end，那么迭代器范围为空；反之，迭代器范围中至少包含一个元素。

while (bgein != end){
	*begin = val;
	++begin;
}

通过类型别名，可以在不了解容器中元素类型的情况下使用它。有：

说明：

以string为例，所有用于存放string类的size函数返回值的变量，都应该是string::size_type。list::iterator iter;iter是通过list定义的一个迭代器类型。

拷贝初始化：相同容器类型、相同元素类型（对于array来说还需要具有相同的大小）。列表初始化：元素类型相容（对于array来说列表大小与array大小相同）。默认构造函数：对于array来说是非空的，对于其他来说则是空的。迭代器初始化(拷贝初始化)：元素类型相容（array不适用）。对于顺序容器而言（array除外）：C seq(N)，seq包含n个元素，这些元素进行了值初始化（string不适用）；C seq(n,t)包含n个值为t的元素。

关于拷贝初始化，有两种。其中，迭代器初始化是不要求元素类型一样的。

如果元素类型是内置类型或者具有默认构造函数的类类型，可以只为构造函数提供一个容器大小参数。如果没有默认构造函数，除了大小参数之外还需要一个显式的元素初始值。

当定义一个array时，除了指定元素类型，还需要指定容器大小array

赋值运算的本质为将左边容器中的全部元素替换为右边容器中的拷贝。

如果两边的大小不同，那么赋值后的长度为右边的容器大小。

关于赋值 *** 作，对于顺序容器而言还有三种（不适用于array）

除了array之外，swap知识交换了两个容器的内部数据结构，不对任何元素进行拷贝、删除或插入 *** 作，可以在常数时间内完成。

因为元素不会被移动，所以除了string之外，指向容器的迭代器、引用和指针都不会失效，但是这些元素是属于不同容器的。

与其他容器不同的是，swap两个array是会真正交换元素的。

对于vector、string、deque插入的元素会使所有指向容器的迭代器、引用和指针失效。

forward_list有自己版本的insert和emplace；

forward_list不支持push_back和emplace_back；

vector和string不支持push_front和emplace_front。

需要注意的是，容器的初始化或者插入都是对象的一个拷贝，所以说，容器内和原始对象的任何一方做出改动都不会互相影响。

insert可以实现任何位置的插入。

通过insert的返回值，可以在容器中的一个特定位置反复插入元素。

list lst;
auto iter = lst.begin();
while (cin >> word)
	iter = lst.insert(iter,word); //等价于调用push_front

关于emplace

// 在c的末尾构造一个Sales_data对象
c.emplace_back("978-059",25,15.99);
c.push_back(Sales_data("978-059",25,15.99));

使用emplace时，会在容器管理的内存空间中直接创建对象；而调用push_back则会创建一个局部临时对象，并将其压入容器中。

at和下标 *** 作只适用于string、vector、deque和array；back不适用于forward_list。

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

与插入 *** 作相对应的：

forward_list有自己版本的erase；forward_list不支持pop_back；vector和string不支持pop_front；删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效；指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。

对于单向链表而言，当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继需要改变。因此，我们需要访问其前驱。对于list而言就没有这个烦恼，因为双端队列的每一个Node同时保存了前驱和后继。所以对于单向链表来说访问前驱比登天还难。所以说就不支持push_back和pop_back。

另外，也是基于这个原因，在forward_list中添加或删除元素的 *** 作是通过改变给定元素之后的元素来实现的。也就是我已知当前元素，在这个元素后面进行添加或删除的 *** 作。

于是有

#include 
using std::stack;
stack intStack;
for (size_t ix=0; ix != 10; ++ix)
	intStack.push(ix)
while (!intStack.empty()){
	int value = intStack.top();
	intStack.pop();
}