Does a standard implementation of a Circular List exist for C++?

Question

I want to use a circular list.

Short of implementing my own (like this person did) what are my options?

Specifically what I want to do is iterate over a list of objects. When my iterator reaches the end of the list, it should automatically return to the beginning. (Yes, I realize this could be dangerous.)

See Vladimir's definition of a circular_iterator: "A circular_iterator will never be equal with CircularList::end(), thus you can always dereference this iterator."

Fichtean

Answer 1

There's no standard circular list.

However, there is a circular buffer in Boost, which might be helpful.

If you don't need anything fancy, you might consider just using a vector and accessing the elements with an index. You can just mod your index with the size of the vector to achieve much the same thing as a circular list.

Janaye

Thanks Naaff! Modding the index with the size of the vector is such a simple solution, I'm embarrassed I didn't think of it. – Fichtean

If you ensure that the size of your vector is a power of two, then instead of the expensive overhead of the modulus operation, use the bitwise & operator instead as it only costs one cycle. It works like this: (n mod (2^k)) == (n & (2^k - 1)) e.g. n % 256 == (n & (255)) – Solace

The compiler will replace mod with bit operations where appropriate for you anyway, no need to obfuscate code unless you really need the unoptimized debug performance – Ce

Unfortunately -1 % n almost never does what you want here, failing differently for signed and unsigned n. (Except for unsigned n that is a power of two.) Ask me how I know – Pyo

Answer 2

If you want something looking like an iterator you can roll your own, looking something like

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;}}
};

(Other iterator operations left as exercise to reader).

Strader

Answer 3

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

Leah

Answer 4

In addition to @captain-segfault and @mahmoud-khaled's iterator-focused answers, you can also use std::list as a circular list by altering what you do to retrieve elements from it. Use splice to move one end of the list to the other end as you process it.

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();
}

Oleum

Answer 5

No. There isn't a standard implementation. See other answers like @Naaff's.

Here is my implementation:

#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_;
};

It passes tests and has some examples here:

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

Stagnant

Answer 6

I found this solition. Works fine for me.

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';
    }

In this case we will loop indefinitely. Should work backward too.

Output

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

Fluoridate

Hi Doctor smail, the question here is not about making a linked list circular, Runcible is looking for a list class that is circular. – Numerator