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

Ответ 1

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

Ответ 2

Вы можете объединить std::vector с std::tr1::unordered_map (хеш-таблицей). Здесь ссылка на Boost documentation для 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';
}

Ответ 3

Храните параллель list<string> insertionOrder.

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

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

Ответ 4

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

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

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

Ответ 5

Tessil имеет очень приятное воплощение упорядоченной карты (и набора), которая является лицензией MIT. Вы можете найти его здесь: ordered-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;
}
}

Ответ 6

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

Ответ 7

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

Ответ 8

Другим способом реализации этого является 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 для insertion_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_, чтобы вы могли легко ссылаться на запись в insertion_order_. Но я оставляю эти проблемы дизайна как упражнение: -).

Обновление. Я полагаю, что я должен сказать что-то об эффективности использования map vs. vector для insertion_order _

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

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

Ответ 9

//Должен быть такой человек!

//Это поддерживает сложность вставки 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_;
};

Ответ 10

Вот решение, для которого требуется только стандартная библиотека шаблонов без использования boost multiindex:
Вы можете использовать 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
}

Ответ 11

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

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

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

Grab:

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, не требуя, чтобы я упал в массивную библиотеку. Я был разочарован. Поэтому я написал свой собственный. И теперь я поделился ею.

Ответ 12

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

Ответ 13

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

Ответ 14

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