c++ - 用于随机访问和遍历元素的最佳数据结构(在 C++ 中)

Question

我有以下问题:我有一组 N 个元素(N 在几百到几千个元素之间，比方说在 500 到 3000 个元素之间)。在这些元素中，小部分将具有某些属性“X”，但元素以半随机方式“获得”和“失去”该属性；因此，如果我将它们全部存储在一个数组中，并将 1 分配给具有属性 X 的元素，否则为零，则这个 N 元素数组将有 n 个 1 和 N-n 个零(n 在 20-50 范围内很小)。

问题如下:这些元素以半随机的方式变化非常频繁(意味着任何元素都可以从 0 翻转到 1，反之亦然，但控制它的过程有点稳定，所以总数“n"有点波动，但在 20-50 范围内相当稳定)；并且我经常需要该集合的所有“X”元素(换句话说，数组的索引，其中数组的值为 1)，以对它们执行一些任务。

实现此目的的一种简单而缓慢的方法是简单地遍历数组，如果索引 k 的值为 1，则执行任务，但这有点慢，因为超过 95% 的元素的值为 1。解决方案将把所有的 1 放入一个不同的结构(有 n 个元素)，然后循环遍历该结构，而不是循环遍历所有 N 个元素。问题是最好使用什么结构？

元素会随机从 0 翻转到 1，反之亦然(从几个不同的线程)，所以没有任何顺序(元素从 0 翻转到 1 的时间与它翻转回来的时间无关) ，当我(从另一个线程)循环遍历它们时，我不需要以任何特定顺序循环(换句话说，我只需要全部获取它们，但与顺序无关)。

对此最佳结构有何建议？想到“std::map”，但由于 std::map 的键已排序(而且我不需要该功能)，问题是是否有更快的东西？

编辑:澄清一下，数组示例只是解决问题的一种(缓慢的)方法。问题的本质是，在一个包含“N”个元素的大集合“S”中，有一个不断变化的“n”个元素的子集“s”(n 比 N 小得多)，我需要循环设置“s”。速度至关重要，无论是向“s”添加/删除元素，还是循环遍历它们。因此，虽然从迭代的角度来看，像拥有 2 个数组并在它们之间移动元素这样的建议会很快，但向数组添加和删除元素会非常慢。听起来像 std::set 这样的基于散列的方法在迭代和添加/删除方面都能相当快地工作，问题是还有比这更好的方法吗？阅读关于“unordered_map”和“unordered_set”的文档并没有真正阐明元素的添加/删除相对于 std::map 和 std::set 有多快，也没有阐明通过它们的迭代会慢多少。另一件要记住的事情是，我不需要一个在所有情况下都能最好地工作的通用解决方案，我需要一个在 N 在 500-3000 范围内并且 n 在 20-50 范围内时效果最好的解决方案。最后，速度真的很重要；有很多慢速的方法，所以我正在寻找最快的方法。

Answer 1

由于顺序似乎并不重要，您可以使用单个数组并将具有属性 X 的元素放在前面。您还需要一个索引或迭代器，指向数组中从 X set 到 unset 的转换点。

• 要设置 X，请递增索引/迭代器并将该元素与您要更改的元素交换。
• 要取消设置 X，请执行相反的操作:递减索引/迭代器并将该元素与您要更改的元素交换。

自然地，对于多线程，您将需要某种互斥锁来保护数组和索引。

编辑:要在通常使用迭代器时保持半开范围，您应该颠倒上述操作的顺序:交换，然后递增/递减。如果您保留一个索引而不是一个迭代器，那么该索引将作为 X 的数量的计数来执行双重任务。