程序员C++C++

C++标准库学习（一）：顺序容器

2016-03-23  本文已影响312人  Mr希灵

参考书籍：C++ primer 第四版

顺序容器：它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。

标准库定义了三种顺序容器：vector、list和deque，他们的差别在于访问元素访问元素的方式，以及添加或删除元素相关操作的运行代价。vector支持快速随机访问，list支持快速插入/删除，deque是一个双端队列。
标准库来提供了三种容器适配器。实际上，适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。顺序容器适配器包括stack、queue和priority_queue类型。

容器只定义了少量操作，大多数额外操作则有算法库提供。容器类型的操作集合具有以下层次结构特点：一些操作适用于所有容器类型；另外一些操作则只适用于顺序或关联容器类型；还有一些操作只适用于顺序或关联容器类型的一个子集。

1 顺序容器的定义

所有的容器都是类模版，要定义某种特殊的容器，必须在容器后的尖括号内提供存放元素的数据类型。。容器元素类型必须满足以下两个约束：元素类型必须支持赋值运算； 元素类型的对象必须可以复制。C++ 语言中，大多数类型都可用作容器的元素类型。

vector<string> svec;

所有容器类型都定义了默认构造函数，用于创建指定类型的空容器对象。**为了使程序更清晰、简短，容器类型最常用的构造函数是默认构造函数。在大多数的程序中，使用默认构造函数能达到最佳运行时性能，并且使容器更容易使用。 **除了默认构造函数，容器类型还提供其他的构造函数，使程序员可以指定元素初值。

**将一个容器初始化为另一个容器的副本 **
将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。

vector<string> svec;
vector<string> svec2(svec);

初始化为一段元素的副本
尽管不能直接将一种容器内的元素复制给另一种容器，但系统允许通过传递一对迭代器间接实现该实现该功能。使用迭代器时，不要求容器类型相同。容器内元素类型也可以不相同，只要它们相互兼容，能够将要复制的元素转换为所构建的新容器的元素类型，即可实现复制。

 list<string> slist(svec.begin(), svec.end());

**分配和初始化指定数目的元素 **
创建顺序容器时，可显式指定容器大小和一个（可选的）元素初始化式。容器大小可以是常量或非常量表达式，元素初始化则必须是可用于初始化其元素类型的对象的值。

const list<int>::size_type list_size = 64; 
list<string> slist(list_size, "eh");

*注：接受容器大小做形参的构造函数只适用于顺序容器，而关联容器不支持这种初始化。 *

2 迭代器

与容器类型一样，所有迭代器具有相同的接口。例如，所有容器迭代器都支持以解引用运算从容器中读入一个元素，所有容器都提供自增和自减操作符来支持从一个元素到下一个元素的访问。

关系操作符只适用于 vector 和 deque 容器，这是因为只有这种两种容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素位置实现的随机访问，因此它们的迭代器可以有效地实现算术和关系运算。

//用于计算vector对象的重点位置
vector<int>::iterator iter = vec.begin() + vec.size()/2;

注：所有的容器都支持iter1 ==iter2和iter1!=iter2，而只有vector 和 deque 才支持iter1 <=iter2等关系运算。所以在用迭代器遍历容器时，最好使用iter1!=iter2来判断终止。

一些容器操作会修改容器的内在状态或移动容器内的元素，这样会使所有指向被移动的元素的迭代器失效，也可能同时使其他迭代器失效。使用无效迭代器是没有定义的，可能会导致与悬垂指针相同的问题。 例如，每种容器都定义了一个或多个 erase 函数。这些函数提供了删除容器元素的功能。任何指向已删除元素的迭代器都具有无效值，毕竟，该迭代器指向了容器中不再存在的元素。

3 顺序容器的常用操作

容器定义的操作非常少，只定义了构造函数、添加或删除元素的操作、设置容器长度的操作以及返回指向特殊元素的迭代器的操作。其他一些有用的操作，如排序、查找，则不是由容器类型定义，而是由标准算法定义。

3.1 begin 和 end 成员

begin 和 end 操作产生指向容器内第一个元素和最后一个元素的下一位置的迭代器，这两个迭代器通常用于标记包含容器中所有元素的迭代器范围。

迭代器操作

3.2 添加元素

添加元素的方法.png 
vector<string> container;
string text_word; 
while (cin >> text_word) 
     container.push_back(text_word); 

list<int> ilist; 
for (size_t ix = 0; ix != 4; ++ix) 
     ilist.push_front(ix);

任何 insert 或 push 操作都可能导致迭代器失效。当编写循环将元素插入到 vector 或 deque 容器中时，程序必须确保迭代器在每次循环后都得到更新。为了避免存储 end 迭代器，可以在每次做完插入运算后重新计算 end 迭代器值：

vector<int>::iterator first = v.begin();//不要令last = v.end();
while (first != v.end()) 
{ 
     first = v.insert(first, 42); // insert new value 
     ++first; // advance first just past the element we added 
}

3.3 顺序容器大小的操作

顺序容器大小的操作.png

3.4 访问元素

访问元素的操作.png 
if (!ilist.empty()) { 
     list<int>::reference val = *ilist.begin(); 
     list<int>::reference val2 = ilist.front(); 

     list<int>::reference last = *--ilist.end(); 
     list<int>::reference last2 = ilist.back(); 
}

在调用 front 或 back 函数之前，或者在对 begin 或 end 返回的迭代器进行解引用运算之前，必须保证 ilist 容器非空。如果该 list 容器为空，则 if 语句内所有的操作都没有定义。

在使用下标运算时，必须保证在指定下标位置上的元素确实存在，因为下标操作符本身不会做相关的检查。使用下标运算的另一个可选方案是 at 成员函数，这个函数的行为和下标运算相似，但是如果给出的下标无效，at 函数将会抛出 out_of_range 异常。

3.5 删除元素

删除顺序容器内元素的操作.png

pop_front 和 pop_back 函数的返回值并不是删除的元素值，而是 void。要获取删除的元素值，则必须在删除元素之前调用 front 或 back 函数。

while (!ilist.empty()) { 
         process(ilist.front()); // do something with the current top of ilist 
         ilist.pop_front();      // done; remove first element 
     }

erase 操作不会检查它的参数，因此必须确保用作参数的迭代器或迭代器范围是有效的。通常，程序员必须在容器中找出要删除的元素后，才使用 erase 操作。寻找一个指定元素的最简单方法是使用标准库的 find 算法。

string searchValue("Quasimodo"); 
list<string>::iterator iter = find(slist.begin(), slist.end(), searchValue); 
if (iter != slist.end())    slist.erase(iter);

3.6 swap交换操作

swap 操作实现交换两个容器内所有元素的功能。要交换的操作数必须是相同类型的容器，而且所存储的元素类型也必须相同。调用了 swap 函数后，右操作数原来存储的元素被存放在左操作数中，反之亦然。 **该操作不会删除或插入任何元素，而且保证在常量时间内实现交换。由于容器内没有移动任何元素，因此迭代器不会失效。 **

4 容器的选用

程序应根据访问、添加、删除容器元素所需的代价决定选择哪种类型的容器。vector 和 deque 容器提供了对元素的快速随机访问，但付出的代价是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的开销更大。list 类型在任何位置都能快速插入和删除，但付出的代价是元素的随机访问开销较大。通常来说，除非找到选择使用其他容器的更好理由，否则 vector 容器都是最佳选择。

如果无法确定某种应用应该采用哪种容器，则编写代码时尝试只使用 vector 和 lists 容器都提供的操作：使用迭代器，而不是下标，并且避免随机访问元素。这样编写，在必要时，可很方便地将程序从使用 vector 容器修改为使用 list 的容器。

5 容器适配器

容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如，stack（栈）适配器可使任何一种顺序容器以栈的方式工作。

所有适配器都定义了两个构造函数：默认构造函数用于创建空对象，而带一个容器参数的构造函数将参数容器的副本作为其基础值。默认的 stack 和 queue 都基于 deque 容器实现，而 priority_queue 则在 vector 容器上实现。在创建适配器时，通过将一个顺序容器指定为适配器的第二个类型实参，可覆盖其关联的基础容器类型。

 stack<int> stk(deq);
 stack< string, vector<string> > str_stk; 
 stack<string, vector<string> > str_stk2(svec);

对于给定的适配器，其关联的容器必须满足一定的约束条件。stack 适配器所关联的基础容器可以是任意一种顺序容器类型。因此，stack 栈可以建立在 vector、list 或者 deque 容器之上。而 queue 适配器要求其关联的基础容器必须提供 push_front 运算，因此只能建立在 list 容器上，而不能建立在 vector 容器上。priority_queue 适配器要求提供随机访问功能，因此可建立在 vector 或 deque 容器上，但不能建立在 list 容器上。

栈容器适配器支持的操作

priority_queue 允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部，而是放在比它优先级低的元素前面。标准库默认使用元素类型的 < 操作符来确定它们之间的优先级关系。


队列和优先级队列支持的操作
上一篇下一篇

猜你喜欢

热点阅读