Avoir une clé composite pour hash map en c ++

J’ai une structure de données qui a,

, , and  

Puisque le titre du livre ou l’auteur peut être dupliqué, j’aimerais construire une clé composite. (disons que je ne peux pas créer de clé unique supplémentaire, telle qu’un ID)

Comme les données sont assez énormes, j’utilise GCC unordered_map pour gagner du temps, et j’ai construit ma structure comme suit:

 typedef pair keys_t typedef unordered_map map_t; 

Tout fonctionne bien en général, mais le problème se pose lorsque je souhaite faire référence à une clé spécifique.

Par exemple, supposons que je recherche le livre le mieux noté parmi les livres intitulés “mathématiques” ou le taux moyen des livres de “Tolstoï”.
Dans ce cas, cela devient très gênant, car je ne peux pas faire référence à une seule des paires de clés.

J’ai trouvé boost::multi_index mais j’ai du mal à comprendre les documents. Quelqu’un a-t-il une idée ou une ligne direcsortingce à cet égard?

Solution pour créer plusieurs index, exemple succinct pour multi_index, toute autre approche, etc. toute aide sera appréciée.

Je vous remercie.

J’ai compris comment utiliser boost::multi_index J’ai référé ce code: Boost clés composites multi_index avec MEM_FUN

et voici mon code pour votre référence.

 #include  #include  #include  #include  #include  #include  #include  using namespace boost::multi_index; using namespace std; class Book { public: Book(const ssortingng &lang1, const ssortingng &lang2, const double &value) : m_lang1(lang1) , m_lang2(lang2) , m_value(value) {} friend std::ostream& operator << (ostream& os,const Book& n) { os << n.m_lang1 << " " << n.m_lang2 << " " << n.m_value << endl; return os; } const string &lang1() const { return m_lang1; } const string &lang2() const { return m_lang2; } const double &value() const { return m_value; } private: string m_lang1, m_lang2; double m_value; }; // These will be Tag names struct lang1 {}; struct lang2 {}; struct value {}; typedef multi_index_container < Book, indexed_by< ordered_non_unique, BOOST_MULTI_INDEX_CONST_MEM_FUN( Book, const ssortingng &, lang1) >, ordered_non_unique, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const ssortingng &, lang2) >, ordered_non_unique, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const double &, value), greater >, ordered_unique< // make as a composite key with Title and Author composite_key< Book, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang1), BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang2) > > > > Book_set; // Indices for iterators typedef Book_set::index::type Book_set_by_lang1; typedef Book_set::index::type Book_set_by_lang2; typedef Book_set::index::type Book_set_by_value; int main() { Book_set books; books.insert(Book("Math", "shawn", 4.3)); books.insert(Book("Math", "john", 4.2)); books.insert(Book("Math2", "abel", 3.8)); books.insert(Book("Novel1", "Tolstoy", 5.0)); books.insert(Book("Novel1", "Tolstoy", 4.8)); // This will not be inserted(duplicated) books.insert(Book("Novel2", "Tolstoy", 4.2)); books.insert(Book("Novel3", "Tolstoy", 4.4)); books.insert(Book("Math", "abel", 2.5)); books.insert(Book("Math2", "Tolstoy", 3.0)); cout << "SORTED BY TITLE" << endl; for (Book_set_by_lang1::iterator itf = books.get().begin(); itf != books.get().end(); ++itf) cout << *itf; cout << endl<<"SORTED BY AUTHOR" << endl; for (Book_set_by_lang2::iterator itm = books.get().begin(); itm != books.get().end(); ++itm) cout << *itm; cout << endl<<"SORTED BY RATING" << endl; for (Book_set_by_value::iterator itl = books.get().begin(); itl != books.get().end(); ++itl) cout << *itl; // Want to see Tolstoy's books? (in descending order of rating) cout << endl; Book_set_by_lang2::iterator mitchells = books.get().find("Tolstoy"); while (mitchells->lang2() == "Tolstoy") cout << *mitchells++; return 0; } 

Merci à tous ceux qui ont fait des commentaires!

Ce que je faisais dans un cas similaire était d’utiliser un seul conteneur pour contenir les objects et de séparer std::multiset pour chaque index possible; lors de l’insertion, je ferais un push_back , puis récupérerais l’adresse de back() , et l’insérerais dans chacun des std::set . ( std::unordered_set et std::unordered_multiset seraient meilleurs dans votre cas: dans mon cas, non seulement l’ordre était significatif, mais je n’avais pas non plus access à un compilateur récent avec unordered_set .)

Notez que cela suppose que les objects sont immuables une fois qu’ils sont dans le conteneur. Si vous souhaitez en muter un, vous devriez probablement l’extraire de tous les ensembles, faire la modification et le réinsérer.

Cela suppose également que le type de conteneur principal n’invalidera jamais les pointeurs et les références à un object; dans mon cas, je connaissais la taille maximale à l’avance, je pouvais donc faire une reserve() et utiliser std::vector . Sinon, vous pouvez utiliser std::deque ou simplement utiliser std::map pour la clé primaire (complète).

Même cela nécessite d’accéder à l’élément complet de la clé. Votre message n’indique pas clairement si cela suffit: «Les livres intitulés« Maths »me donnent à penser que vous pourriez avoir besoin d’une recherche de sous-chaîne dans le titre (et« Tolstoï »devrait-il correspondre à« Léon Tolstoï »?). Si vous souhaitez faire correspondre une sous-chaîne arbitraire, votre multiset sera très, très grand (puisque vous insérerez toutes les sous-chaînes possibles en tant qu’entrées), ou vous ferez une recherche linéaire. (Sur un système long où les entrées ne changent pas, cela vaut la peine d’être compromis: faites la recherche linéaire la première fois que la sous-chaîne est demandée, mais mettez les résultats en cache dans un multiset afin que vous puissiez les retrouver la prochaine fois. Il est probable que les gens utiliseront souvent les mêmes chaînes de caractères, par exemple «maths» pour tout livre dont le titre est «maths».)

Il existe un article sur le même sujet: http://marknelson.us/2011/09/03/hash-functions-for-c-unordered-containers/

L’auteur, Mark Nelson, essayait de faire la même chose: “utiliser une classe ou une structure simple pour tenir le nom de la personne”, en gros, il utilise une paire comme clé (tout comme vous) pour son unordered_map:

 typedef pair Name; int main(int argc, char* argv[]) { unordered_map ids; ids[Name("Mark", "Nelson")] = 40561; ids[Name("Andrew","Binstock")] = 40562; for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ ) cout << ii->first.first << " " << ii->first.second << " : " << ii->second << endl; return 0; } 

Il s'est rendu compte que le unordered_map ne savait pas comment créer un hachage pour le type de clé donné std :: pair. Il montre donc 4 façons de créer une fonction de hachage à utiliser dans unordered_map.

S’il s’agit d’une opération peu fréquente, vous pouvez rechercher la valeur.

 for(auto& p : m) { if(p.second.name==name_to_find) { //you now have the element } } 

Toutefois, si la carte est grande, cela posera un problème car il s’agira d’une procédure linéaire plutôt que de O (log n). Il s’agit d’un problème, car les cartes sont par nature lentes.