Станд.:: карта, которые отслеживают порядок вставки?

Если у вас есть только 50 значений в std :: map, вы можете скопировать их в std :: vector перед печатью и отсортировать через std :: sort, используя соответствующий функтор.

Или вы можете используйте boost :: multi_index . Это позволяет использовать несколько индексов. В вашем случае это могло бы выглядеть следующим образом:

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;

Одна вещь, которую вы должны учитывать, - это небольшое количество используемых вами элементов данных. Возможно, что быстрее будет использовать только вектор. На карте есть некоторые накладные расходы, из-за которых поиск в небольших наборах данных может оказаться более дорогостоящим, чем поиск в более простом векторе. Итак, если вы знаете, что всегда будете использовать примерно одинаковое количество элементов, проведите сравнительный анализ и посмотрите, соответствует ли производительность карты и вектора тем, о чем вы действительно думаете. Вы можете обнаружить, что поиск в векторе всего с 50 элементами почти такой же, как на карте.

Это в некоторой степени связано с ответом Фейсалса. Вы можете просто создать класс-оболочку вокруг карты и вектора и легко синхронизировать их. Правильная инкапсуляция позволит вам контролировать метод доступа и, следовательно, какой контейнер использовать ... вектор или карту. Это позволяет избежать использования Boost или чего-то подобного.

Вы можете объединить std :: vector с std :: tr1 :: unordered_map (хеш-таблица). Вот ссылка на документацию Boost для unordered_map . Вы можете использовать вектор для отслеживания порядка вставки и хеш-таблицу для частого поиска. Если вы выполняете сотни тысяч поисков, разница между поиском O (log n) для std :: map и O (1) для хеш-таблицы может быть значительной.

std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}

Вы не можете сделать это с картой, но вы можете использовать две отдельные структуры - карту и вектор и поддерживать их синхронизацию - то есть когда вы удаляете с карты, находите и удаляете элемент из вектора. Или вы можете создать map > - и в вашей паре сохранить размер () карты после вставки в позицию записи вместе со значением int, и затем при печати используйте элемент position для сортировки.

Если вам нужны обе стратегии поиска, вы получите два контейнера. Вы можете использовать вектор с вашими фактическими значениями ( int s) и поместить рядом с ним map :: difference_type> , возвращая индекс в вектор.

Чтобы завершить все это, вы можете инкапсулировать оба в один класс.

Но я считаю, что boost имеет контейнер с несколькими индексами.

Другой способ реализовать это - использовать карту вместо вектора . Я покажу вам этот подход и расскажу о различиях:

Просто создайте класс, который имеет две скрытые карты.

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

 private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> data_;
};

Затем вы можете предоставить итератор для итератора по data_ в правильном порядке. Вы делаете это итерируете через insert_order_ , и для каждого элемента, полученного в результате этой итерации, выполните поиск в data_ со значением из insert_order_

You Вы можете использовать более эффективный hash_map для Insert_order, так как вам не нужна прямая итерация через Insert_order_ .

Для вставки у вас может быть такой метод:

void SpecialMap::Insert(const string& key, int value) {
  // This may be an over simplification... You ought to check
  // if you are overwriting a value in data_ so that you can update
  // insertion_order_ accordingly
  insertion_order_[counter_++] = key;
  data_[key] = value;
}

Есть много способов улучшить дизайн и позаботиться о производительности, но это хорошая основа для начала реализации этой функциональности на твой собственный. Вы можете сделать это шаблонным, и вы можете фактически хранить пары как значения в data_, чтобы вы могли легко ссылаться на запись в insert_order_. Но я оставляю эти проблемы дизайна в качестве упражнения: -).

Обновление : Полагаю, я должен сказать кое-что об эффективности использования карты и вектора для поиска insert_order_

• непосредственно в данных, в обоих случаях O (1)
• вставок в векторном подходе - O (1), вставки в подходе карты - O (logn)
• , удаления в векторном подходе - O (n), потому что вам нужно сканировать элемент для удаления . При использовании карты они равны O (logn).

Возможно, если вы не собираетесь так часто использовать удаления, вам следует использовать векторный подход. Подход с использованием карты был бы лучше, если бы вы поддерживали другой порядок (например, приоритет) вместо порядка вставки.