Ist „std::list::size()' immer O(1)?

Ist list::size() wirklich O(1)?

Während es einst wahr war, dass std::list::size () in allen Implementierungen eine variable Komplexität aufwies, hat C 11 sein Verhalten standardisiert. Tabelle 96 der Containeranforderungen schreibt eine konstante Komplexität (O(1)) für .size()-Operationen für alle Standardcontainer vor.

Eine bemerkenswerte Ausnahme bleibt jedoch die libstdc-Implementierung von gcc vor Version 5.0. Trotz der C 11-Standardanforderung verwendet seine .size()-Funktion einen O(N)-Algorithmus, wie im folgenden Auszug zu sehen ist:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }

Diese Entscheidung ergibt sich aus Optimierungsüberlegungen innerhalb von libstdc. Die Beibehaltung einer separaten Anzahl von Elementen anstelle des Durchlaufens der Liste verbessert die Leistung für einige Anwendungsfälle, obwohl dies im Widerspruch zur Standardkomplexitätsanforderung steht.

Die Implementierung von Libc hält sich dagegen korrekt an die O(1) Komplexität, wie durch den folgenden Codeausschnitt veranschaulicht:

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type&amp; __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Zusammenfassend lässt sich sagen, dass der C 11-Standard O(1)-Komplexität für vorschreibt std::list::size(), die libstdc-Implementierung von gcc vor Version 5.0 bleibt eine Anomalie und verwendet stattdessen einen O(N)-Algorithmus.

Das obige ist der detaillierte Inhalt vonIst „std::list::size()' immer O(1)?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!