what is the preferred way to expose custom STL-style iteration?

Question

(also see Is there a good way not to hand-write all twelve required Container functions for a custom type in C++? )

---

For a class such as

namespace JDanielSmith {
class C
{
    const size_t _size;
    const std::unique_ptr<int[]> _data;

public:
    C(size_t size) : _size(size), _data(new int[size]) {}

    inline const int* get() const noexcept { return _data.get(); }
    inline int* get() noexcept { return _data.get(); }

    size_t size() const noexcept { return _size; }
};
}

what is the preferred way to expose iteration? Should I write begin()/end() (and cbegin()/cend()) member functions?

const int* cbegin() const {
    return get();
}
const int* cend() const {
    return cbegin() + size();
}

or should these be non-member functions?

const int* cbegin(const C& c) {
    return c.get();
}
const int* cend(const C& c) {
    return cbegin(c) + c.size();
}

Should begin()/end() have both const and non-const overloads?

    const int* begin() const {
        return get();
    }
    int* begin() {
        return get();
    }

Are there any other things to consider? Are there tools/techniques to make this "easy to get right" and reduce the amount of boiler-plate code?

---

Some related questions/discussion include:

• Should custom containers have free begin/end functions?
• Why use non-member begin and end functions in C++11?
• When to use std::begin and std::end instead of container specific versions

Answer 1

There is a standard which describes what your class interfaces should look like if you want them to be congruent with the STL. C++ has this notion of 'concepts' which pin down the requirements for a given class to be a sufficient implementation of a concept. This almost became a language feature in c++11.

A concept you may be interested in is the Container concept. As you can see, in order to meet the requirements of the Container concept, you need begin, cbegin, end, and cend as member functions (among other things).

Since it looks like you're storing your data in an array, you might also be interested in SequenceContainer.

Answer 2

I'll take option C.

The main problem here is that std::begin() doesn't actually work for finding non-member begin() with ADL. So the real solution is to write your own that does:

namespace details {
    using std::begin;

    template <class C>
    constexpr auto adl_begin(C& c) noexcept(noexcept(begin(c)))
        -> decltype(begin(c))
    {
        return begin(c);
    }
}

using details::adl_begin;

Now, it doesn't matter if you write your begin() as a member or non-member function, just use adl_begin(x) everywhere and it'll just work. As well as for both the standard containers and raw arrays. This conveniently side-steps the member vs. non-member discussion.

---

And yes, you should have const and non-const overloads of begin() and friends, if you want to expose const and non-const access.

Answer 3

I suggest creating both sets of functions -- member functions as well as non-member functions -- to allow for maximum flexibility.

namespace JDanielSmith {
   class C
   {
      const size_t _size;
      const std::unique_ptr<int[]> _data;

      public:
      C(size_t size) : _size(size), _data(new int[size]) {}

      inline const int* get() const { return _data.get(); }
      inline int* get() { return _data.get(); }

      size_t size() const { return _size; }

      int* begin() { return get(); }
      int* end() { return get() + _size; }
      const int* begin() const { return get(); }
      const int* end() const { return get() + _size; }
      const int* cbegin() const { return get(); }
      const int* cend() const { return get() + _size; }

   };

   int* begin(C& c) { return c.begin(); }
   int* end(C& c) { return c.end(); }
   const int* begin(C const& c) { return c.begin(); }
   const int* end(C const& c) { return c.end(); }
   const int* cbegin(C const& c) { return c.begin(); }
   const int* cend(C const& c) { return c.end(); }
}

The member functions are necessary if you want to be able to use objects of type C as arguments to std::begin, std::end, std::cbegin, and std::cend.

The non-member functions are necessary if you want to be able to use objects of type C as arguments to just begin, end, cbegin, and cend. ADL will make sure that the non-member functions will be found for such usages.

int main()
{
   JDanielSmith::C c1(10);

   {
      // Non-const member functions are found
      auto b = std::begin(c1);
      auto e = std::end(c1);
      for (int i = 0; b != e; ++b, ++i )
      {
         *b = i*10;
      }
   }

   JDanielSmith::C const& c2 = c1;
   {
      // Const member functions are found
      auto b = std::begin(c2);
      auto e = std::end(c2);
      for ( ; b != e; ++b )
      {
         std::cout << *b << std::endl;
      }
   }

   {
      // Non-member functions with const-objects as argument are found
      auto b = begin(c2);
      auto e = end(c2);
      for ( ; b != e; ++b )
      {
         std::cout << *b << std::endl;
      }
   }
}

Answer 4

In order to create a valid iterator, you must ensure that std::iterator_traits is valid. This means you must set the iterator category among other things.

An iterator should implement iterator(), iterator(iterator&&), iterator(iterator const&), operator==, operator !=, operator++, operator++(int), operator*, operator=, and operator->. It's also a good idea to add operator< and operator+ if you can (you can't always, e.g. linked lists.)

template <typename T>
class foo
{
public:

  using value_type = T;
  class iterator 
  { 
  public:
    using value_type = foo::value_type;
    using iterator_category = std::random_access_iterator_tag;
    // or whatever type of iterator you have...
    using pointer = value_type*;
    using reference = value_type&;
    using difference_type = std::ptrdiff_t;

    // ... 
  };

  class const_iterator 
  {
    // ... 
  };

  iterator begin() { /*...*/ }
  iterator end() { /*...*/ }

  const_iterator cbegin() const { /*...*/ }
  const_iterator cend() const { /*...*/ }

  /* ... */
};

See: http://en.cppreference.com/w/cpp/iterator/iterator_traits for more information on what you need to make a valid iterator. (Note: You also need certain properties to be a valid "container", like .size())

Ideally you should use member functions for begin and end, but it's not required... you can also overload std::begin and std::end. If you don't know how to do that, I suggest you use member functions.

You should create begin() const and end() const, but it should be an alias for cbegin(), NEVER the same as begin()!