É lista :: size () realmente O (n)?

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

Pergunta

Recentemente, eu notei algumas pessoas mencionar que std::list::size() tem uma complexidade linear.
De acordo com a alguns fontes , este é na implementação fato dependente como o padrão não diz o que a complexidade tem que ser.
O comentário neste blog diz :

Na verdade, isso depende do que você STL estão usando. Microsoft Visual Studio V6 tamanho implementos () {return como (_size); Considerando} gcc (pelo menos em versões 3.3.2 e 4.1.0) fazê-lo como {return std :: distância (begin (), final ()); } O primeiro tem velocidade constante, a segunda tem o (N) de velocidade

  1. Assim, o meu palpite é que para o VC ++ size() multidão tem complexidade constante como Dinkumware provavelmente não terá mudado esse fato desde VC6. Am I ali?
  2. O que faz com que pareça atualmente em gcc? Se é realmente O (n), por que o desenvolvedores optar por fazê-lo?
Foi útil?

Solução

Pré-C ++ 11 resposta

Está certo que a norma não estado que a complexidade da lista :: size () deve ser - no entanto, ele recomenda que "deve ter complexidade constante" (Nota Um na Tabela 65)

.

Aqui está um artigo interessante por Howard Hinnant que explica por que algumas pessoas lista :: tamanho (pense ) deve ter o (N complexidade) (basicamente porque eles acreditam que o (1) lista :: size () lista :: splice () tem o (N) complexidade faz) e por um o (1) lista :: size ( ) é ser uma boa idéia (na opinião do autor):

Eu acho que os principais pontos do documento são:

  • Há poucas situações onde a manutenção de uma contagem interna de modo list::size() pode ser O (1) faz com que a operação de emenda para tornar-se linear
  • Existem provavelmente muitas mais situações onde alguém pode não estar cientes dos efeitos negativos que podem acontecer, porque eles chamam de O (N) size() (como seu único exemplo em que list::size() é chamado mantendo um bloqueio).
  • que, em vez de permitir size() ser O (N), no interesse de 'menor surpresa', o padrão deve requerer qualquer recipiente que implementa size() a aplicá-lo em uma junta (1) da forma. Se um recipiente não pode fazer isso, ele não deve implementar size() em tudo. Neste caso, o usuário do recipiente vai estar cientes de que size() não está disponível e se eles ainda querem ou precisam para obter o número de elementos no contêiner eles ainda podem usar container::distance( begin(), end()) para obter esse valor - mas eles vão estar completamente ciente que é uma operação o (N).

Eu acho que eu tendo a concordar com a maioria de seu raciocínio. No entanto, eu não gosto de seu aditamento proposto para as sobrecargas splice(). Ter que passar em uma n que deve ser igual a distance( first, last) para obter o comportamento correto parece ser uma receita para o difícil de diagnosticar erros.

Eu não tenho certeza o que deveria ou poderia ser feito avançar, como qualquer mudança teria um impacto significativo sobre o código existente. Mas, tal como está, acho que o código existente já é afetado - o comportamento pode ser bastante significativamente diferente de uma aplicação para outra por algo que deveria ter sido bem definida. Talvez comentário onebyone é sobre ter o tamanho 'cache' e marcado conhecido trabalho poderio / unknown bem - você começa amortizado O (1) comportamento - a única vez que você começa o (n) o comportamento é quando a lista é modificada por alguns splice () operações . A coisa agradável sobre isso é que ele pode ser feito por implementadores hoje sem uma mudança para o padrão (a menos que eu estou faltando alguma coisa).

Até onde eu sei, C ++ 0x não está mudando nada nesta área.

Outras dicas

C ++ 11 que é necessária para que qualquer recipiente padrão a operação .size() deve ser completo na complexidade "constante" (O (1)). (Tabela 96 - requisitos de contentores). Anteriormente em C ++ 03 .size() deve tem complexidade constante, mas não é necessário (ver é std :: tamanho string) a O (1) operação (? ).

A mudança no padrão é introduzido por n2923 : Especificar a complexidade do tamanho () (Revisão 1) .

No entanto, a aplicação de .size() em libstdc ++ ainda utiliza um O algoritmo (N) no gcc até 4,8: ??

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

Veja também Por que é std :: lista maior em c ++ 11? para o detalhe porque ele é mantido desta forma.

Atualização : std::list::size() é adequadamente O (1) quando se utiliza gcc 5.0 em C ++ 11 modo (ou acima).

A propósito, o .size() em libc ++ é correctamente O (1): 

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Eu tive que olhar para gcc 3.4 da lista :: tamanho antes, então eu posso dizer o seguinte:

  1. usa std :: distância (cabeça, cauda)
  2. std :: distância tem duas implementações: para tipos que satisfazem RandomAccessIterator, ele usa "cauda-cabeça", e para os tipos que simplesmente satisfazer InputIterator, ele usa um (n) algoritmo O contando com "iterator ++", a contagem até que bate a cauda dada.
  3. std :: lista não satsify RandomAccessIterator, então tamanho é O (n).

Como para o "porquê", só posso dizer que std :: lista é adequada para problemas que requerem acesso sequencial. Armazenar o tamanho como uma variável de classe iria introduzir sobrecarga em cada insert, delete, etc., e que os resíduos é uma grande falta de nenhum acordo com a intenção do STL. Se você realmente precisa de um tamanho de tempo constante (), usar std :: deque.

Eu, pessoalmente, não vejo a questão com emenda sendo O (N) como a única razão pela qual tamanho é permitido para ser O (N). Você não pagar por aquilo que você não usa é um importante lema C ++. Neste caso, mantendo o tamanho da lista requer um incremento / decréscimo extra em cada inserção / apagar se você verificar o tamanho da lista ou não. Este é um pequeno fixo em cima, mas ainda é importante a considerar.

Verificar o tamanho de uma lista é raramente necessária. Iteração do início ao fim sem se importar com o tamanho total é infinitamente mais comum.

Eu iria para o fonte ( arquivo ). Página STL da SGI diz que é permitido ter uma complexidade linear. Eu acredito que a diretriz de design que se seguiu foi para permitir a implementação lista para ser tão geral quanto possível, e, portanto, para permitir uma maior flexibilidade na utilização de listas.

Este relatório bug: [C ++ 0x] std :: list: : tamanho complexidade , capturas em excruciante detalhe o facto da aplicação em CCG 4.x é tempo linear e como a transição para a constante de tempo para C ++ 11 foi lentos (disponível em 5.0) devido à compatibilidade ABI preocupações.

A página de manual para o GCC 4.9 série inclui ainda o seguinte exclusão:

O suporte para C ++ 11 ainda é experimental, e podem mudar de maneiras incompatíveis em versões futuras.

O mesmo relatório de erro é referenciado aqui: Should std :: list :: size tem complexidade constante em C ++ 11

Se você estiver usando corretamente listas você está provavelmente não perceber qualquer diferença.

As listas são bons com estruturas de dados grandes que pretende reorganizar sem copiar, por dados que deseja manter ponteiros válidos após a inserção.

No primeiro caso, não faz diferença, no segundo eu preferiria a implementação de idade (menor) size ().

De qualquer forma std é mais sobre a correção e behavious padrão e 'friendlyness usuário' do que a velocidade crua.

Não afiliado a StackOverflow
scroll top