Является ли std::string size() операцией O(1)?
Является ли std::string size() операцией O(1)?
Я использую реализацию STL, встроенную в VC++
7 ответов
Если вы спрашиваете, имеет ли MSVC реализация string::size() постоянную сложность, тогда ответ - да. Но Дон Уэйкфилд упомянул Таблицу 65 в 23.1 Стандарта C++, где говорится, что сложность size() следует следовать тому, что сказано в "Примечании А". Примечание А говорит:
Эти записи, помеченные '' (Примечание A) '', должны иметь постоянную сложность.
Однако это не означает, что эти записи должны иметь постоянную сложность. Стандарты используют очень специфическую терминологию, и "должен" означает, что это не обязательно.
"Примечание A" было добавлено к стандарту специально, чтобы успокоить тех, кто считает, что size() должно быть разрешено иметь линейную сложность, чтобы не было необходимости сохранять размер при модификации контейнеров.
Таким образом, вы не можете положиться на size() с постоянной сложностью, но я честно не уверен, есть ли реализации, которые не имеют постоянной string::size(),
Вот простой способ ответить на этот вопрос для msvC++.
Напишите некоторый код в проекте:
string happy;
happy.size();
Подсветите вызов.size, щелкните правой кнопкой мыши, перейдите к определению.
На моей установке (vs2005sp1) это отправляет меня к xstring:1635, который выглядит так:
size_type __CLR_OR_THIS_CALL size() const
{ // return length of sequence
return (_Mysize);
}
Таким образом, похоже, что в строке есть член с именем _Mysize, и он просто возвращает это.
Другими словами, это реализация O(1).
Для строки size() операция должна быть постоянной для всех строковых реализаций, которые не используют веревки (1). В стандарте нет явного требования, которое требует O(1) наиболее близким является общее требование size() должно быть постоянным временем, но это оставляет место для любой другой меры сложности.
Так почему это должно быть O(1)?
Это связано с тем, что размер не может быть рассчитан из содержимого самой строки. В то время как в C вы используете терминатор NUL для определения конца строки, в C++ NUL так же допустим, как и любой другой символ в строке. Поскольку размер строки не может быть рассчитан из содержимого (2), он должен обрабатываться извне, независимо от фактического размера строки.
(1) Стандарт C++03 позволяет реализации использовать веревки в качестве реализации для строк, но факт в том, что ни одна из текущих реализаций стандартных библиотек не использует их.
(2) Если в реализации используются веревки, операция может зависеть от размера посредством количества блоков, из которых была построена веревка, если блоки были связаны через связанный список или похожую конструкцию, или если им было разрешено иметь разные размеры. Но веревки не используются ни в одной стандартной реализации библиотеки, о которой я знаю.
См. Таблицу 65 в разделе 23.1 стандарта. "a.size()" указан как "(Примечание A)", что говорит о том, что "Эти записи... должны иметь постоянную сложность".
В разделе 21.3 говорится, что строки соответствуют требованиям последовательности (23.1), ipso facto, size() - постоянное время.
STL гарантирует производительность как минимум O(N) для контейнеров, однако многие контейнеры, включая std::string, могут реализовать это как O(1) и будут. Обычно он либо возвращает простую переменную, либо делает что-то вроде _End - _Begin и возвращает это.
Сложность size() должен следовать за "примечанием А". Значит, он должен иметь постоянную сложность, то есть O(1). Хотя я не уверен в реализации, но итераторы в C++ действительно имеют связанные операции, такие как begin() и end(), которые указывают на контейнеры STL. Эти операции имеют постоянную временную сложность, поскольку они являются требованиями контейнера. Это означает, чтоbegin() - end()также имеет постоянную сложность. Это значит,size() является операцией O(1).
size_type __CLR_OR_THIS_CALL size() const
{ // return length of sequence
return (_Mysize);
}
Так что в конечном итоге это может быть так, но вы никогда не можете быть уверены.