В статье на cppreference.com указано, что сложность std::vector::shrink_to_fit постоянна. Насколько я знаю, это возможно только в том случае, если элементы не перемещаются, потому что если они тогда сложны, то n. В нем также говорится, что все итераторы, включая прошлый итератор конца, потенциально недействительны. что означает, что перемещение элементов является четко определенной возможностью.
Является ли статья неисправной?... или есть какая-то магия, о которой я не знаю?
Неверная статья , я ее исправил.
В официальном стандарте ничего не говорится о сложности std::vector::shrink_to_fit, в N3376 они изменили формулировку, тем самым установив DR 2033:
23.3.6.3:
void shrink_to_fit();Требуется:
Tдолжно бытьMoveInsertableв*this.Сложность: линейная по размеру последовательности.