c++ - 如何存储需要随机挑选和删除的数据， vector ，哈希表或其他？

Question

我正在编写一个程序，目前使用 vector ，它需要存储数据(以特定概率移动的原子)，以便能够以有偏随机概率有效地选取数据。

目前 vector 似乎很适合这个，因为我可以将多个站点分配给一个概率然后选择一个随机站点(所以如果原子 a 被选中的相对概率为 0.6，而原子 b 有 0.4，我可以分配3 个元素到 a 和 2 个到 b 然后随机选择任何元素)

然而，我需要删除与所选原子相关的所有站点，这在 vector 中意味着找到它们(或单独存储它们的位置)，将它们交换到最后并使用 push_back。根据我执行此操作的方式，它似乎非常慢或占用大量内存。

哈希表似乎是一种更好用的结构，因为它们可以让我更轻松地查找与特定原子相关的站点，但我仍然可以对哈希表使用相同的加权选择机制吗？

我以前从未使用过哈希表，还有其他并发症吗？还是我应该研究另一种更好的结构？

Answer 1

您是否考虑过使用 STL::list？然后你可以使用 list::remove .例如。将项目定位到 randomIndex:

auto it = myList.begin();
advance(it4, randomIndex-1);
cout << "Randomly picked atom is " << *it;

现在从列表中删除所有与该原子匹配的元素(没有双关语意):

myList.remove(*it);

STL::list 是一个链表，因此在删除元素时它通常比 vector 表现更好。