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

Question

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

Я использую реализацию STL, встроенную в VC ++

Answer 1

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

Эти записи, отмеченные Note ‘(Примечание A)’ ’ должен иметь постоянную сложность.

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

«Примечание A» было добавлено в стандарт специально для того, чтобы успокоить тех, кто считал, что size() должно иметь линейную сложность, поэтому нет необходимости сохранять размер при изменении контейнеров.

Так что вы не можете полагаться на size(), имеющую постоянную сложность, но я, честно говоря, не уверен, есть ли реализации, которые не имеют постоянной string::size().

Answer 2

Вот простой способ ответить на этот вопрос для 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).

Answer 3

Да, std :: string :: size () - это O (1).

Answer 4

Для строки операция size() имеет значение , которое должно быть постоянным для всех реализаций строки, которые не используют веревки ⁽¹⁾ . В стандарте нет явного требования, согласно которому операция должна быть O(1), наиболее близким является общее требование, согласно которому size() должно быть постоянным временем, но при этом остается место для любой другой меры сложности.

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

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

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