Comment puis-je obtenir un std :: ensemble de clés pour un std :: map

J’écrivais un algorithme ce matin et j’ai rencontré une situation curieuse. J’ai deux std::map s. Je veux effectuer une intersection de jeu sur les jeux de clés de chacune (pour trouver les clés communes aux deux cartes). Dans le futur, je pense qu’il est également probable que je veuille également effectuer une soustraction d’ensemble. Heureusement, la STL inclut des fonctions pour ces deux opérations. Le problème est que je n’arrive pas à obtenir un std::set des clés d’un std::map . Y a-t-il un moyen de faire ça? Je cherche quelque chose qui soit aussi simple, comme en Java:

 std::set keys = myMap.getKeySet(); 

Si j’ai bien compris, je ne peux pas utiliser la fonction std::set_intersection() directement sur des iterators dans les cartes, car celles-ci exposent des objects std::pair au lieu de simples clés. De plus, je ne pense pas que la carte garantisse l’ordre. Je suis également intéressé par la même opération sur une paire de std::multimap s, si cela fait une différence.

EDIT : J’ai oublié de mentionner au début que, du fait de l’âge du compilateur que je suis obligé d’utiliser (MSVC ++ 6), la plupart des astuces de modèles astucieuses disponibles dans boost ne peuvent pas être utilisées.

Vous pouvez utiliser le module polyvalent boost :: transform_iterator pour renvoyer un iterator qui renvoie uniquement les clés (et non les valeurs). Voir Comment récupérer toutes les clés (ou valeurs) d’un std :: map et les mettre dans un vecteur?

Ce que vous voulez fondamentalement, c’est une copie, car std :: map ne garde pas les clés dans un std :: set. std :: copy suppose que les types de valeur sont compatibles, ce qui n’est pas le cas ici. Le std :: map :: value_type est un std :: pair. Vous voulez copier uniquement la première partie de la paire, ce qui signifie que vous avez besoin d’un std :: transform. Maintenant, puisque vous utiliserez un insert_iterator sur l’ensemble, l’ordre n’a pas d’importance. Le std :: set sortingera lors de l’insertion, même si la carte était déjà sortingée.

[edit] Le code pourrait être plus facile. Au sumt de ma tête, pas compilé.

 std::transform(MyMap.begin(), MyMap.end(), std::inserter(MySet, MySet.end()), boost::bind(&std::pair::first, _1)); 

Si vous avez select1st SGI, vous n’avez pas besoin de boost :: bind.

[edit] Mis à jour pour C ++ 14

 std::transform(MyMap.begin(), MyMap.end(), std::inserter(MySet, MySet.end()), [](auto pair){ return pair.first; }); 

La carte garantit la commande; c’est pourquoi on l’appelle un conteneur associatif sortingé . Vous pouvez utiliser set_intersection avec une fonction de comparaison personnalisée, la deuxième variante répertoriée ici .

Donc, quelque chose comme

 bool your_less(const your_map::value_type &v1, const your_map::value_type &v2) { return v1.first < v2.first; } set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(), your_output_it, your_less); 

devrait faire l'affaire. (Il est également possible d'utiliser boost :: lambda et bind pour éviter d'écrire une fonction temporaire.)

L'opérateur par défaut

En pratique,

 yourmap::const_iterator mi; set k; for (mi = yourmap.begin(); mi != yourmap.end(); ++mi) k.insert(mi->first); return k; 

La meilleure solution conviviale pour les algorithmes STL non-SGI et non-boost consiste à étendre map :: iterator comme ceci:

 template class key_iterator : public map_type::iterator { public: typedef typename map_type::iterator map_iterator; typedef typename map_iterator::value_type::first_type key_type; key_iterator(const map_iterator& other) : map_type::iterator(other) {} ; key_type& operator *() { return map_type::iterator::operator*().first; } }; // helpers to create iterators easier: template key_iterator key_begin(map_type& m) { return key_iterator(m.begin()); } template key_iterator key_end(map_type& m) { return key_iterator(m.end()); } 

et ensuite les utiliser comme suit:

  map test; test["one"] = 1; test["two"] = 2; set keys; // // method one // key_iterator > kb(test.begin()); // key_iterator > ke(test.end()); // keys.insert(kb, ke); // // method two // keys.insert( // key_iterator >(test.begin()), // key_iterator >(test.end())); // method three (with helpers) keys.insert(key_begin(test), key_end(test)); 

Vous pouvez simplement parcourir et append chaque clé à un ensemble. Les ensembles et les cartes sont tous deux ordonnés, les variantes non ordonnées ne le sont pas.

J’ai trouvé un bon lien pour votre question ici

et avoir du code pour votre problème:

  #include  #include  #include  #include  typedef std::map MyMap; // also known as select1st in SGI STL implementation template struct GetKey: public std::unary_function { const typename T_PAIR::first_type& operator()(const T_PAIR& item) const { return item.first; } }; int main(int argc, char** argv) { MyMap m1,m2; m1["a"] = 1; m1["b"] = 2; m2["c"] = 3; m2["b"] = 3; std::set s; std::transform(m1.begin(), m1.end(), std::inserter(s, s.begin()), GetKey()); std::transform(m2.begin(), m2.end(), std::inserter(s, s.begin()), GetKey()); std::copy(s.begin(), s.end(), std::ostream_iterator(std::cout, " ")); std::cout << std::endl; return 0; } 

Vous pourriez peut-être créer un iterator pour une carte qui ne fournira les clés qu’en utilisant boost :: adapters :: map_key, voir exemple dans la documentation de boost :: adapters :: map_key . Cela semble avoir été introduit dans Boost 1.43, et est supposé être compatible C ++ 2003, mais je ne connais pas spécifiquement VC ++ 6, qui appartient à l’ère C ++ 98.

Construire à partir de la réponse de zvrba et du commentaire de dianot:

Il suffit de faire de la collection de destination un vecteur de paires au lieu d’une carte, et le problème signalé par dianot est résolu. Donc, en utilisant l’exemple zvrba:

 std::vector> v; set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(), std::back_inserter(v), []( std::pair const & a, std::pair const & b){return a.first < b.first;}); 

Donc, sans construire des copies ou des ensembles intermédiaires, nous pouvons obtenir efficacement l'intersection de deux cartes. Cette construction comstack avec gcc5.3.