寫迭代器的STL

Question

我正在嘗試學習寫迭代器的stl，爲此我編寫了一個簡單的循環數組並添加了一個迭代器。請查看代碼的底部以查看問題。當編譯不起作用部分

template<typename T, int N> 
class RingQueue{ 
    T * _marray; 
    int _mbegin; 
    int _msize; 
public: 
    RingQueue(){ 
     _marray = new T[N]; 
     _mbegin = 0; 
     _msize= 0; 
    } 
    void push_back(const T& val){ 
     if(_msize!=N){ 
      _marray[(_mbegin+_msize)%N] = val; 
      _msize++; 
     } 
     else 
      throw "Queue Full"; 
    } 
    T pop_front(){ 
     if(_msize!=0){ 
      T&val = _marray[_mbegin]; 
      _mbegin = (_mbegin+1)%N; 
      _msize--; 
      return val; 
     } 
     else 
      throw "Queue Empty"; 
    } 

    class iterator{ 
     RingQueue<T,N>* _container; 
     int _idx; 
     public: 
     iterator(RingQueue<T,N>* container,int idx):_container(container){ 
      _idx = idx; 
     } 

     bool operator==(iterator &rhs){ 
      return (this->_container==rhs._container && this->_idx == rhs._idx); 
     } 
     bool operator!=(iterator &rhs){ 
      return !(*this==rhs); 
     } 
     T operator*(){ 
      if(_container->_msize>0&&_idx<_container->_msize){ 
       return _container->_marray[(_container->_mbegin+_idx)%N]; 
      } 
     } 

     iterator& operator++(){ 
      if(_container->_msize ==0){ 
       *this = _container->end(); 
       return *this; 
      } 
      if(_idx==_container->_msize){ 
       *this = _container->end(); 
       return *this; 
      } 
      _idx++; 
      return *this; 
     } 
    }; 
    iterator begin(){ 
     return iterator(this,0); 
    } 
    iterator end(){ 
     return iterator(this,_msize); 
    } 
}; 
int current=0; 
int gen(){ 
    return current++; 
} 

int curr_op=0; 
int operation(){ 
    return 2*(curr_op++&1)-1; 
} 
int main(){ 
    RingQueue<int,10> ring; 
    vector<int> v(9),op(9); 
    generate(v.begin(),v.end(),gen); 
    random_shuffle(v.begin(),v.end()); 
    copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));  
    cout<<endl; 

    generate(op.begin(),op.end(),operation);   
    random_shuffle(op.begin(),op.end()); 
    // copy(op.begin(),op.end(),ostream_iterator<int>(cout," ")); 
    cout<<endl; 

    for(vector<int>::iterator itv = v.begin();itv!=v.end();itv++){ 
     try{ 
      ring.push_back(*itv); 
     }catch(const char * e){ 
      cout<<*itv<<e<<endl; 
     } 
    } 
    //works 
    RingQueue<int,10>::iterator ite = ring.end(); 
    for(RingQueue<int,10>::iterator it = ring.begin(); it!=ite; ++it){ 
     cout<<*it<<endl; 
    } 
    // doesn't work 
    for(RingQueue<int,10>::iterator it = ring.begin(); it!=ring.end(); ++it){ 
     cout<<*it<<endl; 
    } 
    return 0; 
} 

當我編譯不工作的一部分，G ++轉儲以下錯誤

ringqueue.cpp: In function ‘int main()’: 
ringqueue.cpp:112: error: no match for ‘operator!=’ in ‘it != ring.RingQueue<T, N>::end [with T = int, int N = 10]()’ 
ringqueue.cpp:48: note: candidates are: bool RingQueue<T, N>::iterator::operator!=(RingQueue<T, N>::iterator&) [with T = int, int N = 10] 

作品部分無縫編譯。有人可以解釋我有什麼不對。

Answer 1

我認爲這個問題是在這些線路：

bool operator==(iterator &rhs){ 
     return (this->_container==rhs._container && this->_idx == rhs._idx); 
    } 
    bool operator!=(iterator &rhs){ 
     return !(*this==rhs); 
    } 

的這裏的問題是，這些功能在拿自己的論點左值引用。這意味着如果您嘗試將右值（例如，從函數返回的臨時對象）傳遞給這些運算符，您將收到編譯時錯誤，因爲引用無法綁定到臨時對象。爲了解決這個問題，可以更改的參數爲const引用：

bool operator==(const iterator &rhs){ 
     return (this->_container==rhs._container && this->_idx == rhs._idx); 
    } 
    bool operator!=(const iterator &rhs){ 
     return !(*this==rhs); 
    } 

由於const的引用可以綁定到臨時對象，或讓他們把他們的論據值：

bool operator==(iterator rhs){ 
     return (this->_container==rhs._container && this->_idx == rhs._idx); 
    } 
    bool operator!=(iterator rhs){ 
     return !(*this==rhs); 
    } 

你無論作何選擇，你應該標記這些函數const，因爲它們不會突變接收者對象。

希望這會有所幫助！

Answer 2

#include <vector> 
#include <iostream> 
#include <sstream> 
#include <iterator> 
using namespace std; 

template<typename T, int N> 
class RingQueue{ 
    T * _marray; 
    int _mbegin; 
    int _msize; 
public: 
    RingQueue(){ 
     _marray = new T[N]; 
     _mbegin = 0; 
     _msize= 0; 
    } 
    void push_back(const T& val){ 
     if(_msize!=N){ 
      _marray[(_mbegin+_msize)%N] = val; 
      _msize++; 
     } 
     else 
      throw "Queue Full"; 
    } 
    T pop_front(){ 
     if(_msize!=0){ 
      T&val = _marray[_mbegin]; 
      _mbegin = (_mbegin+1)%N; 
      _msize--; 
      return val; 
     } 
     else 
      throw "Queue Empty"; 
    } 

    class iterator{ 
     RingQueue<T,N>* _container; 
     int _idx; 
     public: 
     iterator(RingQueue<T,N>* container,int idx):_container(container){ 
      _idx = idx; 
     } 

     bool operator==(iterator rhs){ // XXX do not pass it as a reference 
      return (this->_container==rhs._container && this->_idx == rhs._idx); 
     } 
     bool operator!=(iterator rhs){ // XXX do not pass it as a reference 
      return !(*this==rhs); 
     } 
     T operator*(){ 
      if(_container->_msize>0&&_idx<_container->_msize){ 
       return _container->_marray[(_container->_mbegin+_idx)%N]; 
      } 
      throw "XXX"; // XXX missing return statement 
     } 

     iterator& operator++(){ 
      if(_container->_msize ==0){ 
       *this = _container->end(); 
       return *this; 
      } 
      if(_idx==_container->_msize){ 
       *this = _container->end(); 
       return *this; 
      } 
      _idx++; 
      return *this; 
     } 
    }; 
    iterator begin(){ 
     return iterator(this,0); 
    } 
    iterator end(){ 
     return iterator(this,_msize); 
    } 
}; 
int current=0; 
int gen(){ 
    return current++; 
} 

int curr_op=0; 
int operation(){ 
    return 2*(curr_op++&1)-1; 
} 
int main(){ 
    RingQueue<int,10> ring; 
    vector<int> v(9),op(9); 
    generate(v.begin(),v.end(),gen); 
    random_shuffle(v.begin(),v.end()); 
    copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));  
    cout<<endl; 

    generate(op.begin(),op.end(),operation);   
    random_shuffle(op.begin(),op.end()); 
    // copy(op.begin(),op.end(),ostream_iterator<int>(cout," ")); 
    cout<<endl; 

    for(vector<int>::iterator itv = v.begin();itv!=v.end();itv++){ 
     try{ 
      ring.push_back(*itv); 
     }catch(const char * e){ 
      cout<<*itv<<e<<endl; 
     } 
    } 
    for(RingQueue<int,10>::iterator it = ring.begin(); it!=ring.end(); ++it){ 
     cout<<*it<<endl; 
    } 
    return 0; 
} 

該代碼正在工作。尋找XXX標記;）

Answer 3

爲自定義容器編寫迭代器時，可能會發現使用boost::iterator_facade會很有幫助。它是一個庫，它允許你定義你的迭代器的基本操作（增量，取消引用和相等比較，如果適用的話，遞減和提前），並通過提供所有必需的操作符爲你填空。這裏是你的迭代會是什麼樣使用boost :: iterator_facade：

class iterator : public boost::iterator_facade<iterator, T, boost::forward_traversal_tag>{ 
    RingQueue<T,N>* _container; 
    int _idx; 
public: 
    iterator(RingQueue<T,N>* container,int idx):_container(container){ 
     _idx = idx; 
    } 

    bool equal(const iterator &rhs) const { 
     return (this->_container==rhs._container && this->_idx == rhs._idx); 
    } 

    T dereference() const { 
     if(_container->_msize>0&&_idx<_container->_msize){ 
      return _container->_marray[(_container->_mbegin+_idx)%N]; 
     } 
    } 

    void increment(){ 
     if(_container->_msize ==0) 
      *this = _container->end(); 
     else if(_idx==_container->_msize) 
      *this = _container->end(); 
     else 
      _idx++; 
    } 
}; 

boost::forward_traversal_tag指定迭代器遍歷 - 這意味着你只能使用迭代器遍歷容器中的前進方向，並在同一時間只有一個元素步進。