Есть ли способ пересечения/diff std :: map и std :: set?

Question

мне интересно, если есть способ, чтобы пересекаться или сделать различия между двумя структурами, определенными в std::set<MyData*> и std::map<MyData*, MyValue> со стандартными алгоритмами (как std::set_intersect)

Проблема в том, что мне нужно, чтобы вычислить разницу между заданной и , но я хотел бы избежать перераспределения его (поскольку это то, что делается много раз в секунду с большими структурами данных). Есть ли способ получить «ключевой вид» std::map? В конце концов, все, что я ищу, это рассмотреть только ключи при выполнении заданной операции, поэтому из точки реализации это должно быть возможно, но я ничего не смог найти.

Answer 1

Вы можете использовать transform_iterator от повышения для того, чтобы адаптировать std::map итератор и возвращать только ключи:

#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 работы по упорядоченным коллекциям. Вы можете написать собственный итератор, который обертывает стандартный итератор карты и возвращает ключ. Затем вы можете использовать это с помощью set_intersect