C++程序设计:原理与实践(进阶篇)15.10 容器概览-阿里云开发者社区

开发者社区> 华章计算机> 正文

C++程序设计:原理与实践(进阶篇)15.10 容器概览

简介:
+关注继续查看

15.10 容器概览


STL提供了一些容器:

标准容器

vector 连续存储的元素序列;应用作默认容器

list 双向链表;当你希望在不移动现有元素的情况下完成对元素的插入和删除时使用

deque list和vector的交叉;除非你对算法和计算机体系结构知识非常精通,否则不要使用它

map 平衡有序树;当你需要按值访问元素时使用它(参见16.6.1~16.6.3节)

multimap 平衡有序树,可以包含同一个key的多个拷贝;当你需要按值访问元素时使用它(参见16.6.1~16.6.3节)

unordered_map 哈希表;一种优化的map;当映射规模很大、对性能要求很高且可以设计出好的哈希函数时使用它(参见16.6.4节)

unordered_multimap 可以包含同一个key的多个拷贝的哈希表;一种优化的multimap;当映射规模很大、对性能要求很高且可以设计出好的哈希函数时使用它(参见16.6.4节)

set 平衡有序树;当你需要追踪单个值时使用它(参见16.6.5节)

multiset 可以包含同一个key的多个拷贝的平衡有序树;当你需要追踪单个值时使用它(参见16.6.5节)

unordered_set 类似unordered_map,但只保持值而非(键,值)对

unordered_multiset 类似unordered_multimap,但只保持值而非(键,值)对

array 大小固定的数组,不存在内置数组所存在的大部分问题(参见15.9节)

 

你能在书籍或在线文档中找到关于这些容器及其使用的大量信息。下面是一些高质量的参考资料:

Josuttis, Nicholai M. The C++ Standard Library: A Tutorial and Reference. Addison-Wesley, 2012. ISBN 978-0321623218. Use only the 2nd edition.

Lippman, Stanley B., Jose Lajoie, and Barbara E. Moo. The C++ Primer. Addison-Wesley, 2005. ISBN 0201721481. Use only the 5th edition.

Stroustrup, Bjarne. The C++ Programming Language. Addison-Wesley, 2012. ISBN 978-0321714114. Use only the 4th edition.

The documentation for the SGI implementation of the STL and the iostream library: www.sgi.com/tech/stl. Note that they also provide complete code.

你觉得被骗了吗?你觉得我们应该向你介绍所有容器及其应用吗?这是不可能的。相关的标准特性、技术以及库实在是太多了,你不可能一下就把它们全部掌握。程序设计领域是如此丰富,任何人都难以掌握所有特性和技术,它同时也是一门高雅的艺术。作为一名程序员,你必须养成查找语言特性、库和相关技术新信息的习惯。程序设计是一个时刻快速变化的领域,所以安于现状是走向落后的“秘诀”。“查一查”对很多问题都是一个很好的答案,而随着你的技能逐渐增长、成熟,这一答案会变得越来越重要。

另一方面,你会发现当你了解了vector、list、map以及第16章中介绍的标准算法后,其他STL容器或类STL容器的使用会变得非常容易,你还会发现非STL容器及其应用也变得容易理解了。

那么什么是容器呢?在上述所有资源中你都可以找到STL容器的定义。这里我们只给出一个非正式的定义。一个STL容器

是一个元素序列[begin():end())。

提供拷贝元素的拷贝操作。拷贝可以通过赋值操作或拷贝构造函数来实现。

其元素类型命名为value_type。

具有名为iterator和const_iterator的迭代器类型。迭代器提供具有恰当语义的*、++(前缀和后缀)、==以及!=运算符。list的迭代器还提供可以在序列中向后移动的--操作,它也被称为双向迭代器(bidirectional iterator)。vector的迭代器还提供--、[]、+以及-运算符,它也被称为随机访问迭代器(random-access iterator)(参见15.10.1节)。

提供insert()、erase()、front()、back()、push_back()、pop_back()以及size()等操作,vector和map还提供下标操作(例如运算符[])。

提供比较运算符(==、!=、<、<=、>以及>=)进行元素比较。容器对<、<=、>、>=采用字典顺序,也就是说,它们按字典中开始单词排在首位的顺序比较元素。

上面这个列表只是给你一个关于容器的大概印象。更详细的内容请参见附录C。更准确的说明和更完整的特性列表可以参考《The C++ Programming Language》或C++标准。

一些数据类型提供了标准容器所要求的大部分特性,但又不是全部。我们称之为“拟容器”。最常见的如下表所示。

“拟容器”

T[n]内置数组 没有size()或其他成员函数;当可以使用vector、string或array等容器时,尽量不要选择内置数组

string 只存储字符,但对文本处理提供了许多有用的操作,例如连接(+和+=);相对于其他字符串,应优先选用标准字符串

valarray 具有向量操作的数值向量,但有许多限制制约了高性能实现;只有当你需要进行大量向量计算时使用

 

另外,许多个人与组织都致力于开发符合(或接近符合)标准容器要求的容器。

如存疑,选用vector。除非有充分的理由,否则选用vector。

15.10.1 迭代器类别

在我们之前的讨论中,似乎所有迭代器都是可以通用的。其实,只有在进行简单的操作时它们才是通用的,比如对某个序列进行一次遍历并读取每个值一次。如果你希望完成更为复杂的操作,例如向后遍历或下标操作,就会需要一些更为高级的迭代器了。

迭代器类别

输入迭代器 我们可以用++向前移动,用*读取元素值。istream提供的就是这类迭代器,参见16.7.2节。如果(*p).m有效,则可使用简写形式p->m

输出迭代器 我们可以用++向前移动,用*写入元素值。ostream提供的就是这类迭代器,参见16.7.2节

前向迭代器 我们可以反复用++向前移动,用*读写元素(当然,元素不能是const的)。如果(*p).m有效,则可使用简写形式p->m

双向迭代器 我们可以用++向前移动,用--向后移动,用*读写元素(除非元素是const的)。list、map和set所提供的就是这类迭代器。如果(*p).m有效,则可使用简写形式p->m

随机访问迭代器 我们可以用++向前移动,用--向后移动,用*或[]读写元素(除非元素是const的)。我们可以对随机访问迭代器进行下标操作,用+向迭代器加上一个整数,用-向迭代器减去一个整数。我们可以通过对指向同一序列的两个迭代器进行减法操作来得到它们的距离。vector提供的就是这类迭代器。如果(*p).m有效,则可使用简写形式p->m

 

从这些提供的操作我们可以看出,当可以使用输出或输入迭代器时,也可以使用前向迭代器完成相同的功能。双向迭代器也是一种前向迭代器,而随机访问迭代器也是一种双向迭代器。我们可以把迭代器类别图示如下:

 

注意,由于迭代器种类并不是类,因此这个层次结构并非是用派生实现的类层次。

简单练习

1. 定义一个含有10个元素{0,1,2,3,4,5,6,7,8,9}的int型数组。

2. 定义一个含有10个同样元素的vector<int>。

3. 定义一个含有10个同样元素的list<int>。

4. 另外再定义一个数组、一个向量、一个链表,并分别把它们初始化为上面所定义的数组、向量和链表的拷贝。

5. 把数组中的每个元素值加2,把向量中的每个元素值加3,把链表中的每个元素值加5。

6. 编写一个简单的copy()操作。

该操作像标准库copy函数一样把[f1,e1)复制到[f2, f2+(e1-f1))并返回f2+(e1-f1)。注意如果f1==e1,那么该序列为空,此时不需要复制任何内容。

7. 使用你的copy把数组中的内容拷贝到向量中,再把链表中的内容拷贝到数组中。

8. 用标准库f?ind()来判断向量中是否含有值3,如果有则输出它的位置;用f?ind()来判断链表中是否含有值27,如果有则输出它的位置。第一个元素的位置为0,第二个元素的位置为1,以此类推。注意,如果f?ind()返回的是序列尾,则说明没有找到所查的元素。记住,每一步后都要进行测试。

思考题

1. 为什么不同人编写的代码看起来会不一样?请举例说明。

2. 会有哪些关于数据的简单问题?

3. 存储数据有哪些不同的方式?

4. 可以对一组数据做哪些基本操作?

5. 理想的数据存储方式应该是怎样的?

6. 什么是STL序列?

7. 什么是STL迭代器?它支持哪些操作?

8. 如何把迭代器移到下一个元素?

9. 如何把迭代器移到上一个元素?

10. 当你试图把迭代器移动到序列尾之后时会出现什么情况?

11. 哪些迭代器可以移动到上一个元素?

12. 为什么要把数据与算法分离开?

13. 什么是STL?

14. 什么是链表?它和向量本质上的区别是什么?

15. 链表中的链接是什么?

16. insert()的功能是什么?erase()呢?

17. 如何判断一个序列是否为空?

18. list中的迭代器提供了哪些操作?

19. 如何使用STL遍历一个容器?

20. 什么时候应该使用string而不是vector?

21. 什么时候应该使用list而不是vector?

22. 什么是容器?

23. 容器的begin()和end()应该实现什么功能?

24. STL提供了哪些容器?

25. 什么是迭代器类别?STL提供了哪几类迭代器?

26. 哪些操作是随机访问迭代器提供了而双向迭代器没有提供的?

术语

algorithm(算法) begin() doubly-linked list(双向链表)

array container(array容器) container(容器) element(元素)

auto contiguous(连续的) empty sequence(空序列)

end() linked list(链表) traversal(遍历)

erase() sequence(序列) using

insert() singly-linked list(单向链表) type alias(类型别名)

iteration(迭代) size_type value_type

iterator(迭代器) STL(标准模板库)

习题

1. 如果还未完成本章所有“试一试”,请完成。

2. 编译运行15.1.2节中的例子Jack-and-Jill。利用几个小文件作为输入测试它。

3. 回顾回文的例子(见13.7节),用不同技术重写15.1.2节中的Jack-and-Jill程序。

4. 用STL技术找到并修改15.3.1节Jack-and-Jill例子中的错误。

5. 为vector定义输入和输出运算符(>>和<<)。

6. 基于15.6.2节中的内容,为Document编写一个“查找并替换”操作。

7. 在一个未排序的vector<string>中查找按字典顺序排在最后的字符串。

8. 编写一个可以统计Document中字符总数的函数。

9. 编写一个可以统计Document中单词数的程序。该程序有两个版本:一种将单词定义为“以空白符分隔的字符序列”,另一种将单词定义为“一个连续的字母序列”。例如,在第一种定义下,alpha.numeric和as12b都是一个单词,而在第二种定义下它们则都为两个单词。

10. 编写另一个统计单词的程序。在该程序中,用户可以指定空白符集合。

11. 以list<int>为(引用)参数,创建一个vector<double>,并将链表中的元素拷贝到向量中。验证拷贝操作的完整性与正确性。然后将元素按照值升序排序并打印。

12. 完成15.4.1~15.4.2节中list的定义,并让high()能正确运行。分配一个Link表示链表尾之后一个位置。

13. 实际上,在list中我们并不需要一个“真的”尾后位置Link。改写上面的程序,用0表示指向(不存在的)尾后位置Link(list<Elem>::end())的指针,这样可以使空列表的大小和一个指针的大小相同。

14. 定义一个单向链表slist,风格类似std::list。由于slist没有后向指针,list中的哪些操作可以合理地去掉?

15. 定义一个与指针vector很相似的pvector,不同之处在于pvector中的指针指向对象,而且其析构函数会对每个对象进行delete操作。

16. 定义一个与pvector很相似的ovector,不同之处在于[]和*运算符返回元素所指向的对象的引用,而不是返回指针。

17. 定义一个ownership_vector,像pvector一样保存对象指针,但为用户提供了一种机制,可以决定哪些对象为向量所有(即哪些对象由析构函数进行delete操作)。

18. 为vector定义一个范围检查迭代器(随机访问迭代器)。

19. 为list定义一个范围检查迭代器(双向迭代器)。

20. 运行一个小的计时实验来比较vector和list的使用代价。有关如何对程序进行计时的内容可以在26.6.1节中找到。生成N个属于区间[0,N)的int型随机数。每生成一个随机数就把它加入vector<int>中(该vector大小每次增加1)。保持该vector为有序的,也就是说,新元素插入位置之前的所有元素都小于等于新元素的值,而新元素之后的所有元素都大于新元素的值。用list<int>保存int完成相同的实验。在N取什么样的值时list会比vector快?请解释实验结果。该实验由John Bentley最先提出。

附言

如果我们有N种数据容器和M种想要对其执行的操作,那么结果很容易变成我们要编写N×M段代码。如果数据有K种不同的类型,那么代码的总数甚至会达到N×M×K。STL通过将元素类型作为参数(解决了因子K)以及将算法与数据访问分离解决了这一问题。通过利用迭代器实现任意算法对任意容器中数据的访问,我们只需编写N+M种算法。这大大简化了我们的工作。例如,如果我们有12种容器和60种算法,暴力方法需要编写720个函数;而STL的策略只需要编写60个函数和定义12种迭代器,这可以省去我们90%的工作。实际上,这还低估了节省的工作量,因为很多算法接受一对迭代器参数,而两个迭代器可以是不同类型(例如,参见习题6)。而且,STL还给出了算法定义规范,可以简化编写正确的、可组合的代码的工作,因此工作量的节省实际上会更大。

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
C++程序设计课程师生互动(2012年春第9周)
  今天看完同学博客比较早,看空间的动态,同学们还在继续上传。从中午开始,不断地有同学上线,赶在19:00之前传完。今天看得比较粗,很多没有写总结的,我数个数也就过去了;对留了言的,由感而发对上两句;有人提出疑问是必定要解答的,甚至代码中的问题可能还需要我调试一下才能发言。   在拳场上,我们有个规矩:当徒弟的,该怎么练就怎么练,时候到了,师傅自然就会指点。徒弟要主动练,要主动接近师傅。
933 0
C语言及程序设计进阶例程-28 动态规划法问题求解
贺老师教学链接 C语言及程序设计进阶 本课讲解 最短路径问题 #include&lt;stdio.h&gt; #define n 7 #define x 9999 /*用一个尽可能大的开销,代表结点之间没有通路*/ int map[n][n]= /*对图7.33中交通网的描述,map[i][j]代表i结点到j结点的开销*/ { {x,4,5,8,x,x,x
835 0
SNMP从入门到开发:进阶篇
管理信息库:MIB 我们要扩展mib首先必须清楚mib是如何定义的,用的什么语言,有哪些约定,遵循哪些规则等等。这些基本东西掌握过后,我们就可以很轻松的来写自己的mib文件了。 所谓管理信息库,或者MIB,就是所有代理进程包含的、并且能够被管理进程进行查询和设置的信息的集合,或者叫管理对象的集合,在RFC 1213 [McColghrie 和Rose 1991]中定义了MIB-II,即第二版的MIB库。
945 0
《C语言程序设计进阶教程》一1.1 编译
本文讲的是C语言程序设计进阶教程一1.1 编译,本节书摘来华章计算机《C语言程序设计进阶教程》一书中的第1章,第1.1节, Intermediate C Programming[美] 陆永祥(Yung-Hsiang Lu) 著 徐东 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2140 0
C语言及程序设计进阶例程-26 回溯溯法问题求解
贺老师教学链接 C语言及程序设计进阶 本课讲解 8皇后问题实现代码 #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;malloc.h&gt; void nQueens(int *x, int n); /*求解n皇后问题*/ int place(int *x, int k); /*判断是否可以
1004 0
C语言及程序设计进阶例程-29 枚举类型及其应用
贺老师教学链接 C语言及程序设计进阶 本课讲解 He先生方案一:用整型表示品牌、颜色 #include &lt;stdio.h&gt; int main( ) { int brand,color; //brand=0,1,2分别表示Lavida、Tiggo和Skoda //color=0,1,2分别表示红黑白 for(color=0; c
826 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载