2

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

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

所以，如果我有这个向量 pos，当我在其中插入一个元素时，我仍然必须制作 multiset，不仅要将它放在 multiset 中的正确位置，还要更改所有交换元素的 pos[]。

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

swap(a,b);

我会有类似的东西。

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

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

编辑

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

4

2 回答 2

2

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

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

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

这似乎是最好的方法，尽管不幸的是顺序统计树不在 C++ 标准库中。您需要为他们找到第三方库。

希望这可以帮助！

于 2012-02-13T20:53:28.007 回答
0

如果不继承multiset，则无法覆盖这些，不推荐这样做。所以你需要的是跟踪元素在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针对您的类型，当交换两个元素时，交换它们在位置向量中的位置。

于 2012-02-13T20:44:53.397 回答