5
\$\begingroup\$

I tried to write a small header-only library that provides a type similar to iterators for std::tuple as well as some STL-like algorithms. I would be grateful for your comments and suggestions.

Code on GitHub: https://github.com/Nicholas42/Cpp-Bits-and-Pieces/tree/master/tup_iter

// tup_iter.hpp
#ifndef TUP_ITER_HPP
#define TUP_ITER_HPP

#include <iterator>
#include <tuple>
#include <type_traits>
#include <variant>

namespace tuple_iter {

// Tag objects to enable deduction of index
template<size_t Index>
inline constexpr std::integral_constant<size_t, Index> index_tag;

template<class Tup, size_t Index>
struct TupleIter {
    using tuple_t = Tup;

    explicit TupleIter(tuple_t &t) : tup(t) {}

    TupleIter(tuple_t &t, std::integral_constant<size_t, Index> /*unused*/) : tup(t) {}

    // BEGIN - Static Method Section

    static constexpr auto size() noexcept -> size_t {
        return std::tuple_size_v<std::decay_t<tuple_t>>;
    }

    static constexpr auto index() noexcept -> size_t {
        return Index;
    }

    template<class Inp>
    static constexpr decltype(auto) get(Inp &&inp) {
        if constexpr (Index < size()) {
            return std::get<Index>(inp);
        } else {
            // Improves error messages.
            static_assert(Index < size(), "Enditerator is not dereferencable.");
            return 0;
        }
    }

    // END - Static Method Section

  private:
    tuple_t &tup;

    // Helper for value_t since we cannot specialize a type alias directly and have to prevent the
    // instantiation of std::tuple_element_t<I, tuple_t> for the case of I == size() sinze then this
    // would not compile. Hence, we cannot simply use std::conditional.

    // value_t for the past-the-end iterator
    template<size_t I = Index, class = void>
    struct helper_struct {
        struct incomplete;
        using value_type = incomplete;   // Wanted to take void, but then references do not compile even
                                         // if in SFINAE-deactivated functions.
        using next_type = incomplete;
    };

    // value_t for all dereferencable iterators
    template<size_t I>
    struct helper_struct<I, std::enable_if_t<(I < size())>> {
        using value_type = std::tuple_element_t<I, std::decay_t<tuple_t>>;
        using next_type = TupleIter<tuple_t, Index + 1>;
    };

  public:
    // Return value of dereferencing operator
    using value_t = typename helper_struct<>::value_type;
    using next_t = typename helper_struct<>::next_type;

    // Comparison methods. Compare equal to objects of the same type (i.e. have same index are over same
    // tuple type)

    constexpr auto operator==([[maybe_unused]] const TupleIter<tuple_t, Index> &other) const noexcept
        -> bool {
        return true;
    }

    template<size_t I, class = std::enable_if_t<I != Index>>
    constexpr auto operator==([[maybe_unused]] const TupleIter<tuple_t, I> &other) const noexcept
        -> bool {
        return false;
    }

    template<size_t I>
    constexpr auto operator!=(const TupleIter<tuple_t, I> &other) const noexcept -> bool {
        return !(*this == other);
    }

    // Canonical way to convert to bool, false iff past-the-end-iterator.

    constexpr explicit operator bool() const noexcept {
        return Index < size();
    }

    // These seem a bit weird since they are const de-/increment operators. But we cannot implement
    // operator+(int inc) as one would normally do it, since inc had to be a constant expression. So
    // this seems like the best way to do this. Furthermore it is actually similar to normal iterators,
    // since for them the following would be equivalent:
    //      ++it;       AND       it = ++it;
    // So reassigning the return value is not that weird.

    template<size_t I = Index, class = std::enable_if_t<(0 < I)>>
    [[nodiscard]] constexpr auto operator--() const noexcept -> TupleIter<tuple_t, Index - 1> {
        return TupleIter<tuple_t, Index - 1>{tup};
    }

    template<size_t I = Index, class = std::enable_if_t<(I < size())>>
    [[nodiscard]] constexpr auto operator++() const noexcept -> TupleIter<tuple_t, Index + 1> {
        return TupleIter<tuple_t, Index + 1>{tup};
    }

    template<std::ptrdiff_t N>
    [[nodiscard]] constexpr auto advance() const noexcept -> TupleIter<tuple_t, Index + N> {
        return TupleIter<tuple_t, Index + N>{tup};
    }

    template<size_t I = Index, class = std::enable_if_t<(I < size())>>
    constexpr auto operator*() noexcept -> value_t & {
        return std::get<Index>(tup);
    }

    template<size_t I = Index, class = std::enable_if_t<(I < size())>>
    constexpr auto operator*() const noexcept -> const value_t & {
        return std::get<Index>(tup);
    }

    template<size_t I = Index, class = std::enable_if_t<(I < size())>>
    constexpr explicit operator value_t() const {
        return std::get<index()>(tup);
    }

    [[nodiscard]] constexpr auto get_tuple() const noexcept -> const tuple_t & {
        return tup;
    }

    constexpr auto get_tuple() noexcept -> tuple_t & {
        return tup;
    }
};

template<size_t Index, class Tuple>
TupleIter(Tuple, std::integral_constant<size_t, Index>)->TupleIter<Tuple, Index>;

namespace detail {
template<class T>
struct is_tuple_iter_impl : std::false_type {};

template<class Tup, size_t Index>
struct is_tuple_iter_impl<TupleIter<Tup, Index>> : std::true_type {};
}   // namespace detail

template<class TupIter>
struct is_tuple_iter : detail::is_tuple_iter_impl<std::decay_t<TupIter>> {};

template<class T>
inline constexpr bool is_tuple_iter_v = is_tuple_iter<T>::value;

template<class TupIter>
struct tuple {
    using type = typename std::decay_t<TupIter>::tuple_t;
};

template<class TupIter>
using tuple_t = typename tuple<TupIter>::type;

template<std::ptrdiff_t N, std::size_t Index, class Tup>
constexpr auto advance(const TupleIter<Tup, Index> &it) -> TupleIter<Tup, Index + N> {
    return it.template advance<N>();
}

// Easier to use in constant expressions
template<class TupIter1, class TupIter2,
         class = std::enable_if_t<is_tuple_iter_v<TupIter1> && is_tuple_iter_v<TupIter2>>>
constexpr size_t distance_v = TupIter2::index() - TupIter1::index();

// Performs template argument deduction
template<class TupIter1, class TupIter2>
constexpr auto distance([[maybe_unused]] const TupIter1 &it1, [[maybe_unused]] const TupIter2 &it2) {
    return distance_v<TupIter1, TupIter2>;
}

template<class T>
using begin_t = TupleIter<T, 0>;

template<class T>
using end_t = TupleIter<T, std::tuple_size_v<std::decay_t<T>>>;

template<class T>
constexpr auto begin([[maybe_unused]] T &tup) noexcept -> begin_t<T> {
    return begin_t<T>{tup};
}

template<class T>
constexpr auto end([[maybe_unused]] T &tup) noexcept -> end_t<T> {
    return end_t<T>{tup};
}

template<class TupIter, class = std::enable_if_t<is_tuple_iter_v<TupIter>>>
struct is_end :
        std::conditional_t<std::decay_t<TupIter>::index() == std::decay_t<TupIter>::size(),
                           std::true_type, std::false_type> {};

template<class TupIter>
constexpr bool is_end_v = is_end<TupIter>::value;
}   // namespace tuple_iter

#endif   // TUP_ITER_HPP

// any_iter.hpp
#ifndef ANY_ITER_HPP
#define ANY_ITER_HPP

#include "tup_iter.hpp"
#include <type_traits>
#include <variant>

namespace tuple_iter {

// I decided to directly use a variant for this type and not wrap it in another class since this makes
// the integration in existing visitor code much easier.

namespace detail {
template<class Tuple, class T>
struct helper_t;

template<class Tuple, size_t... Indices>
struct helper_t<Tuple, std::index_sequence<Indices...>> {
    using type = std::variant<TupleIter<Tuple, Indices>...>;
};

template<class Tuple>
using default_index_sequence = std::make_index_sequence<std::tuple_size_v<std::decay_t<Tuple>>>;

template<class Begin, class End, size_t... Indices>
struct span_sequence_impl :
        span_sequence_impl<decltype(++std::declval<Begin>()), End, Indices..., Begin::index()> {};

template<class Iter, size_t... Indices>
struct span_sequence_impl<Iter, Iter, Indices...> {
    using sequence = std::index_sequence<Indices...>;
};
}   // namespace detail

// Not including the past-the-end iterator per default. It is easier to handle it with std::optional in
// application code and do not have to handle it in visitors, since contrary to the others, it does not
// have the same methods. It is possible to provide an own sequence of indices that should be considered
template<class Tuple, class index_seq = detail::default_index_sequence<Tuple>>
using AnyIter = typename detail::helper_t<Tuple, index_seq>::type;

template<class Begin, class End>
using span_sequence =
    typename detail::span_sequence_impl<std::decay_t<Begin>, std::decay_t<End>>::sequence;

template<class TupleIter, class index_seq = detail::default_index_sequence<tuple_t<TupleIter>>,
         class = std::enable_if_t<is_tuple_iter_v<TupleIter>>>
constexpr auto make_any_iter(TupleIter &&it, index_seq /*unused*/ = {})
    -> AnyIter<tuple_t<TupleIter>, index_seq> {
    return AnyIter<tuple_t<TupleIter>, index_seq>{std::forward<TupleIter>(it)};
}

template<class Tuple, size_t N, class index_seq = detail::default_index_sequence<Tuple>,
         class = std::tuple_element<N, Tuple>>
constexpr auto make_any_iter(Tuple &&tup, std::integral_constant<size_t, N> /*unused*/ = {},
                             index_seq /*unused*/ = {}) -> AnyIter<Tuple, index_seq> {
    return AnyIter<Tuple, index_seq>{TupleIter<Tuple, N>{std::forward<Tuple>(tup)}};
}
}   // namespace tuple_iter

#endif   // ANY_ITER_HPP
// tup_algo.hpp
#ifndef TUP_ALGO_HPP
#define TUP_ALGO_HPP

#include <tuple>
#include <type_traits>
#include <optional>
#include "any_iter.hpp"

namespace tuple_iter {

// Type based find algorithm, only works on the types. Pred should be a class template that explicitly converts to bool.
template<template<class> class Pred, class Begin, class End>
constexpr auto find_type(Begin begin, End end) noexcept {
    if constexpr (begin == end) {
        return end;
    } else {
        if constexpr (Pred<typename Begin::value_t>()) {
            return begin;
        } else {
            return find_type<Pred>(++begin, end);
        }
    }
}

template<template<class> class Pred, class Begin, class End>
using find_type_t = decltype(find_type<Pred>(std::declval<Begin>(), std::declval<End>()));

// Value based find algorithm, can use both types and values in the tuple. Pred should be an object that can be called with each of the searched types.
template<class Pred, class Begin, class End, class Sequence = span_sequence<Begin, End>>
constexpr auto find_type_any(Begin begin, End end, Pred pred, Sequence seq = {}) noexcept
    -> std::optional<AnyIter<typename Begin::tuple_t, Sequence>> {
    if constexpr (begin == end) {
        return {};
    } else {
        if (pred(*begin)) {
            return {begin};
        } else {
            return find_type_any(++begin, end, pred, seq);
        }
    }
}

// Applies f on each element in the iterated range. f should be an object that is callable on each of the types in the range.
template<class Begin, class End, class Func>
constexpr auto for_each(Begin begin, End end, Func f) noexcept -> Func {
    if constexpr (begin == end) {
        return f;
    } else {
        f(*begin);
        return for_each(++begin, end, f);
    }
}

// Accumulates the iterated range in the form:
//   Op(...Op(Op(v, begin), ++begin), ..., end)
// Op should be an object that can be called appropriately.
template<class Begin, class End, class Val = typename Begin::value_t, class Op = std::plus<>>
constexpr auto accumulate(Begin begin, End end, Val v = {}, Op op = {}) noexcept {
    if constexpr (begin == end) {
        return v;
    } else {
        return accumulate(++begin, end, op(v, *begin), op);
    }
}

}   // namespace tuple_iter
#endif   // TUP_ALGO_HPP
#include "any_iter.hpp"
#include "tup_algo.hpp"
#include "tup_iter.hpp"
#include <cassert>
#include <iostream>
#include <vector>

using namespace tuple_iter;

// Templated class that evaluates to true iff it is templated on cv char.
template<class Found>
struct StructFinder {
    constexpr explicit operator bool() {
        return std::is_same_v<std::remove_cv_t<Found>, char>;
    }
};

// Templated class that evaluates to true iff its template argument passed to its template template
// argument instantiates a true type

// Templated class that searches for the value of its data member.
template<class Val>
struct ValueFinder {
    template<class T, class = std::enable_if_t<!std::is_same_v<Val, T>>>
    constexpr auto operator()(T && /*unused*/) -> bool {
        return false;
    }

    constexpr auto operator()(const Val &v) -> bool {
        return v == searched;
    }

    Val searched;
};

template<class Val>
ValueFinder(Val)->ValueFinder<Val>;

auto main() -> int {
    std::tuple<int, const char, double> tup{1, 'A', 2.1};
    using tup_t = decltype(tup);

    end_t<tup_t> e{tup};
    auto a = --e;
    auto b = ++++begin(tup);
    TupleIter iter(tup, index_tag<1>);

    static_assert(e.index() == 3);
    static_assert(std::is_same_v<decltype(a), decltype(b)>);
    static_assert(std::is_same_v<decltype(a)::value_t, double>);
    static_assert(std::is_same_v<begin_t<tup_t>::value_t, std::tuple_element_t<0, tup_t>>);
    static_assert(distance_v<begin_t<tup_t>, end_t<tup_t>> == 3);
    static_assert(iter.index() == 1);
    static_assert(std::is_same_v<begin_t<std::tuple<>>, end_t<std::tuple<>>>);

    // decltype(e)::value_t i = 5; // Good: Does not compile
    assert(*a == 2.1);

    auto any = make_any_iter(iter);
    auto any2 = make_any_iter(tup, index_tag<2>, std::index_sequence<2>{});
    assert(any.index() == 1);
    assert(any2.index() == 0);

    std::visit(
        [](auto &&first, auto &&second) { std::cout << *first << ' ' << *second << '\n'; }, any, any2);

    const char value{std::get<1>(any)};
    assert(value == std::get<1>(tup));
    static_assert(span_sequence<decltype(a), end_t<tup_t>>::size() == 1);
    static_assert(span_sequence<end_t<tup_t>, end_t<tup_t>>::size() == 0);

    using it_t = find_type_t<StructFinder, begin_t<tup_t>, end_t<tup_t>>;
    it_t it = find_type<StructFinder>(begin(tup), end(tup));
    std::cout << *it << '\n';

    using tup2_t = std::tuple<int, std::vector<int>, int, char, double>;
    using it2_t = find_type_t<std::is_integral, typename begin_t<tup2_t>::next_t, end_t<tup2_t>>;
    static_assert(it2_t::index() == 2);

    auto any_iter = *find_type_any(begin(tup), a, ValueFinder{1});
    static_assert(std::variant_size_v<decltype(any_iter)> == 2);
    assert(any_iter.index() == 0);

    // Should be type safe
    assert(!find_type_any(begin(tup), end(tup), ValueFinder<int>{'A'}));

    std::tuple numbers{1, 1.4, 3l, -7.123f, 'A'};

    auto sum1 = for_each(++begin(numbers), --end(numbers), [sum = 0.](auto v) mutable {
        std::cout << v << ", ";
        return sum += v;
    });
    auto sum2 = accumulate(++begin(numbers), --end(numbers));

    assert(sum1(0.) == sum2);
    std::cout << '\n' << sum2 << '\n';
}
```
\$\endgroup\$
  • \$\begingroup\$ I think it would help if there were more examples of why this is useful. For example, summing up the items of a tuple can already be done in standard C++: std::apply( [](auto... v) { return (v + ...); }, numbers); or with std::visit and a closure. How is this better than normal fold expressions, or a vector<any>? \$\endgroup\$ – butt Jan 17 at 22:23
  • \$\begingroup\$ I think the most interesting is find_type_t and maybe other algorithms on the types of a tuple. One is able search for a type, and not just an exact type, like with std::get<T> but following pretty arbitrary constraints, this question inspired me for this project. I will add some examples what one can do with this. But mostly this is just an exercise for me and I am not that interested in the usefulness of the code but more the experience I gather by writing it and hopefully by other people commenting on it. \$\endgroup\$ – n314159 Jan 17 at 23:03
  • \$\begingroup\$ Hi n314159, it seems that you mistakenly post tup_iter.hpp twice when you meant to have tup_iter.hpp + any_iter.hpp. I have replaced the second code block with any_iter.hpp according to your GitHub repository. Feel free to roll back my edit if I am wrong! \$\endgroup\$ – L. F. Jan 18 at 10:37
  • \$\begingroup\$ @L.F. Thanks very much, yes I messed that a bit up. \$\endgroup\$ – n314159 Jan 18 at 10:46
  • \$\begingroup\$ @butt I added a further example for find and also changed the example for accumulate to show it is a bit more flexible than std::apply. But I agree, that most use-cases are a bit contrived. I think if I expand the algorithms a bit, there are interesting things to be done on types (i.e. splicing parts of two tuples together or tranforming a tuple<a,b,c,d> to tuple<pair<a,b>, pair<c,d> pretty easily) but that is not done right now. \$\endgroup\$ – n314159 Jan 18 at 10:50
2
\$\begingroup\$

Great. Clean and readable code, following modern C++ programming practices. Good job!

Here are my suggestions on further improvements:

Tag types

The point of tags is disambiguation. Instead of reusing std::integral_constant<size_t, Index>, I prefer to use a separate type:

template <std::size_t I>
struct index_type {
    explicit index_type() = default;
};
template <std::size_t I>
inline constexpr index_type<I> index{};

About std::conditional_t

// Helper for value_t since we cannot specialize a type alias directly and have to prevent the
// instantiation of std::tuple_element_t<I, tuple_t> for the case of I == size() sinze then this
// would not compile. Hence, we cannot simply use std::conditional.

We can. Just a bit differently:

// somewhere
template <typename T>
struct type_identity {
    using type = T;
};

struct incomplete;

then

using decay_tuple_t = std::decay_t<tuple_t>;  // exposition only

using value_t = typename std::conditional_t<  // note: _t
    I < size(),
    std::tuple_element<Index, decay_tuple_t>, // note: no _t
    incomplete
>::type;                                      // note: ::type
using next_t = typename std::conditional_t<
    I < size(),
    TupleIter<tuple_t, Index + 1>,
    incomplete
>::type;

Think of why _t and ::type are used at the same time.

Comparison

Now, according to your logic, two TupleIters are equal if and only if they are the same type. We can already compare types with is_same, so I'd expect the == and != operators to take the tuple into account as well. I also prefer to define symmetrical operators as non-members, but that's unimportant in this case:

template <typename Tuple, std::size_t I>
constexpr auto operator==(const TupleIter<Tuple, I>& lhs, const TupleIter<Tuple, I>& rhs)
    -> decltype(lhs.get_tuple() == rhs.get_tuple()) // for SFINAE
{
    return lhs.get_tuple() == rhs.get_tuple();
}

template <typename Tuple, std::size_t I>
constexpr auto operator!=(const TupleIter<Tuple, I>& lhs, const TupleIter<Tuple, I>& rhs)
    -> decltype(lhs == rhs)
{
    return !(lhs == rhs);
}

++ and --

// These seem a bit weird since they are const de-/increment operators. But we cannot implement
// operator+(int inc) as one would normally do it, since inc had to be a constant expression. So
// this seems like the best way to do this. Furthermore it is actually similar to normal iterators,
// since for them the following would be equivalent:
//      ++it;       AND       it = ++it;
// So reassigning the return value is not that weird.

(You actually cannot reassign because the type changes.)

One sec ... you can implement this:

auto new_iter = it + incr<5>;

or even

using namespace tuple_iter::literals;
auto new_iter = it + 5_i;

(Let's pray that it + 5 will become implementable in a future standard.)

distance

Don't forget you can implement iter1 - iter2.

is_end

This is convoluted:

template<class TupIter, class = std::enable_if_t<is_tuple_iter_v<TupIter>>>
struct is_end :
        std::conditional_t<std::decay_t<TupIter>::index() == std::decay_t<TupIter>::size(),
                           std::true_type, std::false_type> {};

Consider:

template <class TupIter, class = std::enable_if_t<is_tuple_iter_v<TupIter>>>
struct is_end :
        std::bool_constant<std::decay_t<TupIter>::index() == std::decay_t<TupIter>::size()> {};

Also, is_end is SFINAE-friendly but is_end_v issues hard errors.

if else if

// Type based find algorithm, only works on the types. Pred should be a class template that explicitly converts to bool.
template<template<class> class Pred, class Begin, class End>
constexpr auto find_type(Begin begin, End end) noexcept {
    if constexpr (begin == end) {
        return end;
    } else {
        if constexpr (Pred<typename Begin::value_t>()) {
            return begin;
        } else {
            return find_type<Pred>(++begin, end);
        }
    }
}

We can use else if to avoid one level of indentation:

template <template <class> class Pred, class Begin, class End>
constexpr auto find_type(Begin begin, End end) noexcept
{
    if constexpr (begin == end) {
        return end;
    } else if constexpr (Pred<typename Begin::value_t>()) {
        return begin;
    } else {
        return find_type<Pred>(++begin, end);
    }
}

You add a level of recursion for every element in the tuple.

Conversion to bool

The operator bool is a bit weird to me. if (iter)? I guess a named function like .is_valid() may be clearer.

Small issues

  • Macro names like TUP_ITER_HPP are common and easy to clash. I would append a random sequence of characters: TUP_ITER_HPP_Hfod7C3iAQ (generated with Random String Generator on random.org).

  • size_t should be std::size_t, and #include <cstddef> is missing.

Stylistic (subjective)

The points below are purely subjective and can be ignored if they contradict with your established style guidelines.

  • I don't really like the always-trailing-return style. I prefer static constexpr std::size_t size() noexcept. This is especially distracting: auto main() -> int.
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your in-depth-analysis. I will consider your comments carefully. \$\endgroup\$ – n314159 Jan 18 at 14:36
  • \$\begingroup\$ Your comments were very helpful, thanks again. I will be reworking my code to include them. The only thing I am still unsure about is the comparison. I see your reasoning, but I will at least add SFINAE s.t. the code still compiles when the tuple is not equality comparable (i.e. deactivate operator==). And in my opinion, it would be cleaner if the operator== only takes really comparable types if it works with the values (so that comparing between different TupleIters will not compile). \$\endgroup\$ – n314159 Jan 23 at 9:37
  • \$\begingroup\$ @n314159 I see your point. Instead of accepting incompatible types and always returning false, you argue that it's less misleading to disable it in the first place, right? I agree. I'll update my code. \$\endgroup\$ – L. F. Jan 23 at 9:47
  • \$\begingroup\$ @n314159 (btw, don't declare operator== as a member function. It breaks SFINAE.) \$\endgroup\$ – L. F. Jan 23 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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