Concatenação eficiente de strings em C ++

108

Eu ouvi algumas pessoas expressando preocupações sobre o operador "+" em std :: string e várias soluções alternativas para acelerar a concatenação. Algum desses é realmente necessário? Em caso afirmativo, qual é a melhor maneira de concatenar strings em C ++?

sneg
fonte
13
Basicamente, o + NÃO é um operador de concatentação (já que gera uma nova string). Use + = para concatenação.
Martin York
1
Desde C ++ 11, há um ponto importante: operator + pode modificar um de seus operandos e retorná-lo por movimento se esse operando foi passado por referência rvalue. libstdc++ faz isso, por exemplo . Portanto, ao chamar o operador + com temporários, ele pode atingir um desempenho quase tão bom - talvez um argumento a favor de padronizar para ele, por uma questão de legibilidade, a menos que haja benchmarks mostrando que é um gargalo. No entanto, uma variável padronizada append()seria ótima e legível ...
sublinhado_d

Respostas:

85

O trabalho extra provavelmente não vale a pena, a menos que você realmente precise de eficiência. Você provavelmente terá uma eficiência muito melhor simplesmente usando operator + = em vez disso.

Agora, após esse aviso, vou responder sua pergunta real ...

A eficiência da classe de string STL depende da implementação de STL que você está usando.

Você pode garantir eficiência e ter maior controle fazendo a concatenação manualmente por meio de c funções integradas.

Por que operator + não é eficiente:

Dê uma olhada nesta interface:

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)

Você pode ver que um novo objeto é retornado após cada +. Isso significa que um novo buffer é usado a cada vez. Se você estiver fazendo uma tonelada de operações extras +, isso não será eficiente.

Por que você pode torná-lo mais eficiente:

  • Você está garantindo eficiência em vez de confiar em um delegado para fazer isso de forma eficiente para você
  • a classe std :: string não sabe nada sobre o tamanho máximo de sua string, nem com que freqüência você estará concatenando com ela. Você pode ter esse conhecimento e fazer coisas com base nessas informações. Isso levará a menos realocações.
  • Você controlará os buffers manualmente para ter certeza de que não copiará a string inteira em novos buffers quando não quiser que isso aconteça.
  • Você pode usar a pilha para seus buffers em vez do heap, que é muito mais eficiente.
  • O operador string + criará um novo objeto string e o retornará usando um novo buffer.

Considerações para implementação:

  • Acompanhe o comprimento da corda.
  • Mantenha um ponteiro para o final da string e o início, ou apenas o início e use o início + o comprimento como um deslocamento para encontrar o final da string.
  • Certifique-se de que o buffer em que você está armazenando sua string seja grande o suficiente para que você não precise realocar os dados
  • Use strcpy em vez de strcat para que você não precise iterar sobre o comprimento da string para encontrar o final dela.

Estrutura de dados da corda:

Se você precisa de concatenações realmente rápidas, considere o uso de uma estrutura de dados de corda .

Brian R. Bondy
fonte
6
Nota: "STL" refere-se a uma biblioteca de código aberto completamente separada, originalmente pela HP, parte da qual foi usada como base para partes da Biblioteca C ++ do padrão ISO. "std :: string", no entanto, nunca fez parte do STL da HP, por isso é completamente errado fazer referência a "STL e" string "juntos.
James Curran
1
Eu não diria que é errado usar STL e string juntos. Consulte sgi.com/tech/stl/table_of_contents.html
Brian R. Bondy,
1
Quando a SGI assumiu a manutenção do STL da HP, ele foi adaptado para corresponder à Biblioteca Padrão (é por isso que eu disse "nunca faz parte do STL da HP"). No entanto, o originador de std :: string é o Comitê ISO C ++.
James Curran
2
Nota lateral: O funcionário da SGI que foi responsável pela manutenção do STL por muitos anos foi Matt Austern, que, ao mesmo tempo, chefiou o subgrupo de Biblioteca do Comitê de Padronização ISO C ++.
James Curran,
4
Você pode esclarecer ou dar alguns pontos sobre o porquê Você pode usar a pilha para seus buffers ao invés do heap que é muito mais eficiente. ? De onde vem essa diferença de eficiência?
h7r
76

Reserve seu espaço final antes e, em seguida, use o método append com um buffer. Por exemplo, digamos que você espera que o comprimento final da string seja de 1 milhão de caracteres:

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

while (whatever)
{
  s.append(buf,len);
}
Carlos A. Ibarra
fonte
17

Eu não me preocuparia com isso. Se você fizer isso em um loop, as strings sempre pré-alocarão a memória para minimizar as realocações - apenas use operator+=nesse caso. E se você fizer manualmente, algo assim ou mais

a + " : " + c

Então está criando temporários - mesmo se o compilador pudesse eliminar algumas cópias de valor de retorno. Isso ocorre porque em um chamado sucessivamente, operator+ele não sabe se o parâmetro de referência faz referência a um objeto nomeado ou a um temporário retornado de uma sub operator+invocação. Prefiro não me preocupar com isso antes de não ter feito o perfil primeiro. Mas vamos dar um exemplo para mostrar isso. Primeiro, introduzimos parênteses para tornar a ligação clara. Eu coloco os argumentos diretamente após a declaração da função que é usada para maior clareza. Abaixo disso, mostro qual é a expressão resultante:

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

Agora, nessa adição, tmp1é o que foi retornado pela primeira chamada ao operador + com os argumentos mostrados. Assumimos que o compilador é realmente inteligente e otimiza a cópia do valor de retorno. Portanto, terminamos com uma nova string que contém a concatenação de ae " : ". Agora, isso acontece:

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

Compare isso com o seguinte:

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

Ele está usando a mesma função para uma string temporária e para uma string nomeada! Portanto, o compilador precisa copiar o argumento em uma nova string e anexar a ela e retorná-la do corpo de operator+. Não pode tirar a memória de um temporário e anexar a isso. Quanto maior a expressão, mais cópias de strings precisam ser feitas.

Em seguida, o Visual Studio e o GCC oferecerão suporte à semântica de movimentação de c ++ 1x (complementando a semântica de cópia ) e referências rvalue como uma adição experimental. Isso permite descobrir se o parâmetro faz referência a um temporário ou não. Isso tornará essas adições incrivelmente rápidas, já que todos os itens acima acabarão em um "add-pipeline" sem cópias.

Se for um gargalo, você ainda pode

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

As appendchamadas acrescentam o argumento a *thise, em seguida, retornam uma referência a si mesmas. Portanto, nenhuma cópia de temporários é feita lá. Ou, alternativamente, o operator+=pode ser usado, mas você precisaria de parênteses feios para fixar a precedência.

Johannes Schaub - litb
fonte
Eu tive que verificar se os implementadores stdlib realmente fazem isso. : P libstdc++para operator+(string const& lhs, string&& rhs)faz return std::move(rhs.insert(0, lhs)). Então, se ambos são temporários, o seu operator+(string&& lhs, string&& rhs)caso lhstem capacidade suficiente disponível só vai diretamente append(). Onde eu acho que isso corre o risco de ser mais lento do que operator+=se lhsnão tiver capacidade suficiente, pois então ele volta para rhs.insert(0, lhs), o que não só deve estender o buffer e adicionar novos conteúdos como append(), mas também precisa se deslocar ao longo do conteúdo original da rhsdireita.
sublinhado_d
A outra parte da sobrecarga em comparação com operator+=é que operator+ainda deve retornar um valor, portanto, para move()qualquer operando ao qual foi anexado. Ainda assim, acho que é uma sobrecarga bem menor (copiar alguns ponteiros / tamanhos) em comparação com copiar em profundidade a string inteira, então é bom!
underscore_d
11

Para a maioria dos aplicativos, isso simplesmente não importa. Apenas escreva seu código, felizmente sem saber como exatamente o operador + funciona, e só resolva o problema com suas próprias mãos se isso se tornar um aparente gargalo.

Pesto
fonte
7
Claro que não vale a pena na maioria dos casos, mas isso realmente não responde à sua pergunta.
Brian R. Bondy,
1
sim. concordo que apenas dizer "perfil e otimizar" pode ser colocado como comentário sobre a questão :)
Johannes Schaub - litb
6
Tecnicamente, ele perguntou se eles são "necessários". Eles não são, e isso responde a essa pergunta.
Samantha Branham
É justo, mas é definitivamente necessário para algumas aplicações. Portanto, nessas aplicações, a resposta se reduz a: 'faça justiça com as suas próprias mãos'
Brian R. Bondy,
4
@Pesto Existe uma noção pervertida no mundo da programação de que o desempenho não importa e podemos simplesmente ignorar o negócio todo porque os computadores estão cada vez mais rápidos. O fato é que não é por isso que as pessoas programam em C ++ e não é por isso que postam perguntas no estouro de pilha sobre concatenação de strings eficiente.
MrFox
7

Ao contrário do .NET System.Strings, std :: strings do C ++ são mutáveis ​​e, portanto, podem ser construídas por meio de concatenação simples tão rápido quanto por meio de outros métodos.

James Curran
fonte
2
Especialmente se você usar reserve () para tornar o buffer grande o suficiente para o resultado antes de começar.
Mark Ransom
acho que ele está falando sobre operador + =. também está concatenando, embora seja um caso degenerado. james era um vc ++ mvp, então espero que ele tenha alguma pista de c ++: p
Johannes Schaub - litb
1
Não duvido por um segundo que ele tenha amplo conhecimento em C ++, apenas que houve um mal-entendido sobre a questão. A pergunta feita sobre a eficiência do operador + que retorna novos objetos de string cada vez que é chamado e, portanto, usa novos buffers de char.
Brian R. Bondy,
1
sim. mas aí ele perguntou para o caso do operador + é lento, qual a melhor forma é fazer uma concatenação. e aqui o operador + = entra em jogo. mas concordo que a resposta de James é um pouco curta. faz parecer que todos nós poderíamos usar operator + e é altamente eficiente: p
Johannes Schaub - litb
@ BrianR.Bondy operator+não precisa retornar uma nova string. Os implementadores podem retornar um de seus operandos, modificado, se esse operando foi passado pela referência rvalue.libstdc++ faz isso, por exemplo . Portanto, ao chamar operator+com temporários, ele pode atingir o mesmo ou quase tão bom desempenho - o que pode ser outro argumento a favor do inadimplemento, a menos que haja benchmarks que mostrem que isso representa um gargalo.
sublinhado_d
4

No Imperfect C ++ , Matthew Wilson apresenta um concatenador de string dinâmico que pré-calcula o comprimento da string final para ter apenas uma alocação antes de concatenar todas as partes. Também podemos implementar um concatenador estático brincando com modelos de expressão .

Esse tipo de ideia foi implementado na implementação STLport std :: string - que não está em conformidade com o padrão por causa deste hack preciso.

Luc Hermitte
fonte
Glib::ustring::compose()das ligações glibmm para o GLib faz isso: estima reserve()es o comprimento final com base na string de formato fornecida e os varargs, então append()s cada (ou sua substituição formatada) em um loop. Imagino que seja uma forma bastante comum de trabalhar.
sublinhado_d
4

std::string operator+aloca uma nova string e sempre copia as duas strings de operandos. repita muitas vezes e fica caro, O (n).

std::string appende, operator+=por outro lado, aumente a capacidade em 50% sempre que a corda precisar crescer. O que reduz significativamente o número de alocações de memória e operações de cópia, O (log n).

Timmerov
fonte
Não tenho certeza de por que isso foi rejeitado. O valor de 50% não é exigido pelo padrão, mas IIRC isso ou 100% são medidas comuns de crescimento na prática. Tudo o mais nesta resposta parece inquestionável.
sublinhado_d
Meses depois, suponho que não seja tão preciso, já que foi escrito muito depois do lançamento do C ++ 11, e sobrecargas de operator+onde um ou ambos os argumentos são passados ​​pela referência rvalue podem evitar a alocação de uma nova string por concatenação no buffer existente de um dos operandos (embora eles possam ter que realocar se tiver capacidade insuficiente).
underscore_d
2

Para cordas pequenas, isso não importa. Se você tiver strings grandes, é melhor armazená-las como estão em vetor ou em alguma outra coleção como partes. E adapte seu algoritmo para trabalhar com esse conjunto de dados em vez de uma grande string.

Eu prefiro std :: ostringstream para concatenação complexa.

Mykola Golubyev
fonte
2

Como a maioria das coisas, é mais fácil não fazer algo do que fazer.

Se você deseja gerar strings grandes para uma GUI, pode ser que o que quer que você esteja produzindo possa lidar com as strings em partes melhor do que em uma string grande (por exemplo, concatenando texto em um editor de texto - geralmente eles mantêm as linhas separadas estruturas).

Se você deseja enviar para um arquivo, transmita os dados em vez de criar uma string grande e gerá-la.

Nunca achei a necessidade de tornar a concatenação mais rápida necessária se removesse a concatenação desnecessária do código lento.

Pete Kirkham
fonte
2

Provavelmente melhor desempenho se você pré-alocar (reservar) espaço na string resultante.

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

Uso:

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

Um array simples de caracteres, encapsulado em uma classe que controla o tamanho do array e o número de bytes alocados é o mais rápido.

O truque é fazer apenas uma grande alocação no início.

em

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

Benchmarks

Para Visual Studio 2015, compilação de depuração x86, melhoria substancial em relação a C ++ std :: string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |  
Pedro Vicente
fonte
1
O OP está interessado em como concatenar com eficiência std::string. Eles não estão pedindo uma classe de string alternativa.
underscore_d
0

Você pode tentar este com reservas de memória para cada item:

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)), ...);
}
voltento
fonte