选择数据结构

Question

我使用C++,说我想存储40个用户名,我只想使用一个数组.但是,如果我想存储40000个用户名,这在搜索速度方面仍然是一个好主意吗？我应该使用哪种数据结构来提高速度？

Answer 1

您需要指定插入和删除要求.是否需要删除并插入序列中的随机点？

另外,为什么需要按顺序搜索？您是否正在进行不适合哈希表查找的搜索？

目前我建议一个deque或一个list.通常最好选择一个具有接口的容器,以便为您的算法提供最简单的实现,然后只有在性能不足且备选方案提供必要的加速时才更改选择.

A vector有两个主要优点,没有每个对象的内存开销,尽管向量将过度分配以防止频繁复制并且对象被连续存储,因此顺序访问往往很快.这些也是它的缺点.不断增长的向量需要重新分配和复制,并且从向量末尾以外的任何位置插入和删除也需要复制.连续存储可能会对具有大量对象或大对象的向量产生问题,因为即使只有轻微的内存碎片,连续的存储要求也很难满足.

A list不需要连续存储,但列表节点通常具有两个指针的每对象开销(在大多数实现中).这在非常小的对象列表中可能很重要(例如,在指针列表中,每个节点是数据项大小的3倍).从列表中间插入和删除非常便宜,并且列表节点永远不需要在创建后移动到内存中.

A deque使用分块存储,因此它具有与向量类似的低每个对象开销,但不需要在整个容器上进行连续存储,因此对于碎片化的内存空间没有相同的问题.它通常是收藏品的一个很好的选择,往往被忽视.