C++基本序列式容器

我们以 vector、deque 和 list 为例介绍基本序列式容器，先来看一个关于 vector 容器的例子。

【例 1】

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

int main()
{
    vector< int > num;
    num.push_back( 50 );
    num.insert(num.begin(), 10);
    num.insert(num.end(), 20);
    num.push_back( 60 );
    num.push_back( 40 );
    cout << num.size() << endl;
    for(int i = 0; i < num.size(); i++)
        cout << num[i] << " ";
    cout << endl;
    num.erase(num.begin());
    cout << num.size() << endl;
    for(int i = 0; i < num.size(); i++)
        cout<< num[i] <<" ";
    cout << endl;
    return 0;
}

vector 可以理解为可以在两端插入、删除数据的数组，它提供了丰富的成员函数，用于操作数据。在使用 vector 时，必须包含<vector>头文件。

我们接着来看一下主函数。我们定义了一个 vector 类的 int 型实例 num，需要注意的是我们并没有指定实例的大小，因为 vector 是可以根据需求自动调整大小的，这一点跟数组不同。接下来我们调用函数 push_back()，该函数时在 vector 实例 num 的最后添加一个元素，因为一开始定义的时候为空，因此此时的 num 中只包含一个元素 50。

之后我们再调用 insert() 函数，该函数可以在指定位置插入元素。在 insert() 函数参数中，我们分别调用了 begin() 和 end() 函数，这两个函数分别用来访问 num 实例的头部和尾部：

• begin() 函数返回的是一个迭代器，如果容器不为空，则返回的迭代器指向容器的第一个元素；如果容器为空，则返回的迭代器指向容器尾部之后的位置。
• end() 函数同样返回的是一个迭代器，该迭代器指向的是容器尾部之后的位置。

当容器为空时，begin() 函数和 end() 函数都指向同一个位置，当容器有一个元素的时候，begin() 函数指向第一个元素的位置，end() 函数则指向第一个元素之后的位置。

调用 insert() 函数时，如果不是在容器尾部插入元素，则需要将所插入位置以后的元素都向后移一位，然后再将需要插入的元素插入到当前位置。例如，我们要在开头插入一个元素，则需要将容器现有的元素都向后移动一个位置，然后再将元素插入到第一个位置，因此 vector 在非尾部位置插入元素的效率不高。

在主函数中调用两次 insert() 函数之后，此时 num 容器中的元素有：10，50，20。之后又调用了两个 push_back() 函数，在容器尾部插入了两次数据，容器中的数据按顺序依次为：10，50，20，60，40。之后调用 size() 函数，返回容器的大小，因为此时容器中包含五个元素，因此返回值为 5。接下来我们将容器中的元素一一打印出来，我们可以通过下标操作符访问容器中的元素，打印结果为：10，50，20，60，40。

接下来调用 erase() 函数删除容器中的元素，删除位置是容器第一个元素，删除之后，该位置就会空出，此时后面的元素需要全部向前移动一个位置。此时容器中的元素按顺序一次为：50，20，60，40。

【例 2】

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

int main()
{
    deque< int > num;
    num.push_back(50);
    num.insert(num.begin(), 10);
    num.insert(num.end(), 20);
    num.push_back(60);
    num.push_back(40);
    cout<<num.size()<<endl;
    for(int i=0; i < num.size(); i++)
        cout<<num[i]<<" ";
    cout<<endl;
    num.erase(num.begin());
    cout<<num.size()<<endl;
    for(int i=0; i < num.size(); i++)
        cout<<num[i]<<" ";
    cout<<endl;
    return 0;
}

我们将例 1 中的 vector 换成 deque，运行程序发现两个程序的运行结果完全相同，是不是 vector 和 deque 相同呢？

答案是否定的。vector 说到底是个数组，在非尾部插入元素都需要移动其它元素，而 deque 则不同，它是一个可以操作数组头部和尾部的数组，因此在头部或尾部插入或删除数据的效率都是一样的。当我们需要频繁在头部和尾部插入或删除数据，则 deque 优于 vector。

【例 3】

#include <iostream>
#include <string>
#include <list>
using namespace std;

int main()
{
    list< string > str;
    str.insert( str.begin(), "A" );
    str.insert( str.begin(), "B" );
    str.insert( str.end(), "C" );
    str.insert( str.end(), "D" );
    str.insert( str.begin(), "E" );
    str.insert( str.begin(), "F" );
    list< string >::iterator iter;
    for(iter = str.begin(); iter != str.end(); iter++)
        cout<< * iter <<endl;
    str.reverse();
    for(iter = str.begin(); iter != str.end(); iter++)
        cout<< * iter <<endl;
    return 0;
}

本例中，我们定义了一个 list 容器 string 类型的实例 str，之后我们先在容器中添加了 6 个 string 类型元素，为了遍历 str 容器，我们定义了一个 iter 迭代器。通常每定义一个容器，就会有一个与容器数据类型相关的迭代器，本例中定义了 str 容器，则它对应的迭代器有：

list <string>::iterator
list<string>::const_iterator

如果我们不需要修改容器中的元素，仅仅只是进行访问的话，则可以定义为 const_iterator。

为了从头到尾遍历容器，我们先将迭代器指向 str.begin()，for 循环的结束条件是 str.end()，每次运行一遍循环体中的内容，迭代器自增一次，相当于指向下一个元素。我们之所以能够直接使用自增运算符，那是因为在容器类中已经对自增操作符进行了重载。

当我们需要获得当前迭代器所指的元素时，可以用取址操作符“*”来操作迭代器，“*iter”就为迭代器所指向的元素。此程序中之所以没有按照 vector 和 deque 的方式，以下标进行访问容器中的元素，是因为 list 并没有重载下标操作符，因而不能根据下标进行直接访问。

在主函数中我们调用了 reverse() 函数，对容器中的元素进行翻转，然后再次打印容器中的元素。

list 容器是一个双向链表，因此在容器中的任何位置插入元素，都不需要移动其它元素，因此执行效率是稳定的。