Iteratory kompatybilne ze standardem STL dla niestandardowych pojemników

Question

Mam niestandardowy pojemnik, z którego korzystam od wielu lat bez problemów. Niedawno dowiedziałem się, że jeśli zdefiniuję iteratory dla mojego kontenera, będę mógł efektywnie używać wszystkich algorytmów zdefiniowanych w <algorithm>. Nie tylko to, wydaje się, że thrust library (w zasadzie myślę, że wersja CUDA dla procesorów graficznych Nvidia) intensywnie używa iteratorów i mam nadzieję, że korzystając z nich, będę mógł również użyć tej biblioteki.

W każdym razie, ponieważ jest to moja pierwsza próba napisania własnych iteratorów, pomyślałem, że opublikuję to, co mam tutaj, aby poprosić o dalszą pomoc i upewnić się, że to, co robię, jest właściwe. Napisałem więc małą klasę tablicową, która obsługuje klasy iterator i const_iterator. Prowadziłem moją klasę z wieloma różnymi algorytmami STL i wszystko wydaje się działać dobrze, ale to niekoniecznie oznacza, że ​​wszystko jest w porządku! W szczególności, czy jest jakiś operator, którego brakuje mi do moich iteratorów? Czy zdefiniowałem dodatkowe niepotrzebne? Ponadto, ponieważ większość modeli iterator i const_iterator wygląda podobnie, czy istnieje sposób zapobiegania duplikacji?

Jestem otwarty na sugestie i ulepszeń :)

żywo Przykład: 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 zapewnia ramy do tworzenia STL zgodny iteratory i przystosowania istniejących.

Pozwala skupić się na funkcjonalności i generuje wszystkie niezbędne cechy, typowane dla Ciebie.

iterator i const_iterator tworzenie bez większego duplikowania kodu jest również obsługiwane.

Answer 2

Zwiększenie wartości iterator_adaptor może znacznie uprościć kod. Model documentation ma np. Ten przykład dla połączonej listy 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(); } 
}; 

Uwaga że przykład zapewnia tylko konstruktor domyślny, konstruktor biorąc wskaźnik węzła uogólnioną konstruktor kopiujący, który akceptuje tylko elementy, które mogą być zamienione na wskaźnik węzła, oraz funkcja zwiększania. Funkcja inkrementacji jest szczegółem implementacji udostępnianym zarówno przez operator++(), jak i operator++(int).

Wszystkie pozostałe płyty kotła są automatycznie generowane przez parametry pochodzące z boost::iterator_adaptor. Obejmuje to wszystkie zagnieżdżone typedef, które można również uzyskać wywodząc z std::iterator, a także wszystkie przeciążone operatory (++, *, ->, ==,! =, Awans) i wszystko inne, aby uczynić go w pełni zgodnym ze standardem iterator.

Po podaniu Value const* i użyciu typedef można zdefiniować const_iterator, który ponownie wykorzystuje cały kod z odpowiednimi modyfikacjami. Przestudiowanie tego przykładu pozwoli Ci znacznie zaoszczędzić na drodze.