7.2　容器

容器主要有两类：顺序（sequence）容器和关联（associative）容器。顺序容器（vector、list和deque）是一系列元素的有序集合。其中，vector是用处最大的一种顺序容器；deque是一个双端队列容器，能够很方便地在头部和尾部添加元素；list使得内部插入和删除更有效和便利。关联容器（set、multiset、map和multimap）包含查找元素的键值。set是一种按照有序关系存储值的容器，其中每个元素只出现一次；multiset可以存储多个数值相同的元素；map容器是基本的关联数组，它需要为存储的元素定义一个比较操作；multimap是map的泛化实例，它允许键值重复，所以一个键可以链接到多个值上。

两类不同的容器共享一个相似的接口。

典型的STL容器接口

?构造函数，包括默认构造函数和复制构造函数。

?元素访问接口。

?元素插入接口。

?元素删除接口。

?析构函数。

?迭代器。

可以使用迭代器遍历容器。迭代器作为一个模板，可以优化对STL容器的使用。

文件 stl_deque.cpp

// A typical container algorithm

template <class Summable>

Summable sum(deque<Summable> &dq)

{

   deque<Summable>::iterator p;

   Summable s = 0;

   for (p = dq.begin(); p != dq.end(); ++p)

      s += *p;

   return s;

}

deque sum()函数解析

■ template <class Summable>

 double sum(deque<Summable> &dq)

这个函数计算包含在双端队列容器dq中的元素的总和。这里使用引用传递参数可以避免大数据结构可能产生的复制成本；选择标识符Summable是为了指出实例化类型应该能够做加法运算，并能识别出值0。将模板类标识符的首字母大写是一种惯例，原因是类标识符是一个元变量（meta-variable），编译器使用它生成机器代码时，要使用实际的类型对它进行实例化。

■ deque<Summable>::iterator p;

使用一个iterator遍历双端队列容器。迭代器p被解除引用后可以依次获得队列中存储的每一个值。这个算法与顺序容器一起工作，所有类型都定义了operator+=()。容器中包括判等运算符和比较运算符，以及一些标准数据成员和成员函数。

■ for (p = dq.begin(); p != dq.end(); ++p)

     s += *p;

这是一个对STL容器进行遍历的标准方法，注意，这里也可以使用普通指针。如果使用一个基于迭代器区间的参数代替一个特定的容器类型，这个算法将更通用。

如表7-1所示，在下面对于容器类接口的描述中将容器类指定为CAN。选择标识符CAN是因为容器能够存储数据项。

表7-1　 STL容器定义

CAN::value_type    CAN中存放值的类型

CAN::reference      值的引用类型

CAN::const_reference    const引用

CAN::pointer  指向值类型的指针

CAN::iterator  迭代器类型

CAN::const_iterator       访问const值的const迭代器

CAN::reverse_iterator    向后移动的反向迭代器

CAN::const_reverse_iterator  const反向迭代器

CAN::difference_type    表示两个CAN::iterator值之差

CAN::size_type      表示difference_type值的整型大小

所有的容器类中都包含这些定义。例如，在使用vector容器类的时候，vector <char> :: value_type表示一个存储在vector容器中的字符值，可以使用vector<char>:: it-erator遍历整个容器。例如：

文件 stl_vector_char.cpp

#include <iostream>

#include <typeinfo>

#include <vector>

using namespace std;

int main() {

   char c;

   vector<char>::value_type v;

   if (typeid(c) == typeid(v))

      cout << "vector<char>::value_type is just char"

           << endl;

   else

      cout << "vector<char>::value_type differs "

           << "from char" << endl;

}

表7-2列出了容器中包含的大量的标准成员函数，表7-3列出了容器中使用的判等运算符和比较运算符。

表7-2　STL容器成员

CAN::CAN()  默认构造函数

CAN::CAN(c) 复制构造函数

c.begin() CAN c的起始位置

c.end()    CAN c的警戒位置，即CAN c的最后一个元素的下一个位置

c.rbegin()       反向迭代器的起始位置

c.rend()   反向迭代器的警戒位置

c.size()    CAN中的元素个数

c.max_size()   元素的最大可能数量

c.empty()       如果c为空则为true

c.swap(d)       交换c和d的数据

表7-3　STL容器运算符

== != < > <= >=    用于CAN::value_type的判等运算符和比较运算符

7.2.1　顺序容器

顺序容器（vector、list和deque）有一个可访问的元素序列。在许多情况下，C++的数组类型也可以看作是一个顺序容器。stl_vector2程序中创建了一个包含5个元素的vector v。这里使用了deque库和vector库。

文件 stl_vector2.cpp

// Sequence Containers - insert a vector into a deque

// Simple STL vector program

#include <iostream>

#include <vector>

#include <deque>

using namespace std;

int main()

{

   int data[5] = { 6, 8, 7, 6, 5 };

   vector<int> v(5, 6);                             // 5 element vector

   deque<int> d(data, data + 5);

   deque<int>::iterator p;

   cout << "\nDeque values" << endl;

   for (p = d.begin(); p != d.end(); ++p)

      cout << *p << '\t';            // print:6 8 7 6 5

   cout << endl;

   d.insert(d.begin(), v.begin(), v.end());

   for (p = d.begin(); p != d.end(); ++p)

      cout << *p << '\t';             // print:6 6 6 6 6 6 8 7 6 5

   cout << endl;

}

stl_vector程序解析

■ int data[5] = { 6, 8, 7, 6, 5 };

 vector<int> v(5, 6);           // 5 element vector

 deque<int> d(data, data + 5);

 deque<int>::iterator p;

向量v初始化了一个有5个int型元素的容器，初值为6。双端队列d使用迭代器值data和data+5初始化了一个有5个元素的容器。这里使用的是一种标准的容器类构造函数，注意它是如何使用迭代器区间为构造函数传递参数的。许多STL函数使用迭代器区间作为参数，这里使用数组指针作为迭代器的值，起始值是指针地址d，结尾警戒值是指针地址d+5。这里声明了迭代器p但是没有初始化，而deque<int>d由5个值（6,8,7,6和5）初始化。

■ for (p = d.begin(); p != d.end(); ++p)

 cout << *p << '\t'; // print:6 8 7 6 5

注意，在标准用法中，d.end()用于终止循环，原因是它是容器结束迭代器的警戒值。另外还要注意，++这个增量操作将迭代器推进到容器的下一个位置，对迭代器的解除引用也与指针操作类似。

■ d.insert(d.begin(), v.begin(), v.end());

成员函数insert()将从v.begin()开始到v.end()结束这个迭代器区间（不包括v.end()）的值插入在d.begin()处。成员函数insert()是STL中一个非常典型的成员函数，它使用第一个迭代器值作为插入点，使用迭代器区间的值作为插入值。

■ for (p = d.begin(); p != d.end();++p)

     cout << *p << '\t';        // print:6 6 6 6 6 6 8 7 6 5

在双端队列d的开始处插入5个值为6的新元素，现在遍历d后的输出是10个元素，如注释所示。

表7-4中给出了一些顺序容器的成员函数。下面对容器类接口的描述中将容器类名指定为SEQ，表中不包括已经在CAN中介绍的接口。表7-4中指定的结尾值e_it可以理解为警戒值。

表7-4　STL顺序容器成员

SEQ::SEQ(n,v)      使用值为v的n个元素初始化

SEQ::SEQ(b_it,e_it)     使用[b_it,e_it)区间内的元素初始化

c.insert(w_it,v)      在w_it前面插入值v

c.insert(w_it,v,n)    在w_it前面插入n个v值

c.insert(w_it,b_it,e_it)   在w_it前面插入[b_it,e_it)区间内的元素

c.erase(w_it)   移除w_it处的元素

c.erase(w_it,e_it)    移除[w_it,e_it) 区间内的元素

7.2.2　关联容器

关联容器（set、multiset、map和multimap）拥有基于键（key）的可访问元素和一个有序关系Compare，Compare是关联容器中的比较方法。7.6节中介绍如何为类编写Compare方法，这些类中重载了operator()函数。

简单来说， set是一个按照有序关系存储唯一值的容器。例如，它可能按照字典顺序（按照字母或者字典顺序）存储了一系列字符串，或者按照值的大小存储了一系列整数。multiset是set的泛化，它能存储同一个值的多个副本。map容器包含一对值，每一个元素都是一个键-值（key-value）对。map可以按照一种有效的方式根据键来查找值，这也称为关联数组。multmap是map的泛化，它允许键值重复，所以一个键可以链接到多个值上。

下面是一个使用map库和string库的例子。

文件 stl_age.cpp

// Associative Containers - looking up ages

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

   map<string, int, less<string> > name_age;

   name_age["Pohl,Laura"] = 12;

   name_age["Dolsberry,Betty"] = 39;

   name_age["Pohl,Tanya"] = 14;

   cout << "Laura is " << name_age["Pohl,Laura"]

        << " years old." << endl;

}

stl_age程序解析

■ #include <map>

 #include <string>

这是map容器需要的两个标准头文件库，根据这些库可以基于string查找相应的信息。

■ map<string, int, less<string> > name_age;

map name_age是一个关联数组，它的键是string类型的，Compare对象是less<string>。map模板需要3个参数，这意味着可以使用string值查找存储在map里的int值，有序关系是less<string>。

■ name_age["Pohl,Laura"] = 12;

 name_age["Dolsberry,Betty"] = 39;

 name_age["Pohl,Tanya"] = 14;

map name_age里存储了3个人的年龄。

■ cout << "Laura is " << name_age["Pohl,Laura"]

       << " years old." << endl;

这里，关联检索用来获得Laura Pohl的年龄。普通数组检索一个存储的值需要花费常量级的时间，而map在每次查找时只需要一个对数级时间。

关联容器中有一些用于初始化的标准构造函数，这些构造函数与顺序容器的构造函数的区别是它们使用了比较方法。当不存在相同键的元素时，可以插入元素。

如表7-5所示，关联类为ASSOC。注意表中不包含CAN中已经描述的接口。

表7-5　STL关联容器定义

ASSOC::key_type  检索的键类型

ASSOC::key_compare   键的比较方法对象

ASSOC::value_compare 值的比较方法对象

如表7-6所示，关联容器中有一些用于初始化的标准构造函数。

表7-6　STL关联容器构造函数

ASSOC()       使用Compare的默认构造函数

ASSOC(cmp) 使用cmp作为比较方法的构造函数

ASSOC(b_it,e_it)   使用Compare，用[b_it, e_it)区间的元素初始化

ASSOC(b_it,e_it,cmp)   使用cmp作为比较方法，并使用[b_it, e_it)区间的元素初始化

如表7-7所示，关联容器的构造函数与顺序容器的构造函数的区别是使用了比较方法。

表7-7　STL插入和移除成员函数

c.insert(t)       　如果不存在与t具有相同键的元素，则插入t，并返回pair <iterator,bool>，如果插入成功，则bool的值为true

c.insert(w_it,t)       　以w_it作为查找的起始位置，并插入t。在set和map中，如果键值已经存在则插入失败，否则返回插入位置

c.insert(b_it,e_it)    　插入[b_it, e_it]区间内的元素

c.erase(k)       　移除键值为k的元素，并返回移除元素的个数

c.erase(w_it)   　移除w_it指向的元素

c.erase(b_it,e_it)    　移除[b_it, e_it)区间内的元素

如表7-8所示，当不存在相同键的元素时，可以插入元素。

表7-8　STL成员函数

c.find(k)  返回指向具有键k的元素的迭代器；否则结束查找

c.count(k)       返回具有键k的元素的个数

c.lower_bound(k)   返回指向大于或等于键k的第一个元素的迭代器

c.upper_bound(k)   返回指向大于键k的第一个元素的迭代器

c.equal_range(k)    返回由lower_bound和upper_bound返回值组成的一对迭代器

关联容器包括set、multiset、map和multimap，它们拥有基于键的可访问元素和一个有序关系Compare，Compare是关联容器中的比较方法。

下面是一个关于关联容器的更深入的例子，它使用multiset统计在100餐中每种蔬菜出现在菜单中的次数。这里使用一个随机数生成器选择给定的一餐中的蔬菜种类。除了打印每种蔬菜出现的次数以外，还将打印出multiset是如何存储这一信息的。

文件 stl_multiset.cpp

// Associative Containers - checking up on your diet 

#include <iostream>

#include <set>   // used for both set and multiset

#include <vector>

using namespace std;

enum vegetables { broccoli, tomato, carrot, lettuce,

                  beet, radish, potato };

int main() {

   vector<vegetables> my_diet(100);

   vector<vegetables>::iterator pos;

   vegetables veg;

   multiset<vegetables, greater<vegetables> > v_food;

   multiset<vegetables, greater<vegetables>>::iterator vpos;

   for (pos = my_diet.begin(); pos != my_diet.end();

         ++pos) {

      *pos = static_cast<vegetables>(rand() % 7);

      v_food.insert(*pos);

   }

   cout << "How often a vegetable is eaten." << endl;

   cout << " broccoli, tomato, carrot, lettuce,"

        <<"beet, radish, potato " << endl;

   for (veg = broccoli; veg <= potato;

        veg = static_cast<vegetables>(veg + 1) )

      cout << v_food.count(veg) << endl;

   cout << "\nOffering of vegetables" << endl;

   for (vpos = v_food.begin(); vpos != v_food.end();

            ++vpos)

      cout << *vpos << '\t';

   cout << endl;

}

stl_multiset程序解析

■ #include <set>               // used for both set and multiset

 #include <vector>

 using namespace std;

 enum vegetables { broccoli, tomato, carrot,

                 lettuce, beet, radish, potato };

这段程序产生一份随机的蔬菜菜单，然后使用multiset的特殊属性形成一个计数器，用于统计菜单中每种蔬菜出现的频率。set中的元素来自于类型vegetables。set库文件包含了set和multiset的模板。

■ vector<vegetables> my_diet(100);

 vector<vegetables>::iterator pos;

 vegetables veg;

在vector my_diet中存储所选择的vegetables。这个vector的长度为100，并且有一个关联式迭代器变量pos。变量veg是枚举类型vegetables类型的变量。

■ multiset<vegetables, greater<vegetables> > v_food;

 multiset<vegetables, greater<vegetables>>::iterator vpos;

multiset要使用比较关系，用于排序和有效地检索set中的元素。注意，迭代器是如何声明的。在声明相关迭代器时，必须再次复制所有的模板参数。

■ for (pos = my_diet.begin(); pos != my_diet.end();

     ++pos) {

     *pos = static_cast<vegetables>(rand() % 7);

     v_food.insert(*pos);

  }

这里随机生成7种可能的蔬菜。这些值同时插入到vector类型的my_diet以及multiset类型的v_food里。

■ for (veg = broccoli; veg <= potato;

       veg = static_cast<vegetables>(veg + 1) )

      cout << v_food.count(veg) << endl;

multiset的count()方法打印出multiset存储的每个值。因此，v_food.count (broccoli)告诉我们这100餐中吃了多少次花椰菜。

7.2.3　容器适配器

容器适配器类修改现有的容器，它基于现有的类实现产生各种公有行为。STL提供了3种容器适配器，分别是stack、queue和priority_queue。stack可以与vector、list和deque进行配接，它需要实现back、push_back和pop_back操作。从这些基本的操作和表示中可以看到，stack适配器模板使用pop和push操作建立了等价的标准stack容器。stack是一种后进先出的数据结构。

queue可以与list或者deque配接，它需要实现empty、size、front、back、push_back和pop_front 操作。从这些基本的操作和表示中可以看到，queue适配器模板使用pop和push操作建立了等价的标准queue容器。queue是一种先进先出的数据结构。

priority_queue是一个队列，它有一些可访问的值，这些值之间的顺序由比较操作决定。它可以与vector或者deque配接，需要实现empty、size、push_back和front操作。它也需要一个比较函数对象，而且基础的容器必须支持随机访问迭代。

下面实现基础的vector容器与stack的配接。注意，这里使用STL的ADT代替了为这些类型个别设计的实现。这里需要stack、vector和string库。

嘿，我带来了加热器，但是我忘了带适配器了！

文件 stl_stack.cpp

// Adapt a stack from a vector

#include <iostream>

#include <stack>

#include <vector>

#include <string>

using namespace std;

int main()

{

   stack<string, vector<string> > str_stack;

   string quote[3] =

      { "The wheel that squeaks the loudest\n",

         "Is the one that gets the grease\n",

         "Josh Billings\n" };

   for (int i = 0; i < 3; ++i)

      str_stack.push(quote[i]);

   while (!str_stack.empty()) {

      cout << str_stack.top();

      str_stack.pop();

   }

}

程序的输出结果如下：

stl_stack程序解析

■ int main()

 {

     stack<string, vector<string> > str_stack;

这个栈使用了基础的表示，在这个例子中是vector。实际上，这限制了vector的实现只能采用后进先出的数据结构，即按照栈的方式实现。模板的第一个参数是存储在栈中的数据的类型，这里就是string；第二个参数是栈的实现。

■ for (int i = 0; i < 3; ++i)

     str_stack.push(quote[i]);

这里的基本操作是将数据压入栈中。注意3个字符串是如何从一句以逗号分隔的格言变成3行的。在将数据压入栈中后，最后一行出现在栈顶。

■ while (!str_stack.empty()) {

     cout << str_stack.top();

     str_stack.pop();

  }

这里先打印栈顶元素，然后再弹出栈中的元素。上述操作将一直持续到栈空为止，这将使得格言按照反序逐行输出。注意，push()、pop()、empty()和top()都是栈容器中的标准方法。

适配器类中有一些特殊的函数，如表7-9到表7-11所示。

表7-9　STL的stack适配器函数

void push(const value_type&v)     将v压入栈中

void pop()      移除栈顶元素

value_type& top() const 返回栈顶元素

bool empty() const 栈空时返回true

size_type size() const     返回栈中的元素个数

operator== 和 operator<      判等运算符和按字典顺序计算的小于运算符

表7-10　 STL的queue适配器函数

void push(const value_type&v)     将v放在队列尾部

void pop()      从队列前端移除元素

value_type& front() const     返回队列前端元素

value_type& back() const      返回队列尾部元素

bool empty() const 队列空时返回true

size_type size() const     返回队列中的元素个数

operator== 和 operator<      判等运算符和按字典顺序计算的小于运算符

表7-11　 STL的priority_queue适配器函数

void push(const value_type&v)     将v放在priority_queue中

void pop()      从priority_queue的头部移除元素

value_type& top() const 返回priority_queue的头部元素

bool empty() const priority_queue空时返回true

size_type size() const     返回priority_queue中的元素个数

正如表7-9中所述，使用判等运算符和小于运算符会分别比较两个栈的完整的内容。按字典顺序进行运算的小于运算符首先比较两个栈中的第一个元素，接着再依次比较每个元素对，直到出现小于关系为止。请检查一下厂商是否提供了依赖于特定系统的一些实现。一般说来，最好能够符合标准，这样可以避免只能使用特定产品。