一、容器
作为STL的最主要组成部分--容器,分为向量(vector),双端队列(deque),表(list),队列(queue),堆栈(stack),集合(set),多重集合(multiset),映射(map),多重映射(multimap)。
STL容器就为我们提供了这样的方便,它允许我们重复利用已有的实现构造自己的特定类型下的数据结构,通过设置一些模版类,STL容器对最常用的数据结构提供了支持,这些模板的参数允许我们指定容器中元素的数据类型,可以将我们许多重复而乏味的工作简化。容器
特性
所在头文件
向量vector
可以用常数时间访问和修改任意元素,在序列尾部进行插入和删除时,具有常数时间复杂度,对任意项的插入和删除就有的时间复杂度与到末尾的距离成正比,尤其对向量头的添加和删除的代价是惊人的高的
双端队列deque
基本上与向量相同,唯一的不同是,其在序列头部插入和删除操作也具有常量时间复杂度
表list
对任意元素的访问与对两端的距离成正比,但对某个位置上插入和删除一个项的花费为常数时间。
队列queue
插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。
堆栈stack
堆栈是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则
集合set
由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序,具有快速查找的功能。但是它是以牺牲插入车删除操作的效率为代价的
多重集合multiset
和集合基本相同,但可以支持重复元素具有快速查找能力
映射map
由{键,值}对组成的集合,以某种作用于键对上的谓词排列。具有快速查找能力
阅读(1459) | 评论(0) | 转发(0) |