现在,我们要检查一些可以补充算法复杂度的重要的容器相关问题,但首先我需要介绍一种STL容器的分类

来源:百度文库 编辑:神马文学网 时间:2024/03/29 18:23:26
方法,它被讨论的次数并不像它应该的那样多。那是连续内存容器和基于节点的容器的区别。
连续内存容器(也叫做基于数组的容器)在一个或多个(动态分配)的内存块中保存它们的元素。如果一个
条款1:仔细选择你的容器
新元素被查入或者已存元素被删除,其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率(参见条款5和14)和异常安全(就像我们将会看到的)。
标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。
基于节点的容器在每个内存块(动态分配)中只保存一个元素。容器元素的插入或删除只影响指向节点的指针,而不是节点自己的内容。所以当有东西插入或删除时,元素值不需要移动。表现为链表的容器——比如list和slist——是基于节点的,所有的标准关联容器也是(它们的典型实现是平衡树)。非标准的散列容器使用不同的基于节点的实现,就像我们将会在条款25中看到的。
利用这个不恰当的术语,我们已经准备好描述一些大多数关于在容器间选择的问题。在这个讨论中,我略过考虑非STL类容器(比如,数组、bitset等),因为毕竟这是本关于STL的书。
● 你需要“可以在容器的任意位置插入一个新元素”的能力吗?如果是,你需要序列容器,关联容器做不到。
● 你关心元素在容器中的顺序吗?如果不,散列容器就是可行的选择。否则,你要避免使用散列容器。
● 必须使用标准C++中的容器吗?如果是,就可以除去散列容器、slist和rope。
● 你需要哪一类迭代器?如果必须是随机访问迭代器,在技术上你就只能限于vector、deque和string,但你也可能会考虑rope(关于rope的更多信息在条款50)。如果需要双向迭代器,你就用不了slist(参见条款50)和散列容器的一般实现(参见条款25)。
● 当插入或者删除数据时,是否非常在意容器内现有元素的移动?如果是,你就必须放弃连续内存容器(参见条款5)。
● 容器中的数据的内存布局需要兼容C吗?如果是,你就只能用vector(参见条款16)。
● 查找速度很重要吗?如果是,你就应该看看散列容器(参见条款25),排序的vector(参见条款23)和标准的关联容器——大概是这个顺序。
● 你介意如果容器的底层使用了引用计数吗?如果是,你就得避开string,因为很多string的实现是用引用计数(参见条款13)。你也不能用rope,因为权威的rope实现是基于引用计数的(参见条款50)。
于是你得重新审核你的string,你可以考虑使用vector
● 你需要插入和删除的事务性语义吗?也就是说,你需要有可靠地回退插入和删除的能力吗?如果是,你就需要使用基于节点的容器。如果你需要多元素插入(比如,以范围的方式——参见条款5)的事务性语义,你就应该选择list,因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对于有兴趣写异常安全代码的程序员来说非常重要。(事务性语义也可以在连续内存容器上实现,但会有一个性能开销,而且代码不那么直观。要了解这方面的知识,请参考Sutter的《Exceptional C++》的条款17[8]。)
● 你要把迭代器、指针和引用的失效次数减到最少吗?如果是,你就应该使用基于节点的容器,因为在
这些容器上进行插入和删除不会使迭代器、指针和引用失效(除非它们指向你删除的元素)。一般来
说,在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
● 你需要具有有以下特性的序列容器吗:1)可以使用随机访问迭代器;2)只要没有删除而且插入只发
条款1:仔细选择你的容器
生在容器结尾,指针和引用的数据就不会失效?这个一个非常特殊的情况,但如果你遇到这种情况,
deque就是你梦想的容器。(有趣的是,当插入只在容器结尾时,deque的迭代器也可能会失效,deque
是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。)
这些问题几乎不是事情的完结。比如,它们没有关注不同的容器类型使用不同的内存配置策略(条款10和14
讨论了这些策略的一些方面)。但是,它们已经足够是你信服了,除非你对元素顺序、标准的一致性、迭代
器能力、内存布局和C的兼容性、查找速度、因为引用计数造成的行为不规则、事务性语义的轻松实现和迭
代器失效的条件没兴趣,你得在容器操作的算法复杂度上花更多的考虑时间。当然这样的复杂度是重要的,
但这离整个故事很远。
当面对容器时,STL给了你很多选项。如果你的视线超越了STL的范围,那就会有更多的选项。在选择一个容
器前,要保证考虑了所有你的选项。一个“默认容器”?我不这么认为。
author:我要去桂林 summary.........