A std::map that keep track of the order of insertion?

Question

I currently have a std::map<std::string,int> that stores an integer value to an unique string identifier, and I do look up with the string. It does mostly what I want, except for that it does not keep track of the insertion order. So when I iterate the the map to print out the values, they are sorted according to the string; but I want them to be sorted according to the order of (first) insertion.

I thought about using a vector<pair<string,int>> instead, but I need to look up the string and increment the integer values about 10,000,000 times, so I don't know whether a std::vector will be significantly slower.

Is there a way to use std::map or is there another std container that better suits my need?

[I'm on GCC 3.4, and I have probably no more than 50 pairs of values in my std::map].

Thanks.

Answer 1

If you have only 50 values in std::map you could copy them to std::vector before printing out and sort via std::sort using appropriate functor.

Or you could use boost::multi_index. It allows to use several indexes. In your case it could look like the following:

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag<string_tag>, member<value_t, string, &value;_t::s> >
    >
> values_t;