How to Retrieve the Firsts from a Collection of Pairs

When using the STL, there is a use case that pops up every now and then and that often causes more trouble than necessary: if we have a collection of pairs, like an std::vector of pairs, or simply a std::map, how can we retrieve the collection of the first elements of each item in the collection?

In C++14, it is quite straightforward. But before that, it’s not, even though this need is very simple. Let’s review the various options we have to achieve this operation.

In C++14

The feature that C++14 brings and that helps in getting the firsts of a collection of pairs is generic lambdas. Which means lambda that can take an auto parameter that will take care of deducing the type of the objects it is applied to.

Here is a piece of code to illustrate it:

std::map<int, std::string> numbers_with_names = { {1, "one"}, {2, "two"}, {3, "three"} };
std::vector<int> numbers;

std::transform(begin(numbers_with_names), end(numbers_with_names),
               std::back_inserter(numbers),
               [](auto const& pair){ return pair.first; });

This code uses std::transform, a central algorithm of the STL, and the generic lambda that takes the first elements of each pair in the numbers_with_names container. And note that we could have a std::vector<std::pair<int, std::string>> instead of the map, and the code would be exactly the same.

However this code needs a bit more work to make it more expressive. Indeed, from the perspective of the call to std::transform, what we want to achieve is extracting the numbers out of the elements in the containers. It so happens that these numbers are stored in the first of each pair item of the collection, but this is an implementation detail. Taking the first is how to get the number. And to respect levels of abstraction, we should show what we do, and not how we do it. It would be nice to have a getNumber function instead.

And since the fact of taking the first element of a pair in a collection is fairly common, we can replace the generic lambda by a shorter name, get_first. We can define it into a general purpose technical namespace, say util, and in a separate header file so that other contexts can use too. And we may as well return a const reference to the first since the pair is itself passed by const reference:

namespace util
{
    const auto get_first = [](auto const& pair) -> auto const& { return pair.first; };
}

Then we can create a named lambda that carries the description of what we want to achieve, getNumber, defined in the vicinity of our calling code:

const auto getNumber = get_first;

And the call to std::transform becomes:

std::transform(begin(numbers_with_names), end(numbers_with_names),
               std::back_inserter(numbers),
               getNumber);

Are there two many layers of objects here? Maybe. I think the exact number of layers is a matter of style. But to me, what matters is that the call site of the algorithm is written at the level of abstraction of the collection, so here with the word “Number”.

The range library

The range-v3 library has a different approach, using range adaptors. Ranges are the future of the STL. Even if they are only a library today, some of its components are likely to make it into the next version of the standard. So let’s see how ranges get the firsts of the elements in a collection of pairs (or a map):

std::map<int, std::string> numbers_with_names = { {1, "one"}, {2, "two"}, {3, "three"} };
const auto numbers = numbers_with_names | ranges::view::keys;

Then numbers can be treated like any other range:

for (int number : numbers)
{
    std::cout << number << ' ';
}

Note that, just like in the C++14 solution, we can be more explicit about the contents of the collection we are handling by defining a getNumber range adaptor:

const auto getNumber = ranges::view::keys;

And the calling code then becomes:

std::map<int, std::string> numbers_with_names = { {1, "one"}, {2, "two"}, {3, "three"} };
auto numbers = numbers_with_names | getNumber;

Before C++14

What if you don’t have C++14 nor the range library available for your production code? At the time I’m writing these line, it represents quite a few C++ developers, although this number should dwindle with time.

Anyway, if this is your case, all hope is not lost! We can obtain just the same call site as in C++14, except it needs a slightly larger implementation of get_first, to emulate the generic lambda. And the good news is that you only need to write this implementation once.

A generic lambda (the one that takes auto as a function parameter) is pretty much equivalent to a function object (the good old Functor! Functional Programming experts, pardon my French). So we need a function object that can accept anything as a parameter of its operator(). We can achieve this with a template operator():

struct get_first
{
    template<typename T, typename U>
    T const& operator()(std::pair<T, U> const& pair)
    {
        return pair.first;
    }
};

Which is a tad less generic than the lambda because it accepts a std::pair whereas the lambda works on anything that has a first member. In C++11 we could achieve this by using std::result_of, but I have yet to see a case for such a half generic function object.

Now to take the seconds of a collection of pairs

Next up, a sequel of this post will be how to extract the seconds instead of the firsts of a collection of pairs, and we’ll see the intricacies related to this special case.

Just joking, if you can get the first, then you have everything you need to get the second. The adaptation is left as an exercise to the reader.

Joke inception, level two: I’m not going to make you write it! Don’t you hate those exercises left to the reader? Just replace “first” with “second” in the whole article (and return a U const& in the latest function object), and you should be good to go.

If you’re using this article for your Daily C++, you don’t have to include those traits of humour to get the message across. Or do you (joke inception, level three)?

Don't want to miss out ? Follow:   
Share this post!