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中插入删除时复制元素的代价。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。