Gibt es eine Standardimplementierung einer Circular List für C++?

Question

Ich möchte eine zirkuläre Liste verwenden.

Wenn ich nicht meine eigene ( wie diese Person es getan hat ) Welche Möglichkeiten habe ich?

Konkret möchte ich über eine Liste von Objekten iterieren. Wenn mein Iterator das Ende der Liste erreicht, sollte er automatisch an den Anfang zurückkehren. (Ja, ich weiß, dass das gefährlich sein könnte.)

Siehe Vladimirs Definition eines circular_iterator : "Ein circular_iterator wird nie gleich sein mit CircularList::end(), daher kann man diesen Iterator immer dereferenzieren."

Answer 1

Es gibt keine standardisierte Rundschreibenliste.

Es gibt jedoch eine Ringspeicher in Boost, was hilfreich sein könnte.

Wenn Sie nichts Ausgefallenes brauchen, können Sie auch einfach eine vector und den Zugriff auf die Elemente mit einem Index. Sie können einfach mod Ihren Index mit der Größe des Vektors, um das Gleiche zu erreichen wie eine kreisförmige Liste.

Answer 2

Wenn Sie etwas wollen, das wie ein Iterator aussieht, können Sie einen eigenen Iterator erstellen, der etwa so aussieht

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

(Andere Iterator-Operationen werden dem Leser als Übung überlassen).

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

Zusätzlich zu den Antworten von @captain-segfault und @mahmoud-khaled, die sich auf Iteratoren konzentrieren, können Sie auch std::list als zirkuläre Liste zu verwenden, indem Sie die Vorgehensweise zum Abrufen von Elementen aus der Liste ändern. Verwenden Sie Spleiß um bei der Bearbeitung der Liste das eine Ende an das andere Ende zu verschieben.

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

Ich habe diese Lösung gefunden. Funktioniert gut für mich.

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 diesem Fall wird die Schleife unendlich lang sein. Sollte auch rückwärts funktionieren.

Ausgabe

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