在有关数据结构的经典内容讲解中,数据结构和附着其上的算法可以算得是两大华彩乐章。让我们稍微回想一下,数据结构在入门级领域都涉及到 一些什么内容?
首先是排序算法,各种各样的;其次是数据结构,有栈、队列、堆、链表、二叉树、哈希表、红黑树、B树、跳跃表等;然后是更复杂和抽象的,我也不了解了,像图、矩阵神马的,gemfield的日常编程工作中用不到,所以就没有学习和了解的欲望了。
然而,即使对于上面的那些提到的数据结构,c++标准库也提供了完整的实现,让我们来看看:
———字符串容器————
string
——–顺序容器———
vector
list
deque
——-顺序容器适配器—-
stack
queue
priority_queue
——-关联容器———-
set
map
****************************gemfield的分割线**************
上面的这些c++容器内部或者使用了堆、栈、红黑树、跳跃表等结构,或者其中的操作使用了排序等算法,然后结合了泛型编程技术,就形成了伟大的耐用的c++容器及算法库——STL(标准模板库)。下面详细说说:
C++ 语言中,大多数类型都可用作容器的元素类型。容器元素类型必须满足以下两个约束:元素类型必须支持赋值运算,元素类型的对象必须可以复制。
大多数类型满足上述最低限度的元素类型要求。除了引用类型外,所有内置或复合类型都可用做元素类型。引用不支持一般意义的赋值运算, 因此没有元素是引用类型的容器。
第一部分:关于顺序容器的操作:
每种顺序容器都提供了一组有用的类型定义以及以下操作:
1、在容器中添加元素;
2、在容器中删除元素;
3、设置容器大小以及相关大小的操作;
4、(如果有的话)获取容器内的第一个和最后一个元素;
5、关系操作符,如果两个容器具有相同的长度而且所有元素都相等,那么这两个容器就相等;否则,它们就不相等;
6、访问元素;
7、赋值与 swap。
特别的,对于vector容器来说:vector元素是连续存储的,当我们在容器内添加一个元素时,想想会发生什么事情:如果容器中已经没有空间容纳新的元素,此时,由于元素必须连续存储以便索引访问,所以不能在内存中随便找个地方存储这个新元素。于是,vector 必须重新分配存储空间,用来存放原来的元素以及新添加的元素:存放在旧存储空间中的元素被复制到新存储空间里,接着插入新元素,最后撤销旧的存储空间。如果 vector 容器在在每次添加新元素时,都要这么分配和撤销内存空间,其性能将会非常慢,简直无法接受。
对于不连续存储元素的容器,不存在这样的内存分配问题。例如,在 list 容器中添加一个元素,标准库只需创建一个新元素,然后将该新元素连接在已存在的链表中,不需要重新分配存储空间,也不必复制任何已存在的元素。
为了使 vector 容器实现快速的内存分配,其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区,用于存放新添加的元素。于是,不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器,这个分配策略带来显著的效率。事实上,其性能非常好,因此在实际应用中,比起 list 和 deque 容器,vector 的增
长效率通常会更高。
vector 容器处理内存分配的细节是其实现的一部分。然而,该实现部分是由 vector 的接口支持的。vector 类提供了两个成员函数:
capacity 和 reserve 使程序员可与 vector 容器内存分配的实现部分交互工作。capacity 操作获取在容器需要分配更多的存储空间之前能够存储的元素总数,而 reserve 操作则告诉 vector 容器应该预留多少个元素的存储空间。
弄清楚容器的 capacity(容量)与 size(长度)的区别非常重要。size 指容器当前拥有的元素个数;而 capacity 则指容器在必须分配新存储空间之前可以存储的元素总数。
程序使用这些操作的程序将决定应该选择哪种类型的容器。vector 和 deque 容器提供了对元素的快速随机访问,但付出的代价是,在容器的任意位置插入或删除元素,比在容器尾部插入和删除的开销更大。list 类型在任何位置都能快速插入和删除,但付出的代价是元素的随机访问开销较大。
通常来说,除非找到选择使用其他容器的更好理由,否则 vector 容器都是最佳选择。
适配器(adaptor)是标准库中通用的概念,包括容器适配器、迭代器适配器和函数适配器。本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。
例如,stack(栈)适配器可使任何一种顺序容器以栈的方式工作。
第二部分:关于关联容器的操作:
在开始介绍关联容器之前,必须先了解一种与之相关的简单的标准库类型——pair,该类型在 utility 头文件中定义。 继续阅读 →