8
\$\begingroup\$

I was playing with some of the wonderful new C++11 features and tried to reimplement a function reversed that would behave just like the one in Python to allow reverse iteration on bidirectional iterables.

And to clarify since I'm been told that I was unclear, that reverse function would be used in range-based for loops. Also, I define an iterator as whatever satisfies the functions std::begin and std::end (ForwardIterator concept). I don't think I've got to explain what a bidirectional iterator is... :D

Here's my code:

template<typename BidirectionalIterable>
class ReversedObject
{
    private:

        BidirectionalIterable& _iter;

        ReversedObject(BidirectionalIterable&& iter):
            _iter(iter)
        {}

    public:

        using value_type = typename std::decay<decltype(*std::begin(_iter))>::type;
        using difference_type = std::ptrdiff_t;
        using reference = value_type&;
        using pointer = value_type*;
        using iterator = typename std::remove_reference<decltype(itertools::rbegin(_iter))>::type;
        using const_iterator = typename std::remove_reference<decltype(itertools::rbegin(_iter))>::type;
        using reverse_iterator = decltype(std::begin(_iter));
        using const_reverse_iterator = decltype(std::begin(_iter));
        using iterator_category = typename std::iterator_traits<iterator>::iterator_category;

        // Iterator functions
        auto begin() -> iterator
            { return itertools::rbegin(_iter); }
        auto begin() const -> const_iterator
            { return itertools::rbegin(_iter); }
        auto cbegin() const -> const_iterator
            { return itertools::rbegin(_iter); }
        auto end() -> iterator
            { return itertools::rend(_iter); }
        auto end() const -> const_iterator
            { return itertools::rend(_iter); }
        auto cend() const -> const_iterator
            { return itertools::rend(_iter); }

        // Reverse iterator functions
        auto rbegin() -> reverse_iterator
            { return std::begin(_iter); }
        auto rbegin() const -> const_reverse_iterator
            { return std::begin(_iter); }
        auto crbegin() const -> const_reverse_iterator
            { return std::begin(_iter); }
        auto rend() -> reverse_iterator
            { return std::end(_iter); }
        auto rend() const -> const_reverse_iterator
            { return std::end(_iter); }
        auto crend() const -> const_reverse_iterator
            { return std::end(_iter); }

    friend auto reversed<>(BidirectionalIterable&& iter)
        -> ReversedObject<BidirectionalIterable>;
};

template<typename BidirectionalIterable>
inline auto reversed(BidirectionalIterable&& iter)
    -> ReversedObject<BidirectionalIterable>
{
    return { std::forward<BidirectionalIterable>(iter) };
}

In order for that code to work, I had to write the global functions rbegin and rend with specializations for fixed-size arrays. Since c++14, these functions can be replaced by the standard functions std::rbegin and std::rend.

template<typename T>
auto rbegin(T& iter)
    -> decltype(iter.rbegin())
{
    return iter.rbegin();
}

template<typename T>
auto rbegin(const T& iter)
    -> decltype(iter.crbegin())
{
    return iter.crbegin();
}

template<typename T, std::size_t N>
auto rbegin(T (&array)[N])
    -> std::reverse_iterator<T*>
{
    return std::reverse_iterator<T*>(std::end(array));
}

template<typename T>
auto rend(T& iter)
    -> decltype(iter.rend())
{
    return iter.rend();
}

template<typename T>
auto rend(const T& iter)
    -> decltype(iter.crend())
{
    return iter.crend();
}

template<typename T, std::size_t N>
auto rend(T (&array)[N])
    -> std::reverse_iterator<T*>
{
    return std::reverse_iterator<T*>(std::begin(array));;
}

Is there any way I could improve this construct's design? :)


Example of use case of the class:

int array[] = { 1, 2, 3, 4, 5 };
std::vector<int> vec = { 6, 7, 8, 9, 123 };

// Reverse iteration with fixed-size arrays
for (int i: reversed(array))
{
    std::cout << i << std::endl;
}

// Reverse iteration with standard containers
for (auto& i: reversed(vec))
{
    i *= 5;
    std::cout << i << std::endl;
}

// Reverse iteration with initilizer_list
for (const char* str:  reversed({"one", "two", "three"}))
{
    std::cout << str << std::endl;
}
\$\endgroup\$
  • \$\begingroup\$ Is an 'iterable' a container usually? Everywhere you use iter is tremendously confusing because that usually means iterator not iterable (container) \$\endgroup\$ – David Mar 11 '13 at 16:28
  • \$\begingroup\$ What's the point of this class? If you plug in std::vector for instance you just get a subset of the functionality that std::vector gave you in the first place? Is it for pseudo-concepts purposes? But if so, maybe accepting a begin and end and using SFINAE and iterator_traits to disallow the method unless the iterator is bidirectional is a better option \$\endgroup\$ – David Mar 11 '13 at 16:31
  • \$\begingroup\$ @Dave I expressed the purpose in the introduction: find a simple way to use reverse iteration on iterables on C++11 foreach loops. Nothing to do with concepts or anything. I just liked how simple it was in Python and tried to mimick it in C++11. \$\endgroup\$ – Morwenn Mar 11 '13 at 18:50
  • \$\begingroup\$ You never mentioned foreach loops. I don't know how it is in Python. I also don't entirely know what you mean by iterable. I mostly get it. See my first comment. Now that you have mentioned C++11 range based for loops (presumably what you were referring to), check out the proposal for a std::range. It entirely covers your use case here. I would link it, but I don't feel particularly inclined to help too much after that response... \$\endgroup\$ – David Mar 11 '13 at 22:13
  • \$\begingroup\$ @Dave Well, that's true that I may have forgotten to mention the foreach loop, but reversed was introduced in Python mostly for that loop (see PEP 322). I would have defined an iterable object by whichever object that could be used with the functions std::begin and std::end (at least forward iterable that is, see iterator_concept for more details). I already knew about std::range, but it's still not in the standard and I would simply like for my class to be usesable with the components that already exist in N3485^^ \$\endgroup\$ – Morwenn Mar 12 '13 at 0:52
3
\$\begingroup\$

Overall I like this helper. Most potential complaints are due to evaluating how well it would handle something it wasn't intended to support. Here are some of my thoughts from examining its implementation.

This code goes out of its way to define a lot of names for types that are not used directly by the consuming code (value_type, difference_type, etc.), nor by my understanding of the mechanisms of range-based for. Yet it doesn't offer an explicit overload for std::begin and friends.

There's no specialization for reversed(reversed(container)). While this is probably fine because it's unlikely to come up, and likely to be inlined down to the original container, I almost expected to see something like this explicitly cover this case:

template<typename BidirectionalIterable>
inline auto reversed(ReversedObject<BidirectionalIterable>&& iter)
    -> BidirectionalIterable
{
    return { std::forward<BidirectionalIterable>(iter._iter) };
}

As other commenters have said, calling it iter in a c++ world is a bit confusing. Then again calling it iter in python would be stomping on the builtin. So I would recommend renaming it iterable or container.

It would be interesting to try to reveal more of the underlying container per Dave's comment about a subset of a vector's functionality. If this is only ever used directly in a range-based for loop, that's not too important. But if someone starts saving reversed containers (it could be interesting to have a vector that effectively has a push_front instead of a push_back), it would become frustrating to lack other methods. Could an approach that derives from the reversed container do the trick? Hmm, probably not; this would typically result in copying the full data structure, operator[] would have to be adjusted, and data() would fall apart. But that thought about copying brings up another point. The name ReversedObject is misleading; it's more like a ReversedView.

I do like the fact that trying to reverse something that doesn't have reverse iterators will fail at compile time, even if its iterators are not invoked. The following gave me clear compilation errors:

struct NonReversible {};
auto a = NonReversible();
auto b = reversed(a); // clear errors pointing here

I don't like the itertools items as much. If we could just jump ahead to C++14, that'd be fine. Outside that, my first inclination is that I'd rather see this specialization done as a partial specialization of the ReversedObject class. But it's more reusable the way you did it, and the way C++ is going, so it's hard to justify my reaction.

Thanks for the interesting code to review. It makes me want to try to write a zip for range-based for loops. (Even though it's already been done too.)

\$\endgroup\$
  • \$\begingroup\$ At first, it was only intended to be used in a range-based for loop. Therefore, I think you're right, I can delete value_type and its friends. I will also rename iter to iterable, you're right :) I'll also delete the itertools stuff and use C++14, I did not realize that I left that in place... \$\endgroup\$ – Morwenn Nov 17 '13 at 21:35
  • \$\begingroup\$ fwiw, I disagree with explicitly covering reversed(reversed(t)) - reversed should almost always produce a zero overhead layer (totally optimized out out of existence) so it doesn't matter. Plus, who would write that? \$\endgroup\$ – David Nov 16 '16 at 19:23

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.