Um std :: map que acompanha a ordem de inserção?

Eu tenho atualmente um std::map que armazena um valor inteiro para um identificador de string exclusivo, e eu procuro com a string. Ele faz basicamente o que eu quero, exceto que ele não monitora o pedido de veiculação. Então, quando eu percorrer o mapa para imprimir os valores, eles são classificados de acordo com a string; mas eu quero que eles sejam classificados de acordo com a ordem de (primeira) inserção.

Eu pensei em usar um vector<pair> , mas eu preciso procurar a string e incrementar os valores inteiros cerca de 10.000.000 vezes, então eu não sei se um std::vector será significativamente mais lento.

Existe uma maneira de usar std::map ou há outro contêiner std que melhor se adapte às minhas necessidades?

[Eu estou no GCC 3.4, e eu provavelmente não tenho mais do que 50 pares de valores no meu std::map ].

Obrigado.

Se você tem apenas 50 valores em std :: map você pode copiá-los para std :: vector antes de imprimir e ordenar via std :: sort usando o functor apropriado.

Ou você poderia usar boost :: multi_index . Permite usar vários índices. No seu caso, poderia parecer com o seguinte:

 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, member > > > values_t; 

Você pode combinar um std::vector com um std::tr1::unordered_map (uma tabela de hash). Aqui está um link para a documentação do Boost para o unordered_map . Você pode usar o vetor para acompanhar o pedido de inserção e a tabela de hash para fazer as pesquisas freqüentes. Se você estiver fazendo centenas de milhares de pesquisas, a diferença entre a pesquisa de O (log n) para std::map e O (1) para uma tabela de hash pode ser significativa.

 std::vector insertOrder; std::tr1::unordered_map 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'; } 

Mantenha uma list insertionOrder paralela list insertionOrder .

Quando chegar a hora de imprimir, faça uma iteração na lista e faça pesquisas no mapa .

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

Se você precisar de ambas as estratégias de pesquisa, acabará com dois contêineres. Você pode usar um vector com seus valores reais ( int s) e colocar um map< string, vector< T >::difference_type> próximo a ele, retornando o índice para o vetor.

Para completar tudo isso, você pode encapsular ambos em uma class.

Mas acredito que o boost tenha um contêiner com vários índices.

Tessil tem uma implementação muito boa de mapa ordenado (e set) que é licença do MIT. Você pode encontrá-lo aqui: mapa-ordenado

Exemplo de mapa

 #include  #include  #include  #include "ordered_map.h" int main() { tsl::ordered_map 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; } } 

Você não pode fazer isso com um mapa, mas você poderia usar duas estruturas separadas – o mapa e o vetor e mantê-las sincronizadas – que é quando você exclui do mapa, localiza e exclui o elemento do vetor. Ou você poderia criar um map> – e em seu par armazenar o tamanho () do mapa após a inserção para registrar a posição, junto com o valor do int e, quando imprimir, usar o membro de posição para classificar.

Isso é um pouco relacionado à resposta Faisals. Você pode simplesmente criar uma class wrapper em torno de um mapa e vetor e mantê-los facilmente sincronizados. O encapsulamento adequado permite controlar o método de access e, portanto, qual contêiner usar … o vetor ou o mapa. Isso evita usar Boost ou qualquer coisa assim.

Outra maneira de implementar isso é com um map vez de um vector . Eu vou te mostrar essa abordagem e discutir as diferenças:

Basta criar uma class que tenha dois mapas nos bastidores.

 #include  #include  using namespace std; class SpecialMap { // usual stuff... private: int counter_; map insertion_order_; map data_; }; 

Você pode então expor um iterador ao iterador sobre data_ na ordem correta. A maneira como você faz isso é iterar por meio de insertion_order_ e, para cada elemento obtido dessa iteração, faça uma pesquisa no data_ com o valor de insertion_order_

Você pode usar o hash_map mais eficiente para insertion_order, já que não se preocupa com a iteração direta de insertion_order_ .

Para fazer inserções, você pode ter um método como este:

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

Há várias maneiras de melhorar o design e se preocupar com o desempenho, mas esse é um bom esqueleto para começar a implementar essa funcionalidade sozinho. Você pode modelá-lo e, na verdade, pode armazenar os pares como valores em data_ para poder referenciar facilmente a input em insertion_order_. Mas deixo esses problemas de design como um exercício :-).

Atualização : suponho que devo dizer algo sobre a eficiência do uso de mapa vs. vetor para inserção_ordem_

  • pesquisas diretamente nos dados, em ambos os casos são O (1)
  • inserções na abordagem vetorial são O (1), inserções na abordagem de mapa são O (logn)
  • As exclusões na abordagem vetorial são O (n) porque você precisa varrer o item a ser removido. Com a abordagem do mapa, eles são O (logn).

Talvez se você não for usar tanto deleta, você deve usar a abordagem vetorial. A abordagem do mapa seria melhor se você estivesse dando suporte a um pedido diferente (como prioridade) em vez de ordem de inserção.

// Deve ser assim homem!

// Isso mantém a complexidade da inserção é O (logN) e a exclusão também é O (logN).

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

O que você quer (sem recorrer ao Boost) é o que chamo de “hash ordenado”, que é essencialmente um mashup de um hash e uma lista encadeada com chaves string ou integer (ou ambas ao mesmo tempo). Um hash ordenado mantém a ordem dos elementos durante a iteração com o desempenho absoluto de um hash.

Eu tenho reunido uma biblioteca de fragments C ++ relativamente nova que preenche o que eu vejo como falhas na linguagem C ++ para desenvolvedores de bibliotecas C ++. Vá aqui:

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

Agarrar:

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

Se os dados controlados pelo usuário forem colocados no hash, você também pode querer:

 security/security_csprng.cpp security/security_csprng.h 

Invoque-o:

 #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 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 TempHash(47, Key1, Key2); CubicleSoft::OrderedHashNode *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(); } 

Eu corri para este thread SO durante a minha fase de pesquisa para ver se alguma coisa como OrderedHash já existia sem exigir que eu fosse parar em uma biblioteca enorme. Eu fiquei desapontado. Então eu escrevi o meu próprio. E agora eu compartilhei.

Aqui está uma solução que requer apenas uma biblioteca de modelos padrão sem usar o multiindex do boost:
Você poderia usar std::map; e vector ; onde no mapa você armazena o índice da localização dos dados no vetor e o vetor armazena os dados na ordem de inserção. Aqui o access aos dados tem complexidade O (log n). exibir dados no pedido de inserção tem complexidade O (n). inserção de dados tem complexidade O (log n).

Por exemplo:

 #include #include #include struct data{ int value; std::string s; } typedef std::map MapIndex;//this map stores the index of data stored //in VectorData mapped to a string typedef std::vector VectorData;//stores the data in insertion order void display_data_according_insertion_order(VectorData vectorData){ for(std::vector::iterator it=vectorData.begin();it!=vectorData.end();it++){ std::cout< value< s< second; else return -1;//it signifies that key does not exist in map } int insert_value(data d,mapIndex,vectorData){ if(mapIndex.find(ds)==mapIndex.end()){ mapIndex.insert(std::make_pair(ds,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 } 

Uma coisa que você precisa considerar é o pequeno número de elementos de dados que você está usando. É possível que seja mais rápido usar apenas o vetor. Existe alguma sobrecarga no mapa que pode fazer com que seja mais caro fazer pesquisas em pequenos conjuntos de dados do que o vetor mais simples. Então, se você sabe que estará sempre usando o mesmo número de elementos, faça um benchmarking e veja se o desempenho do mapa e do vetor é o que você realmente acha que é. Você pode achar que a pesquisa em um vetor com apenas 50 elementos é quase igual ao mapa.

Use boost::multi_index com índices de map e list.

Um mapa de par (str, int) e static int que incrementa em inserir chamadas indexa pares de dados. Coloque em uma estrutura que pode retornar o int estático com um membro index (), talvez?