как я могу получить std :: набор ключей к std :: map

Question

Я писал алгоритм этим утром, и я столкнулся с любопытной ситуацией. У меня есть два std::map s. Я хочу выполнить набор пересечений на наборах ключей каждого (чтобы найти, какие ключи являются общими для обеих карт). В какой-то момент в будущем, я думаю, что, вероятно, мне также понадобится выполнить вычитание здесь. К счастью, STL включает функции для обеих этих операций. Проблема в том, что я не могу получить std::set ключей из std::map. Есть какой-либо способ сделать это? Я искал что-то, что бы это просто, как это в Java:

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

Я понимаю, что я не могу использовать функцию std::set_intersection() непосредственно на итераторах в карты, так как карты выставить std::pair объектов вместо просто ключей. Кроме того, я не думаю, что карта гарантирует заказ. Я также заинтересован в выполнении этой же операции по паре std::multimap, если это имеет значение.

EDIT: Я забыл упомянуть, что первоначально в связи с возрастом компилятора я вынужден использовать (MSVC++ 6), большинство из хитроумных уловок шаблонов, которые доступны в импульс не может быть использован.

Answer 1

Вы можете использовать универсальное повышение :: transform_iterator вернуть итератор, который возвращает только ключи (а не значение). См. How to retrieve all keys (or values) from a std::map and put them into a vector?

Answer 2

Вы можете просто перебирать и добавлять каждую клавишу в набор. Наборы и карты являются как упорядоченными, так и неупорядоченными вариантами.

Answer 3

Что вы в основном хотите, это копия, так как std :: map не хранит ключи в std :: set. std :: copy предполагает, что типы значений совместимы, что здесь не так. Std :: map :: value_type - std :: пара. Вы хотите скопировать только первую часть пары, что означает, что вам нужен std :: transform. Теперь, поскольку вы будете использовать insert_iterator на наборе, порядок не имеет значения. Std :: set будет сортировать по вставке, даже если карта уже была отсортирована.

[изменить] Код может быть проще. Вершина головы, а не компиляция.

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

Если у вас есть SGI select1st, вам не нужен boost :: bind.

[править] Обновления для 14

C++

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

Answer 4

гарантийный заказ; поэтому он называется sorted associative container. Вы можете использовать set_intersection с пользовательской функцией компаратора, второй вариант указан here.

Так, что-то вроде

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

должен сделать трюк. (Также можно использовать boost :: lambda и bind, чтобы избежать записи временной функции.)

Оператор по умолчанию < по парам сравнивает оба компонента. Так как вам нужна эквивалентность только над первой частью пары (ключ карты), вам необходимо определить собственный оператор сравнения, который обеспечивает такое отношение (что и делает функция выше).

Answer 5

На практике

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

Answer 6

Я нашел хорошую ссылку на ваш вопрос here

и есть некоторый код для вашей проблемы:

#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

Лучшее без SGI, не повышающего Решение, совместимое с алгоритмом STL, состоит в том, чтобы расширить map :: итератор следующим образом:

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

, а затем использовать их, как так:

 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

Вы могли бы, возможно, создать итератор для карты, которая только дает ключи, используя подталкивания :: адаптеры :: map_key, смотри пример в boost::adapters::map_key documentation. Это, похоже, было введено в Boost 1.43 и должно быть совместимо с C++ 2003, но я не знаю о VC++ 6, в частности, от эпохи C++ 98.

Answer 9

Построение из ответа от zvrba и комментария от dianot:

Просто делают коллекцию Принимающей быть вектором пара вместо карты, и проблема указываемого dianot закончился. Таким образом, используя zvrba пример:

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

Так что без построения промежуточных копий или наборов мы можем получить эффективное пересечение двух карт. Эта конструкция компилируется с помощью gcc5.3.