第4章 序列式容器
容器是个大东西，还是带着问题分析好。
序列式容器里，我用的最多的还是vector。
1.我知道vector中有内存有预先分配，这种机制是好的，但有时候会浪费内存。
2.重点分析vector初始化大小，resize，erase等
vector容器
4.1.vector(n,v),使用这个构造函数可以指定含有n个v值的元素
看下源码：
构造函数
1 /**
2 * @brief Creates a %vector with copies of an exemplar element.
3 * @param n The number of elements to initially create.
4 * @param value An element to copy.
5 * @param a An allocator.
6 *
7 * This constructor fills the %vector with @a n copies of @a value.
8 */
9 explicit
10 vector(size_type __n, const value_type& __value = value_type(),
11 const allocator_type& __a = allocator_type())
12 : _Base(__n, __a)
13 { _M_fill_initialize(__n, __value); }
14
15 // Called by the first initialize_dispatch above and by the
16 // vector(n,value,a) constructor.
17 void
18 _M_fill_initialize(size_type __n, const value_type& __value)
19 {
20 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
21 _M_get_Tp_allocator());
22 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
23 }
最后一句this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
说明内存申请不会多不会少，刚刚好。
4.2.那么resize呢
看源码：
resize
1 /**
2 * @brief Resizes the %vector to the specified number of elements.
3 * @param new_size Number of elements the %vector should contain.
4 * @param x Data with which new elements should be populated.
5 *
6 * This function will %resize the %vector to the specified
7 * number of elements. If the number is smaller than the
8 * %vector's current size the %vector is truncated, otherwise
9 * the %vector is extended and new elements are populated with
10 * given data.
11 */
12 void
13 resize(size_type __new_size, value_type __x = value_type())
14 {
15 if (__new_size < size())
16 _M_erase_at_end(this->_M_impl._M_start + __new_size);
17 else
18 insert(end(), __new_size - size(), __x);
19 }
20 //你懂的
21 void
22 clear()
23 { _M_erase_at_end(this->_M_impl._M_start); }
24 //insert有好多，别找错了
25 /**
26 * @brief Inserts a number of copies of given data into the %vector.
27 * @param position An iterator into the %vector.
28 * @param n Number of elements to be inserted.
29 * @param x Data to be inserted.
30 *
31 * This function will insert a specified number of copies of
32 * the given data before the location specified by @a position.
33 *
34 * Note that this kind of operation could be expensive for a
35 * %vector and if it is frequently used the user should
36 * consider using std::list.
37 */
38 void
39 insert(iterator __position, size_type __n, const value_type& __x)
40 { _M_fill_insert(__position, __n, __x); }
clear没有改变capacity这个大家都知道。所以resize小了，capacity也不会小掉。
里面的 Note that this kind of operation could be expensive for a
* %vector and if it is frequently used the user should
* consider using std::list.
值得玩味，如果能看到invert后start和finsh的指针位置发生改变，就可以证明_M_fill_insert有开辟新的空间。
这个_M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
实现在vector.tcc里，比较复杂，就不深究了
4.3.push_back新增元素，如果vector中size==capacity，则会开辟一个双倍大小的连续新空间，将原来的数据拷贝过去，插入新元素。
给个小例子：
push_back
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int main()
6 {
7 int n = 16;
8 vector<int> temp;
9 for (int i = 1; i <= n; i ++)
10 {
11 cout << "before push, n: " << i << " capacity: " << temp.capacity() << endl;
12 temp.push_back(i);
13 cout << "after push, n: " << i << " capacity: " << temp.capacity() << endl;
14 }
15 return 0;
源码：
push_back
1 /**
2 * @brief Add data to the end of the %vector.
3 * @param x Data to be added.
4 *
5 * This is a typical stack operation. The function creates an
6 * element at the end of the %vector and assigns the given data
7 * to it. Due to the nature of a %vector this operation can be
8 * done in constant time if the %vector has preallocated space
9 * available.
10 */
11 void
12 push_back(const value_type& __x)
13 {
14 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
15 {
16 this->_M_impl.construct(this->_M_impl._M_finish, __x);
17 ++this->_M_impl._M_finish;
18 }
19 else
20 _M_insert_aux(end(), __x);
21 }
_M_insert_aux没找到实现，不过书上有。总之push_back慎用，还是resize在赋值好。
4.4.erase函数
erase
1 template<typename _Tp, typename _Alloc>
2 typename vector<_Tp, _Alloc>::iterator
3 vector<_Tp, _Alloc>::
4 erase(iterator __position)
5 {
6 if (__position + 1 != end())
7 _GLIBCXX_MOVE3(__position + 1, end(), __position);
8 --this->_M_impl._M_finish;
9 this->_M_impl.destroy(this->_M_impl._M_finish);
10 return __position;
11 }
源码有点怪，反正要注意的是erase会返回一个iterator，指向被删除的下一个。
list容器
list容器erase时只有被删除的那个iterator无效，其它的都有效，这点也在情理之中。其它的就不讲了。
deque容器
这个容器还真没用过，书上说deque由一段一段的定量连续空间构成。
一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，
串接在整个deque的头端或尾端。deque的最大任务，
便是在这些分段的定量连续空间上，维护其整体连续的假象。
并提供随机存取的结果。避开了像Vector那样“重新配置，复制，释放”的轮回，
代价则是复杂的迭代器架构。具体细节以后用到再看，先略过。
stack容器
stack是容器适配器，就是基于其它容器封装出来的。
默认stack用的是deque，我们可以用vectror,list指定。
比如 stack<int, vector<int> >，除此之外，stack不提供iterator。
queue容器
queue也不允许遍历，即不提供iterator。
queue也是容器适配器，默认基于deque构造。同样我们可以指定vector或list