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

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

59 голосов
/ 23 октября 2008

Недавно я заметил, что некоторые люди упоминают, что 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), почему разработчики решили сделать это?

Ответы [ 7 ]

68 голосов
/ 07 декабря 2012

В 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() правильно 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();}
50 голосов
/ 23 октября 2008

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

14 голосов
/ 23 октября 2008

Раньше мне приходилось заглядывать в список gcc 3.4: 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.

11 голосов
/ 23 октября 2008

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

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

4 голосов
/ 23 октября 2008

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

1 голос
/ 04 декабря 2015

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

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

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

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

0 голосов
/ 18 мая 2017

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

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

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

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

...