CODEWITHSUNDEEP
c++sortingc++11booststl
mmdanziger
mmdanziger

Reputation: 4658

Is there a container in STL or Boost that retains sorted values after modification?

I would like to retain a running tally of ids and sizes, which are modified individually and accessible by id, as well as in order of size. Using the STL, the only things I can think of are:

  1. set<pair<int,int>,custom_comp> in which I remove and reinsert the pair every time I modify it. Big downside: can't be accessed by id, so O(N) to access anything because the hash table isn't being used and I have to iterate through everything to find by id...
  2. unordered_map<int,int> in which I just dump and sort (or search for max if that's all I need) when I need them in order. Big downside, O(N) to get the max, O(N log(N)) to sort (presumably).

Not the end of the world but it would be nice if there was a priority_queue-like container that allowed access to the whole heap or a map-like container that would re-sort (by value) on modification. Does such a thing exist in STL? In Boost? If not, why not? (At least that way, I'd learn something about data-structures even if I have to use a messy solution)

Upvotes: 1

Views: 160

Answers (1)

NetVipeC
NetVipeC

Reputation: 4432

Boost MultiIndex let you maintain a collection of element order by multiple key element, in your case you could use the two interesting data (id and order of size) as he key used to sort the multiindex and the data structure allow inplace replacement of elements (even changing keys, if keys are changed the replacement performances is O(log N) and no O(1) as in other data).

Upvotes: 2

Related Questions