size () сложность контейнеров STL в G ++: какие контейнеры O (n)? - PullRequest
Новая
       24

size () сложность контейнеров STL в G ++: какие контейнеры O (n)?

12 голосов
/ 12 декабря 2011

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

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

Ответы [ 3 ]

16 голосов
/ 12 декабря 2011

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

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

7 голосов
/ 12 декабря 2011

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

Для последних версий 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 * 

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

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

0 голосов
/ 17 февраля 2017

Для G ++ 5.4.0, файл /usr/include/c++/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/c++/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

...