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();
}

score 6 · Accepted Answer · edited May 23 '17 at 12:11

6

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.

edited May 23 '17 at 12:11

Community

1
1

answered Apr 19 '10 at 02:00

James McNellis

348,265
75
913
977

Thanks. Seems like a duplicated question. – Cheok Yan Cheng Apr 19 '10 at 03:00

Nikolai Fetissov · Answer 2 · 2010-04-19T18:52:22.373

4

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.

edited Apr 19 '10 at 18:52

answered Apr 19 '10 at 02:09

Nikolai Fetissov

82,306
11
110
171

Iiiirrk. And yet another developer recommends a `list`. Neil will bash you on the head if he ever hears of this. Hint: you'd better recommend a `vector` or a `deque`, there is absolutely no requirement here that would suggest using a `list` is ever remotely useful. – Matthieu M. Apr 19 '10 at 08:16
There's no requirement to use vector either. At some point one has to learn to make one's own decisions and not just listen to Neil. – Nikolai Fetissov Apr 19 '10 at 10:41

score 0 · Answer 3 · answered Apr 19 '10 at 19:11

0

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.

answered Apr 19 '10 at 19:11

frankc

11,290
4
32
49

Make Map Key Sorted According To Insert Sequence

3 Answers3

Edit:

Linked