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

https://stackoverflow.com/questions/228908

04-07-2019
|

Вопрос

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

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

Решение

Ответ до 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. : Указание сложности 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 :: больше на 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();}

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

<Ол>

он использует std :: distance (голова, хвост)

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

std :: list не соответствует случайным образом в RandomAccessIterator, поэтому размер равен O (n).

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

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

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

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

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

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

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

<Ч>

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow