vector<int> a{1, 2, 4};

vector<int> a = {1, 2, 4};

void clear ()

list<string> names;
vector<const char*> oldstyle = { "I","love","you" };
//names = oldstyle;错误！不同的类型不能执行"="操作
names.assign(oldstyle.cbegin(), oldstyle.cend());
list<string>::iterator it;
for (auto it = names.begin(); names.begin() != names.end(); it++)
? ? ? ? cout << *it << " ";

reference operator[](n)? ? ? ?{vector, deque, string}

reference back()? ? ? ? ? ? ? ? ? {vector, deque, list, string}

reference front () ? ? ? ? ? ? ? ? ?{ vector, deque, list, string(C++11)}

size_type capacity () const ?{ vector, string}

iterator insert (pos, x)

void insert (pos, n, x)

void insert (pos, InIterFirst, InIterLast)

iterator insert (pos, InIterFirst, InIterLast)

iterator insert (pos, init_list)

size_type count (k) const

pair<iterator, bool> emplace(arg1, arg2, …)?{set(С++11), map(С++11)}

iterator emplace(arg1, arg2, …) {multiset(С++11), multimap(С++11)}

pair<iterator, iterator> equal_range (k)

iterator find (k)

key_compare key_comp () const

iterator lower_bound (k)

iterator upper_bound (k)

value_compare value_comp () const

4.1 顺序（序列）容器

顺序容器插入操作：

最重要的函数是insert，有下面三种重载形式：

iterator insert(iterator here,value_type const& item)
//在指定位置前插入item，并返回新插入项目的迭代器。
void insert(iterator here,size_type n,value_type const& item)
//在指定位置前插入n个item副本
template<class inputIterator>
void insert(iterator here,inputIterator first,inputIterator last)
//将范围[first,last)的值直接复制到容器中here之前。

还有两个函数：push_front：在容器头部插入项目，push_back在容器尾部插入项目。

容器类型只会提供能用常数复杂度实现的函数，因此，vector提供push_back但没有push_front，而list和deque同时提供push_front和push_back。

顺序容器的清除操作：
erase：两种erase形式：

iterator erase(iterator pos)
//清楚pos所指向的项目，并返回其后继项目的迭代器。
iterator erase（iterator first，iterator last）
//清楚范围[first,last)的全部项目，并返回指向最后一个删除项目的后一项目的迭代器。

clear：会清除容器内所有项目。

除了这两个基本的清除函数外，顺序容器还使用pop_front来清除容器头部的项目，pop_back清除尾部的项目。
类似push函数，vector提供了pop_back,而list和deque均提供pop_back和pop_front。
（1）vector
典型的顺序容器，任意元素的读取、修改具有O(1)，在序列尾部进行插入、删除是O(1)，但在序列的头部插入、删除的时间复杂度是O(n)，可以在任何位置插入新元素，有随机访问功能，插入删除操作需要考虑。

（2）deque
序列容器，内存也是连续的，和vector相似，区别在于在序列的头部插入和删除操作也是O(1), 可以 在任何位置插入新元素，有随机访问功能。

（3）list
序列容器，内存是不连续的，任意元素的访问、修改时间复杂度是O(n)，插入、删除操作是O(1), 可以在任何位置插入新元素。

4.2 关联容器

插入操作：
关联容器的插入操作函数insert存在几种形式，和顺序容器的主要区别在于，它不需要提供一个位置(有一种形式需要提供一个提示性的位置)。

insert的行为与容器是否允许重复项目有关。类型set、map、unordered_set、unordered_map要求唯一键，而multiset、multimap、unordered_multiset和unordered_multiset允许重复键。

interator insert(value_type const& iterm)
std::pair<iterator,bool>insert(value_type const& item)
它会试图把item插入到容器中。如果容器允许重复键，则insert一定成功，并返回指向新插入项目的迭代器；而如果容器要求唯一键，则仅当该项目不在容器中时才插入成功。它返回包含一个迭代器和一个bool类型的pair，item被插入是bool为真。

iterator insert（iterator hint,value_type const& item）
它会尝试把item插入到容器中，如果容器允许重复键，则insert一定会成功；否则仅当该项不在容器中时insert才会插入该项。在两种情况下insert均会返回指向新插入项目或已存在的项目的迭代器。

template<class inputInterator>
void insert(inputIterator first,inputIterator last)
它会把范围[first,last)的值复制到容器中，对于有序容器，如果范围[first,last)有序，则性能有所提高。
清除操作：

erase:
void erase(iterator pos)
iterator erase(iterator pos)
清楚pos指向的项目。有序容器没有返回值，无序容器返回后继迭代器（或者为end()）。

void erase（iterator first，iterator last）
iterator erase（iterator first，iterator last）
清楚范围[first，last)的全部项目。有序容器没有返回值，无序容器返回指向最后一个删除项目的后一项目的迭代器。
（1）set
关联容器，元素不允许有重复，数据被组织成一棵红黑树，查找的速度非常快，时间复杂度是O(logN)

（2）multiset
关联容器，和set一样，是允许有重复的元素，具备时间复杂度O(logN)查找功能。

（3）map
关联容器，按照{键，值}方式组成集合，按照键组织成一棵红黑树，查找的时间复杂度O(logN)，其中键不允许重复。

（4）multimap
和map一样，区别是键可以重复

4.3 容器适配器

使用中需要考虑的一些因素
1、需要添加大量元素
不适合用vector，因为vector底层是数组，当前容量不足时就要扩容，将所有旧元素全部拷贝到新内存中，开销太大

适合用list
deque是vector和list的折中，内存不够时需要申请新内存但不用拷贝旧数据

2、查找速度
?对于序列容器需要分两种情况，区分依据是元素是否排序
?1)对于已经排序的序列容器，使用binary_search可以获得对数时间复杂度的查找速度(O(logN));
?2)而未排序的序列容器二分查找肯定是用不了，能达到的最好的时间复杂度是线性的(O(n))。

对于关联容器，存储的时候存储的是一棵红黑树，总是能达到对数时间复杂度(O(logN))的效率，因为关联容器是按照键值排好序的。

3、内存是否连续
vector、deque是连续内存的，其中vector是完全连续内存，而deque是vector和list的折中实现，是多个内存块组成的，每个块中存放的元素连续内存，而内存块又像链表一样连接起来。所以需要考虑在操作的过程中是否有在任意位置插入元素的需求，有这种需求的话尽量避免使用连续内存的vector、deque

4、元素的排序
序列容器是不会自动排序的，而关联容器通过键值对根据某种关系进行排序；所以默认情况下序列容器中的元素是无序的，而关联容器中的元素是有序的。

具体使用
在实际使用过程中，到底选择这几种容器中的哪一个，可以根据以下原则：

1、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；

2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；

3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；

4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；

5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset

? 反向迭代器是一种反向遍历容器的迭代器。也就是，从最后一个元素到第一个元素遍历容器。反向迭代器将自增（和自减）的含义反过来了：对于反向迭代
器，++ 运算将访问前一个元素，而 -- 运算则访问下一个元素。

??????? 回想一下，所有容器都定义了 begin 和 end 成员，分别返回指向容器首元素和尾元素下一位置的迭代器。容器还定义了 rbegin 和 rend 成员，分别返回指向容器尾元素和首元素前一位置的反向迭代器。与普通迭代器一样，反向迭代器也有常量（const）和非常量（nonconst）类型。图 11.1 使用一个假设名为 vec 的 vector 类型对象阐明了这四种迭代器之间的关系。

图?1 比较 begin/end 和 rbegin/rend 迭代器

??????假设有一个 vector 容器对象，存储 0-9 这 10 个以升序排列的数字：

vector<int> vec;

for (vector<int>::size_type i = 0; i != 10; ++i)

vec.push_back(i); // elements are 0,1,2,...9

下面的 for 循环将以逆序输出这些元素：

// reverse iterator of vector from back to front

vector<int>::reverse_iterator r_iter;

for (r_iter = vec.rbegin(); // binds r_iter to last element

r_iter != vec.rend(); // rend refers 1 before 1st element

++r_iter) // decrements iterator one element

cout << *r_iter << endl; // prints 9,8,7,...0

????? 虽然颠倒自增和自减这两个操作符的意义似乎容易使人迷惑，但是它让程序员可以透明地向前或向后处理容器。例如，为了以降序排列 vector，只需向 sort传递一对反向迭代器：

// sorts vec in "normal" order

sort(vec.begin(), vec.end());

// sorts in reverse: puts smallest element at the end of vec

sort(vec.rbegin(), vec.rend());

????? 1.反向迭代器需要使用自减操作符
????? 从一个既支持 -- 也支持 ++ 的迭代器就可以定义反向迭代器，这不用感到吃惊。毕竟，反向迭代器的目的是移动迭代器反向遍历序列。标准容器上的迭代器既支持自增运算，也支持自减运算。但是，流迭代器却不然，由于不能反向遍历流，因此流迭代器不能创建反向迭代器。
????? 2.反向迭代器与其他迭代器之间的关系
????? 假设有一个名为 line 的 string 对象，存储以逗号分隔的单词列表。我们希望输出 line 中的第一个单词。使用 find 可很简单地实现这个任务：

// find first element in a comma-separated list

string::iterator comma = find(line.begin(), line.end(), ',');

cout << string(line.begin(), comma) << endl;

????????如果在 line 中有一个逗号，则 comma 指向这个逗号；否则，comma 的值为 line.end()。在输出 string 对象中从 line.begin() 到 comma 的内容时，从头开始输出字符直到遇到逗号为止。如果该 string 对象中没有逗号，则输出整个 string 字符串。
????? 如果要输出列表中最后一个单词，可使用反向迭代器：

// find last element in a comma-separated list

string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ',');

因为此时传递的是 rbegin() 和 rend()，这个函数调用从 line 的最后一个字符开始往回搜索。当 find 完成时，如果列表中有逗号，那么 rcomma 指向其最后一个逗号，即指向反向搜索找到的第一个逗号。如果没有逗号，则 rcomma 的值为 line.rend()。
????? 在尝试输出所找到的单词时，有趣的事情发生了。直接尝试：

// wrong: will generate the word in reverse order

cout << string(line.rbegin(), rcomma) << endl;

会产生假的输出。例如，如果输入是：
????? FIRST,MIDDLE,LAST
则将输出 TSAL！

????? 图 2 阐明了这个问题：使用反向迭代器时，以逆序从后向前处理 string对象。为了得到正确的输出，必须将反向迭代器 line.rbegin() 和 rcomma 转换为从前向后移动的普通迭代器。其实没必要转换 line.rbegin()，因为我们知道转换的结果必定是 line.end()。只需调用所有反向迭代器类型都提供的成员
函数 base 转换 rcomma 即可：

// ok: get a forward iterator and read to end of line

cout << string(rcomma.base(), line.end()) << endl;

?

假设还是前面给出的输入，该语句将如愿输出 LAST。

????????

????????????????????????????????????????图 2. 反向迭代器与普通迭代器之间的区别

????? 图 2 显示的对象直观地解释了普通迭代器与反向迭代器之间的关系。例如，正如 line_rbegin() 和 line.end() 一样，rcomma 和 rcomma.base() 也指向不同的元素。为了确保正向和反向处理元素的范围相同，这些区别必要的。从技术上来说，设计普通迭代器与反向迭代器之间的关系是为了适应左闭合范围
（第 9.2.1 节）这个性质的，所以，[line.rbegin(), rcomma) 和[rcomma.base(), line.end()) 标记的是 line 中的相同元素。
????? 反向迭代器用于表示范围，而所表示的范围是不对称的，这个事实可推导出一个重要的结论：使用普通的迭代器对反向迭代器进行初始化或赋值时，所得到的迭代器并不是指向原迭代器所指向的元素。