Std :: map, отслеживающая порядок вставки?

В настоящее время у меня есть объект std::map<std::string,int>, в котором целочисленное значение хранится в уникальном строковом идентификаторе, и я ищу эту строку. Он делает в основном то, что я хочу, за исключением того, что не отслеживает порядок вставки. Поэтому, когда я перебираю карту, чтобы распечатать значения, они сортируются по строке; но я хочу, чтобы они были отсортированы в соответствии с порядком (первой) вставки.

Я думал об использовании vector<pair<string,int>>вместо этого, но мне нужно найти строку и увеличить целочисленные значения примерно в 10 000 000 раз, поэтому я не знаю, std::vectorбудет ли a значительно медленнее.

Есть ли способ использовать std::mapили есть другой stdконтейнер, который лучше соответствует моим потребностям?

[Я использую GCC 3.4, и у меня, вероятно, не более 50 пар значений std::map].

Спасибо.

Если у вас есть только 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;

Вы можете объединить a 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';
}

Проведите параллель list<string> insertionOrder.

Когда пришло время печатать, перебирайте список и просматривайте карту .

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map

У Tessil есть очень хорошая реализация упорядоченной карты (и набора), которая является лицензией MIT. Вы можете найти это здесь: order-map

Пример карты

#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"

int main() {
tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}

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

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

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

То, что вы хотите (не прибегая к Boost), - это то, что я называю «упорядоченным хешем», который, по сути, представляет собой гибрид хэша и связанного списка со строковыми или целочисленными ключами (или и тем, и другим одновременно). Упорядоченный хеш поддерживает порядок элементов во время итерации с абсолютной производительностью хеша.

Я собирал относительно новую библиотеку сниппетов C ++, которая заполняет то, что я считаю дырами в языке C ++ для разработчиков библиотеки C ++. Иди сюда:

https://github.com/cubiclesoft/cross-platform-cpp

Взять:

templates/detachable_ordered_hash.cpp
templates/detachable_ordered_hash.h
templates/detachable_ordered_hash_util.h

Если данные, управляемые пользователем, будут помещены в хэш, вам также может потребоваться:

security/security_csprng.cpp
security/security_csprng.h

Вызвать это:

#include "templates/detachable_ordered_hash.h"
...
// The 47 is the nearest prime to a power of two
// that is close to your data size.
//
// If your brain hurts, just use the lookup table
// in 'detachable_ordered_hash.cpp'.
//
// If you don't care about some minimal memory thrashing,
// just use a value of 3.  It'll auto-resize itself.
int y;
CubicleSoft::OrderedHash<int> TempHash(47);
// If you need a secure hash (many hashes are vulnerable
// to DoS attacks), pass in two randomly selected 64-bit
// integer keys.  Construct with CSPRNG.
// CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode<int> *Node;
...
// Push() for string keys takes a pointer to the string,
// its length, and the value to store.  The new node is
// pushed onto the end of the linked list and wherever it
// goes in the hash.
y = 80;
TempHash.Push("key1", 5, y++);
TempHash.Push("key22", 6, y++);
TempHash.Push("key3", 5, y++);
// Adding an integer key into the same hash just for kicks.
TempHash.Push(12345, y++);
...
// Finding a node and modifying its value.
Node = TempHash.Find("key1", 5);
Node->Value = y++;
...
Node = TempHash.FirstList();
while (Node != NULL)
{
  if (Node->GetStrKey())  printf("%s => %d\n", Node->GetStrKey(), Node->Value);
  else  printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value);

  Node = Node->NextList();
}

Я столкнулся с этим потоком SO на этапе исследования, чтобы узнать, существует ли уже что-нибудь вроде OrderedHash, не требуя от меня добавления огромной библиотеки. Я был разочарован. Так что я написал свой. И теперь я поделился им.

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

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

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

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

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

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

Вы можете использовать более эффективный hash_mapдля insert_order, поскольку вам не нужно напрямую выполнять итерацию insertion_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).

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

Вот решение, для которого требуется только стандартная библиотека шаблонов без использования мультииндекса boost:
вы можете использовать std::map<std::string,int>;и vector <data>;где на карте вы храните индекс расположения данных в векторе, а вектор хранит данные в порядке вставки. Здесь доступ к данным имеет сложность O (log n). отображение данных в порядке вставки имеет сложность O (n). вставка данных имеет сложность O (log n).

Например:

#include<iostream>
#include<map>
#include<vector>

struct data{
int value;
std::string s;
}

typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored 
                                           //in VectorData mapped to a string              
typedef std::vector<data> VectorData;//stores the data in insertion order

void display_data_according_insertion_order(VectorData vectorData){
    for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){
        std::cout<<it->value<<it->s<<std::endl;
    }
}
int lookup_string(std::string s,MapIndex mapIndex){
    std::MapIndex::iterator pt=mapIndex.find(s)
    if (pt!=mapIndex.end())return it->second;
    else return -1;//it signifies that key does not exist in map
}
int insert_value(data d,mapIndex,vectorData){
    if(mapIndex.find(d.s)==mapIndex.end()){
        mapIndex.insert(std::make_pair(d.s,vectorData.size()));//as the data is to be
                                                               //inserted at back 
                                                               //therefore index is
                                                               //size of vector before
                                                               //insertion
        vectorData.push_back(d);
        return 1;
    }
    else return 0;//it signifies that insertion of data is failed due to the presence
                  //string in the map and map stores unique keys
}

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

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

// Должно быть похоже на этого человека!

// При этом сохраняется сложность вставки O (logN) и удаления также O (logN).

class SpecialMap {
private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> insertion_order_reverse_look_up; // <- for fast delete
  map<string, Data> data_;
};

Используется boost::multi_indexс индексами карты и списка.

Карта пары (str, int) и статического int, которая увеличивается при вызовах вставки, индексирует пары данных. Возможно, добавить структуру, которая может возвращать статический int val с членом index ()?