Container begin / end / cbegin / cend semantics, iterator / const_iterator compatibility

user_616460 0
Viewed 234

I've been working on a custom ReversibleContainer, and I thought I was on the right track, but I've hit a snag in testing while going through the semantics of the Container named requirements which makes me think I've fundamentally mis-implemented this. I'm working with C++17.

In particular, my current implementation is formed somewhat like this (pardon errors, I'm condensing it to an example as I type here), where:

  • Item is the type the container holds
  • element is the type iterators dereference to (it's convertible to Item)
  • struct is used for overall brevity in this snippet
  • only the types and members that I think are relevant are included
struct my_container {

    using value_type = Item;
    using reference = value_type &;
    using const_reference = const value_type &;
    using size_type = std::vector<Item>::size_type;
    using difference_type = std::vector<Item>::difference_type;

    struct element { 
        // ... 
    };

    // V is value type, D is part of forward/reverse iterator control
    template <typename V, int D> struct iterator_ {

        using iterator_category = std::random_access_iterator_tag;
        using value_type = V;
        using reference = V &;
        using pointer = V *;
        using difference_type = my_container::difference_type;

        iterator_ (); // custom
        iterator_ (const iterator_<V,D> &) = default;
        iterator_ (iterator_<V,D> &&) = default;
        ~iterator_ () = default;

        iterator_<V,D> & operator = (const iterator_<V,D> &) = default;
        iterator_<V,D> & operator = (iterator_<V,D> &&) = default;

        bool operator == (const iterator_<V,D> &) const;

        // ...

    };

    using iterator = iterator_<element, 1>;
    using const_iterator = iterator_<const element, 1>;
    using reverse_iterator = iterator_<element, -1>;
    using const_reverse_iterator = iterator_<const element, -1>;

    iterator begin ();
    iterator end ();
    const_iterator cbegin () const;
    const_iterator cend () const;

    reverse_iterator rbegin ();
    reverse_iterator rend ();
    const_reverse_iterator crbegin () const;
    const_reverse_iterator crend () const;

};

Now, I'm looking at the operational semantics of begin, end, cbegin and cend (where a is a my_container, and C is its type):

expression return type semantics
a.begin() (const_)iterator iterator to the first element of a
a.end() (const_)iterator iterator to one past the last element of a
a.cbegin() const_iterator const_cast<const C&>(a).begin()
a.cend() const_iterator const_cast<const C&>(a).end()

And the problem with my current implementation is that this expression, derived from the cbegin (and likewise cend), is invalid:

a.cbegin() == const_cast<const my_container&>(a).begin()

Because my iterator and const_iterator types are incompatible due to the const being wrapped up in the iterator type via the template parameters to iterator_, and also because my begin() is not const. And now I'm getting that sinking feeling that I have a fundamental flaw in my implementation.

The second problem with my current implementation is that the requirements list the return type of begin and end as "(const_)iterator", and I am only just noticing the "(const_)" now. However, my begin and end do not return a const_iterator.

My conclusion, then, is that my implementation does not meet the operational semantics requirements of Container, and is therefore invalid in its current form. And now I'm sad. :(

So, I'm confused about:

  • General compatibility requirements of iterator and const_iterator.
  • The cv-qualifiers on the declaration of begin() and end().

And my questions are:

  1. Am I correct in my conclusion that my container currently fails to meet the requirements of Container wrt. begin, end, cbegin, and cend?
  2. Do the iterator and const_iterator types need to be equality comparable with each other?
  3. Does const_iterator need to be copy constructible and assignable from an iterator?
  4. Do begin() and end() have to be declared as const?
  5. Did I make a mistake in wrapping up the const in iterator_::value_type?
  6. What does "(const_)iterator" mean for the return type of begin and end?

I realize that looks like a lot of questions but they all sort of boil down to the single question of what the requirements for interoperability between iterator and const_iterator are. I hope this post makes sense.

c++17 const-correctness iterator containers c++
1 Answers
iterator begin ();
iterator end ();
const_iterator begin () const;
const_iterator end () const;
const_iterator cbegin () const;
const_iterator cend () const;

And yes, const_iterator it = iterator; should work (but not the other way around), as should == (I am not certain the first is mandated, but you should still do it).

Also consider writing SCARY iterators, where the iterator is not a subtype of the container.

template<class T>
struct foo {
   template<class U, std::enable_if_t<std::is_same_v<std::remove_cv_t<U>, std::remove_cv_t<T>>,bool> =true>
   friend bool operator==( foo const& lhs, foo<U> const& rhs );
};

This is an example of a == that works between types.

user_17746670
Related