Size() сложности контейнеров STL в g++: в каких контейнерах O (n)?

Я думаю, большинство людей понимает, что сложность функции size() не гарантируется постоянной. Хотя в некоторых реализациях он постоянный.

Компилятор g++, вероятно, является наиболее часто используемым компилятором. Итак, в реализации g++ какая сложность size()? Если это зависит от разных контейнеров, какие контейнеры имеют линейную сложность? Для наиболее часто используемых (например, списка, вектора, deque, set и map) все они постоянны?

Ответ 1

Он может меняться в зависимости от версии стандартной библиотеки.

Для последних версий GCC (по крайней мере, до 4.6.2) List и те, которые основаны на List, не являются постоянным временем, но реализованы как { return std::distance(begin(), end()); }.

Стандартная библиотека MSVC отслеживает размер по мере его изменения и просто возвращает свое значение (что делает splice() O (n), потому что он должен учитывать, когда он сращивается).

Из моего /usr/include/c++/4.6.2/bits/stl_list.h:

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

vector, set, deque и map - постоянное время.,

это std::deque 's

  size_type
  size() const
  { return this->_M_impl._M_finish - this->_M_impl._M_start; }

queue и stack являются фактически контейнерными адаптерами и зависят от базового контейнера, который может быть указан. Однако по умолчанию используется значение deque, которое является постоянным.

Ответ 2

Для С++ 11 стандарт (23.2.1) указывает, что size является O (1) для всех контейнеров в согласованных реализациях стандартной библиотеки (к сожалению, это не означает, что все реализации являются совместимыми; gcc имеет эту проблему).

Для С++ 03 стандарт (23.1) говорит, что size "должен иметь постоянную сложность", который, как оказывается (спасибо, комментаторы), является сильным, но необязательным предложением; это означает, что вы должны прочитать документацию для реализации, предоставляемую каждому компилятору.

Ответ 3

Для g++ 5.4.0 файл/usr/include/С++/5.4.0/bits/stl_list.h

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return this->_M_node_count(); }

Для g++ 4.8.5 файл/usr/include/С++/4.8.5/bits/stl_list.h

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

Поэтому он является линейным для 4.8.5 и константой для 5.4.0