cómo puedo obtener un estándar :: conjunto de claves para un estándar :: map

Question

Estaba escribiendo un algoritmo esta mañana y me encontré con una situación curiosa. Tengo dos std::map s. Quiero realizar una intersección de conjuntos en los conjuntos de las claves de cada uno (para encontrar qué teclas son comunes a ambos mapas). En algún momento en el futuro, creo que es probable que también quiera realizar la resta del set aquí. Afortunadamente, el STL incluye funciones para ambas operaciones. El problema es que parece que no puedo obtener un std::set de las claves de std::map. ¿Hay alguna manera de hacer esto? Estoy buscando algo que sería este sencillo, como lo es en Java:

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

Mi opinión es que no puedo utilizar la función std::set_intersection() directamente sobre iteradores en los mapas porque los mapas exponen objetos en lugar std::pair de solo llaves. Además, no creo que el mapa garantice el orden. También estoy interesado en realizar esta misma operación en un par de std::multimap s, si eso hace alguna diferencia.

EDITAR: Olvidé mencionar que inicialmente debido a la antigüedad del compilador que estoy obligado a utilizar (MSVC++ 6), la mayoría de los trucos ingeniosos plantilla que están disponibles en el impulso no se puede utilizar.

Answer 1

Puede utilizar el impulso versátil :: transform_iterator devolver un iterador que devuelve sólo las teclas (y no los valores). Ver How to retrieve all keys (or values) from a std::map and put them into a vector?

Answer 2

Puede iterar y agregar cada tecla a un conjunto. Los conjuntos y los mapas son ambos ordenados, las variantes desordenadas no lo son.

Answer 3

Lo que básicamente quiere es una copia, ya que std :: map no mantiene las claves en un conjunto estándar. std :: copy supone que los tipos de valores son compatibles, que no es el caso aquí. Std :: map :: value_type es un std :: pair. Desea copiar solo la primera parte del par, lo que significa que necesita una transformación std ::. Ahora, como usará un insert_iterator en el conjunto, el orden no importa. Std :: set clasificará la inserción, aunque el mapa ya esté ordenado.

[editar] El código puede ser más fácil. Parte superior de mi cabeza, no compilada.

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

Si tiene la primera opción de SGI, no necesita boost :: bind.

[editar] Actualización para C++ 14

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

Answer 4

Mapa hace orden de garantía; es por eso que se llama sorted associative container. Puede usar set_intersection con una función de comparador personalizada, la segunda variante aparece here.

Por lo tanto, algo así como

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

debe hacer el truco. (También es posible usar boost :: lambda y se unen a evitar la escritura de una función temporal.)

El valor predeterminado operador < a través de pares compara ambos componentes. Como necesita la equivalencia solo sobre la primera parte del par (la clave del mapa), necesita definir su propio operador de comparación que proporcione dicha relación (que es lo que hace la función anterior).

Answer 5

En la práctica,

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

Answer 6

me encontré con buen enlace de tu pregunta here

y tienen algo de código para su problema:

#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

La mejor no SGI, no impulso La solución amigable con el algoritmo STL es extender map :: iterator como lo siguiente:

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

y luego usarlos como tan:

 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

tal vez podría crear un iterador para un mapa que sólo da las claves utilizando adaptadores de impulso :: :: map_key, véase el ejemplo en el boost::adapters::map_key documentation. Esto parece haber sido introducido en Boost 1.43, y se supone que es compatible con C++ 2003, pero no conozco específicamente VC++ 6, que es de la era C++ 98.

Answer 9

, construyendo desde la respuesta de zvrba y el comentario de dianot:

Sólo hacen de la colección de recepción sea un vector de pares en lugar de un mapa, y el problema señalado por dianot ha terminado. Por lo tanto, el uso de zvrba ejemplo:

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

Así que sin la construcción de copias intermedias o conjuntos que podemos obtener de manera eficiente la intersección de dos mapas. Esta construcción se compila con gcc5.3.