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

Question

В обсуждении от Is `std::vector<primitive>::clear()` a constant time operation? было отмечено, что стандарт C++ не указывает время работы vector::clear.

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

Действительно ли это не указано, или я что-то пропустил?

Answer 1

Действительно ли это не указано, или я что-то пропустил?

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

There is an open library issue for this, текст которого содержит ссылку на соответствующий вопрос Q & A на StackOverflow. Ответ Jonathan Wakely на этот вопрос уточняет, что происходит.

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

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

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

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

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