Действительно ли 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 ничего не меняет в этой области.

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

Изменение стандарта вводится n2923: указание сложность размера () (редакция 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() is правильно 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();}

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

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

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

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

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

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

Этот отчет об ошибке: [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 - это больше о правильности, стандартном поведении и «удобстве для пользователя», чем о чистой скорости.