16

在我的应用程序中，我有以下要求 -

  1. 数据结构将只用一些值（不是键/值对）填充一次。这些值可能会重复，但我希望数据结构只存储一次。

  2. 我将通过上面创建的数据结构的所有元素迭代 100 次。元素在迭代中出现的顺序无关紧要。

约束 1 表明我必须使用 set 或 unordered_set，因为数据不是键值对的形式。

现在集合插入比 unordered_set 插入成本更高，但数据结构在我的程序开始时只填充一次。

我相信决定因素将是我可以多快地遍历数据结构的所有元素。为此，我不确定 set 或 unordered_set 是否会更快。我相信标准没有提到这个事实，因为对于任何一种数据结构，这个操作都是 O(n)。但我想知道哪个数据结构 iterator.next() 会更快。

4

5 回答 5

16

有几种方法。

  1. 对您的问题的评论建议保留std::unordered_set具有最快O(1)查找/插入和O(N)迭代的 a（每个容器也是如此）。如果您的数据变化很大，或者需要大量随机查找，这可能是最快的。但是测试。
  2. 如果您需要在没有中间插入的情况下迭代 100 次，您可以对 a 进行一次O(N)复制std::vector并从连续的内存布局中获得 100 次。测试这是否比普通的std::unordered_set.
  3. 如果您在迭代之间有少量中间插入，则使用专用向量可能是值得的。如果您可以使用Boost.Container，请尝试boost::flat_set它提供了一个std::set带有std::vector存储后端的接口（即一个非常缓存和预取友好的连续内存布局）。再次测试这是否可以加快其他两种解决方案。

对于最后一个解决方案，请参阅 Boost 文档以了解一些权衡（最好了解所有其他问题，例如迭代器无效、移动语义和异常安全）：

Boost.Container flat_[multi]map/set 容器是基于 Austern 和 Alexandrescu 指南的基于有序向量的关联容器。这些有序向量容器最近也受益于向 C++ 添加移动语义，大大加快了插入和擦除时间。平面关联容器具有以下属性：

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

注意：通过更快的查找，这意味着 a在连续内存上执行，而不是flat_set对常规. 当然，a确实查找，这对于 large 会更快。O(log N)O(log N)std::setstd::unordered_setO(1)N

于 2014-07-01T09:38:58.797 回答
5

我建议您使用 set 或 unordered_set 进行“过滤”，完成后，将数据移动到固定大小的向量

于 2014-07-01T09:30:20.530 回答
4

如果数据结构的构建没有考虑到性能问题（或至少只是略微考虑），请考虑将数据保存到std::vector: 没有什么比它更好的了。

为了加快数据结构的初始构建，您可以先插入一个std::unordered_set或至少使用一个在插入之前检查是否存在。

在第二种情况下，它不需要包含元素，但可以包含例如索引。

std::vector<T> v;
auto h = [&v](size_t i){return std::hash<T>()(v[i]);};
auto c = [&v](size_t a, size_t b){return v[a] == v[b];};
std::unordered_set<size_t, decltype(h), decltype(c)> tester(0, h, c);
于 2014-07-01T09:34:56.370 回答
2

我强烈建议您不要在这种情况下使用。set是二叉树，并且unordered_set是哈希表 - 所以它们使用大量内存，并且迭代速度慢且参考局部性差。如果你不得不频繁地插入/删除/查找数据，set还是unordered_set不错的选择，但现在你只需要读取、存储、排序数据一次，只需要多次使用数据。

在这种情况下，排序向量可能是一个不错的选择。vector是动态数组，所以开销很低。

直接看代码就行了。

std::vector<int> data;

int input;
for (int i = 0; i < 10; i++)
{
    std::cin >> input;
    data.push_back(input); // store data
}

std::sort(data.begin(), data.end()); // sort data

就这样。您的所有数据都已准备就绪。

如果您需要删除重复项set，只需在排序后使用unique-即可。erase

data.erase(
    std::unique(data.begin(), data.end()),
    data.end()
    );

请注意，您应该使用lower_bound,upper_bound而equal_range不是findorfind_if来使用排序数据的好处。

于 2014-07-01T13:17:57.543 回答
2

无序集使用哈希表来提供接近 O(1) 的时间搜索。这是通过使用键的散列来计算您正在寻找的元素（键）与数据集开头的偏移量来完成的。除非您的数据集很小（如chars），否则不同的键可能具有相同的哈希（冲突）。

为了最大限度地减少冲突，无序集必须保持数据存储相当稀疏。这意味着找到一个密钥将是 O(1) 时间（除非发生冲突）。

然而，当迭代哈希表时，我们的迭代器会在我们的数据存储中遇到大量未使用的空间，这将减慢我们的迭代器查找下一个元素的速度。我们可以用额外的指针链接哈希表中的相邻元素，但我认为无序集不会这样做。

鉴于上述情况，我建议您为“集合”使用排序向量。使用二分法，您可以在 O(log n) 时间内搜索商店，并且迭代列表是微不足道的。向量具有内存连续的额外优势，因此您不太可能遇到缓存未命中。

于 2014-07-01T10:46:02.227 回答