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

我可以以某种方式重载任何std :: multiset的操作符（就像用'（）'创建自定义comapre函数一样），以便当多重集中的2个元素被交换，所以另外两个元素是与另外两个元素链接的吗？Std :: multiset，跟踪元素的位置插入

我的意思是，我实际上想在multiset中插入elemetns {a，b，c，d，e}，但我也想跟踪它们在multiset中的位置，而不必使用.find （）。所以我想创建另一个向量pos，其中pos [k]是多重集中元素k的位置。因此，如果我有这个向量pos，我仍然必须在插入一个元素的时候创建多重集，而不是只把它放在多重集的正确位置，而且还要改变所有元素的pos []交换。

我并不确切地知道它的变化/掉期如何多集的元素对它们进行排序，但我能以某种方式重写所以不是：

swap(a,b);

我会碰到这样的。

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

如果你有，我怎么能跟踪一个多集内元素的位置的，任何其他的想法，而无需使用.find（）（它具有相等的元素O（N）复杂度）将是巨大的！

编辑

还有，我想我得改变一些东西，这样，当我插入一个新元素（N），它会得到正确的初始化为pos[n]，任何“交换”才制成。

来源

2012-02-13 Cristy

如果不继承multiset，即is not recommended，则无法覆盖这些值。所以你需要的是追踪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-13 20:44:53

作为替代方案，你可能想看看进入order statistic tree数据结构，它具有以下功能为O所有工作（log n）的时间：

插入
删除
Find Successor
查找前处理
通过键查找
查找指数
元素的泰尔指数（在O（1），如果你已经有一个迭代它）

换句话说，您可以通过位置或关键要求树的元素，并且可以让树告诉你给定元素的位置。它还以排序顺序存储元素（如std::multiset），并且可以很容易地处理重复的元素。总之，它可以像std::multiset一样有效地支持索引。

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

希望这会有所帮助！

来源

2012-02-13 20:53:28 templatetypedef

这个想法是我知道如何推动堆结构来完成我所需要的操作，但是我只想使用C++ std库中的函数来完成此操作，因为我需要为编程角色“尽可能快”地编写代码。 – Cristy 2012-02-13 21:32:23

@ Cristy-您需要支持哪些堆操作？你可以使用priority_queue吗？ – templatetypedef 2012-02-14 09:14:08

我需要：插入，删除第一个元素，并在更改一个元素值时更新。现在我使用multiset，当我更新时，我找到该元素的位置，从堆中删除它，更新元素值，重新插入堆中。 – Cristy 2012-02-14 14:00:56

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

回答

相关问题