CODEWITHSUNDEEP
c++boostdictionary
rahul.deshmukhpatil
rahul.deshmukhpatil

Reputation: 997

How to retrieve the elements from map in the order of insertion?

I have a map which stores <int, char *>. Now I want to retrieve the elements in the order they have been inserted. std::map returns the elements ordered by the key instead. Is it even possible?

Upvotes: 5

Views: 5067

Answers (3)

utnapistim
utnapistim

Reputation: 27375

Now I want to retrieve the elements in the order they have been inserted. [...] Is it even possible?

No, not with std::map. std::map inserts the element pair into an already ordered tree structure (and after the insertion operation, the std::map has no way of knowing when each entry was added).

You can solve this in multiple ways:

  1. use a std::vector<std::pair<int,char*>>. This will work, but not provide the automatic sorting that a map does.

  2. use Boost stuff (@BartekBanachewicz suggested Boost.MultiIndex)

  3. Use two containers and keep them synchronized: one with a sequential insert (e.g. std::vector) and one with indexing by key (e.g. std::map).

  4. use/write a custom container yourself, so that supports both type of indexing (by key and insert order). Unless you have very specific requirements and use this a lot, you probably shouldn't need to do this.

Upvotes: 4

Sneftel
Sneftel

Reputation: 41503

A couple of options (other than those that Bartek suggested):

  • If you still want key-based access, you could use a map, along with a vector which contains all the keys, in insertion order. This gets inefficient if you want to delete elements later on, though.

  • You could build a linked list structure into your values: instead of the values being char*s, they're structs of a char* and the previously- and nextly-inserted keys**; a separate variable stores the head and tail of the list. You'll need to do the bookkeeping for that on your own, but it gives you efficient insertion and deletion. It's more or less what boost.multiindex will do.

** It would be nice to store map iterators instead, but this leads to circular definition problems.

Upvotes: 1

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39390

If you are not concerned about the order based on the int (IOW you only need the order of insertion and you are not concerned with the normal key access), simply change it to a vector<pair<int, char*>>, which is by definition ordered by the insertion order (assuming you only insert at the end).

If you want to have two indices simultaneously, you need, well, Boost.MultiIndex or something similar. You'd probably need to keep a separate variable that would only count upwards (would be a steady counter), though, because you could use .size()+1 as new "insertion time key" only if you never erased anything from your map.

Upvotes: 6

Related Questions