C++拾遗(四)——顺序容器

  之前一篇博文(《初窥标准库》)简单了解了一种最常用的顺序容器:vector类型。本文将对该文内容进行进一步的学习和完善,继续讨论标准库提供的顺序容器类型。所谓顺序容器,即将单一类型的元素聚集起来成为容器,并根据位置来存储和访问这些元素。标准库定义了三种顺序容器类型:vector,list和deque(double-ended queue双端队列)。同时还提供了三种顺序容器适配器(adaptor):stack,queue,priority_queue。

顺序容器 vector 支持快速随机访存
list 支持快速插入/删除
deque 双端队列
顺序容器适配器 stack 后进先出栈
queue 先进先出队列
priority_queue 有优先管理的队列

顺序容器的定义及迭代器

  • 容器元素类型必须满足两个条件:元素支持赋值运算,元素对象可以复制。以上为容器要满足的最低限度,关联容器则需要满足其他元素。注意到,引用不支持赋值运算,IO库类型不支持赋值或复制,故两者都不能作为容器的元素。
  • 注意:容器定义时,必须用空格隔开两个相邻的>符号,否则系统会将>>当作右移操作符,导致编译错误。
1 vector< vector<string> > liens; //ok
2 vector < vector<string>> lines; //error:>>treated as shift operator
  • 标准库为迭代器提供一些常用的运算,如解引用,自增自减等。
  • 关系操作符只适用于vector和deque容器,因为它们提供快速随机访存,可以根据元素位置直接访问容器元素。而list容器的迭代器既不支持算术运算,也不支持关系运算。
  • 迭代器范围为左闭合区间,即[first,last),表示从first所指示的位置到last所指示的位置之前的所有元素。对迭代器的要求为:它们指向同一个容器中的元素或超出末端的下一位置;first反复做自增运算能够到达last。
  • 某些容器操作会修改容器的内在状态或移动容器内的元素,这样将会使部分迭代器失效,进而导致与悬垂指针同样的问题。考虑如下两段代码,有何不同?为何?
     1 vector<int>::iterator mid = iv.begin() + iv.size()/2;
     2 vecor<int>::iterator iter = iv.begin();
     3 while (iter != mid)
     4     if (*iter == someVal)
     5         iv.insert(iter, 2*someVal);
     6 
     7 vector<int>::iterator iter = iv.begin();
     8 while (iter != iv.begin() + iv.size()/2)
     9 {
    10     if (*iter == someVal)
    11     {    
    12           iter = iv.insert(iter, 2*someVal);
    13           iter += 2;
    14     }        
    15     else
    16         ++iter;
    17 }

     

顺序容器的操作

  • 一些基本的操作,如begin和end成员,insert操作,resize操作,erase操作,assign操作,关系操作符等。

vector容器的自增长

  • vector类提供了两个成员函数:capacity和reserve,前者获取在容器需要分配更多的存储空间之前能够存储的元素总数,后者则告诉容器应该预留多少空间。注意,capacity不等于size。

容器的选用

  • 若要随机访存元素,应使用vector或deque。
  • 若要在容器的中间位置插入或删除元素,应使用list。
  • 若是在首尾部分插入或删除,使用deque。
  • 如果只需要在读取输入时在容器的中间位置插入元素,然后需要随即访问元素,则可将元素读入list容器,接着对此容器重新排序,使之适合顺序访问,在复制到vector中。
  • 选择容器的核心取决于:随机访存list的代价与在vector/deque中插入删除时复制元素的代价。

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。