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

113

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.

poliglota
źródło
8
Cóż, część czasu szybkiego wyszukiwania std :: map ma związek z faktem, że jest on posortowany w kolejności, więc może wyszukiwać binarnie. Po prostu nie mogę mieć ciasta i też go zjeść!
bobobobo
1
Czego wtedy użyłeś?
aggsol

Odpowiedzi:

56

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;
Kirill V. Lyadvinsky
źródło
To wspaniale! Boost ma nawet selektora członków, który wykona tę pracę!
xtofl
2
Tak, multi_index to moja ulubiona funkcja w Boost :)
Kirill V. Lyadvinsky.
3
@Kristo: nie chodzi o rozmiar kontenera, chodzi o ponowne wykorzystanie istniejącej implementacji dokładnie dla tego problemu. To jest klasyczne. Trzeba przyznać, że C ++ nie jest językiem funkcjonalnym, więc składnia jest nieco skomplikowana.
xtofl
4
Od kiedy w programowaniu chodziło o zapisywanie naciśnięć klawiszy?
GManNickG,
1
Dzięki za opublikowanie tego. Czy istnieje książka „Zwiększ multi-indeks dla opornych”? Przydałby mi się ...
daj jasny
25

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';
}
Michael Kristofik
źródło
4
@xtofl, Jak to sprawia, że ​​moja odpowiedź nie jest pomocna i zasługuje na negatywną opinię? Czy mój kod jest w jakiś sposób nieprawidłowy?
Michael Kristofik
To najlepszy sposób na zrobienie tego. Bardzo tani koszt pamięci (tylko dla 50 ciągów!), Pozwala std::mapna pracę tak, jak powinna (tj. Sortuje się podczas wstawiania) i ma szybki czas wykonania. (Przeczytałem to po napisaniu mojej wersji, w której użyłem std :: list!)
bobobobo
Myślę, że std :: vector lub std :: list to kwestia gustu i nie jest jasne, co jest lepsze. (Wektor ma dostęp losowy, który nie jest potrzebny, ma również ciągłą pamięć, która również nie jest potrzebna. Lista przechowuje zamówienie bez ponoszenia kosztów którejkolwiek z tych 2 funkcji, np. Realokacji podczas wzrostu).
Oliver Schönrock
14

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
bobobobo
źródło
1
To też była moja pierwsza myśl, ale powiela klucze w drugim pojemniku, prawda? W przypadku klucza std :: string, który nie jest genialny, prawda?
Oliver Schönrock
2
@OliverSchonrock Począwszy od C ++ 17, możesz używać std::string_viewjako kluczy mapy odnoszących się do std::stringna insertionOrderliście. Pozwala to uniknąć kopiowania, ale musisz uważać, aby insertionOrderelementy przeżywały klucze na mapie, które się do nich odnoszą.
flyx
Skończyło się na pisaniu kontenera, który zintegrował mapę i listę w jeden: codereview.stackexchange.com/questions/233177/ ... Bez duplikatów
Oliver Schönrock
10

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;
}
}
aggsol
źródło
4

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.

xtofl
źródło
3

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.

CubicleSoft
źródło
2

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.

Faisal Vali
źródło
2

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.

Tomek
źródło
Podejście do mapy jest również lepsze, jeśli chcesz uzyskać elementy za pomocą „identyfikatora wstawienia”. Na przykład, jeśli chcesz, aby element, który został wstawiony na piątym miejscu, przeszukujesz w insertion_order z kluczem 5 (lub 4, w zależności od tego, gdzie zaczynasz counter_). Przy podejściu wektorowym, jeśli piąty element zostałby usunięty, w rzeczywistości otrzymano by szósty element, który został wstawiony.
Tom
2

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
}
Himanshu Pandey
źródło
1

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.

Polaris878
źródło
1

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.

Chad Simpkins
źródło
1

// 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_;
};
Ka Yan
źródło
0

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

Vladimir Voznesensky
źródło
-1

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 ()?

Mikrofon
źródło
2
Powinieneś dodać przykład.
m02ph3u5