Make Map Key Sorted According To Insert Sequence

Question

Without help from additional container (like vector), is it possible that I can make map's key sorted same sequence as insertion sequence?

#include <map>
#include <iostream>

using namespace std;

int main()
{
  map<const char*, int> m;
  m["c"] = 2;
  m["b"] = 2;
  m["a"] = 2;
  m["d"] = 2;


  for (map<const char*, int>::iterator begin = m.begin(); begin != m.end(); begin++) {
      // How can I get the loop sequence same as my insert sequence.
      // c, b, a, d
      std::cout << begin->first << std::endl;
  }

  getchar();
}

Answer 1

No. A std::map is a sorted container; the insertion order is not maintained. There are a number of solutions using a second container to maintain insertion order in response to another, related question.

That said, you should use std::string as your key. Using a const char* as a map key is A Bad Idea: it makes it near impossible to access or search for an element by its key because only the pointers will be compared, not the strings themselves.

Answer 2

No. std::map<Key, Data, Compare, Alloc> is sorted according to the third template parameter Compare, which defaults to std::less<Key>. If you want insert sequence you can use std::list<std::pair<Key, Data> >.

Edit:

As was pointed out, any sequential STL container would do: vector, deque, list, or in this particular case event string. You would have to decide on the merits of each.

Answer 3

Consider using a boost::multi_index container instead of a std::map. You can put both an ordered map index and an unordered sequential index on your container.