现在的位置: 首页 > 综合 > 正文

【温故而知新】C和C++5:STL容器技术综述

2014年09月05日 ⁄ 综合 ⁄ 共 1800字 ⁄ 字号 评论关闭

容器类是可以包含其他对象的类。STL中提供的较为常用的容器类有向量、链表、队列、集合和图等,每一种容器类都是一个模板,可以包含各种类型的对象。这些容器可以分为序列式和关联式两大类。

序列式容器主要有:

1、vector:向量类,可以认为是一种容量可变的数组,可以提供对元素的随机访问,而且可以在序列尾部快速插入和删除数据,并且在需要的时候可以方便地改变容器的大小;

2、list:双向链表类,不支持随机访问的数组类,遍历链表的元素需要从某个端点开始向前或向后遍历;

3、queue:队列,实现先进先出的功能。使用deque和list实现。所有元素占用连续存储控件,但是不能提供随机存取;

4、stack:栈容器,实现先进后出功能。使用vector、list和deque实现;

5、deque:双端队列,实现数据的先进先出功能,可以随机访问;

6、priority_queue:按值排序的队列容器,使用vector和deque创建了排序队列,依照优先级决定下一个元素。

关联式容器的数据存储按照顺序进行,其余序列式容器不同的地方在于使用关键字查找元素,主要分类有:

1、set:集合,该容器中的关键字和数据是同一个值因此不能包含相同元素;由于各个元素经过了排序,因此不能直接修改其中的元素,只能删除后重新添加;

2、multiset:多重集合,同set类似,区别在于可以包含相同元素;

3、map:映射类,由一组键值对组成的集合,每一个键只能与一个特定的值相联系,且不能存在重复的键;

4、multimap:多重映射类,同map类似,区别在于可以存在重复的键;

5、hash table:散列表,通常可以用于大数据搜索。


一、向量容器vector:

向量容器vector是STL提供的最简单的容器之一,可以提供类似数组的随机访问功能,此外比数组更强大之处在于可以方便地动态调整容器的容量。由于vector的存储结构是顺序存储,因此虽然vector可以在任意位置增删数据,但是只有在末尾进行操作时效率最高。vector类定义在头文件<vector.h>中。

vector定义了两个最常用的成员:

size_type vector::capacity() const;//返回当前能容纳的最大成员的个数;
void vector::reserve(size_type n);//申请分配内存达到n;

其他成员可参照相关文档;


二、双端队列deque:

一种动态数组的形式,可以高效率地向两端增删数据,同时在需要时可以动态地调整大小。deque类定义在<deque.h>中。

deque类完全继承自其基类,没有添加派生成员,其所有的变量和方法定义在随机接入容器random access、前向插入序列front insertion sequence、反向插入序列back insertion sequence中。

与vector相比,deque除了可以方便地使用push_back()在末尾添加数据之外,也可以使用push_front()在头部添加数据。


三、链表list:

list实现了双向链表功能。由于list采用链式存储结构,因此不支持随机存取,但是其优点是在链表的任何位置插入和删除元素都非常迅速。list结构定义在<list.h>中。

list类主要继承自双向容器Reversible、前向插入序列front insertion sequence和反向插入序列back
insertion sequence。此外还定义了多种自有方法,如splice/remove/unique/merge/reverse/sort等,具体可以查看官方文档。


以上三类是STL提供的基本容器,除此之外STL还在这些基本容器的基础上提供了stack、queue、priority_queue、slist等容器,分别实现了栈、队列、优先级队列和双向迭代链表等功能。其使用方法大同小异,具体可搜索官方文档。


四、关联式容器:

set、map等关联式容器相比于序列式应用稍少一些。从总的思想上来看,序列式容器可以认为是数组、链表等结构的扩展,倾向于以排列的形式组织数据;而关联式容器通常没有这种先后继的关系,更倾向于一种集合的形式,因此可以处理更加复杂的数据结构。具体各个类的方法可以参考官方文档。


ps:看到这里,感觉STL跟Objective-C中的Foundation Framework有些神似的感觉……



抱歉!评论已关闭.