Является ли list::size() действительно O(n)?

Недавно я заметил, что некоторые люди упоминают, что std::list::size() имеет линейную сложность.
Согласно некоторым источникам, это на самом деле зависит от реализации, так как стандарт не говорит о том, какой должна быть сложность.
Комментарий в этой записи блога говорит:

На самом деле, это зависит от того, какой STL вы используете. Microsoft Visual Studio V6 реализует size() как {return (_Size); } тогда как gcc (по крайней мере в версиях 3.3.2 и 4.1.0) делает это как { return std::distance(begin(), end()); } Первый имеет постоянную скорость, второй имеет o(N) скорость

  1. Так что я думаю, что для толпы VC++ size() имеет постоянную сложность, так как Dinkumware, вероятно, не изменил бы этот факт со времен VC6. Я тут прав?
  2. Как это выглядит в настоящее время в gcc? Если это действительно O(n), почему разработчики решили сделать это?
Источник

9 ответов

Решение

Pre-C++11 ответ

Вы правы в том, что в стандарте не указано, какой должна быть сложность list::size(), однако он рекомендует, чтобы он "имел постоянную сложность" (Примечание A в таблице 65).

Вот интересная статья Говарда Хиннанта, которая объясняет, почему некоторые люди думают, что list::size() должен иметь сложность O(N) (в основном потому, что они считают, что O(1) list::size() делает list::splice() имеющим O(N) сложность) и почему O(1) list::size() будет хорошей идеей (по мнению автора):

Я думаю, что основные моменты в статье:

  • Есть несколько ситуаций, когда ведение внутреннего счета так list::size() может быть O (1) приводит к тому, что операция соединения становится линейной
  • вероятно, есть еще много ситуаций, когда кто-то может не знать о негативных последствиях, которые могут произойти, потому что они называют O(N) size() (например, его один пример, где list::size() вызывается, удерживая замок).
  • что вместо разрешения size() быть O(N), в интересах "наименьшего удивления", стандарт должен требовать любой контейнер, который реализует size() реализовать его O (1). Если контейнер не может сделать это, он не должен реализовывать size() совсем. В этом случае пользователь контейнера узнает, что size() недоступен, и если они все еще хотят или должны получить количество элементов в контейнере, они могут все еще использовать container::distance( begin(), end()) чтобы получить это значение - но они будут полностью знать, что это операция O(N).

Я думаю, что я склонен согласиться с большинством его рассуждений. Однако мне не нравится его предложенное дополнение к splice() Перегрузки. Должен пройти в n это должно быть равно distance( first, last) получить правильное поведение похоже на рецепт для трудно диагностируемых ошибок.

Я не уверен, что нужно или можно сделать, чтобы двигаться вперед, поскольку любое изменение окажет значительное влияние на существующий код. Но в нынешнем виде я думаю, что существующий код уже подвержен влиянию - поведение может довольно существенно отличаться от одной реализации к другой для чего-то, что должно быть четко определено. Возможно, один комментарий о том, что размер "кэширован" и помечен как известный / неизвестный, может работать хорошо - вы получаете амортизированное поведение O (1) - единственный раз, когда вы получаете поведение O(N), это когда список изменяется некоторыми операциями splice (), Хорошая вещь об этом - то, что это может быть сделано разработчиками сегодня без изменения стандарта (если я что-то упускаю).

Насколько я знаю, C++0x ничего не меняет в этой области.

Источник

В C++11 требуется, чтобы для любого стандартного контейнера .size() операция должна быть завершена в "постоянной" сложности (O(1)). (Таблица 96 - Требования к контейнерам). Ранее в C++03 .size() должен иметь постоянную сложность, но не является обязательным (см. Является ли std::string size() операцией O (1)?).

Изменение в стандарте введено n2923: указание сложности size() (редакция 1).

Тем не менее, реализация .size() в libstdC++ все еще использует алгоритм O (N) в gcc до 4.8:

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

Смотрите также Почему std:: list больше на C++11? для деталей, почему это так.

Обновление: std::list::size() правильно O (1) при использовании gcc 5.0 в режиме C++11 (или выше).

Кстати, .size() в libC++ это правильно 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();}
Источник

Я должен был посмотреть в gcc 3.4's list::size, так что я могу сказать это:

  1. он использует std::distance(голова, хвост)
  2. std:: distance имеет две реализации: для типов, которые удовлетворяют RandomAccessIterator, он использует "tail-head", а для типов, которые просто удовлетворяют InputIterator, он использует алгоритм O(n), опираясь на "iterator++", считая, пока не достигнет заданного хвост.
  3. std:: list не имеет отношения к RandomAccessIterator, поэтому размер равен O(n).

Что касается "почему", я могу только сказать, что std:: list подходит для задач, которые требуют последовательного доступа. Хранение размера в виде переменной класса приведет к дополнительным затратам на каждую вставку, удаление и т. Д., И это означает, что отходы являются большими нет-нет в соответствии с намерением STL. Если вам действительно нужен постоянный размер (), используйте std::deque.

Источник

Лично я не вижу проблемы со сращиванием O(N) как единственной причины, по которой размер может быть O(N). Вы не платите за то, что не используете, это важный девиз C++. В этом случае поддержание размера списка требует дополнительного увеличения / уменьшения при каждой вставке / удалении независимо от того, проверяете ли вы размер списка или нет. Это небольшие фиксированные накладные расходы, но их все же важно учитывать.

Проверка размера списка редко требуется. Итерирование от начала до конца без учета общего размера встречается гораздо чаще.

Источник

Я бы пошел к источнику. Страница STI SGI гласит, что разрешено иметь линейную сложность. Я считаю, что руководящие принципы разработки, которым они следовали, должны были сделать реализацию списка как можно более общей и, таким образом, обеспечить большую гибкость в использовании списков.

Источник

Это можно ясно показать в текущем исходном коде GCC :size() реализован, как показано ниже.

        _GLIBCXX_NODISCARD
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return _M_node_count(); }

Он вызвал _M_node_count(), а _M_node_count реализован следующим образом:

          #if _GLIBCXX_USE_CXX11_ABI
      static size_t
      _S_distance(const_iterator __first, const_iterator __last)
      { return std::distance(__first, __last); }

      // return the stored size
      size_t
      _M_node_count() const
      { return this->_M_get_size(); }
#else
      // dummy implementations used when the size is not stored
      static size_t
      _S_distance(const_iterator, const_iterator)
      { return 0; }

      // count the number of nodes
      size_t
      _M_node_count() const
      { return std::distance(begin(), end()); }
#endif

если для _GLIBCXX_USE_CXX11_ABI установлено значение 0, size() равно O(N), в противном случае — O(1). _GLIBCXX_USE_CXX11_ABI, установленный в 0, произойдет, когда вы используете скомпилированные библиотеки GCC высокой версии и вам нужна ссылка на скомпилированные библиотеки GCC низкой версии, например, ваша система установила скомпилированные GCC 4.8 библиотеки GTEST, но ваш код теперь использует GCC 7.3 и использует C ++ 11, и вам нужно связать эти библиотеки, в этом случае вам нужно добавить следующее в свой CMakeLists.txt, иначе возникнет проблема со ссылкой.

      add_compile_definitions(_GLIBCXX_USE_CXX11_ABI=0)
Источник

Этот отчет об ошибке: [C++ 0x] std::list::size, в мельчайших деталях фиксирует тот факт, что реализация в GCC 4.x представляет собой линейное время и как медленный переход к постоянному времени для C++ 11 в ближайшее время (доступно в 5.0) из-за проблем совместимости ABI.

Страница руководства для серии GCC 4.9 по-прежнему содержит следующий отказ от ответственности:

Поддержка C++ 11 все еще является экспериментальной и может измениться несовместимыми способами в будущих выпусках.

Ссылка на тот же отчет об ошибке здесь: Должна ли std::list::size иметь постоянную сложность в C++11?

Источник

Если вы правильно используете списки, вы, вероятно, не замечаете никакой разницы.

Списки хороши для больших структур данных, которые вы хотите переставить без копирования, для данных, которые вы хотите сохранить действительными указателями после вставки.

В первом случае это не имеет значения, во втором я бы предпочел старую (меньшую) реализацию size().

Во всяком случае, стандартный вывод - это больше о корректности и стандартном поведении, а также о "удобстве использования", а не о скорости.

Источник

std :: list :: size() возвращает количество элементов в контейнере списка.
Если вы используете C++11, то временная сложность равна O(1), в противном случае в C++98 это O(n).
Эта ссылка описывает сложности всех функций контейнеров STL.

Источник
Другие вопросы по тегам