Является ли сложность вектора:: clear unspecified?

В обсуждении из Является ли` std::vector <primitive> :: clear() `постоянной операцией времени?, было отмечено, что стандарт С++ делает не указывается время работы vector::clear.

Указывает время работы list::clear (linear; §23.3.5.4.5), .clear для упорядоченных (таблица 102) и неупорядоченных ассоциативных контейнеров (таблица 103) (как линейных). Тем не менее, vector::clear, кажется, отсутствует (хотя другие члены vector, такие как .data и .swap, как представляется, имеют определенную сложность).

Неужели это неуточнено, или я что-то пропустил?

Ответ 1

Неужели это неуточнено, или я что-то пропустил?

Да. На данный момент это действительно неуказано.

Для этого есть проблема с открытой библиотекой, текст которой содержит ссылку на соответствующий Q & A на StackOverflow. Ответ Джонатан Вакли на этот вопрос уточняет, что происходит.

Согласно связанному предложению, требование сложности clear() должно быть сделано linear для всех контейнеров последовательностей. Однако следует иметь в виду, что требования сложности - это просто верхние границы. В соответствии с пунктом 17.5.1.4/7 стандарта С++ 11:

Требования к сложности, указанные в разделах библиотеки, являются верхними границами, а реализации, обеспечивающие лучшие гарантии сложности, удовлетворяют требованиям.

Это позволяет сделать возможную оптимизацию, но не дает им мандат.

Даже если связанное предложение будет принято, нам не будет позволено предположить, что clear() имеет сложность O (1) для контейнеров последовательностей неклассических элементов, хотя это, по-видимому, является естественной и общей стратегией оптимизации (и ответ dasblinkenlight на этот вопрос на SO подтверждает это).

Реализациям будет разрешено принять эту стратегию (в соответствии с 17.5.1.4/7), но от них не потребуется этого, потому что нигде в Стандарте такое ограничение не предусмотрено (и не предлагается).