Является ли временная сложность `std::vector <T>:: clear` * really * не указанной?
В ходе обсуждения этого вопроса выяснилось, что, по-видимому, нет требований к сложности времени, установленных на std::vector<T>::clear стандартом С++.
В таблице 100 в разделе 23.2.3 говорится:
Уничтожает все элементы в a. Недействительность всех ссылок, указателей и итераторов, относящихся к элементам a, и может привести к аннулированию итератора прошедшего конца. post: a.empty() возвращает true
И... это. Там нет записи для нее в соответствии с 23.3.6 и нет явного указания, что для clear применяется следующее:
[C++11: 23.3.6.1/1]: Вектор представляет собой контейнер последовательности, который поддерживает итераторы произвольного доступа. Кроме того, он поддерживает (амортизируется) постоянное время вставки и стирания операций в конце; вставлять и стирать в середине, принимать линейное время. Управление хранилищем обрабатывается автоматически, хотя можно дать подсказки для повышения эффективности. [..]
Итак... это правда? Или я просто пропустил это?
Ответы
Ответ 1
Это кажется непреднамеренным последствием DR 704 (и связанный DR 1301), который удалил формулировку, в которой выражение clear() эквивалентно erase(begin(), end()), потому что erase() требует MoveAssignable, что не требуется при стирании каждого элемента. Удаление определения в терминах erase() также устраняет требование сложности. Это, вероятно, можно обрабатывать в редакционной форме; Я поднял его с комитетом.
N.B. std::deque::clear() и std::forward_list::clear() также затронуты. std::list::clear() имеет гарантию сложности.
Изменить: теперь http://cplusplus.github.com/LWG/lwg-active.html#2231
