как я могу получить std :: набор ключей для std :: map - PullRequest
Новая
       40

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

31 голосов
/ 25 марта 2009

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

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

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

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

Ответы [ 9 ]

14 голосов
/ 25 марта 2009

То, что вы в основном хотите, это копия, так как 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.

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

std::transform(MyMap.begin(), MyMap.end(),
    std::inserter(MySet, MySet.end()),
    [](auto pair){ return pair.first; });
12 голосов
/ 25 марта 2009

Карта делает гарантийный заказ; вот почему он называется отсортированный ассоциативный контейнер . Вы можете использовать set_intersection с пользовательской функцией сравнения, второй вариант перечислен здесь .

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

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, чтобы избежать написания временной функции.)

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

8 голосов
/ 25 марта 2009

На практике 

yourmap::const_iterator mi;
set<key_type> k;
for (mi = yourmap.begin(); mi != yourmap.end(); ++mi)
  k.insert(mi->first);
return k;
7 голосов
/ 25 марта 2009

Вы можете использовать универсальный boost :: transform_iterator для возврата итератора, который возвращает только ключи (а не значения). См. Как извлечь все ключи (или значения) из std :: map и поместить их в вектор?

4 голосов
/ 05 марта 2010

Лучшее решение, не поддерживающее SGI и не поддерживающее алгоритм STL, - это расширение map :: iterator следующим образом: 

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));
2 голосов
/ 25 марта 2009

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

и укажите код вашей проблемы: 

    #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;
    }
2 голосов
/ 25 марта 2009

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

1 голос
/ 20 июня 2016

Построение из ответа от 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.

1 голос
/ 23 декабря 2015

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

...