1

我正在编写一个程序，目前使用向量，该程序需要以这样一种方式存储数据（以特定概率移动的原子），以便可以以有偏的随机概率有效地选择它。

目前，向量似乎很好，因为我可以将多个位点分配给一个概率，然后选择一个随机位点（因此，如果原子 a 的相对概率为 0.6，而原子 b 的相对概率为 0.4，我可以将 3 个元素分配给a 和 2 到 b 然后随机选择任何元素）

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

看起来哈希表可能是一个更好的结构，因为它们可以让我更容易地查找与特定原子相关的站点，但我仍然可以使用与哈希表相同的加权选择机制吗？

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

4

1 回答 1

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 是一个链表，因此在删除元素时它通常比向量执行得更好。

于 2013-10-02T13:36:30.363 回答