Std :: map, która śledzi kolejność wstawiania?

Obecnie mam, std::map<std::string,int>który przechowuje wartość całkowitą do unikalnego identyfikatora ciągu i wyszukuję ciąg. Robi głównie to, co chcę, z wyjątkiem tego, że nie śledzi zamówienia reklamowego. Więc kiedy iteruję mapę, aby wydrukować wartości, są one sortowane według ciągu; ale chcę, aby były sortowane zgodnie z kolejnością (pierwszego) wstawienia.

Zastanawiałem się nad użyciem vector<pair<string,int>>zamiast tego, ale muszę poszukać ciągu i zwiększyć wartości całkowite około 10 000 000 razy, więc nie wiem, czy a std::vectorbędzie znacznie wolniejsze.

Czy istnieje sposób użycia std::maplub czy jest inny stdpojemnik, który lepiej odpowiada moim potrzebom?

[Jestem na GCC 3.4 i prawdopodobnie mam nie więcej niż 50 par wartości w moim std::map].

Dzięki.

Jeśli masz tylko 50 wartości w std :: map, możesz skopiować je do std :: vector przed wydrukowaniem i posortować przez std :: sort za pomocą odpowiedniego funktora.

Lub możesz użyć boost :: multi_index . Pozwala na użycie kilku indeksów. W twoim przypadku może to wyglądać następująco:

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;

Możesz połączyć a std::vectorz std::tr1::unordered_map(tablicą skrótów). Oto link do dokumentacji Boost dla unordered_map. Możesz użyć wektora, aby śledzić kolejność reklam, a tabelę skrótów do częstych wyszukiwań. Jeśli wykonujesz setki tysięcy wyszukiwań, różnica między wyszukiwaniem O (log n) dla std::mapi O (1) dla tabeli skrótów może być znacząca.

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';
}

Zachowaj paralelę list<string> insertionOrder.

Kiedy nadejdzie czas drukowania, powtórz listę i przeszukaj mapę .

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

Tessil posiada bardzo fajną implementację uporządkowanej mapy (i zestawu) jaką jest licencja MIT. Możesz go znaleźć tutaj: Mapa-uporządkowana

Przykład mapy

#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;
}
}

Jeśli potrzebujesz obu strategii wyszukiwania, otrzymasz dwa kontenery. Możesz użyć a vectorze swoimi rzeczywistymi wartościami inti umieścić map< string, vector< T >::difference_type> obok niego, zwracając indeks do wektora.

Aby to wszystko zakończyć, możesz ująć oba w jednej klasie.

Ale uważam, że boost ma pojemnik z wieloma indeksami.

To, czego chcesz (bez uciekania się do Boost), to coś, co nazywam „uporządkowanym hashem”, który jest zasadniczo połączeniem skrótu i ​​połączonej listy z kluczami ciągów lub liczb całkowitych (lub obu jednocześnie). Uporządkowany hash zachowuje kolejność elementów podczas iteracji z absolutną wydajnością hasha.

Tworzyłem stosunkowo nową bibliotekę fragmentów kodu C ++, która wypełnia to, co uważam za dziury w języku C ++ dla programistów bibliotek C ++. Przejdź tutaj:

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

Chwycić:

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

Jeśli dane kontrolowane przez użytkownika zostaną umieszczone w haszu, możesz również chcieć:

security/security_csprng.cpp
security/security_csprng.h

Wywołaj to:

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

Natknąłem się na ten wątek SO podczas mojej fazy badań, aby sprawdzić, czy coś takiego jak OrderedHash już istniało bez konieczności opuszczania ogromnej biblioteki. Byłem rozczarowany. Więc napisałem własne. A teraz się tym podzieliłem.

Nie możesz tego zrobić z mapą, ale możesz użyć dwóch oddzielnych struktur - mapy i wektora i utrzymywać je zsynchronizowane - to znaczy, gdy usuwasz z mapy, znajdujesz i usuwasz element z wektora. Lub możesz utworzyć map<string, pair<int,int>>- i zapisać w swojej parze rozmiar () mapy po wstawieniu do pozycji rekordu, wraz z wartością int, a następnie podczas drukowania użyj elementu członkowskiego pozycji do sortowania.

Innym sposobem zaimplementowania tego jest mapużycie zamiast vector. Pokażę Ci to podejście i omówię różnice:

Po prostu stwórz klasę, która ma dwie mapy za kulisami.

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

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

Następnie możesz udostępnić iterator iteratorowi data_w odpowiedniej kolejności. Sposób, w jaki to robisz, to iteracja insertion_order_, a dla każdego elementu uzyskanego z tej iteracji wykonaj wyszukiwanie wdata_ z wartością zinsertion_order_

Możesz użyć bardziej wydajnego hash_mapdla insertion_order, ponieważ nie zależy ci na bezpośrednim iterowaniuinsertion_order_ .

Aby zrobić wstawki, możesz skorzystać z następującej metody:

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

Istnieje wiele sposobów na ulepszenie projektu i martwienie się o wydajność, ale jest to dobry szkielet, aby rozpocząć samodzielne wdrażanie tej funkcji. Możesz zrobić to na podstawie szablonu i możesz faktycznie przechowywać pary jako wartości w data_, abyś mógł łatwo odwołać się do wpisu w insertion_order_. Ale zostawię te kwestie projektowe jako ćwiczenie :-).

Aktualizacja : przypuszczam, że powinienem powiedzieć coś o efektywności wykorzystania mapy vs. wektor dla insertion_order_

• przeszukuje bezpośrednio dane, w obu przypadkach jest O (1)
• wstawki w podejściu wektorowym to O (1), wstawki w podejściu mapowym to O (logn)
• usunięcia w podejściu wektorowym są O (n), ponieważ musisz skanować, aby usunąć element. Przy podejściu do mapy są O (logn).

Może jeśli nie zamierzasz tak często używać usuwania, powinieneś użyć podejścia wektorowego. Podejście do mapy byłoby lepsze, gdybyś obsługiwał inną kolejność (np. Priorytet) zamiast zamówienia reklamowego.

Oto rozwiązanie, które wymaga tylko standardowej biblioteki szablonów bez użycia multiindeksu boost:
Możesz użyć std::map<std::string,int>;ivector <data>; gdzie na mapie przechowywać indeks lokalizacji danych w wektorze, a wektor przechowuje dane w kolejności wstawiania. Tutaj dostęp do danych ma złożoność O (log n). wyświetlanie danych w kolejności reklamowej ma złożoność O (n). wstawianie danych ma złożoność O (log n).

Na przykład:

#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
}

Jest to w pewnym stopniu związane z odpowiedzią Faisals. Możesz po prostu utworzyć klasę opakowującą wokół mapy i wektora i łatwo je zsynchronizować. Odpowiednia enkapsulacja pozwoli ci kontrolować metodę dostępu, a tym samym, którego kontenera użyć ... wektora czy mapy. Pozwala to uniknąć używania Boost lub czegoś podobnego.

Należy wziąć pod uwagę niewielką liczbę używanych elementów danych. Możliwe, że szybsze będzie użycie samego wektora. Na mapie występuje pewne obciążenie, które może spowodować, że wyszukiwanie w małych zestawach danych będzie droższe niż w przypadku prostszego wektora. Tak więc, jeśli wiesz, że zawsze będziesz używać tej samej liczby elementów, zrób kilka testów porównawczych i sprawdź, czy wydajność mapy i wektora jest taka, jak myślisz. Może się okazać, że wyszukiwanie w wektorze zawierającym tylko 50 elementów jest zbliżone do mapy.

// Powinien być taki jak ten mężczyzna!

// Utrzymuje to złożoność wstawiania O (logN), a usuwanie to również 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_;
};

Używaj boost::multi_indexz indeksami map i list.

Mapa pary (str, int) i statyczna wartość int, która zwiększa się przy wywołaniach wstawiania, indeksuje pary danych. Być może umieścić strukturę, która może zwrócić statyczną wartość int z elementem index ()?