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

Pre-C++ 11 ответ

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

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

• http://howardhinnant.github.io/On_list_size.html

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

• есть несколько ситуаций, когда поддержание внутреннего счетчика, поэтому 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 в этой области ничего не меняет.

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

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

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

Раньше мне приходилось заглядывать в list::size gcc 3.4, поэтому я могу сказать следующее:

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

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

В 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 больше на с ++ 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();}

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

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

Support for C++11 is still experimental, and may change in incompatible ways in future releases.

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

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

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

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

В любом случае std - это больше о правильности, стандартном поведении и «удобстве для пользователя», чем о чистой скорости.