¿Hay alguna manera de intersectar/diff un std :: map y un std :: set?

Question

Me pregunto si hay alguna manera de hacer que se cruzan o las diferencias entre dos estructuras definidas como std::set<MyData*> y std::map<MyData*, MyValue> con algoritmos estándar (como std::set_intersect)

El problema es que necesito para calcular la diferencia entre el aparato y la conjunto de claves del mapa, pero me gustaría evitar la reasignación (ya que es algo que se realiza muchas veces por segundo con estructuras de datos de gran tamaño). ¿Hay alguna manera de obtener una "vista clave" del std::map? Después de todo, lo que estoy buscando es considerar solo las teclas al hacer la operación de configuración, así que desde un punto de implementación debería ser posible, pero no he podido encontrar nada.

Answer 1

Puede utilizar transform_iterator de impulso con el fin de adaptar el iterador std::map y para devolver sólo las teclas:

#include <algorithm> 
#include <iostream> 
#include <map> 
#include <iterator> 
#include <string> 
#include <set> 
#include <vector> 

#include <boost/iterator/transform_iterator.hpp> 

typedef std::map<std::string, int> map_t; 
typedef std::set<std::string> set_t; 

const map_t::key_type & getKey(const map_t::value_type & pair) 
{ 
    return pair.first; 
} 

typedef const map_t::key_type & (*getKey_t)(const map_t::value_type &); 

typedef boost::transform_iterator<getKey_t, map_t::iterator> key_iterator_t; 

int main() 
{ 
    map_t map; 
    map["a"]=1; map["b"]=2; 
    set_t set; 
    set.insert("a"); set.insert("c"); 

    std::vector<std::string> v; 

    std::set_intersection(set.begin(), set.end(), 
     key_iterator_t(map.begin(), getKey), 
     key_iterator_t(map.end(), getKey), 
     std::back_inserter(v)); 
    std::copy(v.begin(), v.end(), 
     std::ostream_iterator<std::string>(std::cout," , ")); 
} 

Answer 2

set_intersection obras en colecciones ordenadas. Puede escribir un iterador personalizado que envuelva el iterador de mapa estándar y devuelva la clave. A continuación, puede usar esto con set_intersect