C ++ Пространственно-временная сложность функции-члена стирания строкового класса
Я хотел знать, знает ли кто-нибудь реализацию функции C ++ string :: erase и ее сложность. Я знаю, что строка C ++ является объектом символов. Я предполагаю, что он не выделяет и не создает новый объект символов, а затем копирует символы из старых строк O (n) и O (n). Смещается ли он по символам O (n) и O (1) пробел? Я просмотрел cplusplus.com и книгу Бьярна Страуструпа, но так и не смог найти ответ. Может кто-нибудь указать мне на исходный код, где он реализован или знать ответ?
Спасибо!
Решение
Как указано в комментариях, стандарт не устанавливает никаких требований к сложности для многих basic_string функции (в том числе erase). Отчасти это связано с тем, что исторически существовал целый ряд различных стратегий реализации (наиболее известным было то, что копирование при записи было популярно в эпоху C ++ 98), поэтому комитет не хотел указывать что-либо слишком точно.
основное поведение типичных современных реализаций очень похож на vector<char>: вставка и удаление дешевы в конце (с перераспределенными перераспределениями) и дороги в начале. Маленькие строки обрабатываются без выделения памяти вообще (путем повторного использования пространства указателей для хранения символов). Это означает, что удаление может привести к копированию всей строки, если она станет очень короткой (но тогда копия будет дешевой). Это также означает, что итераторы и ссылки аннулированных легче чем с vector,
Там нет никаких алгоритмы которые работают лучше на string, но есть альтернативные структуры данных которые имеют разные характеристики производительности. веревка Типичным среди них является то, что он обеспечивает несколько более медленный доступ, но гораздо более быструю вставку и удаление.
Другие решения
Других решений пока нет …