Concatenação de string eficiente em C ++

StackOverflow https://stackoverflow.com/questions/611263

Pergunta

Ouvi algumas pessoas expressando preocupações com 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 no C ++?

Foi útil?

Solução

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 += em vez disso.

Agora, depois desse aviso, responderei sua pergunta real ...

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

Você poderia garantir eficiência e tem maior controle você mesmo fazendo concatenação manualmente por meio de funções internas.

Por que o operador+ 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 +, não é eficiente.

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

  • Você garante a eficiência em vez de confiar em um delegado para fazê -lo com eficiência para você
  • A classe STD :: String não sabe nada sobre o tamanho máximo da sua string, nem com que frequência você concorda com ela. Você pode ter esse conhecimento e pode fazer as coisas com base em ter essas informações. Isso levará a menos re-alocações.
  • Você estará controlando os buffers manualmente para ter certeza de que não copiará a string inteira para novos buffers quando não deseja que isso aconteça.
  • Você pode usar a pilha para seus buffers, em vez do heap, o que é muito mais eficiente.
  • O operador String + criará um novo objeto String e o retornará, 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 corda é grande o suficiente para que você não precise re-alocar dados
  • Use strcpy em vez de strcat para que você não precise iterar ao longo do comprimento da string para encontrar o final da string.

Estrutura de dados de corda:

Se você precisar de concatenações muito rápidas, considere usar um estrutura de dados de corda.

Outras dicas

Reserve seu espaço final antes e use o método Apênd com um buffer. Por exemplo, diga que você espera que seu comprimento final da 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é -alocam memória para minimizar as realocações - basta usar operator+= nesse caso. E se você fizer isso manualmente, algo assim ou mais

a + " : " + c

Em seguida, está criando temporários - mesmo que o compilador possa eliminar algumas cópias de valor de retorno. Isso porque em um chamado sucessivamente operator+ Não sabe se o parâmetro de referência faz referência a um objeto nomeado ou um temporário devolvido de um submarino operator+ invocação. 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 deixar a ligação clara. Coloquei os argumentos diretamente após a declaração de função usada para clareza. Abaixo disso, mostro qual a expressão resultante então é:

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

Agora, nessa adição, tmp1 é o que foi devolvido pela primeira chamada para o operador+ 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 == <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! Então o compilador tem Para copiar o argumento em uma nova string e anexar a isso e devolvê -la do corpo de operator+. Não pode levar a memória de um temporário e anexar a isso. Quanto maior a expressão é, mais cópias das cordas precisam ser feitas.

O próximo Visual Studio e o GCC suportarão C ++ 1x's mover semântica (complementando Copie semântica) e referências de 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, pois todas as opções acima acabarão em uma "linha de adição" sem cópias.

Se for um gargalo, você ainda pode fazer

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

o append Chamadas anexam o argumento a *this e depois devolver uma referência a si mesma. 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, simplesmente não importa. Basta escrever seu código, felizmente inconsciente de como exatamente o operador funciona e apenas toma o assunto com suas próprias mãos se se tornar um gargalo aparente.

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

Talvez STD :: StringStream?

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

Dentro C ++ imperfeito, Matthew Wilson apresenta um dinâmico String concatenator que pré-compra 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 idéia foi implementado no STLPORT STD :: String Implementation - que não está em conformidade com o padrão devido a esse hack preciso.

std::string operator+ aloca uma nova corda e copia as duas seqüências de operando todas as vezes. Repita muitas vezes e fica caro, O (n).

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

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

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ê deseja produzir grandes cordas para uma GUI, pode ser que o que você está usando pode lidar com as cordas em pedaços melhor do que como uma corda grande (por exemplo, concatenando texto em um editor de texto - geralmente eles mantêm linhas como separadas estruturas).

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

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

Uma variedade simples de caracteres, encapsulada em uma classe que acompanha o tamanho da matriz e o número de bytes alocados é o mais rápido.

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

no

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

Benchmarks

Para o Visual Studio 2015, x86 Build, melhoria substancial em relação ao C ++ Std :: String.

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

Provavelmente o melhor desempenho se você pré-alocar espaço (reserva) na sequência 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!");
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top