11
\$\begingroup\$

The code below is my first attempt to create a concat "range adapter" using C++20 ranges. It compiles and runs with the latest Clang. The little test function creates a few different types of ranges, and passes them to concat to create a single concatenated view. It prints the result, as expected:

1 2 3 4 5 6 7 8 9 

The idea of concat is that it can take different types of ranges, as long as the element types are the same (or maybe convertible to one another).

I'm comfortable with some aspects of C++, but I'm more of a beginner with the template meta-programming and recent additions to the standard, like concepts and ranges. So I'm sure this code is far from an "industrial strength" version.

I'm interested in hearing suggestions about any fixes and improvements, and I'm specifically interested in some next steps to make it more like the high-quality range adapters that would appear in the standard library.

If the standard library has a better way to concatenate a bunch of ranges, then I'd like to know about that, but I also want to create this one, because I want to learn how to build my own range adapters and views like this.

In my real project, this will be wrapped in a C++20 module, but for simplicity here I pasted it all in one file and removed the import and exports.

#include <vector>
#include <list>
#include <span>
#include <iostream>
#include <string>
#include <ranges>

using std::vector;
using std::cout; using std::endl;
using std::string;

namespace r = std::ranges;
namespace v = std::views;

namespace my_views {

// For convenience, create a type-function that returns the first type of a parameter pack.
template <typename T, typename... Rest>
struct GetFirstTypeT {
    using Type = T;
};
template <typename... Pack>
using GetFirstType = GetFirstTypeT<Pack...>::Type;

// The `ExpandedIter` type will be recursively instantiated to implement the `ConcatIter` for a
// concatenated view.
template <typename... Ranges>
struct ExpandedIter;

template <typename R, typename... Ranges>
struct ExpandedIter<R, Ranges...> {
    using EltT = r::range_value_t<R>;
    using IterT = r::iterator_t<R>;
    R &r;
    IterT iter;
    ExpandedIter<Ranges...> rest_iter;
    ExpandedIter(R &r, Ranges&... rest) :r(r), rest_iter(rest...) {
        iter = r.begin();
    }
    bool is_end() const {
        if (iter == r.end()) {
            return rest_iter.is_end();
        } else {
            return false;
        }
    }
    int current() {
        if (iter == r.end()) {
            return rest_iter.current();
        } else {
            return *iter;
        }
    }
    void next() {
        if (iter == r.end()) {
            rest_iter.next();
        } else {
            ++iter;
        }
    }
};

template <>
struct ExpandedIter<> {
    bool is_end() const { return true; }
    int current() { throw -111; }
    void next() {}
};

template <typename... Views>
class ConcatIter {    
    ExpandedIter<Views...> exp_iter;
public:
    using EltT = r::range_value_t<GetFirstType<Views...>>;
    
    ConcatIter(Views&... views) :exp_iter(views...) { }
    ConcatIter(const ConcatIter&) = delete;
    ConcatIter(ConcatIter&& other) = default;
    ConcatIter &operator=(const ConcatIter&) = delete;
    ConcatIter &operator=(ConcatIter&&) = delete;    
    
    bool is_end() const {
        return exp_iter.is_end();
    }
    EltT operator*() {
        return exp_iter.current();
    }
    ConcatIter& operator++() {
        exp_iter.next();
        return *this;
    }
private:
};

struct EndIter {
};

template <typename... Rs>
bool operator==(const ConcatIter<Rs...> &iter, EndIter) {
    return iter.is_end();
}

template <typename... Ranges>
class ConcatView {
    using IterT = ConcatIter<decltype(v::all(std::forward<Ranges>(std::declval<Ranges&>())))...>;
    std::tuple<decltype(v::all(std::forward<Ranges>(std::declval<Ranges&>())))...> views;
public:
    ConcatView(Ranges&&... ranges) :views(v::all(std::forward<Ranges>(ranges))...) {
    }

    IterT begin() {
        return std::make_from_tuple<IterT>(views);
    }
    EndIter end() { return {}; };

private:
};

// Concatenate ranges with same (or compatible?) element type.
template <typename... Rs>
requires (r::range<Rs> && ...)
ConcatView<Rs...> concat(Rs&&... rs) {
    ConcatView<Rs...> v(std::forward<Rs>(rs)...);
    return v;
}

} // end my_views namespace

void test1() {
    vector vec{1,2,3};
    int ia[] {7,8,9};
    std::span span{ia};
    vector<int> empty_vec;

    auto view = my_views::concat(vec, std::list{4,5,6}, empty_vec, span);
    for (auto elt : view) {
        cout << elt << ' ';
    }
    cout << endl;
}

int main(int argc, char *argv[])
{
    test1();
    return 0;
}       
\$\endgroup\$
7
  • \$\begingroup\$ Welcome to Code Review! The beginner tag could be applied if desired \$\endgroup\$ Mar 31, 2023 at 17:27
  • 1
    \$\begingroup\$ Is implementing iterators really deemed a "beginner" skill nowadays? :p #JustCppThings \$\endgroup\$
    – user673679
    Mar 31, 2023 at 19:53
  • 2
    \$\begingroup\$ Ha. :) Yeah, I shouldn't call myself a beginner anymore. I've been studying, and writing this has been my rite of passage to a next level. But C++ has a way of making everyone feel like a beginner. \$\endgroup\$
    – Rob N
    Mar 31, 2023 at 20:41
  • \$\begingroup\$ Just FYI, we prefer to see real code from real projects, it helps us understand why you are doing what you are doing. Please read A guide to Code Review for Stack Overflow users to understand the differences between code review and stack overflow. \$\endgroup\$
    – pacmaninbw
    Mar 31, 2023 at 23:01
  • 1
    \$\begingroup\$ The standard library has std::ranges::join_view, but it's hard to use that to concatenate ranges of different types like this (you'd need to use an adapter to type-erase the constituent ranges). On the other hand, that permits concatenation of run-time-variable number of ranges, and could reduce the amount of code produced by instantiating templates. \$\endgroup\$ Apr 3, 2023 at 12:47

1 Answer 1

6
\$\begingroup\$

This is not bad at all for someone who is a beginner in template meta-programming and C++20 features!

I was thinking that the recursive template ExpandedIter could be avoided by storing the individual iterators in a std::tuple and by using std::apply() and fold expressions. This is possible, but turns out to be much more work than your approach.

Don't abbreviate standard types and namespaces

Making shorter names for standard types and namespaces saves a little bit of typing, but it has several drawbacks. For one, it makes reading the code by people who don't know about your abbreviations harder. More importantly though, if you do this in a header file (which is where I would put your ConcatView class), then everyone who includes it will get these abbreviations, whether they want it or not. It is especially troublesome if they already have something named r or v.

Put private implementation details into their own namespace

It's great that you put everything into namespace my_views, this avoids potential conflicts in the global namespace. However, there are a lot of things in my_views. Ideally, you would only expose ConcatView itself. One way to make it more private is to create a second namespace inside my_views, and put everything except ConcatView and concat() in there. Common names for such a namespace are impl or detail.

Throw using proper exception types

If you throw, make sure you throw something that is or derives from one of the [standard exception types][1]. This allows you to pass a string containing a meaningful error message, and it will allow code to catch it and potentially recover from the error, depending on the type thrown. Never throw random integers.

The return type of current() should be EltT

Your ExpandedIter::current() returns int, but this should be EltT or auto. However, there is a problem: what should it return in the specialization with zero template parameters? It can't even be auto there, because it doesn't know what type to choose. Ideally, you don't implement current() for the empty ExpandedIter<>, but then you should of course never call it. You can avoid doing so by using if constexpr:

template <typename R, typename... Ranges>
struct ExpandedIter<R, Ranges...> {
    …
    auto current() {
        if constexpr(sizeof...(Ranges) != 0) {
            if (iter == r.end()) {
                return rest_iter.current();
            }
        }
        return *iter;
    }
    …
};

template<>
struct ExpandedIter<> {
    bool is_end() const { return true; }
    void next() {}
};

Should you return references instead of values?

Your operator*() returns a value, not a reference. There are two reasons why you might want to return a reference instead: one is to allow values to be modified, the other is to handle views of large objects efficiently. Making the concatenated view mutable is tricky; you have to consider whether all the individual views allow modifying the elements. However, returning const references should be easy and safe.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks! I like the if constexpr - that cleans some things up. I tried to do something with a tuple of iterators too, but I couldn't figure it out. One disadvantage, maybe, of my recursive expansion there, is that as the iteration gets to the later ranges, I think it keeps calling iter == r.rend() for all the previous ranges, on each call to is_end() or current(). But typical calls to concat won't have many ranges stacked up there. \$\endgroup\$
    – Rob N
    Mar 31, 2023 at 21:07
  • \$\begingroup\$ The only way to avoid checking iter == r.end() unnecessarily is to add a counter to keep track of how many iterators already have reached their end so you can skip checking them. It's the same whether you have a recursive solution or something like a fold expression. \$\endgroup\$
    – G. Sliepen
    Mar 31, 2023 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.