Concatenação de cadeias eficiente em C ++

Eu ouvi algumas pessoas expressando preocupações sobre o operador “+” em std :: string e várias soluções alternativas para acelerar a concatenação. Alguma dessas coisas é realmente necessária? Em caso afirmativo, qual é a melhor maneira de concatenar seqüências de caracteres em C ++?

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 o operador + =.

Agora depois desse aviso, vou responder a sua pergunta real …

A eficiência da class de strings STL depende da implementação do STL que você está usando.

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

Por que o operador + não é eficiente:

Dê uma olhada nesta interface:

 template  basic_string operator+(const basic_string& s1, const basic_string& s2) 

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

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

  • Você está garantindo eficiência em vez de confiar em um delegado para fazê-lo com eficiência para você
  • a class std :: string não sabe nada sobre o tamanho máximo da sua string, nem com que frequência você estará concatenando nela. Você pode ter esse conhecimento e pode fazer as coisas com base em ter essa informação. Isso levará a menos realocações.
  • Você estará controlando os buffers manualmente para ter certeza de que não copiará toda a string 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.
  • string + operator irá criar um novo object string e retorná-lo, portanto, usando um novo buffer.

Considerações para implementação:

  • Acompanhe o comprimento da string.
  • 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.
  • Verifique se o buffer em que você está armazenando sua string é 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 da string.

Estrutura de dados de corda:

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

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

 std::string s; s.reserve(1000000); while (whatever) { s.append(buf,len); } 

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

 a + " : " + c 

Então está criando temporárias – mesmo se o compilador puder eliminar algumas cópias de valor de retorno. Isso porque, em um operator+ sucessivamente chamado operator+ ele não sabe se o parâmetro de referência faz referência a um object nomeado ou a um retorno temporário de um suboperante operator+ invocação. Eu prefiro não me preocupar com isso antes de não ter perfilado primeiro. Mas vamos dar um exemplo para mostrar isso. Primeiro introduzimos parênteses para tornar a binding clara. Eu coloco os argumentos diretamente após a declaração de function que é usada para maior clareza. Abaixo disso, mostro o que é 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 para operator + com os argumentos mostrados. Assumimos que o compilador é realmente inteligente e otimiza a cópia do valor de retorno. Então acabamos com uma nova string que contém a concatenação de a e " : " . Agora isso acontece:

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

Compare isso com o seguinte:

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

Está usando a mesma function para um temporário e para uma string nomeada! Portanto, o compilador tem que copiar o argumento em uma nova string e anexá-lo ao corpo do operator+ . Não pode tirar a memory de um temporário e append a isso. Quanto maior a expressão, mais cópias de strings devem ser feitas.

O próximo Visual Studio e o GCC suportarão a semântica de movimentação do c ++ 1x (complementando a semântica de cópia ) e as referências de valor como uma adição experimental. Isso permite descobrir se o parâmetro faz referência a um temporário ou não. Isso fará com que tais acréscimos sejam surpreendentemente rápidos, já que todos os itens acima acabarão em um “add-pipeline” sem cópias.

Se for um gargalo, você ainda pode fazer

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

As chamadas anexadas acrescentam o argumento a *this e, em seguida, retornam uma referência para 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 corrigir a precedência.

Para a maioria das aplicações, isso não importa. Simplesmente escreva seu código, felizmente ignorando como exatamente o operador + funciona, e apenas tome o assunto em suas próprias mãos se isso se tornar um gargalo aparente.

Ao contrário do .NET System.Strings, as cadeias de caracteres do C ++ são mutáveis ​​e, portanto, podem ser criadas por meio de concatenação simples tão rapidamente quanto através de outros methods.

talvez std :: stringstream em vez disso?

Mas eu concordo com o sentimento de que você provavelmente deve mantê-lo sustentável e compreensível e, em seguida, perfil para ver se você está realmente tendo problemas.

Em Imperfect C ++ , Matthew Wilson apresenta um concatenador de cadeias dinâmicas que pré-calcula o comprimento da cadeia final para ter apenas uma alocação antes de concatenar todas as partes. Também podemos implementar um concatenador estático jogando 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 devido a esse hack preciso.

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

std::string append e operator+= por outro lado, aumenta a capacidade em 50% toda vez que a string precisa crescer. O que reduz significativamente o número de alocações de memory e operações de cópia, O (log n).

Para pequenas seqüências, não importa. Se você tiver grandes strings, é melhor armazená-los como estão em vetor ou em alguma outra coleção como partes. E addapt seu algoritmo para trabalhar com esse dataset em vez da única cadeia grande.

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

Como na maioria das coisas, é mais fácil não fazer algo do que fazê-lo.

Se você quiser produzir strings grandes para uma GUI, pode ser que o que você está enviando possa manipular as strings em pedaços melhor do que como uma string grande (por exemplo, concatenando texto em um editor de texto – geralmente eles mantêm linhas separadas estruturas).

Se você deseja produzir em um arquivo, transmita os dados em vez de criar uma string grande e gerar isso.

Eu nunca encontrei a necessidade de tornar a concatenação mais rápida se eu removesse concatenações desnecessárias do código lento.

Um array simples de caracteres, encapsulado em uma class 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.

a

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

Referências

Para o Visual Studio 2015, compilation de debugging x86, melhoria substancial sobre C ++ std :: string.

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