C++?反向迭代器模擬實(shí)現(xiàn)

更新時間：2024年01月26日 12:01:45 作者：樊梓慕

反向迭代器reverse_iterator是一種反向遍歷容器的迭代器,也就是從最后一個元素到第一個元素遍歷容器,本文主要介紹了C++?反向迭代器模擬實(shí)現(xiàn),感興趣的可以了解一下

前言

之前我們已經(jīng)模擬實(shí)現(xiàn)過vector、list等容器，但其中我們僅實(shí)現(xiàn)了普通迭代器與const迭代器，今天我們就來學(xué)習(xí)下反向迭代器的實(shí)現(xiàn)。

1.利用適配器的思想

我們知道stack、queue等不稱為容器，而被稱作『適配器』，因?yàn)樗麄兊牡讓邮侨萜鱠eque，即只需要利用deque這個結(jié)構(gòu)來滿足stack、queue的特性，此時stack和queue就是一種適配器。

那反向迭代器是不是就是普通迭代器的一種適配呢？

反向迭代器需不需要我們從零開始寫呢？還是和適配器一樣，利用普通迭代器的結(jié)構(gòu)滿足反向迭代器的特性即可？這樣是不是比較方便？

rbegin()相當(dāng)于end()
rend()相當(dāng)于begin()
反向迭代器++相當(dāng)于正向迭代器--
其他操作* != ->和正向迭代器相同

那么我們再拔高一層：

每一種容器或適配器都要實(shí)現(xiàn)自己的反向迭代器，如果是這樣的話代碼會不會太冗余了，因?yàn)樗麄兊姆聪虻鞯倪壿嫸际窍嗤摹?/p>

所以我們可以利用模板參數(shù)、泛型來通過傳遞不同的模板參數(shù)來讓編譯器自己推演出對應(yīng)容器或適配器的反向迭代器即可。

反向迭代器類：

template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
    typedef ReverseIterator<Iterator, Ref, Ptr> Self;

    Iterator cur;

    ReverseIterator(Iterator it)
        :cur(it)
    {}

    Self& operator++()//前置++
    {
        --cur;
        return *this;
    }

    Self operator++(int)//后置++
    {
        Iterator tmp = cur;
        --cur;
        return tmp;
    }

    Self& operator--()//前置--
    {
        ++cur;
        return *this;
    }

    Self operator--(int)//后置--
    {
        Iterator tmp = cur;
        ++cur;
        return tmp;
    }

    Ref operator*()//解引用
    {
        Iterator tmp = cur;
        --tmp;
        return *tmp;
    }

    Ptr operator->()
    {
        return &(operator*());
    }

    bool operator!=(const Self& s)
    {
        return cur != s.cur;
    }

    bool operator==(const Self& s)
    {
        return cur == s.cur;
    }

};

2.有關(guān)operator*注意

為了其對稱性，使得rbegin()等價于end()，rend()等價于begin()。

但由于end是指向最后一個元素的『下一個位置』，而rbegin由end適配得到，所以反向迭代器中的operator*()不是返回迭代器的當(dāng)前位置的數(shù)據(jù)，而是返回迭代器當(dāng)前位置的『前一個位置』的數(shù)據(jù)。

即如果我們需要返回當(dāng)前位置的數(shù)據(jù)，可以將rbegin()由--end(),rend()由--begin()進(jìn)行適配即可。

3.利用vector來舉例說明

template<class T>
class vector
{
public:
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
    typedef ReverseIterator<const_iterator, T&, T*> const_reverse_iterator;

    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

    iterator begin()
    {
        return _start;
    }
    iterator end()
    {
        return _finish;
    }
    const_iterator begin() const
    {
        return _start;
    }
    const_iterator end() const
    {
        return _finish;
    }

    vector(){}
    vector(const vector<T>& v);
    template <class InputIterator>
    vector(InputIterator first, InputIterator last);
    vector(size_t n, const T& val = T());
    vector(int n, const T& val = T());
    vector<T>& operator= (vector<T> v);
    ~vector();
    size_t size() const;
    size_t capacity() const;
    void reserve(size_t n);
    void resize(size_t n, const T& val = T());
    T& operator[](size_t pos);
    const T& operator[](size_t pos)const;
    void push_back(const T& x);
    void pop_back();
    void swap(vector<T>& v);
    iterator insert(iterator pos, const T& x);
    iterator erase(iterator pos);
private:
    iterator _start = nullptr; // 指向數(shù)據(jù)塊的開始
    iterator _finish = nullptr; // 指向有效數(shù)據(jù)的尾
    iterator _endOfStorage = nullptr; // 指向存儲容量的尾
};

如圖：根據(jù)模板參數(shù)int和reverse_iterator可以推演出該反向迭代器的各個模板參數(shù)類型，在反向迭代器類中寫一個構(gòu)造函數(shù)，該構(gòu)造函數(shù)就是利用的適配器思想，將普通迭代器iterator傳遞給反向迭代器ReverseIterator，然后利用普通迭代器iterator的++或--方法實(shí)現(xiàn)反向迭代器。

同樣的類比到List中：