Практически все контейнеры из стандартной библиотеки STL реализуют метод size. Всем известно, что данная функция-член возвращает количество элементов в контейнере. Однако,  сложность такой операции для известного контейнера std::list не определена однозначно. В реализации STL от Microsoft сложность операции size равна O(1), то есть константная, и не зависит от количества элементов. Напротив, в GCC сложность операции size равна O(N) - линейная, что существенно ограничивает возможности её применения, особенно там, где важна производительность. Ведь каждый раз при вызове size, Вы фактически будете инициировать полный проход по всему списку. В чем же причина такой неоднозначности?

Материал статьи основан на публикации Howard Hinnant: 

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

Howard Hinnant работает в компании Apple, и является членом комитета по стандартизации C++ от компании Apple. Также он занимается разработкой библиотеки Boost.

До стандарта C++11 сложность метода size у списков описывалась, как "от константной до линейной". То есть, на деле все зависило от конкретной реализации контейнера list. Чтобы сделать сложность константной, внутри контейнера помещали счетчик элементов и изменяли его при добавлении или удалении элементов. Тогда реализация size, например у Microsoft, выглядела так:

В GCC не создавали дополнительных счетчиков и size в этом случае реализовывался так:

Определенно, реализация от Microsoft выглядит предпочтительнее. Ведь, если Вы используете gcc, то вызова size нужно практически избегать, так как он крайне неэффективен. Но в пользу линейной сложности для size всегда приводился "весомый" аргумент.

Недостатки size c O(1)

Список отличается наличием эффективных методов для работы с ним. Эти методы схожи со стандартными алгоритмами, но при работе со списками в них никогда не применяется непосредственное копирование элементов. Вместо этого просто изменяются указатели на предыдущий и следующий элементы. Поэтому у списка есть особые методы: merge, splice, remove, reverse, sort, unique.

Операции splice ("сращивание" двух списков) имеет сложность O(1), так как просто изменяет значения указателей. Но, требование от size иметь сложность равную O(1) "портит" одну из версий splice, а именно эту:

Если size должен иметь сложность O(1), и this != &x (соединяются разные списки), тогда данный метод должен иметь линейную сложность O(N), так как придется снова пересчитать количество элементов в объединенном списке, чтобы обеспечить сложность O(1) для size. Если бы сложность size могла быть линейной, то эта версия splice имела бы сложность O(1), как и её другие перегруженные версии. Это и есть, тот самый аргумент в пользу медленного size:

size O(1) приводит к splice O(N) 

И он вполне справедлив, ведь каждый контейнер ценится за тот набор эффективных операций, которые он предоставляет и жаль "терять" одну из таких эффективных операций.  

Но как считает Howard Hinnant этот довод сильно преувеличен. И вот почему: рассмотрим 5 возможных ситуаций соединения (splice situations) списков: соединение с самим собой или с другим списком одного, нескольких или всех элементов сразу. При условии, что size имеет сложность O(1), только один из пяти вариантов "сращивания" списков потеряет в эффективности:


splice с самим собойsplice с другим списком
один элементO(1)O(1)
несколько элементовO(1)O(some) - distance(first, last)
все элементыNot validO(1)


Для того, чтобы обеспечить O(1) для size нужно посчитать те несколько элементов (some), которые будут перенесены в результирующий список (O(some)).

Преимущества size c O(1)

Тем не менее, если size будет иметь сложность O(1), это позволит задействовать оптимизацию для следующих методов:

В случае, когда размер списка уменьшается, использование константного size поможет определить какой вариант прохода будет эффективнее: от начала списка до начала удаляемого диапазона, или от конца списка до начала удаляемого диапазона: 

Операции сравнения списков также могут быть оптимизированы, если вначале сравнить размеры списков, а только потом, при условии равенства результатов size, начинать по-элементное сравнение списков: 

Доводы в пользу константной сложности метода size видимо пересилили и, начиная со стандарта C++11, разработчикам STL рекомендуется для size обеспечивать сложность равную O(1). Но Вы должны иметь ввиду, что на практике size может по-прежнему иметь сложность O(N). Например, в gcc-4.9.1 реализация по-прежнему такая:

Howard Hinnant в своей статье приводит несколько мест из библиотеки boost, где отмечает потенциальное ухудщение производительности, в случае использования "медленного" (O(N)) size.

Howard Hinnant также считает, что если контейнер не может обеспечить для size сложность O(1), то такой контейнер не должен вовсе иметь метод size. А его размер, при необходимости, должен высчитываться, например, с использованием алгоритма sdt::distance. Это будет явно указывать на линейную сложность. Но это требование применимо лишь к новым контейнерам (таким как std::forward_list). Поэтому, если Вы используете std::list и компилируете код разными компиляторами, Вам следует учитывать сложность метода size в разных реализациях STL, чтобы иметь действительное представление об эффективности Вашей работы со std::list.


На этом всё.

P.S.: Если Вам нужно проверить условие, что контейнер не пуст, всегда используйте метод empty(), а не условие size() > 0. Empty всегда будет или быстрее, или таким же по скорости, как size.