將std :: list擴展到循環列表

Question

我想實現一個基於std :: list的循環列表。我想從列表的好處中獲益，但添加了一個特定功能：其迭代器運算符++和 - 應跳過邊並且操作（插入/擦除）不得使現有迭代器失效。我處理模板的能力很弱，理解std容器對我來說是不可能的。因此，我需要你的幫助。現在我不那麼遠：D。對不起，但即使是衆多的帖子都不能幫助我。

編輯： 經過大量的工作，一個steeeep learnig曲線，從std :: list :: iterator繼承的失敗方法，短期的抑鬱症和低迴報你的方法（是的，你們都是對的）我終於做到了。受到所有競爭者的啓發，我現在可以發佈我所做的最後一次......大約12小時：D基本上你建議的是，但是有很好的小操作員。

#pragma once 
#include <list> 
using std::list; 

template<class T> 
class cyclic_iterator; 


template<class T> 
class cyclicList : public list<T> 
{ 
public: 
    typedef cyclic_iterator<T> cyclic_iterator; 

    cyclic_iterator cycbegin() 
    {// not the purpose, but needed for instanziation 
    return cyclic_iterator(*this, this->begin()); 
    } 

    cyclic_iterator cycend() 
    {// not the purpose, but needed for instanziation 
    return cyclic_iterator(*this, this->end()); 
    } 
}; 




template<class T> 
class cyclic_iterator 
{ 
    public: 
    // To hop over edges need to know the container 
    cyclic_iterator(){} 
    cyclic_iterator(typename list<T>::iterator i) 
    : mIter(i){} 
    cyclic_iterator(list<T> &c) 
    : mContainer(&c){} 
    cyclic_iterator(list<T> &c, typename list<T>::iterator i) 
    : mContainer(&c), mIter(i){} 

    cyclic_iterator<T>& operator=(typename list<T>::iterator i) 
    {// assign an interator 
    mIter = i; 
    return *this; 
    } 

    cyclic_iterator<T>& operator=(list<T> &c) 
    {// assign a container 
    mContainer = &c; 
    return *this; 
    } 

    bool operator==(const cyclic_iterator<T>& rVal) const 
    {// check for equality 
    return (this->mIter == rVal.mIter && this->mContainer == rVal.mContainer) ? true : false; 
    } 

    bool operator!=(const cyclic_iterator<T>& rVal) const 
    {// check for inequality 
    return !(this->operator==(rVal)); 
    } 

    cyclic_iterator<T>& operator++() 
    {// preincrement 
    ++mIter; 
    if (mIter == mContainer->end()) 
     { mIter = mContainer->begin(); } 
    return *this; 
    } 

    cyclic_iterator<T> operator++(int) 
    { // postincrement 
    cyclic_iterator<T> tmp = *this; 
    ++*this; 
    return tmp; 
    } 

    cyclic_iterator<T>& operator--() 
    {// predecrement 
    if (mIter == mContainer->begin()) 
     mIter = --mContainer->end(); 
    else --mIter; 
    return *this; 
    } 

    cyclic_iterator<T> operator--(int) 
    {// postdecrement 
    cyclic_iterator<T> tmp = *this; 
    --*this; 
    return tmp; 
    } 

    cyclic_iterator<T>& operator+=(int j) 
    {// hop j nodes forward 
    for (int i = 0; i < j; ++i) 
     ++(*this); 
    return *this; 
    } 

    cyclic_iterator<T>& operator-=(int j) 
    {// hop j nodes backwards 
    for (int i = 0; i < j; ++i) 
     --(*this); 
    return *this; 
    } 

    T& operator*() 
    { 
    return *mIter; 
    } 

    typename list<T>::iterator & getStdIterator() 
    { 
    return mIter; 
    } 

private: 
    list<T>*   mContainer; 
    typename list<T>::iterator mIter; 

}; 

Answer 1

難道你不能只是做一個不同的迭代器類型？

#include <iterator> 
#include <list> 

template <typename T, typename Alloc> 
struct cyclic_iterator 
: std::iterator<typename std::list<T, Alloc>::iterator::iterator_category, T> 
{ 
    typedef std::list<T, Alloc> list_type; 

    cyclic_iterator & operator++() 
    { 
     ++iter; 
     if (iter == container.end()) { iter = container.begin(); } 
     return *this; 
    } 

    T & operator*() { return *iter; } 

    cyclic_iterator(typename list_type::iterator it, list_type & l) 
    : iter(it) 
    , container(l) 
    { 
     if (it == container.end()) { it = container.begin(); } 
    } 

    // everything else 

private: 
    typename list_type::iterator iter; 
    list_type & container; 
}; 

在一名助手：

template <typename List> 
cyclic_iterator<typename List::value_type, typename List::allocator_type> 
make_cyclic_iterator(typename List::iterator it, List & l) 
{ 
    return cyclic_iterator<typename List::value_type, typename List::allocator_type>(it, l); 
} 

用法：

// goes round and round forever 

for (auto ci = make_cyclic_iterator(mylist.begin(), mylist); ; ++ci) 
{ 
    std::cout << *ci << std::endl; 
} 

（有一些修改，這個代碼可以作出對任何容器暴露begin/end工作迭代器）。

Answer 2

這是不可能的。迭代器和end元素的實現是特定於實現的，而不是可定製的。容器不是爲那種事情設計的，它會讓他們很難。你將不得不經歷自己實現這一點的痛苦。請記住，這會變得非常棘手，因爲循環列表沒有真正的過去式迭代器，迭代器也不能真正處理這種情況。一些圖書館有循環器概念來處理圓形結構。

注意：從標準容器繼承是一個壞主意。

Answer 3

當然，你可以使用std::list來實現它，但首先你應該將列表封裝在你的類中，而不是從它派生出來，其次你必須實現你自己的迭代器來完成這個任務，但由於圓形列表的大小是固定的，我更喜歡一個容器像std::array或std::vector這樣的固定大小和線性存儲器。

template< 
    class T, 
    class Container = std::vector<T> 
> 
class circular_list { 
public: 
    // Following typedef are required to make your class a container 
    typedef typename Container::size_type size_type; 
    typedef typename Container::difference_type difference_type; 
    typedef typename Container::pointer pointer; 
    typedef typename Container::const_pointer const_pointer; 
    typedef typename Container::reference reference; 
    typedef typename Container::const_reference const_reference; 
    typedef typename Container::value_type value_type; 
public: 
    class iterator : std::iterator<std::bidirectional_iterator_tag, value_type> { 
    public: 
     iterator() : c_(nullptr) {} 
     iterator(circular_buffer& c, size_type index) 
      : c_(&c.c_), index_(index) {} 

     reference operator*() const { 
      return (*c_)[index_]; 
     } 
     iterator& operator++() { 
      if(++index_ >= c_->size()) index_ = 0; 
      return *this; 
     } 
     iterator& operator--() { 
      if(index_ == 0) index_ = c_->size() - 1; else --index_; 
      return *this; 
     } 

    private: 
     size_type index_; 
     Container* c_; 
    }; 

public: 
    void push(const_reference val) {add item to the container} 
    reference current() {return current item from the container} 
    void pop() {remove item from the container} 

    size_type size() const {return c_.size();} 
    iterator begin() {return iterator(*this, 0);} 
    iterator end() {return iterator(*this, size());} 

private: 
    friend iterator; 
    Container c_; 
}