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

в 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 скорость.