STL: 序列容器（vector, deque, list）

向量：

末尾快速插入和删除， 对变长序列的快速随机访问

构造序列：

vector v1;   //空序列

vector v1(n, value);   //用n个value元素初始化序列

vector v1(n);    //n个元素的序列，通过调用T的默认构造函数所返回的结果来初始化

vector v1(v2.begin(), v2.end());   //v2可以是vector, list或者deque

vector v1(arr, arr+n);  //arr为数组

vector v1(v2);

vector v1=v2;

插入：

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  char arr[] = "Bjarne Stroustrup";
  vector<char> v2, v1(arr, arr+6);
  vector<char>::iterator i;

  for(i=v1.begin(); v1.end(); ++i) {
    v2.push_back(*i); //从末尾插入
  }
  assert(v1 == v2);
  v2.clear();
  for(i=v1.begin(); v1.end(); ++i) {
    v2.insert(v2.begin(), *i); //从前插入
  }
  reverse(v1.begin(), v1.end()); //倒转顺序
  assert(v1 == v2);

  v2.insert(v2.begin()+1, 5, '*'); //在第二个位置前插入5个*
  for(i=v2.begin(); v2.end(); ++i)
    cout << *i;
  cout << endl;
  //输出 e*****nrajB
  return 0;
}

使用insert函数时，如果当前块中没有剩余空间用来插入新元素，就要重新分配存储空间（为原来的两倍）。这样会增加插入开销，并使迭代器失效。可以通过capacity和reserve成员函数对内存重新分配施加某种程度的控制。

capacity函数返回当前所分配的内存块大小，在调用函数v1.reserve(n)之后，v1.capacity将至少为N=n，reserve函数的作用是当（且仅当）现有内存空间小于N时重新分配内存。如果事先知道要插入N个元素，则与不断分配内存相比，预先调用reserve可以加快程序的运行速度，调用reserve函数后，一直到向量到达N之前都不会重新分配内存。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  const int N = 10000;
  vector<int> v1, v2;
  int k;

  //没有预先reserve
  cout << "v1:" << endl;
  for(k=0; k<N; ++k) {
    vector<int>::size_type cap = v1.capacity();
    v1.push_back(k);
    if(v1.capacity() != cap) { //重新分配内存
      cout << "k:" << k << ", new capacity:" << v1.capacity() << endl;
    }
  }
  //预先reserve
  cout << "v2:" << endl;
  v2.reserve(N);
  for(k=0; k<N; ++k) {
    vector<int>::size_type cap = v1.capacity();
    v1.push_back(k);
    if(v1.capacity() != cap) {
      cout << "k:" << k << ", new capacity:" << v1.capacity() << endl;
    }
  }
  return 0;
}

输出：
v1:
k:0, new capacity:1
k:1, new capacity:2
k:2, new capacity:4
k:4, new capacity:8
k:8, new capacity:16
k:16, new capacity:32
k:32, new capacity:64
k:64, new capacity:128
k:128, new capacity:256
k:256, new capacity:512
k:512, new capacity:1024
k:1024, new capacity:2048
k:2048, new capacity:4096
k:4096, new capacity:8192
k:8192, new capacity:16384
v2:
k:6384, new capacity:32768

这样子不仅效率提高了，插入点之前的迭代器和引用也不会失效了。

删除：

从末尾删除

while(v1.size() > 0) {

cout << v1.back();

v1.pop_back();

}

从前面删除,效率低

while(v1.size() > 0) {

cout << v1.front();

v1.erase(v1.begin());

}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  char str[] = "remembering";
  vector<char> v1(str, str+11);
  vector<char>::iterator j;
  j = find(v1.begin(), v1.end(), 'm'); //j指向第一个m
  v1.erase(j--); //"reembering", j指向第一个e
  v1.erase(j--); //"rembering" ,j指向第一个r
  v1.erase(j,j+3); //"bering"
  v1.erase(v1.begin()+1);
  for(j=v1.begin(); j!=v1.end(); ++j) {
    cout << *j;
  }
  cout << endl;
  //cout "bring"
  return 0;
}

erase函数会使删除点之后的迭代器失效，所以要j--;

交换, swap(v1, v2)跟v1.swap(v2)是一样的（部分特殊化）。互换v1和v2中的值。常数时间复杂度。

双端队列

对序列两端快速插入和删除

大部分都和vector差不多， 在队列前面插入可以用deque1.push_front(*i).

还有不同的是deque不需要用capacity和reserve来改善性能。它需要重新分配内存的次数较少。reserve也不会保持其迭代器有效性，在重新分配内存时，会使所有迭代器和引用失效。

链表

需要频繁在序列内部位置上进行插入或删除操作，并且不需要过多在序列内部进行长距离跳转

很多地方也跟deque和vector差不多， 删除那里有不同，可以用list1.erase(j++),这是vector和deque都没有的。

拼接

list1.splice(i1, list2);   i1是list1的有效迭代器，作用是把list2的内容插入到i1前， 完后list2为空链表

list1.splice(i1, list2, i2);   i2是list2的迭代器，作用是删除i2所引用的元素，并把它插入到i1之前，list1和list2可相同

list1.splice(i1, list2, i2, j2);   [i2,j2)是list2中的有效区间，作用是删除那段区间中的元素，并插入到i1之前，list1和list2可相同

排序相关

list1.sort();

list1.unique();

先排序，再删除链表中相邻的重复元素

--《标准模版库自修教程与参考手册》