Why writing reverse iterator can affect whether an iterator is random-access-iterator or not?

user_15204768 0
Viewed 93

I wanna write a container with random-access-iterator:

#include <cstddef>
#include <iterator>
#include <concepts>

namespace foo
{
    struct container
    {
        struct iter
        {
            using difference_type = std::ptrdiff_t;
            using pointer = int*;
            using reference = int&;
            using value_type = int;
            using iterator_category = ::std::random_access_iterator_tag;

            iter& operator++();
            iter operator++(int);
            iter& operator--();
            iter operator--(int);

            iter operator+(difference_type) const;
            iter operator-(difference_type) const;
            iter& operator+=(difference_type);
            iter& operator-=(difference_type);
            bool operator==(const iter&) const;
            bool operator!=(const iter&) const;
            bool operator<(const iter&) const;
            bool operator>(const iter&) const;
            bool operator<=(const iter&) const;
            bool operator>=(const iter&) const;
            difference_type operator-(const iter&) const;

            int& operator*() const;
            int& operator[](difference_type) const;
        };

        // code for reverse iterator, now it is comment out

        /* using riter = std::reverse_iterator<iter>;

        iter end();
        riter rbegin()
        {
            return std::reverse_iterator(this->end());
        }
        */
    };

    inline container::iter operator+(container::iter::difference_type, const container::iter&);
}

int main(void)
{
    static_assert(std::random_access_iterator<foo::container::iter>, "");
    return 0;
}

Then I compile it with g++-11 -std=c++20 and it can be compiled successfully.

But if I want to write a reverse iterator for this container, that is, uncomment those code for reverse iterator, there will be a compile error:

<source>:55:2: error: static_assert failed ""
        static_assert(std::random_access_iterator<foo::container::iter>, "");
        ^                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:55:21: note: because 'foo::container::iter' does not satisfy 'random_access_iterator'
        static_assert(std::random_access_iterator<foo::container::iter>, "");
                           ^
/opt/compiler-explorer/gcc-11.2.0/lib/gcc/x86_64-linux-gnu/11.2.0/../../../../include/c++/11.2.0/bits/iterator_concepts.h:669:8: note: because '__n + __j' would be invalid: invalid operands to binary expression ('const iter_difference_t<foo::container::iter>' (aka 'const long') and 'const foo::container::iter')
        { __n +  __j } -> same_as<_Iter>;
              ^
1 error generated.

And I also use Clang 13 but got the same result. So how should I write the iterator correctly?

iterator stl c++
2 Answers

The mystery here is why adding a few lines of code that don't alter the definition of foo::container::iter causes the static_assert to fail.

This is because the implementation of std::reverse_iterator's constructor, in the body of the commented function, evaluates concept std::random_access_iterator to determine what sort of reverse iterator to create.

When this happens, operator+(difference_type, iter) hasn't been declared yet because it's further down in your code, so the your container::iter initially fails to satisfy the concept.

Later, you declare the required operator+ and your type now would satisfy concept std::random_access_iterator, were it not for the following part of the standard: [temp.constr.atomic]

... If, at different points in the program, the satisfaction result is different for identical atomic constraints and template arguments, the program is ill-formed, no diagnostic required.

At different points in your code, the concept std::random_access_iterator has different satisfaction results! So your code is ill-formed, no diagnostic required. (GCC does actually diagnose this - clang just gives you the error message from when it first evaluated the concept, which is why you were confused).

You can fix this by moving your declaration of operator+ before using std::reverse_iterator. For example:

struct container {
    struct iter {
        // all your methods, as before
        
        friend iter operator+(difference_type, iter);
    }

    using riter = std::reverse_iterator<iter>;

    iter end();
    riter rbegin();
}
user_54419320

Just because you give your iterator a random_access_iterator_tag category doesn't make it a random access iterator.

You have to provide all the operations.

The compiler error is telling you that the expression 3 + iter_var is invalid (where iter_var is one of your iterators).

The link that Remy provided lists the operations that "have to work".

user_9924900
Related