1

I have the need to map some elements to certain ids, elementId's to starting node ids in a graph. I need to store just ids of the elements so generally we could work with just sets or vectors of size_t. Generally there are millions of elements that are added in batches to be mapped to a single id. This is why we use specific representations for typical assignments and store it in a variant.

For example

//std::set -> random set of elements
//Interval -> elements from a starting id up to a final id
//Single -> just a single element 
using VariantSet = std::variant<std::set, Interval, Single>;

//This is the vector containing the mapping
std::vector< std::tuple<VariantSet, size_t> > mapping;

We started using std::ranges on several parts and the general result have been great, but i got stuck with the variant. I'd like to get a range from a function so I could iterate over the elements that are mapped to a given id.

For example:

for (auto elementId: getMappedElements(mapping, interestingId){
   do_something_with_the_element(elementId);
}

The problem I found is that i have to use std::visit to retrieve the range from the underlying object stored in the variant, but that range will be a different type depending on which real container is iterated. For example the Singular container was returning views::single while the Interval was returning iota. Of course, this enrages the compiler as the visitors must return the same type for every possible type in the variant and of course the wrapping function getMappedElements can't return multiple types either.

Currently we are passing the function "do_something_with_the_element" as a lambda so we can do a visitor that in turns applies this lambda, but it messes up some uses that we had in mind. Is there a way to achieve this "polymorphic" range so i can actually return a range that later can be further composed (very likely a transform)

Any help is appreciated.

EDIT: Link to example: https://godbolt.org/z/nx41v3Eqb . It was buried in the comments, copied here for better visibility.

Improve this question
6
  • 3
    Please show the code that enrages the compiler. A minimal reproducible example would be great. Commented Apr 2 at 20:47
  • Suggest: for (auto elementId: getMappedElements(mapping, interestingId){ do_something_with_the_element(elementId); } -> for (auto &v: getMappedVariants(mapping, interestingId){ do_something_with_variant(v); } Commented Apr 2 at 20:54
  • I think this is enough to understand my attempt: godbolt.org/z/nx41v3Eqb I tried some other syntax but the error in the end is that the visitor can't return different types, as they will be for each possible type in the variant. Commented Apr 2 at 21:42
  • Don't make visitors return things. Make visitors operate on things. Pass your visitor an object with a member function template that accepts any range. Commented Apr 3 at 3:43
  • I added an answer that mostly solves this issue. @catnip: i see your point, but i want to hide the fact the collection is stored in a variant from the user of this code. Commented Apr 3 at 13:27

2 Answers 2

Reset to default
3

Since you should rely on variant::visit, the question is then how to provide each iterated item without having to process it through some lambda.

Since c++20, coroutines could be useful in your use case: you normally use std::visit and according to the variant types, you call co_yield for each item to be iterated. A possible implementation of a dedicated mygenerator in your case would be:

using sometype = int;

// We define our variant type.
using VariantSet = std::variant<
    std::set<sometype>,
    std::vector<sometype>,
    sometype
>;

auto mygenerator (VariantSet& v)
{
    // Each visit-lambda has to explicit its return type.
    // Note that `std::generator` is available since `c++23`.
    using result_t = std::generator<sometype>;

    // for 'overloaded', see https://en.cppreference.com/w/cpp/utility/variant/visit2
    return std::visit (overloaded {
        [](std::set<sometype>    const& arg) -> result_t { for (auto const& x : arg)  { co_yield x; } },
        [](std::vector<sometype> const& arg) -> result_t { for (auto const& x : arg)  { co_yield x; } },
        [](sometype              const& arg) -> result_t { co_yield arg; }
    }, v);
}

You can use it with

int main ()
{
    std::set   <sometype> x = {2,4,6,8,10};
    std::vector<sometype> y = {1,3,5,7};
    sometype              z = 42;

    VariantSet v;

    v = x;    for (auto const& i : mygenerator(v)) {  std::cout << i << " ";  }  std::cout << "\n";
    v = y;    for (auto const& i : mygenerator(v)) {  std::cout << i << " ";  }  std::cout << "\n";
    v = z;    for (auto const& i : mygenerator(v)) {  std::cout << i << " ";  }  std::cout << "\n";
}

Demo

I think that you could pipe such a generator with some std::views.

Note however that using coroutines this way may incur some overheads (see this and this).

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

This is super neat and may have been the simpler example I have seen so far of using a coroutine for the greater good!!!! I don't know if I would use coroutines for this though, as i'm really trying to adhere to ranges and coroutines are still daunting to me.
Actually, the object returned by mygenerator is a range, and you can still write something like mygenerator(v) | std::views::drop(10) | std::views::take(5) | std::views::transform([](auto i) { return 1+i;} )
Woow, i was not aware of that!
@edrezen std::generator<const sometype&> can work though.
I accept this answer as I think is the most concise, clean and clever way to answer what I asked. I have to go my answer for other reasons that are not this answer's fault (mostly my platform/compiler constraints). Thanks @edrezen!!!!
|
1

I was toying a lot with this, and so far I have an incomplete answer but some better c++ template wizards can help me. The current code should work for std containers. It still needs work to properly allow things i can get a range from, but this helps me move forward with the desired syntax.

//This structure will take a variant that can contains containers with the same
//value_type (ints, size_t, floats, whatever). It will create a "variant iterator"
//using the variadic template and the iterator_t helper.

template <typename... ContainerTypes>
struct IterableVariantWrapper {

    //This is the part that i have to figure out yet. If the contained type
    //is NOT a container, but i can obtain a range from it, i'd like to 
    //still allow it, but haven't found the way yet.
    using VariantIter = std::variant<const_iterator_t<ContainerTypes>...>;

    //Original variant we want to iterate over.
    const std::variant<ContainerTypes...>& iterable;

    //The iterator
    struct iterator {
        VariantIter iter;

        bool operator!=(
            const iterator& other) const
        {
            return iter != other.iter;
        }
        iterator operator++()
        {
            auto advanceIter = [](auto& v) -> void { ++v; };
            std::visit(advanceIter, iter);
            return *this;
        }
        auto operator*() const
        {
            auto returnElem = [](const auto& v) { return *v; };
            return std::visit(returnElem, iter);
        }
    };

    

    auto begin()
    {
        auto getBegin = [](const auto& v) -> VariantIter {
            VariantIter iter = v.begin();
            return iter;
        };
        return iterator { std::visit(getBegin, iterable) };
    }
    auto end()
    {
        auto getEnd = [](const auto& v) -> VariantIter { return v.end(); };
        return iterator { std::visit(getEnd, iterable) };
    }
};



//Calling this with a variant that contains a container where the contained
//type is the same will build the IterableVariantWrapper structure and provide
//a range-like object
template <typename... ContainerTypes>
auto getVariantRange(
    const std::variant<ContainerTypes...>& variant)
{
    return IterableVariantWrapper { variant };
}

I was thinking that maybe having a function/struct where i could ask the type of the view i can obtain from the iterated objects may be a way to go, but I couldn't get the syntax down. For example having a function for each type that is contained in the variant where the function returns either the same object if it is already a range, or a view derived from it, and then the variant iterator deduces the types from the return type of that function.

As i see, also I still need to figure put how to support actual ranges where the sentinel is a different type too, which i guess will be the next step after the previous paragraph.

A link to a working example using this: https://godbolt.org/z/qhrbP1se6

Any comment for further improvement is greatly appreciated.

UPDATE: I made this work as I wanted, using an intermediary "converter" that creates ranges from whatever representation i have stored in the variant and is std::ranges compliant. I didn't update the code here as it adds more template stuff that I'm not sure is relevant for most people that will find this issue. You can see the working example here: https://godbolt.org/z/68q13GKdq .

Improve this answer

11 Comments

Even it is possible to write iterators for your use case like you did, it is likely to be inefficient since you have to call visit at least for operators operator++ and operator* for each iteration. I would suggest to make some benchmarking by comparing your implementation iterating thestd::vector case versus a bare metal std::vector. OTOH, I'm not sure that a coroutines based solution would be faster, so benchmarking is always the answer.
You can also have a look at Barry's answer from this post that is somewhat related.
Ok, here some code to benchmark on your side with options -O3 -march=native -DNDEBUG. I'm surprised how well the compiler manages to optimize your version since it is as fast as the std::vector version. As expected, the coroutine version is slow if you don't have much work to provide to each iterated item, but the overheads decrease for more work to do.
Don't worry about it. We have to support multi-platform builds (windows, mac and some linux distros) and in general we tend to be conservative about adding new features. Even using ranges we've found very non-uniform support for certain things. Thanks anyway!!!
Not directly related to your question, but you could use in your solution some type traits to make things a little bit clearer. See for instance this where one puts in a single tuple views_map all the required information (ie. one type associates a functor that returns a range for that type) and then use some FunctorsMap type traits to retrieve the variant types of interest.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.