C ++ Время и пространство Сложность функции-члена стирания строкового класса

Question

Я хотел узнать, знает ли кто-нибудь реализацию функции C ++ string :: erase и ее сложность.Я знаю, что строка C ++ является объектом символов.Я предполагаю, что он не выделяет и не создает новый объект символов, а затем копирует символы из старого пространства O (n) и O (n).Смещается ли он по символам O (n) и O (1) пробел?Я просмотрел cplusplus.com и книгу Бьярна Страуструпа, но не смог найти ответ.Может кто-нибудь указать мне исходный код, где он реализован, или знать ответ?

Спасибо!

Answer 1

Как указано в комментариях , стандарт не устанавливает каких-либо требований к сложности для многих функций basic_string (включая erase).Отчасти это связано с тем, что исторически существовал целый ряд различных стратегий реализации (наиболее известным было то, что копирование при записи было популярно в эпоху C ++ 98), поэтому комитет не хотел указывать что-либо слишком точно.

базовое поведение типичных современных реализаций очень похоже на vector<char>: вставка и удаление дешевы в конце (с перераспределенными перераспределениями) и дороги в начале.Маленькие строки обрабатываются без выделения памяти вообще (путем повторного использования пространства указателей для хранения символов).Это означает, что стирание может привести к копированию всей строки, если она станет очень короткой (но тогда копия будет дешевой).Это также означает, что итераторы и ссылки становятся недействительными легче, чем с vector.

Нет никаких алгоритмов , которые лучше работают на string,но существуют альтернативные структуры данных , которые имеют различные характеристики производительности. веревка является типичной среди них тем, что обеспечивает несколько более медленный доступ, но гораздо более быструю вставку и удаление.