STL-совместимые итераторы для пользовательских контейнеров

У меня есть пользовательский контейнер, который я использую в течение многих лет без проблем. Недавно я узнал, что если я определяю итераторы для своего контейнера, я могу эффективно использовать все алгоритмы, определенные в <algorithm>. Не только это, кажется, что упорная библиотека (в основном думает версия CUDA для STL для графических процессоров Nvidia) сильно использует итераторы, и я надеюсь, что, используя их, я смогу для использования этой библиотеки.

В любом случае, так как это моя первая попытка написать собственные итераторы, я подумал, что я размещаю то, что у меня здесь, чтобы попросить дополнительную помощь и убедиться, что я прав. Итак, я написал небольшой класс массива, который поддерживает классы iterator и const_iterator. Я запускал свой класс с множеством различных алгоритмов STL, и все, кажется, работают нормально, но это не обязательно означает, что у меня все в порядке! В частности, есть ли какой-нибудь оператор, которого я пропустил для своих итераторов? Я определил лишние ненужные? Кроме того, поскольку большинство iterator и const_iterator выглядят одинаково, существует ли способ предотвратить дублирование?

Я открыт для предложений и улучшений:)

Пример в реальном времени: 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; }

Ответы

Ответ 1

boost iterator обеспечивает структуру для создания итераторов, соответствующих стандарту STL, и адаптации существующих.

Это позволяет вам сосредоточиться на функциональности и генерировать все необходимые черты, typedefs для вас.

iterator и const_iterator создание без особого дублирования кода поддерживается.

Ответ 2

Boost iterator_adaptor может значительно упростить ваш код. документация имеет, например, этот пример для итератора связанного списка

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(); }
};

Обратите внимание, что в примере представлен только конструктор по умолчанию, конструктор с указателем node, обобщенный конструктор копирования, который принимает только элементы, которые могут быть преобразованы в указатель node, и функцию приращения. Инкрементная функция представляет собой деталь реализации, которая совместно используется как operator++(), так и operator++(int).

Вся другая котельная плита автоматически генерируется путем получения boost::iterator_adaptor. Это включает в себя все вложенные typedef, которые вы также можете получить из std::iterator, а также все перегруженные операторы (++, *, → , ==,! =, Advance) и все остальное, чтобы сделать это полностью стандартный итератор.

Передавая Value const* и используя typedef, вы можете определить const_iterator, который повторно использует весь ваш код с соответствующими изменениями. Изучение примера теперь значительно сэкономит вам дорогу.