c++ - 对于不断添加和删除的一组元素，我应该使用哪个容器

Question

我想知道哪个 STL 容器最适合在性能方面“不断”变化的元素集合。元素表示给定 View 空间中的对象，随着 View 的变化和对象移入和移出 View ，对象集合需要更新。每次更新 View 时，我都会得到一个应该在场景中的对象的 std::vector，按 UID 排序(我们称之为列表 A)。我想检查一下:

• 根据列表 A 从当前场景中的实际事物列表(称为列表 B)中删除不再可见的对象

• 再次基于列表 A 添加现在对列表 B 可见的新对象

两到四千个物体可能是所见物体数量的上限。我不能使用位图 vector ，因为对象 UID 达到数十亿。我在想我可以将 std::map 用于列表 B。我建议的更新列表 B 的策略是:

• 对于列表 B 中的每个 UID“i”，在列表 A 中搜索 UID“i”(使用 std::lower_bound)。如果列表 A 中不存在该 UID，则将其从列表 B 中移除。

• 对于列表 A 中的每个 UID“i”，在列表 B 中搜索 UID“i”(使用 std::map::lower_bound)。如果列表B中不存在该UID，则添加。

所以我想要一些建议，特别是如果我使用正确的容器类型。我不认为 std::vector 是列表 B 的好选择，因为插入/删除会很昂贵，如果我想对 std::find 使用二进制搜索，我必须明确排序。不过除此之外，我对其他容器类型知之甚少，也不知道它们是否更合适。

我还想知道我选择的更新列表 B 的一般方法是否是最有效的方法，我不仅遗漏了一些明显的东西。

Answer 1

听起来您的问题需要集合操作。从场景中移除不在 ListA 中的对象是集差操作。添加不在场景中的 ListA 中的对象是集合并集操作。当数据组织不适合位图时，集合操作通常是散列的候选对象。

您可以将其中一个操作数用于一组操作而不是类似散列的数据结构。这是您迭代的一个，并在另一个中进行查找，以保持行为(摊销)O(N)。

# left operand is list, right is hash:

set_diff (list x, hash y):
   val ret = make_hash()
   for i in x:
      if not y[i]
          ret[i] = i
   return ret

# vice versa

set_diff (hash x, list y)
    val ret = copy_hash(x)
    for i in y:
        if ret[i]
            delete ret[i]
    return ret             

顺便问一下，为什么要使用 lower_bound 进行搜索； ID不是唯一的还是什么？