STL-compatible iterators for custom containers

Question

I have a custom container that I have been using for many years without issues. Recently I found out that if I define iterators for my container, I can effectively use all of the algorithms defined in <algorithm>. Not only that, it seems that thrust library (basically think CUDA version of STL for Nvidia GPUs) heavily uses iterators and I am hoping that by using them I'll be able to use that library as well.

Anyway, since this is my first try at writing my own iterators, I thought I post what I have here to ask for further assistance and make sure what I'm doing is right. So, I wrote a little array class that supports both iterator and const_iterator classes. I ran my class with a bunch of different STL algorithms and all seem to work fine but that does not necessarily mean I've got everything right! In particular, is there any operator that I miss for my iterators? Have I defined extra unnecessary ones? Also, since most of iterator and const_iterator look similar, is there a way to prevent duplication?

I'm open to suggestions and improvements :)

Live example: http://ideone.com/7YdiQY

#include <cstddef>
#include <iostream>
#include <iterator>
#include <algorithm>

template<typename T>
class my_array{
    T* data_;
    std::size_t size_;

public:

    // ---------------------------------
    // Forward declaration
    // ---------------------------------
    class const_iterator;

    // ---------------------------------
    // iterator class
    // ---------------------------------
    class iterator: public std::iterator<std::random_access_iterator_tag, T>
    {
    public:
        iterator(): p_(NULL) {}
        iterator(T* p): p_(p) {}
        iterator(const iterator& other): p_(other.p_) {}
        const iterator& operator=(const iterator& other) {p_ = other.p_; return other;}

        iterator& operator++()    {p_++; return *this;} // prefix++
        iterator  operator++(int) {iterator tmp(*this); ++(*this); return tmp;} // postfix++
        iterator& operator--()    {p_--; return *this;} // prefix--
        iterator  operator--(int) {iterator tmp(*this); --(*this); return tmp;} // postfix--

        void     operator+=(const std::size_t& n)  {p_ += n;}
        void     operator+=(const iterator& other) {p_ += other.p_;}
        iterator operator+ (const std::size_t& n)  {iterator tmp(*this); tmp += n; return tmp;}
        iterator operator+ (const iterator& other) {iterator tmp(*this); tmp += other; return tmp;}

        void        operator-=(const std::size_t& n)  {p_ -= n;}
        void        operator-=(const iterator& other) {p_ -= other.p_;}
        iterator    operator- (const std::size_t& n)  {iterator tmp(*this); tmp -= n; return tmp;}
        std::size_t operator- (const iterator& other) {return p_ - other.p_;}

        bool operator< (const iterator& other) {return (p_-other.p_)< 0;}
        bool operator<=(const iterator& other) {return (p_-other.p_)<=0;}
        bool operator> (const iterator& other) {return (p_-other.p_)> 0;}
        bool operator>=(const iterator& other) {return (p_-other.p_)>=0;}
        bool operator==(const iterator& other) {return  p_ == other.p_; }
        bool operator!=(const iterator& other) {return  p_ != other.p_; }

        T& operator[](const int& n) {return *(p_+n);}
        T& operator*() {return *p_;}
        T* operator->(){return  p_;}

    private:
        T* p_;

        friend class const_iterator;
    };

    // ---------------------------------
    // const_iterator class
    // ---------------------------------
    class const_iterator: public std::iterator<std::random_access_iterator_tag, T>
    {
    public:
        const_iterator(): p_(NULL) {}
        const_iterator(const T* p): p_(p) {}
        const_iterator(const iterator& other): p_(other.p_) {}
        const_iterator(const const_iterator& other): p_(other.p_) {}
        const const_iterator& operator=(const const_iterator& other) {p_ = other.p_; return other;}
        const const_iterator& operator=(const iterator& other) {p_ = other.p_; return other;}

        const_iterator& operator++()    {p_++; return *this;} // prefix++
        const_iterator  operator++(int) {const_iterator tmp(*this); ++(*this); return tmp;} // postfix++
        const_iterator& operator--()    {p_--; return *this;} // prefix--
        const_iterator  operator--(int) {const_iterator tmp(*this); --(*this); return tmp;} // postfix--

        void           operator+=(const std::size_t& n)              {p_ += n;}
        void           operator+=(const const_iterator& other)       {p_ += other.p_;}
        const_iterator operator+ (const std::size_t& n)        const {const_iterator tmp(*this); tmp += n; return tmp;}
        const_iterator operator+ (const const_iterator& other) const {const_iterator tmp(*this); tmp += other; return tmp;}

        void           operator-=(const std::size_t& n)              {p_ -= n;}
        void           operator-=(const const_iterator& other)       {p_ -= other.p_;}
        const_iterator operator- (const std::size_t& n)        const {const_iterator tmp(*this); tmp -= n; return tmp;}
        std::size_t    operator- (const const_iterator& other) const {return p_ - other.p_;}

        bool operator< (const const_iterator& other) const {return (p_-other.p_)< 0;}
        bool operator<=(const const_iterator& other) const {return (p_-other.p_)<=0;}
        bool operator> (const const_iterator& other) const {return (p_-other.p_)> 0;}
        bool operator>=(const const_iterator& other) const {return (p_-other.p_)>=0;}
        bool operator==(const const_iterator& other) const {return  p_ == other.p_; }
        bool operator!=(const const_iterator& other) const {return  p_ != other.p_; }

        const T& operator[](const int& n) const {return *(p_+n);}
        const T& operator*()  const {return *p_;}
        const T* operator->() const {return  p_;}

    private:
        const T* p_;
    };

    my_array()
        : data_(NULL), size_(0)
    {}
    my_array(std::size_t size)
        : data_(new T[size]), size_(size)
    {}
    my_array(const my_array<T>& other){
        size_ = other.size_;
        data_ = new T[size_];
        for (std::size_t i = 0; i<size_; i++)
            data_[i] = other.data_[i];
    }
    my_array(const const_iterator& first, const const_iterator& last){
        size_ = last - first;
        data_ = new T[size_];

        for (std::size_t i = 0; i<size_; i++)
            data_[i] = first[i];
    }

    ~my_array(){
        delete [] data_;
    }
    const my_array<T>& operator=(const my_array<T>& other){
        size_ = other.size_;
        data_ = new T[size_];
        for (std::size_t i = 0; i<size_; i++)
            data_[i] = other.data_[i];
        return other;
    }
    const T& operator[](std::size_t idx) const {return data_[idx];}
    T& operator[](std::size_t& idx) {return data_[idx];}
    std::size_t size(){return size_;}

    iterator begin(){ return iterator(data_); }
    iterator end()  { return iterator(data_+size_); }
    const_iterator begin() const{ return const_iterator(data_); }
    const_iterator end() const  { return const_iterator(data_+size_);}
};

template<typename T>
void print(T t) {
    std::cout << t << std::endl;
}

int main(){

    // works!
    int list [] = {1, 3, 5, 2, 4, 3, 5, 10, 10};
    my_array<int> a(list, list+sizeof(list)/sizeof(int));

    // works!
    for (my_array<int>::const_iterator it = a.begin(), end = a.end();
         it != end; ++it)
        std::cout << ' ' << *it;
    std::cout << std::endl;

    // works!
    std::for_each(a.begin(), a.end(), print<int>);
    std::cout << std::endl;

    // works!
    my_array<int> b(a.size());
    std::copy(a.begin(), a.end(), b.begin());

    // works!
    my_array<int>::iterator end = std::remove(a.begin(), a.end(), 5);
    std::for_each(a.begin(), end, print<int>);
    std::cout << std::endl;

    // works!
    std::random_shuffle(a.begin(), end);
    std::for_each(a.begin(), end, print<int>);
    std::cout << std::endl;

    // works!
    std::cout << "Counts of 3 in array = " << std::count(a.begin(), end, 3) << std::endl << std::endl;

    // works!
    std::sort(a.begin(), end);
    std::for_each(a.begin(), end, print<int>);
    std::cout << std::endl;

    // works!
    if (!std::binary_search(a.begin(), a.end(), 5))
        std::cout << "Removed!" << std::endl;

    return 0;
}

Answer 1

boost iterator provides a framework to create stl-compliant iterators and to adapt existing ones.

It allows you to focus on the functionality and generates all necessary traits, typedefs for you.

iterator and const_iterator creation without much code-duplication is supported as well.

Answer 2

The Boost iterator_adaptor can greatly simplify your code. The documentation has e.g. this example for a linked list iterator

template <class Value>
class node_iter
  : public boost::iterator_adaptor<
        node_iter<Value>                // Derived
      , Value*                          // Base
      , boost::use_default              // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    node_iter()
      : node_iter::iterator_adaptor_(0) {}

    explicit node_iter(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    template <class OtherValue>
    node_iter(
        node_iter<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue*,Value*>
          , enabler
        >::type = enabler()
    )
      : node_iter::iterator_adaptor_(other.base()) {}

 private:
    friend class boost::iterator_core_access;
    void increment() { this->base_reference() = this->base()->next(); }
};

Note that the example only provides a default constructor, a constructor taking a node pointer, a generalized copy constructor that only accepts elements that can be converted to a node pointer, and an increment function. The increment function is an implementation detail that is shared by both operator++() and operator++(int).

All the other boiler-plate is automatically being generated by deriving from boost::iterator_adaptor. That includes all the nested typedef that you could also get from deriving from std::iterator, as well as all the overloaded operators (++, *, ->, ==, !=, advance) and anything else to make it a fully Standard conforming iterator.

By passing a Value const* and using a typedef you can define a const_iterator that reuses all your code with the appropriate modifications. Studying the example now will save you enormously down the road.