时间戳

首页 > 解决方案 > 复杂范围的多个迭代器

c++ - 复杂范围的多个迭代器

问题描述

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

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

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

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

标签： c++range-v3

解决方案

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

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 返回迭代器的函数并不难，但一个重要的缺点是必须计算一次半的序列。

这是一个可能的实现：

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

推荐阅读