为什么要使用无序容器？(C++)

Question

我已经尝试过搜索但没找到任何东西.

我正在学习STL容器,并了解顺序和关联容器的优缺点,但是我不确定为什么有人会更喜欢无关容器而不是关联容器,因为它肯定不会影响元素的插入,查找和删除.

它纯粹是一种性能的东西,即它需要更多的处理才能插入/移除到关联容器,因为它必须经过排序？我不太了解系统方面的事情,但在我脑海中,我觉得无序容器需要比自动组织的容器更多"保养".

如果有人能说出一些亮点,那将非常感激.

Answer 1

纯粹抽象地考虑这样一个事实,即元素的排序是一个额外的"特征",你必须付出代价,所以如果你不需要它(比如在查找字典中),那么你不应该付钱为了它.

从技术上讲,这意味着可以通过使用哈希表来实现无序容器,其具有预期的查找和插入复杂度O(1),而不是有序容器的O(log n).

但是,在切线相关的注释中,当使用字符串作为键时,有一个巨大的实际优势:有序容器必须在树行走的每个地方执行完整的字符串比较,而散列容器只执行单个散列操作(甚至可以"优化"仅从非常长的字符串中采样固定数量的字符),并且在实践中经常变得更快.

如果排序是不是必需的,然后做的最好的办法是尝试了两种容器类型(其接口几乎是相同的),并比较在性能上的用户配置文件.

关于字符串比较的陈述对我来说似乎不直观.我希望`std :: less <std :: string>`是一个*eager*比较,一旦找到第一个不匹配的字符就会返回.相反,`std :: hash <std :: string>`可能会计算整个字符串的哈希值.因此,如果您将长字符串作为键,但字符串在前几个字符中都不同(我知道这是一个人为的例子),`map`可能比`unordered_map`更好.此外,+ 1建议实际尝试它. (5认同)
@Praetorian字符串比较可能会比哈希更多次完成. (3认同)
@Praetorian再想一想.哈希计算一次,其成本基本上等于将相同的字符串与相等的字符串进行一次比较.如果key完全在地图中,则必须在最终匹配元素中至少对字符串进行一次比较.因此,对于几乎所有实际应用,hash*都更快. (3认同)
@aspiring_programmer不,哈希确实是O(1),无论哈希大小.在任何给定时刻散列的每个项目平均重新进行一次,因此每个项目的插入成本平均保持在O(1),它不会增长,百万项目具有99.9999%的插入成本1和0.0001需要重新计算成本为百万的概率为百分之二,平均为2,即.恒定时间.Hash基本上用作表索引,表访问当然也是O(1). (3认同)