1

我想实现一个基于 std::list 的循环列表。我想从列表的好处中获益，但添加一个特定功能：它的迭代器运算符 ++ 和 -- 应该跳过边缘，并且操作（插入/擦除）不能使现有迭代器无效。我处理模板的技能很弱，理解标准容器对我来说是不可能的。因此我需要你的帮助。到目前为止，我还没有那么远：D。抱歉，即使是众多帖子也对我没有任何帮助。

编辑：经过大量工作，陡峭的学习曲线，从 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;

};
4

3 回答 3

5

你不能只做一个不同的迭代器类型吗？

#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迭代器的容器上工作。）

于 2012-10-14T12:46:40.973 回答
3

这是不可能的。迭代器和结束元素的实现是特定于实现的，不可定制。容器不是为那种东西设计的，这会让它们变得非常困难。您将不得不自己经历实现这一点的痛苦。请记住，这变得非常棘手，因为循环列表没有真正的结束迭代器，并且迭代器无法真正处理这种情况。一些库有一个循环器概念来处理循环结构。

注意：从标准容器继承是一个坏主意。

于 2012-10-14T12:19:35.470 回答
1

当然你可以使用 实现它std::list，但首先你应该在你的类中封装列表并且不要从它派生第二你必须实现你自己的迭代器来完成这个，但是由于循环列表的大小是固定的，我更喜欢一个固定大小的容器和线性内存，如std::arrayor 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_;
}
于 2012-10-14T12:52:45.043 回答