Multiple iterators to a complex range

user_635654 0
Viewed 330

I am trying to have multiple iterators to a bit more complex range (using range-v3 library) -- manually implementing a cartesian product, using filter, for_each and yield. However, when I tried to hold multiple iterators to such range, they share a common value. For example:

#include <vector>
#include <iostream>
#include <range/v3/view/for_each.hpp>
#include <range/v3/view/filter.hpp>

int main() {
    std::vector<int> data1{1,5,2,7,6};
    std::vector<int> data2{1,5,2,7,6};
    auto range =
            data1
            | ranges::v3::view::filter([](int v) { return v%2; })
            | ranges::v3::view::for_each([&data2](int v) {
                return data2 | ranges::v3::view::for_each([v](int v2) {
                    return ranges::v3::yield(std::make_pair(v,v2));
                });
            });
    auto it1 = range.begin();
    for (auto it2 = range.begin(); it2 != range.end(); ++it2) {
        std::cout << "[" << it1->first << "," << it1->second << "] [" << it2->first << "," << it2->second << "]\n";
    }
    return 0;
}

I expected the iterator it1 to keep pointing at the beginning of the range, while the iterator it2 goes through the whole sequence. To my surprise, it1 is incremented as well! I get the following output:

[1,1] [1,1]
[1,5] [1,5]
[1,2] [1,2]
[1,7] [1,7]
[1,6] [1,6]
[5,1] [5,1]
[5,5] [5,5]
[5,2] [5,2]
[5,7] [5,7]
[5,6] [5,6]
[7,1] [7,1]
[7,5] [7,5]
[7,2] [7,2]
[7,7] [7,7]
[7,6] [7,6]

While it is not reflected in the MCVE above, consider a use case where someone tries to implement something similar to std::max_element - trying to return an iterator to the highest-valued pair in the cross product. While looking for the highest value you need to store an iterator to the current best candidate. It cannot alter while you search, and it would be cumbersome to manage the iterators if you need a copy of the range (as suggested in one of the answers).

Materialising the whole cross product is not an option either, as it requires a lot of memory. After all, the whole point of using ranges with filters and other on-the-fly transformations is to avoid such materialisation.

range-v3 c++
3 Answers

It seems that the resulting view stores state such that it turns out to be single pass. You can work around that by simply making as many copies of the view as you need:

int main() {
    std::vector<int> data1{1,5,2,7,6};
    std::vector<int> data2{1,5,2,7,6};
    auto range =
            data1
            | ranges::v3::view::filter([](int v) { return v%2; })
            | ranges::v3::view::for_each([&data2](int v) {
                return data2 | ranges::v3::view::for_each([v](int v2) {
                    return ranges::v3::yield(std::make_pair(v,v2));
                });
            });

    auto range1= range;         // Copy the view adaptor
    auto it1 = range1.begin();

    for (auto it2 = range.begin(); it2 != range.end(); ++it2) {
        std::cout << "[" << it1->first << "," << it1->second << "] [" << it2->first << "," << it2->second << "]\n";
    }

    std::cout << '\n';
    for (; it1 != range1.end(); ++it1) { // Consume the copied view
        std::cout << "[" << it1->first << "," << it1->second << "]\n";
    }
    return 0;
}

Another option would be materializing the view into a container as mentioned in the comments.

Keeping in mind the aforementioned limitation of single-pass views, it is not really hard to implement a max_element function that returns an iterator, with the important drawback of having to compute the sequence one time and a half.

Here's a possible implementation:

template <typename InputRange,typename BinaryPred = std::greater<>>
auto my_max_element(InputRange &range1,BinaryPred &&pred = {}) -> decltype(range1.begin()) {
    auto range2 = range1;
    auto it1 = range1.begin();
    std::ptrdiff_t pos = 0L;

    for (auto it2 = range2.begin(); it2 != range2.end(); ++it2) {
        if (pred(*it2,*it1)) {
            ranges::advance(it1,pos);   // Computing again the sequence as the iterator advances!
            pos = 0L;
            }
        ++pos;
        }
    return it1; 
}
user_63500780

What is goin on here?

The entire problem here originates in the fact that std::max_element requires its arguments to be LecacyForwardIterators while the ranges created by ranges::v3::yield apparently (obviously?) only provide LecacyInputIterators. Unfortunately, the range-v3 docs do not explicitly mention the iterator categories one can expect (at least I haven't found it being mentioned). This would indeed be a huge enhancement as all standard library algorithms do explicitly state what iterator categories they require.

In the particular case of std::max_element you are not the first one to stumble over this counterintuitive requirement of ForwardIterator rather than just InputIterator, see Why does std::max_element require a ForwardIterator? for example. In summary, it does make sense, though, because std::max_element does not (despite the name suggesting it) return the max element, but an iterator to the max element. Hence, it is in particular the multipass guarantee that is missing on InputIterator in order to make std::max_element work with it.

For this reason, many other standard library functions do not work with std::max_element either, e.g. std::istreambuf_iterator which really is a pity: you just cannot get the max element from a file with the existing standard library! You either have to load the entire file into memory first, or you have to use your own max algorithm.

The standard library is simply missing an algorithm that really returns the max element rather than an iterator pointing to the max element. Such an algorithm could work with InputIterators as well. Of course, this can very easily be implemented manually, but still it would be handy to have this given by the standard library. I can only speculate why it doesn't exist. Maybe one reason is, that it would require the value_type to be copy constructable because InputIterator is not required to return references to the elements and it might be in turn counterintuitive for a max algorithm to make a copy...

So, now regarding your actual questions:

Why is this? (i.e. why does your range only return InputIterators?)

Obviously, yield creates the values on the fly. This is by design, it's the very reason why one would want to use yield: to not have to create (and thus store) the range upfront. Hence, I do not see how yield could be implemented in a way that it fulfills the multipass guarantee, especially the second bullet is giving me headaches:

  • If a and b compare equal (a == b is contextually convertible to true) then either they are both non-dereferenceable or *a and *b are references bound to the same object

Technically, I could imagine that one could implement yield in a way that all iterators created from one range share a common internal storage that is filled on the fly during the first traversal. Then it would be possible for different iterators to give you the same references to underlying objects. But then std::max_element would silently consume O(n²) memory (all elements of your cartesian product). So, in my opinion it's definitely better to not do this and instead make the users materialize the range themselves, so that they are aware of it happening.

How can I avoid this?

Well, as already said by metalfox, you can copy your view which would result in different ranges and thus independent iterators. Still, that wouldn't make std::max_element work. So, given the nature of yield the answer to this question, unfortunately, is: you simply cannot avoid this with yield or any other technique that creates values on the fly.

How can I keep multiple, independent iterators pointing in various locations of the range?

This is related to the previous question. Basically, this question answers itself: If you want to point independent iterators in various locations, these locations have to exist somewhere in memory. So, you need to materialize at least those elements that did once have an iterator pointing to them, which in case of std::max_element means that you have to materialize all of them.

Should I implement a cartesian product in a different way?

I can imagine many different implementations. But none of them will be able to provide both of these properties all together:

  • return ForwardIterators
  • require less than O(n²) memory

Technically, it could be possible to implement an iterator that is specialized for the usage with std::max_element, meaning that it keeps only the current max element in memory so that it can be referenced... But this would be somewhat ridiculous, wouldn't it? We cannot expect a general purpose library like range-v3 to come up with such highly specialized iterator categories.

Summary

You are saying

After all, I don't think my use case is such a rare outlier and ranges are planned to be added to the C++20 standard - so there should be some reasonable way to achieve this without traps...

I definitely agree that "this is not a rare outlier"! However, that doesn't necessarily imply that "there should be some reasonable way to achieve this without traps". Consider e.g. NP-hard problems. It is not a rare outlier to be facing one. Still, it is impossible (unless P=NP) to solve them in polynomial time. And in your case it is simply not possible to use std::max_element without ForwardIterators. And it is not possible to implement a ForwardIterator (as defined by the standard library) on a cartesian product without consuming O(n²) memory.

For the particular case of std::max_element I would suggest to just implement your own version that returns the max element rather than an iterator pointing to it.

However, if I understand your question correctly your concern is more general and std::max_element is just an example. So, I have to disappoint you. Even with the existing standard library some trivial things are impossible due to incompatible iterator categories (again, std::istreambuf_iterator is an existing example). So, if range-v3 happens to be added, there will just be some more of such examples.

So, finally, my recommendation is to just go with your own algorithms, if possible, and swallow the pill of materializing a view otherwise.

user_98834380

An iterator is a pointer to an element in the vector, in this case, it1 points to the beginning of the vector. And hence, if you are trying to point the iterator to the same location of the vector, they will be the same. However, you can have multiple iterators pointing to different locations of the vector. Hope this answers your question.

user_9395450
Related