c++ - イテレータ風に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イテレータトラバーサルを指定します。これは、イテレータを使用してコンテナーを順方向にトラバースし、一度に 1 つの要素だけをステップ実行できることを意味します。