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

Question

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

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

Answer 1

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

  

Эти записи отмечены как & # 8216; & # 8216; (Примечание A) & # 8217; & # 8217;   должен иметь постоянную сложность.

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

'Примечание 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

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

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

Answer 5

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

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

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

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

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

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);

}

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