Эффективная конкатенация строк в C ++

Question

Я слышал, как несколько человек выражали беспокойство по поводу оператора "+" в std :: string и различных обходных путей, ускоряющих объединение. Являются ли какие-либо из них действительно необходимыми? Если это так, каков наилучший способ объединения строк в C ++?

Answer 1

Дополнительная работа, вероятно, не стоит того, если вы действительно не нуждаетесь в эффективности. Вы, вероятно, получите гораздо лучшую эффективность, просто взамен используя operator + =.

Теперь, после этого заявления об отказе, я отвечу на ваш вопрос ...

Эффективность класса строки STL зависит от реализации STL, которую вы используете.

Вы можете гарантировать эффективность и , чтобы иметь больший контроль самостоятельно, выполняя конкатенацию вручную через встроенные функции c.

Почему оператор + не эффективен:

Посмотрите на этот интерфейс:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Вы можете видеть, что новый объект возвращается после каждого +. Это означает, что каждый раз используется новый буфер. Если вы делаете кучу дополнительных операций, это неэффективно.

Почему вы можете сделать его более эффективным:

• Вы гарантируете эффективность, а не доверяете делегату делать это эффективно для вас
• класс std :: string ничего не знает ни о максимальном размере вашей строки, ни о том, как часто вы будете к ней присоединяться. Вы можете обладать этими знаниями и делать что-то, основываясь на этой информации. Это приведет к меньшему перераспределению.
• Вы будете управлять буферами вручную, так что вы можете быть уверены, что не скопируете всю строку в новые буферы, если не хотите, чтобы это произошло.
• Вы можете использовать стек для своих буферов вместо кучи, которая намного эффективнее.
• string + operator создаст новый строковый объект и вернет его, следовательно, используя новый буфер.

Рекомендации по внедрению:

• Отслеживайте длину строки.
• Держите указатель на конец строки и начало или просто на начало и используйте начало + длину в качестве смещения, чтобы найти конец строки.
• Убедитесь, что буфер, в котором вы храните вашу строку, достаточно большой, чтобы вам не нужно было перераспределять данные
• Используйте strcpy вместо strcat, чтобы вам не приходилось перебирать длину строки, чтобы найти конец строки.

Структура данных веревки:

Если вам нужны действительно быстрые объединения, рассмотрите возможность использования структуры данных веревки .

Answer 2

Зарезервируйте ваш последний пробел раньше, затем используйте метод добавления с буфером. Например, предположим, что вы ожидаете, что ваша конечная длина строки составит 1 миллион символов:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Answer 3

Я бы не беспокоился об этом. Если вы делаете это в цикле, строки всегда будут предварительно выделять память, чтобы минимизировать перераспределение - просто используйте operator+= в этом случае. И если вы делаете это вручную, что-то вроде этого или дольше

a + " : " + c

Затем он создает временные файлы, даже если компилятор может исключить некоторые копии возвращаемых значений. Это связано с тем, что в последовательно вызываемом operator+ он не знает, ссылается ли ссылочный параметр на именованный объект или на временное значение, возвращаемое из вызова sub operator+. Я предпочел бы не беспокоиться об этом, прежде чем не будет профилировать в первую очередь. Но давайте возьмем пример для демонстрации этого. Сначала мы вводим скобки, чтобы сделать привязку понятной. Я помещаю аргументы непосредственно после объявления функции, которое используется для ясности. Ниже я покажу, каково тогда полученное выражение:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Теперь, в этом добавлении, tmp1 - это то, что было возвращено первым вызовом оператора + с указанными аргументами. Мы предполагаем, что компилятор действительно умен и оптимизирует копию возвращаемого значения. Таким образом, мы получаем одну новую строку, которая содержит объединение a и " : ". Теперь это происходит:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Сравните это со следующим:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

Он использует одну и ту же функцию для временной и именованной строки! Таким образом, компилятор имеет , чтобы скопировать аргумент в новую строку, добавить к нему и вернуть его из тела operator+. Он не может взять временную память и добавить к этому. Чем больше выражение, тем больше копий строк должно быть сделано.

Далее Visual Studio и GCC будут поддерживать семантику перемещения c ++ 1x (дополняющую семантику копирования ) и ссылки на значения в качестве экспериментального дополнения. Это позволяет выяснить, является ли параметр временным или нет. Это сделает такие добавления удивительно быстрыми, так как все вышеперечисленное закончится в одном «add-pipe» без копий.

Если это оказывается узким местом, вы все равно можете сделать

 std::string(a).append(" : ").append(c) ...

Вызовы append добавляют аргумент к *this и затем возвращают ссылку на себя. Таким образом, там нет копирования временных файлов. Или, в качестве альтернативы, можно использовать operator+=, но для исправления приоритета вам потребуются ужасные скобки.

Answer 4

Для большинства приложений это просто не имеет значения. Просто напишите свой код, блаженно не зная, как именно работает оператор +, и возьмите дело в свои руки, только если оно станет очевидным узким местом.

Answer 5

В отличие от .NET System.Strings, std :: strings в C ++ являются изменяемыми и поэтому могут быть созданы с помощью простой конкатенации так же быстро, как и другими методами.

Answer 6

возможно вместо std :: stringstream?

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

Answer 7

В Несовершенный C ++ , Мэтью Уилсон представляет динамический строковый конкатенатор, который предварительно вычисляет длину финальной строки, чтобы иметь только одно распределение перед объединением всех частей. Мы также можем реализовать статический конкатенатор, играя с шаблонами выражений .

Такая идея была реализована в реализации STLport std :: string - которая не соответствует стандарту из-за этого точного хака.

Answer 8

std::string operator+ выделяет новую строку и каждый раз копирует две строки операндов. повторить много раз, и это становится дорогим, O (n).

std::string append и operator+=, с другой стороны, увеличивайте пропускную способность на 50% каждый раз, когда нить должна расти. Что значительно сокращает количество выделенных памяти и операций копирования, O (log n).

Answer 9

Как и в большинстве случаев, легче не делать что-либо, чем делать это.

Если вы хотите выводить большие строки в графический интерфейс, может случиться так, что все, что вы выводите, может обрабатывать строки по частям лучше, чем как большая строка (например, объединяя текст в текстовом редакторе - обычно они сохраняют линии как отдельные структуры).

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

Я никогда не считал необходимым ускорять конкатенацию, если я удалял ненужную конкатенацию из медленного кода.

Answer 10

Для маленьких струн это не имеет значения. Если у вас есть большие строки, лучше хранить их как векторные или в какой-либо другой коллекции как части. И добавьте ваш алгоритм для работы с таким набором данных вместо одной большой строки.

Я предпочитаю std :: ostringstream для сложного объединения.