É o tamanho std :: string) a O (1) operação (?

Question

É std :: tamanho string () a O (1) operação?

A implementação de STL que estou usando é o que se construiu em VC ++

Answer 1

Se você está perguntando se a implementação de corda :: size () do MSVC tem complexidade constante, então a resposta é sim. Mas Don Wakefield mencionado Tabela 65 em 23,1 de padrão C ++ onde diz que a complexidade do size() deve seguir o que é dito em 'Nota a'. Nota Um diz:

Essas entradas marcadas ‘‘(Nota A)’’ deve ter complexidade constante.

No entanto, isso não significa que essas entradas deve tem complexidade constante. Normas usar a terminologia muito específica, e "deve" significa que não é obrigatório.

'Nota A' foi adicionado ao padrão especificamente para apaziguar os que acreditava que size() deve ser permitido ter complexidade linear de modo que não seria necessário para manter o tamanho quando os recipientes foram modificados.

Então, você não pode confiar em size() tendo complexidade constante, mas eu não sou honesta certo se há qualquer implementações que não possuem um string::size() constante.

Answer 2

Aqui está uma maneira fácil de responder a essa pergunta para msvc ++.

escrever algum código em um projeto:

string happy;
happy.size();

Hilight a chamada .size, clique com o botão direito, ir para a definição.

No meu instalar (vs2005sp1) isso me envia para xstring: 1635, que tem esta aparência:

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

Portanto, parece que a corda tem um membro chamado _Mysize, e está apenas retornando isso.

Por outras palavras, este é um grupo O (1) aplicação.

Answer 3

Sim, std :: string :: size () é O (1).

Answer 4

Veja a Tabela 65 na Seção 23.1 da Norma. "A.size ()" está listado como "(Nota A)", que diz que "Essas entradas ... deve ter complexidade constante".

Seção 21.3 diz que as cordas estão em conformidade com os requisitos de uma sequência (23,1), ipso facto, size () é de tempo constante.

Answer 5

Para uma corda, a operação size() tem para ser constante para todas as implementações de cadeia que não use cordas ⁽¹⁾ . Não há nenhuma exigência explícita no padrão que requer a operação a ser O(1), o mais próximo é o requisito genérico que size() deve ser de tempo constante, mas que o quarto folhas para qualquer outra medida de complexidade.

Então, por que deve que seja O (1)?

Esta vem do fato de que o tamanho não pode ser calculado a partir do conteúdo da própria corda. Enquanto em C você usar um terminador NUL para determinar o fim da cadeia, em C ++ NUL é tão válida quanto qualquer outro personagem na seqüência. Uma vez que o tamanho da cadeia não pode ser calculado a partir do conteúdo ⁽²⁾ , deve ser tratada externamente, independentemente do tamanho real da cadeia.

⁽¹⁾ C ++ 03 norma permite uma implementação para uso cordas como a implementação de cordas, mas o fato é que nenhuma das implementações atuais da norma bibliotecas usá-los.

⁽²⁾ Se a aplicação utilizado cordas, a operação pode depender do tamanho por meio do número de blocos a partir da qual a corda se construiu se os blocos foram ligados através de uma lista ligada ou semelhante construir, ou se eles foram autorizados a ter tamanhos diferentes. Mas cordas não são usados ??em qualquer implementação da biblioteca padrão que eu saiba.

Answer 6

O desempenho é garantida pelo STL para ser, pelo menos, S (N) para os contentores, no entanto, muitos recipientes incluindo std :: cadeia pode implementar este como o (1) e a vontade. Normalmente ele vai quer retornar uma variável simples ou fazer algo como _END -. _Begin e retornar esse

Answer 7

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

Por isso, eventualmente, pode ser assim, mas você nunca pode ter certeza.