Почему не std:: list.size() постоянное время?

Этот код работал в течение 0,012 секунд:

 std::list<int> list;
 list.resize(100);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

Этот за 9.378 секунд:

 std::list<int> list;
 list.resize(100000);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

По-моему, можно было бы реализовать std:: list таким образом, этот размер будет храниться в частной переменной, но в соответствии с этим он вычисляется снова каждый раз, когда я вызываю размер. Может кто-нибудь объяснить, почему?

Ответ 1

Существует конфликт между постоянным временем size() и постоянным временем list.splice. Комитет предпочел одобрить splice.

Когда вы соединяете узлы между двумя списками, вам нужно будет подсчитать перемещенные узлы для обновления размеров этих двух списков. Это отнимает много преимуществ сплайсинговых узлов, просто изменяя несколько внутренних указателей.

Как отмечено в комментариях, С++ 11 изменил это, отказавшись от O (1) для некоторых редких (?) использования splice:

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);

Сложность: постоянное время, если &x == this; в противном случае - линейное время.

Ответ 2

В ISO/IEC 14882:2011, §C.2.12, раздел 23: "библиотека контейнеров":

Изменить: сложность функций-членов size() теперь постоянна

Обоснование: Отсутствие спецификации сложности size() привело к расходящимся реализациям с непоследовательными характеристиками производительности.

Влияние на оригинальную функцию: некоторые реализации контейнеров, которые соответствуют С++ 2003, могут не соответствовать указанным требованиям размера() в этом Международном стандарте. Настройка контейнеров, таких как std:: list, на более строгие требования, может потребовать несовместимых изменений.

Комментарии:

В 23.3.5.5 - "операции с списком", снова в ISO/IEC 14882:2011:

содержит три операции сплайсинга, которые разрушают элементы из одного списка в другой. Поведение операций сращивания undefined, если get_allocator()!= X.get_allocator().

void splice (позиция const_iterator, список & x);
void splice (позиция const_iterator, список & x);
Требуется: & x!= this.
Эффекты: Вставляет содержимое x перед положением и x становится пустым. Указатели и ссылки на перемещенные элементы х теперь относятся к тем же элементам, но как к членам * этого. Итераторы, ссылающиеся на перемещенные элементы, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в * это, а не в x.
Сложность: постоянное время.

void splice (позиция const_iterator, список & x, const_iterator i);
void splice (позиция const_iterator, список & x, const_iterator i);
Эффекты: Вставляет элемент, на который указывает я из списка x перед положением, и удаляет элемент из x. Результат не изменяется, если позиция == я или позиция == ++ i. Указатели и ссылки на * я продолжаю ссылаться на этот же элемент, но в качестве члена * этого. Итераторы к * я (включая сам i) продолжают ссылаться на один и тот же элемент, но теперь ведут себя как итераторы в * this, а не в x.
Требуется: я - действительный разыменованный итератор x.
Сложность: постоянное время.

void splice (const_iterator position, list & x, const_iterator first, const_iterator последний);
void splice (const_iterator position, list && x, const_iterator сначала, const_iterator последний);
Эффекты: вставляет элементы в диапазон [первый, последний) перед положением и удаляет элементы из x. Требуется: [first, last) - допустимый диапазон в x. Результатом является undefined, если позиция является итератором в диапазоне [первая, последняя]. Указатели и ссылки на перемещенные элементы х теперь относятся к тем же элементам, но как к членам * этого. Итераторы, ссылающиеся на перемещенные элементы, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в * это, а не в x.
Сложность: постоянное время, если & x == this; в противном случае - линейное время.