Сделать ключ карты отсортированным по последовательности вставки

Question

Без помощи дополнительного контейнера (например, вектора) возможно ли, чтобы ключ карты был отсортирован в той же последовательности, что и последовательность вставки?

#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

Нет. A std::map - отсортированный контейнер; порядок вставки не поддерживается. Существует ряд решений, использующих второй контейнер для поддержания порядка вставки в ответ на другой связанный вопрос .

Тем не менее, вы должны использовать std::string в качестве ключа. Использование const char* в качестве ключа карты является плохой идеей: практически невозможно получить доступ к элементу или выполнить поиск по его ключу, поскольку сравниваются только указатели, а не сами строки.

Answer 2

Нет. std::map<Key, Data, Compare, Alloc> сортируется в соответствии с третьим параметром шаблона Compare, который по умолчанию равен std::less<Key>. Если вы хотите вставить последовательность, вы можете использовать std::list<std::pair<Key, Data> >.

Edit:

Как было указано, любой последовательный контейнер STL будет делать: vector, deque, list или в данном конкретном случае событие string. Вам нужно будет определиться с достоинствами каждого.

Answer 3

Рассмотрите возможность использования контейнера boost :: multi_index вместо std :: map. Вы можете поместить в свой контейнер как упорядоченный индекс карты, так и неупорядоченный последовательный индекс.