c++ - 使用 STD 和 C++ 从具有常数时间的集合中删除一个值

Question

我需要一组整数并且能够在恒定时间内删除一个值。我该如何实现？

现在我正在使用 std::list 但它不是常数时间:

int myints[]= {17,89,7,14};
std::list<int> mylist (myints,myints+4);
mylist.remove(89);

Answer 1

如果你真的需要保证恒定的时间删除，那么你可能想要使用 std:bitset如果大小在编译时已知。

如果在编译时不知道大小，您可以考虑使用 Boost dynamic_bitset或 std::vector<bool> .后者经常受到批评，因为它不是容器，自 vector 以来，这可能会非常令人惊讶。在其他类型上实例化的是一个容器。尽管如此，它似乎可以很好地完成手头的工作。

在任何情况下，对于其中任何一个，您都会为允许范围内的每个值提供一个位/ bool 值。您可以通过将该索引处的位/ bool 值设置为 1/true 来“插入”一个值，并通过将该索引处的位/ bool 值设置为 0/false 来“删除”一个值。

对于前面的所有内容，枚举当前在集合中的元素(或者甚至找出它包含多少)在集合可能存储的数字范围内是线性的(而您当前的实现可以找到当前存储的项目数在具有恒定复杂性的集合中，并在集合中找到复杂性与其实际包含的项目数成线性关系的成员。

如果您希望数字集相对稀疏，并且可以忍受删除时间通常 大致恒定，即使不能保证，那么您可能想要使用 std::unordered_set相反。

还有std::set ，这保证了删除的对数复杂度。这通常是 O(log N)，比 std::unordered_set 慢(通常为 O(1))，但它的最坏情况也是 O(log N)，这比 unordered_set 的最坏情况要好。 ，在最坏的情况下是 O(N)。

与 std::list 相比，这些中的任何一个都可能显着提高速度你(显然)目前正在使用。确切的差异会有所不同，但速度提高一个完整数量级(对于此特定操作)根本不会令人惊讶(好吧，无论如何我都不会感到惊讶)。