std::multiset，跟踪元素'插入的位置

Question

我可以以某种方式重载 std::multiset 的任何运算符（就像使用 '()' 创建自定义 comapre 函数一样），以便当交换多重集中的 2 个元素时，另一个向量中的另外 2 个元素是否链接到这些元素？

我的意思是，我实际上想在多重集中插入​​ elemetns {a,b,c,d,e} ，但我也想跟踪它们在多重集中的位置，而不必使用 .find() 。所以我考虑创建另一个向量pos，其中pos[k]是元素k在多重集中的位置。

因此，如果我有这个向量 pos，当我在其中插入元素时，我仍然必须创建多重集，不仅要将其放在多重集中的正确位置，还要更改所有交换元素的 pos[]。

我不完全知道多重集如何更改/交换它的元素来对它们进行排序，但我可以以某种方式覆盖它，而不是：

swap(a,b);

我会有类似的东西。

swap(pos[a],pos[b]);
swap(a,b)

如果您对如何在不使用 .find() （对于相等元素具有 O(N) 复杂度）的情况下跟踪多重集中元素的位置有任何其他想法，那就太好了！

编辑

而且，我想我必须更改一些内容，以便当我插入新元素 (n) 时，它将在 pos[n] 之前获得正确的初始化进行任何“交换”。

Answer 1

作为替代方案，您可能需要查看顺序统计树数据结构，其具有以下功能，所有功能都在O(log n)时间内工作：

• 插入
• 删除
• 查找后继
• 查找前驱按键
• 查找
• 按索引查找
• 告诉元素索引（在O(1)，如果你已经有一个迭代器）

换句话说，你可以通过位置或键向树询问元素，并且可以让树告诉你给定元素所在的位置。它还按排序顺序存储元素（如 std::multiset），并且可以轻松处理重复元素。简而言之，它可以像有效支持索引的 std::multiset 一样使用。

这看起来可能是最好的方法，但不幸的是顺序统计树不在 C++ 标准库中。您需要为它们找到一个第三方库。

希望这有帮助！

Answer 2

如果不从 multiset 继承，则无法覆盖它们，不建议这样做。因此，您需要的是跟踪多重集中元素位置的逻辑。

如果将一个元素插入到 multiset 中，您将获得该元素的迭代器。您可以使用它来确定插入的元素之前的元素，并据此确定新的位置：

std::multiset<your_item_type> it = your_set.insert(item);
std::size_t new_element_pos = it != your_set.begin() ? pos[*(it--)] + 1
                                                     : pos[*(it++)] - 1

重要的是，现在您必须更新插入的元素之后的所有项目位置，方法是将它们加一。

要跟踪交换，您可以简单地将 std::swap 专门化为您的类型，并且当交换两个元素时，您可以交换它们在位置向量中的位置。