问题

为了一个限制为C++17的项目，我想要一个独立实现C++20 std::views::join() 的版本。我知道存在 range-v3，但不幸的是，负责的人不愿意包含其他第三方库。

我希望编写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类，使其能够嵌套/叠加，例如join_view(join_view(T))，同时保留std::views::join提供的功能（即可选可修改的元素Godbolt)？

更新：首先可以为范围的范围（例如std::vector<std::vector<T>> godbolt)创建一个std::views::join对象，因为我怀疑标准意图使其在性能上与编写明确嵌套循环相媲美。我认为限制自己在这个基本情况下可能会导致更好的实现。我下面提供的版本满足这一点，但在设计上存在缺陷，导致了嵌套join_view的段错误。

我已经成功为第一部分实现了C++17的解决方案： (实现)，类代码在最后提供。join_view包装类通过保存对嵌套对象的引用（可以是const也可以不是），并提供begin()和end()函数，以允许基于范围的循环。这些函数返回一个内部迭代器（我认为它满足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的以下Stack Overflow问题：[join view how, join boost problem, join string_view problem, join compilation issue]，但这些问题不涉及实现。我还尝试理解和阅读ranges-v3 join包装类的实现，这证明是困难的。

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

<details>
<summary>英文:</summary>

For a C++17 restricted project I would like to have a standalone implementation of C++20 `std::views::join()`. I am aware of the existence of [range-v3](https://github.com/ericniebler/range-v3) but unfortunately the person in charge is unwilling to include further 3rd party libraries.

My aim is the write the C++17 equivalent of this [(Implementation)](https://godbolt.org/z/GKe81rx7b) --&gt; solved see below

```c++
std::vector&lt;std::vector&lt;int&gt;&gt; data{{1,2},{1,2,3},{1,2,3,4}};
for(const auto &amp; element : std::views::join(data)){
    std::cout &lt;&lt; element &lt;&lt; &quot;\n&quot;;
}

and the more difficult part this (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";
}

I want to additionally emphasis the nesting of calls (std::views::join(std::views::join(data))), as they are the current road-block. To be more specific
> How can I design my join_view class to be nestable [/stackable, e.g. join_view(join_view(T))] [, while preserving the functionality which std::views::join provides (i.e. optionally modifiable elements Godbolt)?](refined/edited question)

> Update: A std::views::join object can first be created for a range of ranges (e.g. a std::vector<std::vector<T>> godbolt), as, I suspect, the standard intends it to be comparable, in the performance sense, with writing the explizit nested loops. I think restricting one self to this basecase may lead to a better implementation. My version provided down below fullfills this, is though design wise flawed, resulting in segfaults for nesting of join_view.

I have successfully implemented a C++17 solution for the first part (Implementation), class code is provided at the end. The join_view wrapper class works by holding a reference to the nested object (which may or may not be const) and provides begin() and end() function to allow a range based for loop. These return an internal iterator (I think it fulfills the LegacyInputIterator requirements), for which the required operators (++,*,==,!=) are implemented.

Now lets consider my unsuccessful attempts to implement the second part.

1. Let's just try if I have written a super code that works as well for nesting the join_view construction. Nope. For a triple nested vector std::vector<std::vector<std::vector<int>>> and a twice applied join_view instead of a int as element type I receive a std::vector<int> (Implementation). If we take a look at the types of the nested construction auto deeper_view = join_view(join_view(data_deeper)); this expands in C++ Insights to join_view<std::vector<...>> deeper_view = join_view(join_view<std::vector<...>>(data_deeper)); which is obviously a sign of an issue?

2. I then tried changing all calls of the std::begin() and std::end() to their $.begin() counterpart, since these are the one defined for the join_view wrapper. Unfortunately this did also not help but now the C++ Insights output is unreadable and I cant follow it anymore.

Now I am no longer sure that this could even work therefore I am asking the question from above: How can I redesign my join_view class to be nestable?

I am aware of the following stackoverflow questions regarding std::views::join [join view how, join boost problem, join string_view problem, join compilation issue], but these do not consider implementation. I have as well tried understanding and reading the implementation of ranges-v3 join wrapper, which has provided to be difficult.

Current partially working status of standalone join_view wrapper:

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(),{});
    }
};

答案1

得分: 1

你需要实现一个递归的类模板来实现你的目标。以下是一个可行的快速而粗糙的原型。

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

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

// 你需要为你需要的容器声明特化。
template <class T, class Alloc>
struct is_container<std::vector<T, Alloc>> : public std::true_type {};

// 视图的基本定义
template <typename T, typename = void>
struct join_view;

// 针对非容器类型的特化
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_;
};

// 针对容器的特化
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 (outer_ == container->end()) return *this;
            if (++inner_ != inner_container_type{*outer_}.end()) return *this;

            for (;;) {
                if (++outer_ == container->end()) break;

                inner_ = inner_container_type{*outer_}.begin();
                if (inner_ != inner_container_type{*outer_}.end()) break;
            }
            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，这对于这个方案的工作至关重要。

#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 (outer_ == container_->end()) return *this;
if (++inner_ != inner_container_type{*outer_}.end()) return *this;
for (;;) {
if (++outer_ == container_->end()) break;
inner_ = inner_container_type{*outer_}.begin();
if (inner_ != inner_container_type{*outer_}.end()) break;
}
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;
}

template <class T, typename = void>
struct is_container : public std::false_type {};
template <typename  T>
struct is_container<T, std::void_t<typename T::iterator>> : public std::true_type {};
template <class T, typename = void>
struct is_const_container : public std::false_type {};
template <typename  T>
struct is_const_container<T, std::void_t<typename T::const_iterator>> : public std::true_type {};