CODEWITHSUNDEEP
c++data-structuresselectionmultiset
XCS
XCS

Reputation: 28147

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

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.

Upvotes: 2

Views: 1614

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

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!

Upvotes: 2

Björn Pollex
Björn Pollex

Reputation: 76828

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.

Upvotes: 0

Related Questions