C++ 是否存在循环列表的标准实现？

Question

我想使用循环列表。

如果没有实现我自己的（像这个人所做的），我有什么选择？

具体来说，我想做的是迭代对象列表。 当我的迭代器到达列表末尾时，它应该自动返回到开头。 （是的，我意识到这可能很危险。）

请参阅 Vladimir 对 circular_iterator 的定义< /a>: “circular_iterator 永远不会与 CircularList::end() 相等，因此您始终可以取消引用此迭代器。”

Answer 1

没有标准的循环列表。

然而，Boost中有一个循环缓冲区 ，这可能会有所帮助。

如果您不需要任何花哨的东西，您可以考虑仅使用向量并通过索引访问元素。 您只需用向量的大小mod您的索引即可实现与循环列表相同的效果。

Answer 2

如果您想要看起来像迭代器的东西，您可以自己推出，看起来像

template <class baseIter>
class circularIterator {
    private:
        baseIter cur;
        baseIter begin;
        baseIter end;
    public:
        circularIterator(baseIter b, baseIter e, baseIter c=b)
            :cur(i), begin(b), end(e) {}
        baseIter & operator ++(void) {++cur; if(cur == end) {cur = begin;}}
};

（其他迭代器操作留给读者作为练习）。

Answer 3

list<int>::iterator circularNext(list<int> &l, list<int>::iterator &it)
{
    return std::next(it) == l.end() ? l.begin() : std::next(it);
}

Answer 4

除了 @captain-segfault 和 @mahmoud-khaled 的以迭代器为中心的答案之外，您还可以通过更改从中检索元素的操作，将 std::list 用作循环列表。 使用 splice 将列表的一端移动到另一端，如下所示你处理它。

template <typename T>
T & circularFront(std::list<T> & l)
{
  l.splice(l.end(), l, l.begin());
  return l.back();
}
template <typename T>
T & circularBack(std::list<T> & l)
{
  l.splice(l.begin(), l, l.rbegin());
  return l.front();
}

Answer 5

不。没有标准实施。 请参阅@Naaff 等其他答案。

这是我的实现：

#include <iostream>
#include <memory>
#include <mutex>

template <typename T>
class CircularList {
public:
  void Insert(const T &item) {
    std::lock_guard<std::mutex> lock(m_);
    if (nullptr == root_) {
      root_ = std::make_shared<Node>();
      root_->item = item;
      root_->next = root_;
      curr_ = root_;
      return;
    }
    for (std::shared_ptr<Node> ptr = root_;; ptr = ptr->next) {
      if (ptr->next == root_) {
        ptr->next = std::make_shared<Node>();
        ptr = ptr->next;
        ptr->item = item;
        ptr->next = root_;
        break;
      }
    }
  }

  bool Remove(const T &item) {
    std::lock_guard<std::mutex> lock(m_);
    if (nullptr == root_) return false;
    std::shared_ptr<Node> before = root_;
    for (;;) {
      if (before->next == root_) break;
      before = before->next;
    }
    for (std::shared_ptr<Node> ptr = root_;; ptr = ptr->next, before = before->next) {
      if (ptr->item == item) {
        if (curr_ == ptr) curr_ = curr_->next;
        if (root_ == ptr) root_ = root_->next;
        before->next = ptr->next;
        return true;
      }
      if (root_ == ptr->next) return false;
    }
  }

  void Clear() {
    std::lock_guard<std::mutex> lock(m_);
    root_ = nullptr;
    curr_ = nullptr;
  }

  bool Empty() const { return nullptr == root_; }

  size_t Size() const {
    if (nullptr == root_) return 0;
    std::shared_ptr<Node> ptr = root_->next;
    size_t sz = 1;
    for (; ptr != root_; ptr = ptr->next, ++sz) {
    }
    return sz;
  }

  void Next(T *out) {
    std::lock_guard<std::mutex> lock(m_);

    if (nullptr == root_) return;
    curr_ = curr_->next;
    *out = curr_->item;
  }

  int Index() const {
    if (nullptr == root_) return -1;
    std::shared_ptr<Node> ptr = root_;
    if (ptr == curr_) return 0;
    for (int ind = 1;; ++ind) {
      ptr = ptr->next;
      if (ptr == curr_) return ind;
    }
  }

  void Print() const {
    if (nullptr == root_) return;
    std::cout << "List elements:" << std::endl;
    for (std::shared_ptr<Node> ptr = root_;; ptr = ptr->next) {
      std::cout << ptr->item << std::endl;
      if (ptr->next == root_) break;
    }
  }

  bool Find(const T &item) const {
    if (nullptr == root_) return false;
    for (std::shared_ptr<Node> ptr = root_;;) {
      if (ptr->item == item) {
        return true;
      }
      ptr = ptr->next;
      if (root_ == ptr) return false;
    }
  }

private:
  struct Node {
    Node() {}
    T item;
    std::shared_ptr<Node> next;
  };

  std::shared_ptr<Node> root_;
  std::shared_ptr<Node> curr_;
  std::mutex m_;
};

它通过了测试，并有一些示例：

https://github.com/OphirCarmi/circular_list /

Answer 6

我找到了这个孤独。 对我来说效果很好。

std::list<int> List{ 1,2,3,4,5,6 };

    auto it = List.end();

    it--;

    it._Ptr->_Next = List.begin()._Ptr; // Next Node of the last elemen is now first elemen of the List
    List.begin()._Ptr->_Prev = it._Ptr; // Prev Node of the first element is now Last node

    for (int num : List)
    {
        std::cout << num << '\n';
    }

在这种情况下，我们将无限循环。 也应该向后工作。

输出

1
2
3
4
5
6
1
2
3
4
5
6
1
.
.