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

时间：2010-08-30 来源：chhaya

http://www.chhaya.me/?p=287

向量：

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

构造序列：

vector<T> v1; //空序列

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

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

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

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

vector<T> v1(v2);

vector<T> 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;
}