Какую производительность мы можем ожидать от std :: string's c_str ()? Всегда постоянное время?

13

В последнее время я делал некоторые необходимые оптимизации. Одна вещь, которую я делал, - это изменение некоторых ostringstreams -> sprintfs. Я sprintf'ing кучу std :: strings в массив стиля AC, аля

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

Оказывается, что реализация Microsoft std :: string :: c_str () выполняется за постоянное время (она просто возвращает внутренний указатель). Похоже, что libstdc ++ делает то же самое . Я понимаю, что std не дает никаких гарантий для c_str, но сложно представить другой способ сделать это. Если, например, они скопировали в память, им либо пришлось бы выделить память для буфера (предоставив вызывающей стороне его уничтожить - НЕ часть контракта STL) ИЛИ им пришлось бы скопировать во внутреннюю статическую память. буфер (вероятно, не потокобезопасный, и у вас нет никаких гарантий на его время жизни). Так что простой возврат указателя на внутренне поддерживаемую строку с нулевым символом в конце кажется единственным реальным решением.

c++ performance strings Дуг Т.
источник

Ответы:

9

Если я помню, стандарт позволяет string::c_str()возвращать почти все, что удовлетворяет:

  • Память, которая достаточно велика для содержимого строки и окончания NULL
  • Должен быть действительным, пока не stringбудет вызван неконстантный член данного объекта

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

С другой стороны, если форматирование строк ограничивает производительность; вам может посчастливиться отложить оценку до тех пор, пока она абсолютно не понадобится с чем-то вроде Boost.Phoenix .

Boost.Format Я полагаю, что внутреннее форматирование откладывается до тех пор, пока не потребуется результат, и вы можете использовать один и тот же объект формата несколько раз без повторного разбора строки формата, что, как я обнаружил, имеет большое значение для высокочастотной регистрации.

Rvalue
источник
2
Для реализации может быть возможным создать новый или вторичный внутренний буфер - достаточно большой, чтобы добавить нулевой терминатор. Несмотря на то, c_strчто это метод const (или, по крайней мере, имеет перегрузку const - я забыл, какой), это не меняет логическое значение, поэтому может быть причиной mutable. Это сломало бы указатели от других вызовов c_str, за исключением того, что любые такие указатели должны ссылаться на одну и ту же логическую строку (так что нет никакой новой причины для перераспределения - там уже должен быть нулевой терминатор), иначе должен был уже быть вызов не -константный метод между ними.
Steve314
Если это действительно верно, c_strвызовы могут быть O (n) время для перераспределения и копирования. Но также возможно, что в стандарте есть дополнительные правила, о которых я не знаю, которые могли бы предотвратить это. Причина, по которой я это предлагаю - вызовы на c_strсамом деле не предназначены для того, чтобы быть обычным AFAIK, поэтому может не считаться важным обеспечить их быструю работу - избегая лишнего байта памяти для обычно ненужного нулевого терминатора в stringслучаях, которые никогда не используются, c_strможет имеют приоритет.
Steve314
Boost.Formatвнутренне проходит через потоки, которые внутренне проходят, sprintfзаканчивая довольно большими накладными расходами. Документация говорит, что это примерно в 8 раз медленнее, чем обычное sprintf. Если вы хотите производительность и безопасность типов, попробуйте Boost.Spirit.Karma.
Ян Худек
Boost.Spirit.KarmaЭто хороший совет для производительности, но имейте в виду, что у него совершенно другая методология, которая может быть сложной для адаптации существующего printfкода стиля (и кодеров). Я в основном придерживался, Boost.Formatпотому что наш ввод / вывод асинхронный; но важным фактором является то, что я могу убедить своих коллег использовать его последовательно (все еще допускает любой тип с ostream<<перегрузкой - что приятно обходит стороной .c_str()дебаты). Показатели эффективности Karma .
rvalue
23

В стандарте c ++ 11 (я читаю версию N 3290) глава 21.4.7.1 говорит о методе c_str ():

const charT* c_str() const noexcept; const charT* data() const noexcept;

Возвращает: указатель p такой, что p + i == & оператор для каждого i в [0, size ()].
Сложность: постоянное время.
Требуется: Программа не должна изменять ни одно из значений, хранящихся в массиве символов.

Итак, да: сложность с постоянным временем гарантируется стандартом.

Я только что проверил стандарт C ++ 03, и он не имеет таких требований, и это не говорит о сложности.

BЈовић
источник
8

В теории C ++ 03 этого не требует, и, следовательно, строка может быть массивом char, в котором присутствие нулевого терминатора добавляется только во время вызова c_str (). Это может потребовать перераспределения (это не нарушает постоянство, если внутренний закрытый указатель объявлен какmutable ).

C ++ 11 более строгий: он требует затрат времени, поэтому перемещение не может быть выполнено, и массив всегда должен быть достаточно широким, чтобы хранить ноль в конце. c_str () сама по себе может делать " ptr[size()]='\0'", чтобы гарантировать, что значение null действительно присутствует. Это не нарушает постоянство массива, так как диапазон [0..size())не изменяется.

Эмилио Гаравалья
источник