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

Question

我可以以某种方式重载任何std：：multiset的操作符(就像使用'()‘来创建自定义comapre函数一样)，以便在交换多集中的两个元素时，另外两个元素也可以从另一个向量链接到这些元素吗？

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

因此，如果我有这个向量pos，当我在其中插入一个元素时，我仍然必须使multiset，不仅把它放在multiset中的正确位置，而且改变所有交换元素的pos[]。

我不知道如何对多集更改/交换进行排序，但我是否可以以某种方式覆盖这些更改/交换，而不是：

swap(a,b);

我要一些类似的东西。

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

如果您有任何其他的想法，如果不使用.find() (对于相同的元素具有O(N)复杂性)，我可以跟踪元素在多个集合中的位置，那就太好了！

编辑

而且，我想我必须改变一些东西，这样当我插入一个新的元素(n)时，它将得到pos[n]的正确初始化，然后再进行任何“交换”。

Answer 1

作为另一种选择，您可能需要查看顺序统计树数据结构，它具有以下功能，所有功能都在O(log )时间内工作：

• 插入
• 删除
• 寻找接班人
• 查找前辈
• 按键查找
• 按索引查找
• 告诉元素的索引(在O(1)中，如果已经有迭代器)

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

这似乎是最好的方法，但不幸的是，C++标准库中没有顺序统计树。你得为他们找个第三方图书馆。

希望这能有所帮助！

Answer 2

如果不继承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，当交换两个元素时，您可以交换它们在位置向量中的位置。