4

我需要一个可以保存一组数字并尽可能快地对它们进行排序的数据结构。

我认为列表会很好，因为在列表中插入一个新数字会比向量更容易（这需要在插入后复制元素）。但是，遍历链表（我使用排序列表作为查找以从 unordered_map 中获取对象）可能要慢得多，因为内存分散在整个堆中。

我正在考虑使用地图，但是由于非连续性，这不会也有不好的内存访问吗？

一个静态分配的数组（有很多空白空间）和一个快速排序算法是我想到的另一个想法......

回顾一下——我需要一个允许我插入新元素并尽快重新排序元素的数据结构。元素将是数字。

任何帮助表示赞赏？

4

5 回答 5

2

The fastest data structure is an array- contiguous regions of memory, optimal for the cache.

Sorting depends. A combination of quicksort with insertion sort used to sort sub-arrays below a certain size might be your best bet without resorting to something more esoteric.

于 2013-10-04T09:55:42.767 回答
0

Boost.Containers库包含一个flat_set数据结构。它在数据存储std::set之上实现了一个接口。std::vector根据文档的优势

  • 比标准关联容器更快的查找
  • 比标准关联容器快得多的迭代
  • 小对象的内存消耗更少（如果使用了 shrink_to_fit 则对于大对象）
  • 提高缓存性能（数据存储在连续内存中）
  • 不稳定的迭代器（插入和擦除元素时迭代器失效）
  • 无法存储不可复制和不可移动的值类型
  • 比标准关联容器更弱的异常安全性（复制/移动构造函数在擦除和插入中移动值时会抛出）
  • 比标准关联容器更慢的插入和擦除（特别是对于不可移动的类型）
于 2013-10-04T10:02:55.597 回答
0

如果“数字集”是指每个数字仅出现一次，并且您希望对其进行排序，请使用 std::set。老实说，除非您要处理大量数据，否则 std::list 甚至 std::vector 可能就足够了。

于 2013-10-04T09:45:57.970 回答
0

您可能想考虑如何将这些对象存储在vector/map中。具有必要比较函子的智能指针可能是您想要的。

于 2013-10-04T09:42:05.363 回答
-1

最快的数据结构是什么

数组。

（和排序算法）

快速排序，前提是您可以容忍最坏情况的行为。否则可能是堆排序。

于 2013-10-04T09:47:14.057 回答