Que desempenho podemos esperar do c_str () do std :: string? Sempre tempo constante?

13

Ultimamente, tenho feito algumas otimizações necessárias. Uma coisa que venho fazendo é mudar alguns fluxos de ostring -> sprintfs. Estou correndo um monte de std :: strings para uma matriz de estilo ac, ala

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

Acontece que a implementação std :: string :: c_str () da Microsoft é executada em tempo constante (apenas retorna um ponteiro interno). Parece que libstdc ++ faz o mesmo . Sei que o std não garante o c_str, mas é difícil imaginar outra maneira de fazer isso. Se, por exemplo, eles copiassem para a memória, teriam que alocar memória para um buffer (deixando o chamador destruí-lo - NÃO faz parte do contrato STL) OU teriam que copiar para uma estática interna buffer (provavelmente não é seguro para threads e você não tem garantias de vida útil). Portanto, simplesmente retornar um ponteiro para uma sequência terminada nula mantida internamente parece ser a única solução realista.

c++ performance strings Doug T.
fonte

Respostas:

9

Se bem me lembro, o padrão permite string::c_str()retornar praticamente qualquer coisa que satisfaça:

  • Armazenamento que é grande o suficiente para o conteúdo da sequência e o final NULL
  • Deve ser válido até que um membro não const do stringobjeto especificado seja chamado

Portanto, na prática, isso significa um ponteiro para o armazenamento interno; pois não há como rastrear externamente a vida útil do ponteiro retornado. Eu acho que sua otimização é segura para assumir que este é (pequeno) tempo constante.

Em uma nota relacionada, se a formatação de cadeia de caracteres é limitadora de desempenho; você pode ter mais sorte adiando a avaliação até que seja absolutamente necessário com algo como o Boost.Phoenix .

Boost.Format Acredito que adia a formatação internamente até que o resultado seja necessário, e você pode usar o mesmo objeto de formato repetidamente sem analisar novamente a cadeia de formatação, que eu achei que fazia uma diferença significativa no log de alta frequência.

rvalue
fonte
2
Pode ser possível para uma implementação criar um buffer interno novo ou secundário - grande o suficiente para adicionar ao terminador nulo. Mesmo que c_strseja um método const (ou pelo menos tenha uma sobrecarga const - eu esqueço qual), isso não altera o valor lógico, portanto pode ser uma razão para isso mutable. Ele iria quebrar ponteiros de outras chamadas para c_str, a não ser que tais indicações devem referir-se a mesma seqüência lógica (então não há nenhuma nova razão para realocar - já deve ser um terminador nulo) ou então há já deve ter sido uma chamada para um não -const no meio.
Steve314
Se isso realmente for válido, as c_strchamadas podem ser O (n) hora para a realocação e cópia. Mas também é possível que exista regras extras no padrão que eu desconheço que impediriam isso. A razão que eu sugiro-lo - as chamadas c_strnão são realmente concebido para ser comum AFAIK, por isso não pode ser considerado importante para garantir que eles são rápidos - evitando que byte extra de armazenamento para um terminador nulo normalmente desnecessário em stringcasos que não utilização c_strpode tomaram precedência.
Steve314
Boost.Formatinternamente passa por fluxos que internamente passam por sprintfuma sobrecarga bastante grande. A documentação diz que é cerca de 8 vezes mais lento que o normal sprintf. Se você deseja desempenho e segurança de tipo, tente Boost.Spirit.Karma.
Jan Hudec
Boost.Spirit.Karmaé uma boa dica para desempenho, mas tenha em atenção que ela possui uma metodologia muito diferente que pode ser complicada para adaptar o printfcódigo de estilo existente (e os codificadores). Eu fiquei bastante preso Boost.Formatporque nossa E / S é assíncrona; mas um grande fator é que posso convencer meus colegas a usá-lo de forma consistente (ainda permite qualquer tipo com ostream<<sobrecarga - o que evita o .c_str()debate) Os números de desempenho do Karma .
Rvalue
23

No padrão c ++ 11 (estou lendo a versão N 3290), o capítulo 21.4.7.1 fala sobre o método c_str ():

const charT* c_str() const noexcept; const charT* data() const noexcept;

Retorna: Um ponteiro p tal que p + i == & operador para cada i em [0, tamanho ()].
Complexidade: tempo constante.
Requer: O programa não deve alterar nenhum dos valores armazenados na matriz de caracteres.

Então, sim: a complexidade do tempo constante é garantida pelo padrão.

Acabei de verificar o padrão c ++ 03, e ele não possui esses requisitos, nem informa a complexidade.

BЈовић
fonte
8

Em teoria, o C ++ 03 não exige isso e, portanto, a string pode ser uma matriz de caracteres em que a presença do terminador nulo é adicionada exatamente no momento em que c_str () é chamado. Isso pode exigir uma realocação (não viola a constância, se o ponteiro privado interno for declarado como mutable).

O C ++ 11 é mais rígido: exige custo de tempo, portanto, nenhuma realocação pode ser feita e a matriz sempre deve ser ampla o suficiente para armazenar o nulo no final. c_str (), por si só, ainda pode " ptr[size()]='\0'" garantir que o nulo esteja realmente presente. Não viola a constância da matriz, pois o intervalo [0..size())não é alterado.

Emilio Garavaglia
fonte