CODEWITHSUNDEEP
c++std-rangesrange-v3
Hesky Fisher
Hesky Fisher

Reputation: 1365

How to create a view over a key/values range?

I have a std::vector<Key> and a function std::vector<Value> lookup(const Key& key);.

I want a view over pairs of key/value as if:

auto iterate(const std::vector<Key>& keys) {
  std::vector<std::pair<Key,Value>> result;
  for (const auto& key : keys) {
    auto values = lookup(key);
    for (const auto& value : values) {
      result.emplace_back(key, value);
    }
  }
  return result;
}

for (const auto& [key, value] : iterate(keys)) {
  // do stuff
}

But I don't want to materialize this vector. I want to just iterate over it with std::ranges/views or range-v3.

Note: I'm currently stuck on GCC 11 for reasons and so owning_views are not available, in case it comes up.

Upvotes: 1

Views: 269

Answers (1)

LHLaurini
LHLaurini

Reputation: 2570

If your function returns a std::vector<Value>, you need something to own it until you're done using it.

If you can change your function to return a view instead, you can just do:

auto iterate(const auto& keys)
{
    auto transform = [&](const auto& key)
    {
        return vw::zip(vw::repeat(key), lookup(key));
    };

    return keys | vw::transform(transform) | vw::join;
}

and you entirely avoid the problem.

Full example:

#include <iostream>
#include <map>
#include <vector>

#include <range/v3/view/all.hpp>
#include <range/v3/view/join.hpp>
#include <range/v3/view/repeat.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/zip.hpp>

using Key = std::string;
using Value = std::string;

namespace vw = ranges::views;

std::map<Key, std::vector<Value>> map
{
    { "Key 1", {"Value 1a", "Value 1b", "Value 1c"} },
    { "Key 2", {"Value 2a", "Value 2b", "Value 2c"} },
    { "Key 3", {"Value 3a", "Value 3b", "Value 3c"} },
};

auto lookup(Key key)
{
    return map.at(key) | vw::all;
}

auto iterate(const auto& keys)
{
    auto transform = [&](const auto& key)
    {
        return vw::zip(vw::repeat(key), lookup(key));
    };

    return keys | vw::transform(transform) | vw::join;
}

int main()
{
    std::vector<Key> keys{"Key 1", "Key 2", "Key 3", "Key 2"};

    for (auto&& [key, value] : iterate(keys))
    {
        std::cout << key << " -> " << value << "\n";
    }
}

If you really can't change the lookup function, nor use a owning view, then you could call lookup for every element, like this:

// DO NOT actually do this

auto iterate(const auto& keys)
{
    auto transform = [&](const auto& key)
    {
        return vw::zip(vw::repeat(key), vw::iota(static_cast<std::size_t>(0), lookup(key).size())
            | vw::transform([&](auto i) { return lookup(key)[i]; }));
    };

    return keys | vw::transform(transform) | vw::join;
}

But, of course, don't actually do this. lookup would return a new std::vector for each value.

A better alternative would be to save the values (not thread-safe):

// This is NOT thread-safe

auto iterate(const auto& keys)
{
    auto transform = [&](const auto& key)
    {
        // This assumes key is never empty
        static std::string heldKey;
        static std::vector<std::string> heldValue;

        if (heldKey != key)
        {
            heldKey = key;
            heldValue = lookup(key);
        }

        return vw::zip(vw::repeat(key), heldValue);
    };

    return keys | vw::transform(transform) | vw::join;
}

A better solution that stores the vector in the lambda passed to transform, based on @Holt's version:

auto iterate(const auto& keys)
{
    auto transform = [keys = std::vector<Value>{}](const auto& key) mutable
    {
        keys = lookup(key);
        return vw::zip(vw::repeat(key), keys);
    };

    return keys | vw::transform(transform) | vw::join;
}

And finally, for completeness, using std::views::owning_view (implicitly, GCC 12+):

namespace vw = std::views;

auto iterate(const auto& keys)
{
    auto transform = [](const auto& key)
    {
        return lookup(key) | vw::transform([&](auto& x)
        {
            return std::make_pair(key, x);
        });
    };

    return keys | vw::transform(transform) | vw::join;
}

or in C++23:

namespace vw = std::views;

auto iterate(const auto& keys)
{
    auto transform = [](const auto& key)
    {
        return vw::zip(vw::repeat(key), lookup(key));
    };

    return keys | vw::transform(transform) | vw::join;
}

In both of these, an std::owning_view is constructed from lookup(key) and "owns" that value until destroyed, avoiding a dangling reference.

Upvotes: 2

Related Questions