Строковые функции С++. Почему они часто имеют неопределенную сложность?

Ответ 1

TL;DR; Поскольку история и сложности времени еще не были предложены

Ситуация:

[basic.string] только напрямую указывает, что несколько операций имеют определенную сложность:

• size(): O (1), так как С++ 11
• max_size(): O (1), так как С++ 11
• shrink_to_fit(): O (n) в С++ 17 (хотя добавлено в С++ 11)
• operator[]: O (1), так как С++ 11
• swap(): O (1)
• data(): O (1), так как С++ 11

Он опосредованно указывает еще много (и я, вероятно, не хватает нескольких здесь):

• length(): равно size()
• empty(): равно size()
• at(): равно operator[]
• front(): равно operator[]
• back(): равно operator[]
• copy(): O (n) (происходит от его характерных черт)
• assign(): O (n) (происходит от его характерных черт)
• find() и вариации: O (n) (происходит от его характерных черт)
• append(char* s): O (m), где m - длина s (исходит из его характерных черт)

Требование к data() здесь является ключевым. До С++ 11 базовое хранилище для строки было определено реализацией. Это могло быть связанным списком для всего, что имеет значение, если оно может быть переведено в массив c-style, когда это необходимо. После С++ 11 базовая реализация по-прежнему зависела от платформы, но требование, чтобы data() было O (1), все же гарантировало, что хранение строки было в смежном массиве C-стиля (не более ленивое копирование связанного списка). В С++ 17, data был перегружен для возврата неконстантного символьного массива, который вы могли бы изменить, и такие модификации будут такими же, как использование operator[], чтобы сделать то же самое, что еще более укрепило реализацию (FWIW хранилище по-прежнему зависит от реализации, но нет способа удовлетворить требованиям временной сложности в противном случае).

Вы можете видеть, что требования к производительности только для С++ 03 были на swap, и это отражает философию стандарта в течение длительного времени; предпочитают указывать только поведение объекта и позволяют реализациям заботиться о гарантиях производительности. Это дает разработчикам библиотек большую гибкость для оптимизации для того, что они считают нужным.

Что произошло исторически

Когда вы вникнете в предложения, которые добавили формулировки сложности (например, n2923: указав сложность размера(), вы увидите что эти требования сложности становятся добавочными по частям, поскольку люди рассматривают их.

Heck, неконстант data() был добавлен в С++ 17 просто потому, что ранее он не предлагался ( ссылка на обсуждение std на (на самом деле просто ссылается на ответ нашего друга Говарда Хиннанта fooobar.com/questions/17092/...))

Copy-On-Write

Int n8215, автор подробно обсуждает basic_string, цитируя copy-on-write как одну из первоначальных философий за ее дизайном (хотя он не совсем туда попал)

С другой стороны, текущие спецификации basic_string предназначены для того, чтобы разрешить ссылки на подсчитанные строки, для которых необходима копирование на запись (COW).

(Википедия со ссылкой на Скотта Мейерса согласна).

Если бы стандарт позволял копировать-на-запись, имеет смысл не делать гарантии производительности в стандарте, потому что запись в строку может быть либо O (1), либо O (N). O (N) было бы правильным, я полагаю, но это свободная граница, которая может вводить в заблуждение.

На самом деле, Дэниел Крюглер интересовался тем же, что и вы в LWG 876: операции доступа к базовым_страницам должны давать более сильные гарантии, а также приводить копии- on-write как остаток:

Из-за более ранней поддержки копирования-на-записи мы обнаруживаем следующие ненужные ограничения для С++ 0x:
... 2. Отсутствующие гарантии сложности: data() и c_str() просто возвращают указатель на их кишки, что гарантируется O (1). Это должно быть указано.

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

Не стесняйтесь предлагать временные сложности для функций basic_string, где они отсутствуют. Стандарт может быть лучше для него: -)

Ответ 2

Давным-давно появилась идея, что вы можете реализовать std::string с помощью канатов. SGI STL даже содержал rope template с очень string -подобным интерфейсом.

Но оказалось, что люди использовали индексный оператор и метод c_str() много, более эффективную конкатенацию, поэтому на практике на практике на основе веревки std::string не были конкурентоспособны.