Por que o vetor não é um contêiner STL?

O item 18 do livro de Scott Meyers STL Efetivo: 50 Formas Específicas de Melhorar o Uso da Biblioteca de Modelos Padrão diz para evitar o vector já que ele não é um contêiner STL e realmente não contém bools.

O seguinte código:

 vector  v; bool *pb =&v[0]; 

não irá compilar, violando o requisito de contêineres STL.

Erro:

 cannot convert 'std::vector::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization 

vector::operator [] tipo de retorno vector::operator [] deve ser T &, mas por que é um caso especial para o vector ?

O que o vector realmente consiste?

O item ainda diz:

 deque v; // is a STL container and it really contains bools 

Isso pode ser usado como alternativa ao vector ?

Alguém por favor pode explicar isso?

Por razões de otimização de espaço, o padrão C ++ (já em C ++ 98) explicitamente chama vector como um contêiner padrão especial onde cada bool usa apenas um bit de espaço ao invés de um byte como um bool normal ( implementando uma espécie de “bitset dynamic”). Em troca dessa otimização, ela não oferece todos os resources e interface de um contêiner padrão normal.

Neste caso, uma vez que você não pode pegar o endereço de um bit dentro de um byte, coisas como operator[] não podem retornar um bool& mas, em vez disso, retornar um object proxy que permita manipular o bit específico em questão. Como este object proxy não é bool& , você não pode atribuir seu endereço a um bool* como faria com o resultado de tal chamada de operador em um contêiner “normal”. Por sua vez, isso significa que bool *pb =&v[0]; não é um código válido.

Por outro lado, o deque não possui tal especialização, então cada bool pega um byte e você pode pegar o endereço do valor retornado pelo operator[] .

Finalmente, note que a implementação da biblioteca padrão do MS é (sem dúvida) sub-ótima, pois usa um pequeno tamanho de fragment para deques, o que significa que usar o deque como substituto nem sempre é a resposta correta.

vector contém valores booleanos em formato compactado usando apenas um bit para o valor (e não 8 como os arrays bool [] fazem). Não é possível retornar uma referência a um bit em c ++, portanto, há um tipo de ajuda especial, “bit reference”, que fornece a você uma interface para algum bit na memory e permite usar operadores padrão e conversões.

O problema é que o vector retorna um object de referência de proxy em vez de uma referência verdadeira, de modo que o código de estilo C ++ 98 bool * p = &v[0]; não compilará. No entanto, o moderno C ++ 11 com auto p = &v[0]; pode ser feito para compilar se o operator& também retorna um object ponteiro do proxy . Howard Hinnant escreveu um post no blog detalhando as melhorias algorítmicas ao usar tais referências de proxy e pointers.

Scott Meyers tem um longo Item 30 em Mais Eficaz C ++ sobre classs proxy. Você pode percorrer um longo caminho para imitar os tipos internos: para qualquer tipo T , um par de proxies (por exemplo, reference_proxy e iterator_proxy ) pode ser feito de modo consistente no sentido de que reference_proxy::operator&() e iterator_proxy::operator*() são inversos um do outro.

No entanto, em algum momento, é necessário mapear os objects proxy para se comportarem como T* ou T& . Para proxies iteradores, pode-se sobrecarregar o operator->() e acessar a interface do template T sem reimplementar toda a funcionalidade. No entanto, para proxies de referência, você precisaria sobrecarregar o operator.() , E isso não é permitido no C ++ atual (embora Sebastian Redl tenha apresentado tal proposta no BoostCon 2013). Você pode fazer um work-around detalhado como um membro .get() dentro do proxy de referência, ou implementar toda a interface de T dentro da referência (isto é o que é feito para o vector::bit_reference ), mas isso ou perder a syntax interna ou introduzir conversões definidas pelo usuário que não tenham semântica incorporada para conversões de tipo (você pode ter no máximo uma conversão definida pelo usuário por argumento).

TL; DR : sem vector não é um contêiner porque o Padrão requer uma referência real, mas pode ser feito para se comportar quase como um contêiner, pelo menos muito mais próximo com C ++ 11 (automático) do que em C ++ 98

Isto vem de http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool Esta é uma versão especializada do vetor, que é usada para elementos do tipo bool e otimiza o espaço.

Ele se comporta como a versão não especializada do vetor, com as seguintes alterações:

  • O armazenamento não é necessariamente uma matriz de valores de bool, mas a implementação da biblioteca pode otimizar o armazenamento para que cada valor seja
    armazenado em um único bit.
  • Elementos não são construídos usando o object alocador, mas seu valor é definido diretamente no bit apropriado no armazenamento interno.
  • Função de membro flip e uma nova assinatura para swap de membro.
  • Um tipo de membro especial, referência, uma class que acessa bits individuais no armazenamento interno do contêiner com uma interface que
    emula uma referência bool. Por outro lado, o tipo de membro const_reference é um bool simples.
  • Os tipos de ponteiro e iterador usados ​​pelo contêiner não são necessariamente nem pointers nem iteradores em conformidade, embora
    deve simular a maior parte do seu comportamento esperado.

Essas alterações fornecem uma interface peculiar para essa especialização e favorecem a otimização da memory durante o processamento (que pode ou não atender às suas necessidades). Em qualquer caso, não é possível instanciar o modelo não especializado de vetor para bool diretamente. Soluções alternativas para evitar esse intervalo de usar um tipo diferente (char, unsigned char) ou contêiner (como deque) para usar tipos de invólucro ou ainda especializar-se para tipos de alocador específicos.

bitset é uma class que fornece uma funcionalidade semelhante para matrizes de bits de tamanho fixo.

Veja como isso é implementado. o STL é construído amplamente em modelos e, portanto, os headers contêm o código que eles usam.

por exemplo, veja a implementação stdc ++ aqui .

também interessante, mesmo que não seja um vetor de bit conformador stl é o llvm :: BitVector daqui .

A essência do llvm::BitVector é uma class aninhada chamada reference e sobrecarga adequada do operador para fazer com que o BitVector se comporte semelhante ao vector com algumas limitações. O código abaixo é uma interface simplificada para mostrar como o BitVector oculta uma class chamada reference para fazer com que a implementação real quase se comporte como uma matriz real de bool sem usar 1 byte para cada valor.

 class BitVector { public: class reference { reference &operator=(reference t); reference& operator=(bool t); operator bool() const; }; reference operator[](unsigned Idx); bool operator[](unsigned Idx) const; }; 

este código aqui tem boas propriedades:

 BitVector b(10, false); // size 10, default false BitVector::reference &x = b[5]; // that's what really happens bool y = b[5]; // implicitly converted to bool assert(b[5] == false); // converted to bool assert(b[6] == b[7]); // bool operator==(const reference &, const reference &); b[5] = true; // assignment on reference assert(b[5] == true); // and actually it does work. 

Este código realmente tem uma falha, tente executar:

 std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator 

não funcionará porque assert( (&b[5] - &b[3]) == (5 - 3) ); irá falhar (dentro de llvm::BitVector )

esta é a versão llvm muito simples. std::vector também tem iteradores de trabalho. assim, a chamada for(auto i = b.begin(), e = b.end(); i != e; ++i) funcionará. e também std::vector::const_iterator .

No entanto, ainda existem limitações no std::vector que faz com que ele se comporte de maneira diferente em alguns casos.

Muitos consideram a especialização vector como um erro.

Em um artigo “Deprecating Vestigial Library Parts in C ++ 17”
Há uma proposta para reconsiderar a especialização parcial vetorial .

Existe uma longa história de especialização parcial de bool de std :: vector não satisfazendo os requisitos de contêiner e, em particular, seus iteradores não satisfazem os requisitos de um iterador de access random. Uma tentativa anterior de descontinuar este contêiner foi rejeitada para C ++ 11, N2204 .


Uma das razões para a rejeição é que não está claro o que significaria reprovar uma especialização particular de um modelo. Isso poderia ser resolvido com uma redação cuidadosa. A questão maior é que a especialização (compactada) do vetor oferece uma otimização importante que os clientes da biblioteca padrão genuinamente buscam, mas que não estariam mais disponíveis. É improvável que consigamos depreciar essa parte do padrão até que uma instalação de substituição seja proposta e aceita, como o N2050 . Infelizmente, não há tais propostas revisadas atualmente sendo oferecidas ao Grupo de Trabalho de Evolução da Biblioteca.