Writing STL as an Iterator

Question

I tried to learn to write stl as iterators, because I wrote a simple circular array and added an iterator to it. Please look at the bottom of the code to see the problem.

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

When I compile the part does not work, g ++ unloads the following error

 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] 

part of the work compiles easily when compiled without work. Can someone explain to me what happened.

Answer 1

I think the problem is in these lines:

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

The problem here is that these functions accept lvalue references to their arguments. This means that if you try to pass an rvalue (for example, a temporary object returned by a function) into these statements, you will get a compile-time error because the links cannot bind to temporary ones. To fix this, change the arguments as const references:

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

Since const links can bind to temporary ones or have their arguments by value:

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

Whichever choice you choose, you should probably mention these const functions because they do not mutate the recipient object.

Hope this helps!

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

the code works. find the XXX sign;)

Answer 3

When writing iterators for custom containers, it might be useful for you to use boost :: iterator_facade . This is a library that allows you to define only the basic operations of your iterator (increment, dereference and comparison of equality and, if applicable, decrease and advance) and fills in the blanks for you, providing all the necessary operators. Here's what your iterator looks like with 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 indicates iterator traversal - this means that you can use the iterator only to move the container in the forward direction and only go through one element at a time.