Существует ли стандартная реализация Циркулярного списка для C ++?

Question

Я хочу использовать круговой список.

Если не считать моих собственных (, как этот человек сделал ), какие у меня варианты?

В частности, я хочу перебрать список объектов. Когда мой итератор достигает конца списка, он должен автоматически вернуться к началу. (Да, я понимаю, что это может быть опасно.)

См. Определение Владимира для circular_iterator: «циркулярный итератор никогда не будет равен CircularList :: end (), поэтому вы всегда можете разыменовать этот итератор».

Answer 1

Нет стандартного кругового списка.

Однако в Boost имеется циклический буфер , что может быть полезно.

Если вам не нужно ничего необычного, вы можете рассмотреть возможность использования vector и доступа к элементам с помощью индекса. Вы можете просто 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 в качестве циклического списка, изменяя то, что вы делаете для извлечения элементов из него. Используйте сращивание , чтобы переместить один конец списка на другой конец по мере его обработки.

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