Является ли std :: string size () операцией O (1)?

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

Так что в конечном итоге может быть так, но никогда нельзя быть уверенным.

Да, std :: string :: size () равно O (1).

STL гарантирует производительность как минимум O (N) для контейнеров, однако многие контейнеры, включая std :: string, могут реализовать это как O (1) и будут. Обычно он либо возвращает простую переменную, либо выполняет что-то вроде _End - _Begin и возвращает это.

См. Таблицу 65 в Разделе 23.1 Стандарта. «a.size ()» отображается как «(Примечание A)», что говорит о том, что «Эти записи ... должны иметь постоянную сложность».

В разделе 21.3 говорится, что строки соответствуют требованиям последовательности (23.1), ipso facto size () является постоянным временем.

Если вы спрашиваете, имеет ли реализация MSVC string :: size () постоянную сложность, то ответ - да. Но Дон Уэйкфилд упомянул Таблицу 65 в 23.1 Стандарта C++, где говорится, что сложность size() должна соответствовать тому, что сказано в «Примечании A». Примечание A говорит:

Those entries marked ‘‘(Note A)’’ should have constant complexity.

Однако это не означает, что эти записи должен имеют постоянную сложность. В стандартах используется очень специфическая терминология, и «следует» означает, что это не обязательно.

«Примечание 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() операция имеет должна быть постоянной для всех строковых реализаций, которые не используют веревки⁽¹⁾. В стандарте нет явного требования, которое требует, чтобы операция была O(1), наиболее близким является общее требование, чтобы size()должен был постоянным временем, но это оставляет место для любых других мер сложности.

Так почему должен это O (1)?

Это происходит из-за того, что размер не может быть вычислен из содержимого самой строки. В то время как в C вы используете терминатор NUL для определения конца строки, в C++ NUL так же действителен, как и любой другой символ в строке. Поскольку размер строки не может быть вычислен на основе content⁽²⁾, он должен обрабатываться извне, независимо от фактического размера строки.

⁽¹⁾ Стандарт C++ 03 позволяет реализации использовать веревки в качестве реализации для строк, но факт в том, что ни одна из текущих реализаций стандартных библиотек не использует их.

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

Сложность size()должен соответствует примечанию A. Это означает, что должен имеет постоянную сложность, то есть O (1). Хотя я не уверен в реализации, но итераторы в C++ действительно имеют связанные операции, такие как begin () и end (), которые указывают на контейнеры STL. Эти операции имеют постоянную временную сложность, поскольку они являются требованиями контейнера. Это означает, что begin() - end() также имеет постоянную сложность. Это означает, что size() - это операция O (1).