复杂范围的多个迭代器

Question

我正在尝试让多个迭代器达到更复杂的范围（使用 range-v3 库）——使用 filter、for_each 和 [=14= 手动实现笛卡尔积].但是，当我尝试将多个迭代器保持在这样的范围内时，它们共享一个共同的值。例如：

#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;
}

我希望迭代器 it1 保持指向范围的开头，而迭代器 it2 遍历整个序列。令我惊讶的是，it1 也增加了！我得到以下输出：

[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]

这是为什么？
我怎样才能避免这种情况？
如何让多个独立的迭代器指向范围的不同位置？
Should I implement a cartesian product in a different way? (that's my previous question)

虽然它没有反映在上面的 MCVE 中，但考虑一个用例，其中有人试图实现类似于 std::max_element 的东西 - 试图 return 一个迭代器到叉积。在寻找最高值时，您需要将迭代器存储到当前最佳候选者。它在您搜索时无法更改，如果您需要范围的 copy（如其中一个答案中所建议的），那么管理迭代器会很麻烦。

实现整个叉积也不是一种选择，因为它需要大量内存。毕竟，将范围与过滤器和其他即时转换一起使用的全部意义在于避免这种具体化。

Answer 1

迭代器是指向向量中元素的指针，在本例中，it1 指向向量的开头。因此，如果您试图将迭代器指向向量的相同位置，它们将是相同的。但是，您可以有多个迭代器指向向量的不同位置。希望这能回答您的问题。

Answer 2

生成的视图似乎存储状态，结果证明是单次传递。您可以通过简单地根据需要制作尽可能多的视图副本来解决这个问题：

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;
}

另一种选择是将视图具体化为评论中提到的容器。

牢记上述单遍视图的局限性，实现 max_element 并不难 returns 迭代器的函数，具有必须计算序列一次半的重要缺点。

这是一个可能的实现：

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; 
}

Answer 3

这是怎么回事？

这里的整个问题源于 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 没有明确提及人们可以期望的迭代器类别这一事实（至少我没有发现它被提及）。这确实是一个巨大的改进，因为所有标准库算法都明确说明了它们需要的迭代器类别。

在 std::max_element 的特殊情况下，您不是第一个被 ForwardIterator 而不仅仅是 InputIterator 的违反直觉的要求绊倒的人，请参阅 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在 InputIterator 上丢失，以便 std::max_element 使用它。

因此，许多其他标准库函数也不适用于 std::max_element，例如std::istreambuf_iterator 真是可惜：你就是无法从现有标准库的文件中获取最大元素！您要么必须先将整个文件加载到内存中，要么必须使用自己的最大算法。

标准库只是缺少一种真正 return 最大元素的算法，而不是指向最大元素的迭代器。这样的算法也可以与 InputIterator 一起使用。当然，这可以很容易地手动实现，但是让标准库提供它仍然很方便。我只能推测为什么它不存在。也许一个原因是，它需要 value_type 是可复制构造的，因为 InputIterator 不需要 return 对元素的引用，而对于最大算法来说，它可能反过来违反直觉复制一份...

所以，现在关于你的实际问题：

这是为什么？（即为什么你的范围只有 return InputIterators？）

显然，yield 会即时创建值。这是设计使然，这就是人们想要使用 yield 的原因：不必预先创建（并因此存储）范围。因此，我看不出 yield 是如何以一种满足 multipass guarantee 的方式实现的，尤其是第二个项目符号让我很头疼：

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

从技术上讲，我可以想象可以实现 yield 的方式是从一个范围创建的所有迭代器共享一个公共内部存储，该存储在第一次遍历期间动态填充。这样不同的迭代器就有可能为您提供对底层对象的相同引用。但是 std::max_element 会默默地消耗 O(n²) 内存（笛卡尔积的所有元素）。因此，在我看来，最好不要这样做，而是让用户自己具体化范围，以便他们意识到它的发生。

如何避免这种情况？

好吧，正如 metalfox 所说，您可以复制您的视图，这将导致不同的范围，从而产生独立的迭代器。不过，这不会使 std::max_element 起作用。因此，考虑到 yield 的性质，不幸的是，这个问题的答案是：您根本无法通过 yield 或任何其他即时创建值的技术来避免这种情况。

如何让多个独立的迭代器指向范围的不同位置？

这与上一个问题有关。基本上，这个问题自己回答了：如果你想 point 独立的迭代器在 不同的位置 ，这些位置必须存在于内存中的某个地方。因此，您至少需要具体化那些曾经有一个指向它们的迭代器的元素，在 std::max_element 的情况下意味着您必须具体化所有这些元素。

我应该用不同的方式实现笛卡尔积吗？

我可以想象出许多不同的实现方式。但是 none 他们将能够同时提供这两个属性：

returnForwardIterators
需要少于 O(n²) 内存

从技术上讲，可以实现一个专门用于 std::max_element 的迭代器，这意味着它只在内存中保留当前的最大元素，以便可以引用它...但是这个会有点荒谬，不是吗？我们不能指望像 range-v3 这样的通用库会提出如此高度专业化的迭代器类别。

总结

你说的是

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...

我绝对同意"this is not a rare outlier"！但是，这并不一定意味着 "there should be some reasonable way to achieve this without traps"。考虑例如NP-hard 问题。面对一个异常值并不罕见。尽管如此，不可能（除非 P=NP）在多项式时间内解决它们。在您的情况下，如果没有 ForwardIterators，根本不可能使用 std::max_element。并且不可能在不消耗 O(n²) 内存的情况下在笛卡尔积上实现 ForwardIterator（由标准库定义）。

对于 std::max_element 的特殊情况，我建议只实现您自己的版本，即 return 是最大元素而不是指向的迭代器它。

但是，如果我正确理解了你的问题，你的问题就更笼统了，std::max_element 只是一个例子。所以，我不得不让你失望了。即使使用现有的标准库，由于迭代器类别不兼容，一些微不足道的事情也是不可能的（同样，std::istreambuf_iterator 是一个现有的例子）。所以，如果恰好添加了range-v3，这样的例子就会多一些。

所以，最后，我的建议是尽可能使用自己的算法，否则吞下实现视图的药丸。

复杂范围的多个迭代器

Multiple iterators to a complex range

c++

range-v3