Ist std::list::size() wirklich O(n) in modernen Implementierungen?

Kürzlich haben einige Entwickler dies vorgeschlagen std::list::size() hat eine lineare Zeitkomplexität (O(n)). Gemäß dem C-Standard ist die Komplexität jedoch nicht definiert und kann je nach Implementierung variieren.

In früheren Versionen des C-Standards (C 03) wurde empfohlen, dass die Operation size() eine konstante Komplexität aufweist (O(1)). Mit der Einführung von C 11 wurde es jedoch zur Pflicht für alle Standardbehälter. In Tabelle 96 des C 11-Standards heißt es ausdrücklich, dass .size() für alle Container eine konstante Komplexität haben sollte.

In der Vergangenheit implementierte die libstdc-Bibliothek von GCC size() mit der Komplexität O(n) mithilfe von std::distance(begin (), end()), wie in dem von Ihnen zitierten Blogeintrag beschrieben. Im C 11-Modus hat sich dieses Verhalten jedoch geändert:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

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

In GCC 5.0 und höher verwendet die Funktion size() eine interne Datenstruktur, um die Anzahl der Elemente zu verfolgen, wodurch die Operation effektiv zu O(1) wird. Dies steht im Einklang mit der C 11-Anforderung für alle Standardcontainer.

Es ist wichtig zu beachten, dass einige Nischenanwendungsfälle immer noch zu O(n)-Komplexität für size() führen können, für die überwiegende Mehrheit der Benutzer jedoch Der Vorgang sollte eine konstante Zeit sein.