Std::multiset, keep track of elements' positions inserted

Question

Can I somehow overload any of std::multiset's operators (like you do with '()' to create a custom comapre function) so that when 2 elements in the multiset are swapped, so are another 2 elements from another vector linked to those?

I mean, I actually want to insert let's say elemetns {a,b,c,d,e} in the multiset, but I also want to keep track of their position inside the multiset, without having to use .find(). So I thought about creating another vector pos, where pos[k] is the position of element k in the multiset.

So, if I have this vector pos, I still must make the multiset when I insert an element in it, not to only put it in the right place in the multiset, but also change the pos[] of all elements swapped.

I don't exactly know how multiset changes/swaps it's element to sort them, but can I somehow override that so instead of:

swap(a,b);

I'll have something like.

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

And if you have any other ideas of how could I keep track of an element's position inside a multiset, without using the .find() (which has O(N) complexity for equal elements) would be great!

EDIT

And also, I guess that I have to change something so that when I insert a new element (n) it will get the right initialization for pos[n] , before any "swaps" are made.

templatetypedef · Answer 1 · 2012-02-13T21:17:40.330

2

As an alternative, you may want to look into the order statistic tree data structure, which has the following functionality all working in O(log n) time:

Insert
Delete
Find Successor
Find Predecessor
Find by key
Find by index
Tell index of element (in O(1), if you already have an iterator to it)

In other words, you can ask the tree for elements by position or by key, and can have the tree tell you what position a given element is at. It also stores the elements in sorted order (like std::multiset) and can easily be made to handle duplicate elements. In short, it can be used like a std::multiset that efficiently supports indexing.

This seems like it might be the best approach, though unfortunately order statistic trees aren't in the C++ standard library. You'd need to find a third-party library for them.

Hope this helps!

edited Feb 13 '12 at 21:17

answered Feb 13 '12 at 20:53

templatetypedef

362,284
104
897
1,065

The idea is that I know how to impelement a heap structure to do what I need, but I want to do this only using functions in C++ std library, because I need to code "as fast as possible" for programming contets. – XCS Feb 13 '12 at 21:32
@Cristy- What heap operations do you need supported? Can you use priority_queue? – templatetypedef Feb 14 '12 at 09:14
I need: insert, delete first element, and update when I change one elements value. Now I use multiset, and when I update, I find the position of that element, delete it from heap, update the elements value, re-insert it in heap. – XCS Feb 14 '12 at 14:00

score 0 · Answer 2 · edited May 23 '17 at 10:34

You cannot override these without inheriting from multiset, which is not recommended. So what you need is the logic to track the positions of the elements in your multiset.

If you insert an element into the multiset, you get an iterator to that element. You can use that to determine the element before the one you inserted, and from that determine the new position:

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

The important part is that now you have to update all positions of items after the one you inserted, by increasing them by one.

To keep track of swaps, you can simply specialize std::swap for your type, and when two elements are swapped, you swap their positions in the position-vector.

Std::multiset, keep track of elements' positions inserted

2 Answers2