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

7 ответов:

Pre-C++11 ответ

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

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

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

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

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

Я не уверен, что должно или может быть сделано движение вперед, так как любое изменение будет иметь значительное влияние на существующий код. Но как бы то ни было, я думаю, что существующий код уже повлиял - поведение может быть довольно значительно отличаться от одной реализации к другой для чего-то, что должно было быть четко определено. Возможно, комментарий onebyone о том, что размер "кэшируется" и помечен известным / неизвестным, может хорошо работать - вы получаете амортизированное поведение 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() и правильно O (1) при использовании gcc 5.0 в режиме c++11 (или выше).


кстати, the .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::size раньше, поэтому я могу сказать следующее:

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

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

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

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

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

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

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

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


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

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

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

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

в любом случае std больше о правильности и стандартном поведении и "дружественности к пользователю", чем raw скорость.