How to use functional programming in C++11 to obtain the keys from a map?

Question

An std::map<K,V> m, in a mathematical view, is a function f_m in which all pairs of domain and range elements (x,y) ∈ K × V such that f_m(x) = y.

So, I want to get the domain of f_m, i.e. the set of all keys (or perhaps the range - the set of all values). I can do this procedurally with C++11, like so:

std::unordered_set<K> keys;
for (const auto& kv_pair : m) { keys.insert(kv_pair->first); }

right? But - I want to do it functionally (read: In a fancy way which makes me feel superior). How would I do that?

Notes:

• I do not necessarily need the result to be an std::unordered_set; something which would could replace such a set would probably work too (e.g. a set Facade).
• Readability, (reasonable) terseness and avoiding gratuitous copying of data are all considerations.

Answer 1

std::map<int, int> m;
std::unordered_set<int> keys;

std::for_each(m.begin(), m.end(), [&keys](decltype(*m.begin()) kv)-> void {keys.insert(kv.first);});

Answer 2

There's a number of ways you could write this. One slightly more 'functional' way is:

vector<string> keys;
transform(begin(m), end(m), back_inserter(keys), [](const auto& p){ return p.first; });

But to really improve on this and enable a more functional style using the standard library we need something like Eric Niebler's Range Proposal to be standardized. In the meantime, there are a number of non-standard range based libraries like Eric's range-v3 and boost Range you can use to get a more functional style.

Answer 3

IMHO, an important characteristic for intuitive functional code is that the algorithm actually return the result, rather than setting some variable elsewhere as a side effect. This can be done with std::accumulate, e.g.:

#include <iostream>
#include <set>
#include <map>
#include <algorithm>

int main()
{
    typedef std::map<int, int> M;

    M m { {1, -1}, {2, -2}, {3, -3}, {4, -4} };

    auto&& x = std::accumulate(std::begin(m), std::end(m), std::set<int>{},
                               [](std::set<int>& s, const M::value_type& e)
                               {
                                  return s.insert(e.first), std::move(s);
                                                // .first is key,
                               });              // .second is value
    for (auto& i : x)
        std::cout << i << ' ';
    std::cout << '\n';
}

Output:

1 2 3 4 

See it run here

The std::begin(m), std::end(m) bit is actually a big headache, as it frustrates chaining of such operations. For example, it's be ideal if we could chain "functional" operations like our "GET KEYS" above alongside others...

x = m. GET KEYS . SQUARE THEM ALL . REMOVE THE ODD ONES

...or at least...

x = f(f(f(m, GET KEYS), SQUARE THEM ALL), REMOVE THE ODD ONES)

...but you'll have to write some trivial code yourself to get there or pick up a library supporting functional "style".

Answer 4

Boost.Range provides exactly that, with the adaptor map_keys. Look at this example from the documentation.

You can write:

auto keys = m | boost::adaptors::map_keys;

// keys is a range view to the keys in your map, no copy involved
// you can use keys.begin() and keys.end() to iterate over it

EDIT : I'll leave my old answer below, it uses iterators instead of ranges. Notice that the range represented by the two boost::transform_iterator still represents the set of keys in your map.

IMO the functional way to do that would require an iterator that points to the keys of the map, so that you can simply use std::copy. It makes sense because you are not transforming or accumulating anything, you are just copying the keys.

Unfortunately the standard does not provide iterator adaptors, but you can use those provided by Boost.Iterator.

#include <algorithm>
#include <map>
#include <unordered_set>    
#include <boost/iterator/transform_iterator.hpp>

struct get_first
{
    template<class A, class B>
    const A & operator()(const std::pair<A,B> & val) const
    {
        return val.first;
    }
};

int main()
{
    std::map<int, std::string> m;
    std::unordered_set<int> r;

    // ...

    std::copy(boost::make_transform_iterator(m.begin(), get_first{}),
              boost::make_transform_iterator(m.end(), get_first{}),
              std::inserter(r, r.end()) );
}

It would be more expressive to have an iterator that dereferences the Kth element of a tuple/pair, but transform_iterator will do the job fine.