Wie bekomme ich einen std :: Schlüsselsatz zu einer std :: map?

Question

Ich habe heute Morgen einen Algorithmus geschrieben und bin in eine seltsame Situation geraten. Ich habe zwei std::map s. Ich möchte einen Satz Schnittpunkt auf den Mengen der Schlüssel von jedem durchführen (um herauszufinden, welche Schlüssel für beide Karten gemeinsam sind). Irgendwann in der Zukunft denke ich, dass ich wahrscheinlich auch hier die Subtraktion durchführen will. Glücklicherweise enthält die AWL Funktionen für beide Operationen. Das Problem ist, ich kann nicht scheinen std::set der Schlüssel aus einer std::map. Gibt es eine Möglichkeit, dies zu tun? Ich bin auf der Suche nach etwas, das so einfach sein würde, wie es in Java ist:

std::set<Foo> keys = myMap.getKeySet(); 

Mein Verständnis ist, dass ich nicht die std::set_intersection() Funktion direkt auf Iteratoren in die Karten verwenden kann, weil die Karten std::pair Objekte belichten statt von nur Schlüsseln. Außerdem glaube ich nicht, dass die Karte Ordnung garantiert. Ich bin auch daran interessiert, dieselbe Operation an einem Paar von std::multimap s durchzuführen, wenn das einen Unterschied macht.

EDIT: Ich habe vergessen zu erwähnen, dass aufgrund des Alters des Compilers ich gezwungen bin zu verwenden (MSVC++ 6), die meisten der raffinierten Vorlagentricks, die in Boost verfügbar sind, können nicht verwendet werden.

Answer 1

können Sie die vielseitige boost :: transform_iterator einen Iterator zurückzugeben, die nur die Schlüssel zurückgibt (und nicht die Werte). Siehe How to retrieve all keys (or values) from a std::map and put them into a vector?

Answer 2

Sie können einfach durchlaufen und jeden Schlüssel zu einem Satz hinzufügen. Sets und Maps sind beide geordnet, ungeordnete Varianten nicht.

Answer 3

Was Sie grundsätzlich wollen, ist eine Kopie, da std :: map die Schlüssel nicht in einem std :: set hält. std :: copy geht davon aus, dass die Werttypen kompatibel sind, was hier nicht der Fall ist. Der std :: map :: value_type ist ein std :: -Paar. Sie möchten nur den ersten Teil des Paars kopieren, was bedeutet, dass Sie eine std :: transform benötigen. Jetzt, da Sie einen insert_iterator auf dem Set verwenden, spielt die Reihenfolge keine Rolle. Der std :: set sortiert beim Einfügen, obwohl die Map bereits sortiert wurde.

[bearbeiten] Code könnte einfacher sein. Spitze meines Kopfes, nicht zusammengestellt.

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

Wenn Sie SGI's select1st haben, brauchen Sie den boost :: bind nicht.

[Bearbeiten] Aktualisiert für C++ 14

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

Answer 4

Karte tut Garantie Bestellung; deshalb heißt es sorted associative container. Sie können set_intersection mit einer benutzerdefinierten Vergleichsfunktion verwenden, die zweite Variante ist here.

Also, so etwas wie

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

sollte es tun. (Es ist auch möglich, boost :: lambda und bind zu verwenden, um das Schreiben einer temporären Funktion zu vermeiden.)

Der Standardoperator < über Paare vergleicht beide Komponenten. Da Sie nur die Äquivalenz über den ersten Teil des Paares benötigen (den Map-Schlüssel), müssen Sie Ihren eigenen Vergleichsoperator definieren, der eine solche Relation bereitstellt (was die obige Funktion tut).

Answer 5

In der Praxis

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

Answer 6

fand ich eine gute Verbindung für Ihre Frage here

und einen Code für Ihr Problem:

#include <iostream> 
    #include <map> 
    #include <set> 
    #include <iterator> 

    typedef std::map<std::string, int> MyMap; 

    // also known as select1st in SGI STL implementation 
    template<typename T_PAIR> 
    struct GetKey: public std::unary_function<T_PAIR, typename T_PAIR::first_type> 
    { 
     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<std::string> s; 
     std::transform(m1.begin(), m1.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>()); 
     std::transform(m2.begin(), m2.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>()); 
     std::copy(s.begin(), s.end(), std::ostream_iterator<std::string>(std::cout, " ")); 
     std::cout << std::endl; 
     return 0; 
    } 

Answer 7

Der beste Nicht-SGI, nicht-Boost STL-Algorithmus-freundliche Lösung ist es, map :: Iterator wie folgt zu erweitern:

template<typename map_type> 
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<typename map_type> 
key_iterator<map_type> key_begin(map_type& m) 
{ 
    return key_iterator<map_type>(m.begin()); 
} 
template<typename map_type> 
key_iterator<map_type> key_end(map_type& m) 
{ 
    return key_iterator<map_type>(m.end()); 
} 

und sich dann wie so verwenden:

 map<string,int> test; 
     test["one"] = 1; 
     test["two"] = 2; 

     set<string> keys; 

//  // method one 
//  key_iterator<map<string,int> > kb(test.begin()); 
//  key_iterator<map<string,int> > ke(test.end()); 
//  keys.insert(kb, ke); 

//  // method two 
//  keys.insert(
//   key_iterator<map<string,int> >(test.begin()), 
//   key_iterator<map<string,int> >(test.end())); 

     // method three (with helpers) 
     keys.insert(key_begin(test), key_end(test)); 

Answer 8

Sie könnten vielleicht einen Iterator für eine Karte erstellen, die mit Hilfe der Tasten boost :: Adapter nur ergibt :: MAP_KEY, siehe Beispiel im boost::adapters::map_key documentation. Dies scheint in Boost 1.43 eingeführt worden zu sein und soll C++ 2003-kompatibel sein, aber ich weiß nicht speziell über VC++ 6, das aus der C++ 98-Ära stammt.

Answer 9

Gebäude aus der Antwort von zvrba und dem Kommentar von dianot:

Gerade den Empfang Sammlung ein Vektor von Paaren statt einer Karte sein lassen, und das Problem von dianot hingewiesen ist vorbei. Also, mit zvrba Beispiel:

std::vector<std::pair<keytype, valtype>> v; 

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

Also ohne Zwischen Kopien oder Sätze zu konstruieren können wir effizient die Schnittmenge von zwei Karten. Diese Konstruktion wird mit gcc5.3 kompiliert.