Czy list:: size() Jest naprawdę O (n)?

W C++11 wymagane jest, aby dla dowolnego standardowego kontenera operacja .size() musi być zakończona w "stałej" złożoności (O(1)). (Tabela 96-wymagania dotyczące kontenerów). Poprzednio w C++03 .size() powinna mieć stałą złożoność, ale nie jest wymagana (zobacz czy std::string size() jest operacją O(1)?).

Zmiana standardu jest wprowadzana przez n2923: określanie złożoności size () (Wersja 1) .

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

Zobacz także dlaczego std:: list jest większy w c++11? dla szczegółów, dlaczego jest tak utrzymywany.

Aktualizacja: std::list::size() jest poprawnie O (1) podczas używania gcc 5.0 w trybie C++11 (lub nowszym).

Przy okazji, .size() w libc++ jest poprawnie O (1):

_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& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Musiałem wcześniej zajrzeć do listy GCC 3.4:: size, więc mogę powiedzieć tak:

1. używa STD:: distance (head, tail)
2. STD::distance ma dwie implementacje: dla typów, które spełniają RandomAccessIterator, używa "tail-head", a dla typów, które spełniają jedynie InputIterator, używa algorytmu O (n) opierającego się na "iterator++", licząc, aż trafi w dany ogon.
3. std:: lista nie satsyfikuje RandomAccessIterator, więc rozmiar to O (n).

Co do "Dlaczego", mogę powiedzmy tylko, że STD:: list jest odpowiednie dla problemów, które wymagają dostępu sekwencyjnego. Przechowywanie rozmiaru jako zmiennej klasy wprowadzi narzut na każdym insert, delete, itp., a te marnotrawstwo to wielkie Nie-Nie zgodnie z intencją STL. Jeśli naprawdę potrzebujesz stałej wielkości (), użyj STD:: deque.

Osobiście nie widzę problemu z O(N) jako jedynym powodem, dla którego rozmiar może być O(N). nie płacisz za to, czego nie używasz to ważne motto C++. W takim przypadku utrzymanie rozmiaru listy wymaga dodatkowego zwiększania / zmniejszania przy każdym wstawianiu/kasowaniu, niezależnie od tego, czy sprawdzasz rozmiar listy, czy nie. Jest to mały stały nad głową, ale nadal ważne do rozważenia.

Sprawdzanie rozmiaru listy jest rzadko potrzebne. Iteracja od początku do końca bez dbanie o całkowity rozmiar jest nieskończenie powszechniejsze.

Udałbym się do Źródła . Strona STL SGI mówi, że dozwolone jest posiadanie złożoności liniowej. Uważam, że wytyczne projektowe, którymi się kierowali, polegały na tym, aby implementacja listy była jak najbardziej ogólna, a tym samym aby umożliwić większą elastyczność w korzystaniu z list.

This bug report: [C++0x] STD::list::size complexity, przechwytuje w niewyobrażalny sposób fakt, że implementacja w GCC 4.x jest czasem liniowym i jak przejście na stały czas dla C++11 było powolne (dostępne w wersji 5.0) ze względu na problemy z kompatybilnością ABI.

Strona podręcznika dla serii GCC 4.9 nadal zawiera następujące zastrzeżenie:

Wsparcie dla C++11 jest nadal eksperymentalne, a w przyszłości mogą ulec zmianie w sposób niezgodny wydania.

Ten sam raport o błędzie znajduje się tutaj: czy std::list:: size powinno mieć stałą złożoność w C++11?

Jeśli poprawnie używasz list, prawdopodobnie nie zauważysz żadnej różnicy.

Listy są dobre z dużymi strukturami danych, które chcesz zmienić bez kopiowania, dla danych, które chcesz zachować ważne wskaźniki po wstawieniu.

W pierwszym przypadku nie robi to różnicy, w drugim wolałbym starą (mniejszą) implementację size ().

W każdym razie std to bardziej poprawność i standardowe zachowanie i "przyjazność dla użytkownika" niż szybkość raw.