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

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

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

Эффективность строкового класса 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 ничего не знает ни о максимальном размере вашей строки, ни о том, как часто вы будете с ней соединяться. У вас могут быть эти знания и вы можете делать что-то, основываясь на этой информации. Это приведет к меньшему количеству перераспределений.
• Вы будете управлять буферами вручную, чтобы быть уверенным, что вы не скопируете всю строку в новые буферы, если вы этого не хотите.
• Вы можете использовать стек для своих буферов вместо кучи, что намного эффективнее.
• Оператор строка + создаст новый строковый объект и, следовательно, вернет его, используя новый буфер.

Соображения по реализации:

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

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

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

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

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

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

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

a + " : " + c

Затем он создает временные объекты, даже если компилятор может удалить некоторые копии возвращаемых значений. Это связано с тем, что в последовательно вызываемом operator+элементе неизвестно, ссылается ли ссылочный параметр на именованный объект или на временный объект, возвращенный из вспомогательного 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 (дополняя семантику копирования). ) и ссылки на rvalue в качестве экспериментального дополнения. Это позволяет выяснить, ссылается ли параметр на временный или нет. Это сделает такие дополнения удивительно быстрыми, так как все вышеперечисленное будет в одном «конвейере добавления» без копий.

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

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

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

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

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

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

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

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

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

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

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

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

Я предпочитаю std :: ostringstream для сложной конкатенации.

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

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

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

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

Вероятно, лучшая производительность, если вы предварительно выделите (зарезервируете) пространство в результирующей строке.

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Использование:

std::string merged = concat("This ", "is ", "a ", "test!");

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

Хитрость заключается в том, чтобы в начале выделить только одно большое выделение.

в

https://github.com/pedro-vicente/table-string

Контрольные точки

Для Visual Studio 2015 отладочная сборка x86, значительное улучшение по сравнению с C ++ std :: string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |  

Вы можете попробовать это с резервированием памяти для каждого элемента:

namespace {
template<class C>
constexpr auto size(const C& c) -> decltype(c.size()) {
  return static_cast<std::size_t>(c.size());
}

constexpr std::size_t size(const char* string) {
  std::size_t size = 0;
  while (*(string + size) != '\0') {
    ++size;
  }
  return size;
}

template<class T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) noexcept {
  return N;
}
}

template<typename... Args>
std::string concatStrings(Args&&... args) {
  auto s = (size(args) + ...);
  std::string result;
  result.reserve(s);
  return (result.append(std::forward<Args>(args)), ...);
}