如何设计独立的 C++17 std::views::join 替代方案？

Question

对于 C++17 受限项目，我希望有一个 C++20 的独立实现

std::views::join()

。我知道 range-v3 的存在，但不幸的是，负责人不愿意包含更多的第 3 方库。

我的目标是编写 C++17 等效的（实现） --> 已解决，见下文

std::vector<std::vector<int>> data{{1,2},{1,2,3},{1,2,3,4}};
for(const auto & element : std::views::join(data)){
    std::cout << element << "\n";
}

和这个（Godbolt）更难的部分

std::vector<std::vector<std::vector<int>>> data{{{1,2},{3,4}},{{5,6,7}}};
auto nested_join = std::views::join(std::views::join(data));
for(const auto element : nested_join){
   std::cout << element << "\n";
}

我想额外强调调用的嵌套 (

std::views::join(std::views::join(data))

)，因为它们是当前的障碍。更具体

如何设计我的

join_view

类是可嵌套的？

---

第一部分(Implementation)我已经成功实现了一个C++17的解决方案，最后提供了类代码。

join_view

包装类通过保存对嵌套对象的引用（可能是也可能不是 const）来工作，并提供

begin()

和

end()

函数以允许基于范围的 for 循环。这些返回一个内部迭代器（我认为它满足LegacyInputIterator要求），为此实现了所需的运算符（++，*，==，！=）。

现在让我们考虑一下我实施第二部分的失败尝试。

1. 让我们试试我是否编写了一个超级代码，该代码也适用于嵌套

   join_view

   结构。没有。对于三重嵌套向量

   std::vector<std::vector<std::vector<int>>>

   和两次应用

   join_view

   而不是

   int

   作为元素类型，我收到

   std::vector<int>

   （实施）。如果我们看一下嵌套结构的类型

   auto deeper_view = join_view(join_view(data_deeper));

   这在 C++ Insights 中扩展为

   join_view<std::vector<...>> deeper_view = join_view(join_view<std::vector<...>>(data_deeper));

   这显然是一个问题的迹象？

2. 然后我尝试将

   std::begin()

   和

   std::end()

   的所有调用更改为它们的

   $.begin()

   对应项，因为这些是为

   join_view

   包装器定义的。不幸的是，这也没有帮助，但现在 C++ Insights 输出不可读，我不能再关注它了。

现在我不再确定这是否可行，因此我从上面提出问题：如何重新设计我的

join_view

类以使其可嵌套？

我知道以下关于

std::views::join

[join view how, join boost problem, join string_view problem, join compilation issue] 的 stackoverflow 问题，但这些不考虑实施。我也尝试理解和阅读 ranges-v3 连接包装器的实现，这提供了困难。

standalone

join_view

包装器的当前部分工作状态：

template<typename T>
class join_view{
private:
    T & ref_range;
    using outer_iterator = decltype(ref_range.begin());
    using inner_iterator = decltype((*ref_range.begin()).begin());

public:
    join_view(T & range) : ref_range{range} {}

    class iterator{
    private:
        outer_iterator outer;
        inner_iterator inner;
    public:
        iterator(outer_iterator outer_, inner_iterator inner_): outer{outer_}, inner{inner_} {}

        auto& operator*(){
            return *inner;
        }
    
        auto& operator++(){
            ++inner;
            if(inner != (*outer).end()){
                return *this;
            }
            ++outer;
            inner = (*outer).begin();
            
            return *this;
        }
        auto operator==(const iterator & other){
            return outer == other.outer;
        }

        auto operator!=(const iterator & other){
            return outer != other.outer;
        }
    };

    auto begin(){
        return iterator(ref_range.begin(),  (*ref_range.begin()).begin());
    }

    auto end(){
        return iterator(ref_range.end(),{});
    }
};

Answer 1

你需要实现一个递归类模板来实现你的目标。这是一个快速但肮脏的原型。

#include <cassert>
#include <iostream>
#include <type_traits>
#include <vector>

template <class T>
struct is_container : public std::false_type {};

// you'll need to declare specializations for the containers you need.
template <class T, class Alloc>
struct is_container<std::vector<T, Alloc>> : public std::true_type {};

// basic definition for our view 
template <typename T, typename = void>
struct join_view;

// specialization for non-container types
template <typename T>
struct join_view<T, std::enable_if_t<!is_container<T>::value>> {
    using contained_type = T;
    using outer_const_iterator = const T*;

    using const_iterator = const T*;

    join_view(const T& t) : t_(t) {}

    const_iterator begin() const { return &t_; }

    const_iterator end() const { return begin() + 1; }

    const T& t_;
};

// specialization for containers
template <typename Container>
struct join_view<Container, std::enable_if_t<is_container<Container>::value>> {

    using contained_type = typename Container::value_type;
    using outer_const_iterator = typename Container::const_iterator;

    using inner_container_type = join_view<contained_type>;
    using inner_const_iterator = typename inner_container_type::const_iterator;

    friend inner_container_type;

    class const_iterator {
        friend join_view;
        friend inner_container_type;

       public:
        const_iterator() = default;
        const_iterator(const const_iterator&) = default;
        const_iterator(const_iterator&&) = default;

        const_iterator& operator=(const const_iterator&) = default;
        const_iterator& operator=(const_iterator&&) = default;

        private:

        const_iterator(const Container* container, const outer_const_iterator& outer,
                       const inner_const_iterator& inner)
            : container_(container), outer_(outer), inner_(inner) {}

        const_iterator(const Container* container, outer_const_iterator outer)
            : container_(container), outer_(outer) {
            assert(outer_ == container_->end());
        }


       public:
        const_iterator& operator++() {
            if (++inner_ != inner_container_type{*outer_}.end()) return *this;
            if (++outer_ != container_->end())
                inner_ = inner_container_type{*outer_}.begin();

            return *this;
        }

        bool operator==(const const_iterator& other) const {
            if (outer_ == other.outer_) {
                if (outer_ == container_->end()) return true;
                return inner_ == other.inner_;
            }
            return false;
        }

        bool operator!=(const const_iterator& other) const {
            return !(*this == other);
        }

        const auto& operator*() const 
        {
            return *inner_;
        }        

       private:
        const Container* container_ = nullptr;
        outer_const_iterator outer_;
        inner_const_iterator inner_;
    };

    join_view(const Container& container) : outer_(container) {}

    const_iterator begin() const {
        return {&outer_, outer_.begin(),
                inner_container_type{*(outer_.begin())}.begin()};
    }

    const_iterator end() const { return {&outer_, outer_.end()}; }

    const Container& outer_;
};

template <typename T>
auto make_join_view(const T& t)
{
    return join_view<T>(t);
}


int main() {
    static_assert(is_container<std::vector<int>>::value);
    static_assert(!is_container<int>::value);

    int test_int = 42;

    for (auto x : make_join_view(test_int)) std::cout << x << std::endl;
    std::cout << std::endl;

    std::vector<int> v{1, 2, 3};
    for (const auto& x : make_join_view(v)) std::cout << x << std::endl;
    std::cout << std::endl;

    std::vector<std::vector<int>> vv{{1}, {2, 3}, {4, 5, 6}};
    for (const auto& x : make_join_view(vv)) std::cout << x << std::endl;
    std::cout << std::endl;

    std::vector<std::vector<std::vector<int>>> vvv{ {{1}, {2, 3}, {4, 5, 6}}, {{11}, {22, 33}, {44, 55, 66}}  };
    for (const auto& x : make_join_view(vvv)) std::cout << x << std::endl;
}

非常粗糙，因为它只处理非常基本的遍历，但应该适用于大多数容器类型。

我认为可以重写 is_container<> 来检查 Container::const_iterator 是否存在。这将使 join_view 可以在任何容器上工作，也可以在任何视图上工作。

注意：确保您的实现使用名称 const_iterator，这对于该方案的工作是绝对必要的。

您可以在这里玩代码：https://godbolt.org/z/jhe93b1rx