Biblioteca de modelos padrão - Standard Template Library

Para outros usos, consulte STL .

Biblioteca padrão C ++
Containers
Biblioteca padrão C

A Standard Template Library ( STL ) é uma biblioteca de software para a linguagem de programação C ++ que influenciou muitas partes da Biblioteca Padrão C ++ . Ele fornece quatro componentes chamados algoritmos , contêineres , funções e iteradores .

O STL fornece um conjunto de classes comuns para C ++, como contêineres e matrizes associativas , que podem ser usados ​​com qualquer tipo integrado e com qualquer tipo definido pelo usuário que suporte algumas operações elementares (como cópia e atribuição). Os algoritmos STL são independentes de contêineres, o que reduz significativamente a complexidade da biblioteca.

O STL alcança seus resultados por meio do uso de modelos . Essa abordagem fornece polimorfismo de tempo de compilação que geralmente é mais eficiente do que o polimorfismo de tempo de execução tradicional . Os compiladores C ++ modernos são ajustados para minimizar as penalidades de abstração decorrentes do uso intenso do STL.

A STL foi criada como a primeira biblioteca de algoritmos genéricos e estruturas de dados para C ++, com quatro ideias em mente: programação genérica , abstração sem perda de eficiência, o modelo de computação de Von Neumann e semântica de valor .

História

Artigo principal: História da Biblioteca de Modelos Padrão

Em novembro de 1993, Alexander Stepanov apresentou uma biblioteca baseada em programação genérica ao comitê ANSI / ISO para padronização C ++. A resposta do comitê foi extremamente favorável e levou a um pedido de Andrew Koenig de uma proposta formal a tempo para a reunião de março de 1994. O comitê tinha vários pedidos de mudanças e extensões e os membros do comitê se reuniram com Stepanov e Meng Lee para ajudar a resolver os detalhes. Os requisitos para a extensão mais significativa ( contêineres associativos ) tinham que ser mostrados para serem consistentes, implementando-os totalmente, uma tarefa que Stepanov delegou a David Musser . Uma proposta recebeu a aprovação final na reunião do comitê ANSI / ISO de julho de 1994. Posteriormente, o documento 17 de Stepanov e Lee foi incorporado ao padrão de rascunho ANSI / ISO C ++ (1, partes das cláusulas 17 a 27).

As perspectivas de disseminação ampla e antecipada do STL foram consideravelmente melhoradas com a decisão da Hewlett-Packard de tornar sua implementação disponível gratuitamente na Internet em agosto de 1994. Esta implementação, desenvolvida por Stepanov, Lee e Musser durante o processo de padronização, tornou-se a base de muitas implementações oferecidas por fornecedores de compiladores e bibliotecas hoje.

Composição

Containers

O STL contém contêineres de sequência e contêineres associativos. Os contêineres são objetos que armazenam dados. Os padrão recipientes de sequências incluem , e . Os padrão recipientes associativos são , , , , , , e . Também existem adaptadores de contentores , e , que são recipientes com interface específica, utilizando outros recipientes como implementação. vectordequelistsetmultisetmapmultimaphash_sethash_maphash_multisethash_multimap queuepriority_queuestack

Recipiente Descrição
Recipientes simples
par O contêiner de pares é um contêiner associativo simples que consiste em 2 tuplas de elementos ou objetos de dados, chamados de 'primeiro' e 'segundo', nessa ordem fixa. O 'par' STL pode ser atribuído, copiado e comparado. A matriz de objetos alocados em um mapa ou hash_map (descritos abaixo) são do tipo 'par' por padrão, onde todos os 'primeiros' elementos atuam como chaves exclusivas, cada uma associada a seus 'segundos' objetos de valor.
Sequências (matrizes / listas vinculadas ): coleções ordenadas
vetor uma matriz dinâmica , como a matriz C (ou seja, capaz de acesso aleatório ) com a capacidade de se redimensionar automaticamente ao inserir ou apagar um objeto. Inserir um elemento atrás do vetor no final leva um tempo constante amortizado . A remoção do último elemento leva apenas um tempo constante, porque não ocorre nenhum redimensionamento. Inserir e apagar no início ou no meio é linear no tempo.

Existe uma especialização para o tipo bool , que otimiza o espaço, armazenando valores bool como bits.

Lista uma lista duplamente vinculada ; os elementos não são armazenados na memória contígua. Desempenho oposto de um vetor. Busca e acesso lentos (tempo linear), mas uma vez que uma posição foi encontrada, inserção e exclusão rápidas (tempo constante).
slist
 uma lista unida individualmente ; os elementos não são armazenados na memória contígua. Desempenho oposto de um vetor. Busca e acesso lentos (tempo linear), mas uma vez que uma posição foi encontrada, inserção e exclusão rápidas (tempo constante). Possui inserção e exclusão um pouco mais eficientes e usa menos memória do que uma lista duplamente vinculada, mas só pode ser iterada para frente. É implementado na biblioteca padrão C ++ como . forward_list
deque ( fila dupla ) um vetor com inserção / apagamento no início ou no final em tempo constante amortizado , porém sem algumas garantias sobre a validade do iterador após a alteração do deque.
Adaptadores de contêiner
fila Fornece interface de fila FIFO em termos de / / / operações. pushpopfrontback

Todas as operações de suporte de sequência , , , e pode ser usada para instanciar fila (por exemplo, e ). front()back()push_back()pop_front()listdeque
Fila de prioridade Fornece interface de fila de prioridade em termos de operações (o elemento com a maior prioridade está no topo). push/pop/top

Qualquer sequência de acesso aleatório que suporte operações , e pode ser usada para instanciar priority_queue (por exemplo, e ). Ele é implementado usando um heap . front()push_back()pop_back()vectordeque

Os elementos também devem oferecer suporte à comparação (para determinar qual elemento tem uma prioridade mais alta e deve ser exibido primeiro).

pilha Fornece interface de pilha LIFO em termos de operações (o último elemento inserido está no topo). push/pop/top

Todas as operações de suporte de sequência , e podem ser usadas para instanciar pilha (por exemplo , , e ). back()push_back()pop_back()vectorlistdeque
Contêineres associativos : coleções não ordenadas
definir um conjunto matemático ; inserir / apagar elementos em um conjunto não invalida os iteradores que apontam para o conjunto. Fornece operações de conjunto de união , interseção , diferença , diferença simétrica e teste de inclusão. O tipo de dados deve implementar o operador de comparação ou a função de comparação personalizada deve ser especificada; tal operador de comparação ou função de comparador deve garantir ordenação estritamente fraca , caso contrário, o comportamento é indefinido. Normalmente implementado usando uma árvore de pesquisa binária de autobalanceamento . <
multiset mesmo que um conjunto, mas permite elementos duplicados ( multiset matemático ).
mapa uma matriz associativa ; permite o mapeamento de um item de dados (uma chave) para outro (um valor). O tipo de chave deve implementar o operador de comparação ou a função de comparação personalizada deve ser especificada; tal operador de comparação ou função de comparador deve garantir ordenação estritamente fraca , caso contrário, o comportamento é indefinido. Normalmente implementado usando uma árvore de pesquisa binária de autobalanceamento. <
multimapa igual a um mapa, mas permite chaves duplicadas.
hash_set
hash_multiset
hash_map
hash_multimap 		semelhante a um conjunto, multiset, mapa ou multimap, respectivamente, mas implementado usando uma tabela hash ; as chaves não são ordenadas, mas deve existir uma função hash para o tipo de chave. Esses tipos foram deixados de fora do padrão C ++; recipientes semelhantes foram padronizados em C ++ 11 , mas com nomes diferentes ( e ). unordered_setunordered_map
Outros tipos de recipientes
bitset armazena séries de bits semelhantes a um vetor de bools de tamanho fixo. Implementa operações bit a bit e não possui iteradores. Não é uma sequência. Fornece acesso aleatório.
Valarray Outro tipo de dados de matriz, destinado ao uso numérico (especialmente para representar vetores e matrizes ); o padrão C ++ permite otimizações específicas para esse propósito pretendido. De acordo com Josuttis, valarray foi mal projetado por pessoas "que deixaram o comitê [padrão C ++] muito tempo antes de o padrão ser concluído", e bibliotecas de modelos de expressão devem ser preferidas. Uma proposta de reescrita da parte valarray do padrão neste sentido foi rejeitada, tornando-se uma permissão para implementá-la usando um modelo de expressão.

Iteradores

O STL implementa cinco tipos diferentes de iteradores . Estes são iteradores de entrada (que só podem ser usados ​​para ler uma sequência de valores), iteradores de saída (que só podem ser usados ​​para escrever uma sequência de valores), iteradores de encaminhamento (que podem ser lidos, escritos e avançar), iteradores bidirecionais (que são como iteradores diretos, mas também podem retroceder) e acesso aleatório iteração s(que pode mover-se livremente qualquer número de etapas na operação de um).

Um conceito STL fundamental é um intervalo que é um par de iteradores que designam o início e o fim da computação, e a maioria dos modelos algorítmicos da biblioteca que operam em estruturas de dados têm interfaces que usam intervalos.

É possível fazer com que os iteradores bidirecionais ajam como iteradores de acesso aleatório, portanto, avançar dez etapas poderia ser feito simplesmente avançando uma etapa em um tempo um total de dez vezes. No entanto, ter iteradores de acesso aleatório distintos oferece vantagens de eficiência. Por exemplo, um vetor teria um iterador de acesso aleatório, mas uma lista apenas um iterador bidirecional.

Os iteradores são o principal recurso que permite a generalidade do STL. Por exemplo, um algoritmo para reverter uma sequência pode ser implementado usando iteradores bidirecionais e, em seguida, a mesma implementação pode ser usada em listas, vetores e deques . Os contêineres criados pelo usuário precisam apenas fornecer um iterador que implemente uma das cinco interfaces de iterador padrão e todos os algoritmos fornecidos no STL podem ser usados ​​no contêiner.

Essa generalidade também tem um preço às vezes. Por exemplo, realizar uma pesquisa em um contêiner associativo , como um mapa ou conjunto, pode ser muito mais lento usando iteradores do que chamando funções de membro oferecidas pelo próprio contêiner. Isso ocorre porque os métodos de um contêiner associativo podem tirar proveito do conhecimento da estrutura interna, que é opaca para algoritmos que usam iteradores.

Algoritmos

Um grande número de algoritmos para realizar atividades como pesquisa e classificação são fornecidos no STL, cada um implementado para exigir um certo nível de iterador (e, portanto, funcionará em qualquer contêiner que forneça uma interface por iteradores). Algoritmos de pesquisa como e usam pesquisa binária e algoritmos de classificação exigem que o tipo de dados deve implementar o operador de comparação ou a função de comparação personalizada deve ser especificada; tal operador de comparação ou função de comparador deve garantir ordenação estritamente fraca . Além desses, algoritmos são fornecidos para fazer heap de uma gama de elementos, gerando permutações ordenadas lexicograficamente de uma gama de elementos, mesclar intervalos classificados e realizar união , interseção , diferença de intervalos classificados. binary_searchlower_bound<

Funções

O STL inclui classes que sobrecarregam o operador de chamada de função ( ). As instâncias dessas classes são chamadas de functores ou objetos de função . Os funções permitem que o comportamento da função associada seja parametrizado (por exemplo, por meio de argumentos passados ​​para o construtor do functor ) e podem ser usados ​​para manter as informações de estado por função associadas junto com a função. Visto que tanto os functores quanto os ponteiros de função podem ser chamados usando a sintaxe de uma chamada de função, eles são intercambiáveis ​​como argumentos para modelos quando o parâmetro correspondente só aparece em contextos de chamada de função. operator()

Um tipo particularmente comum de functor é o predicado . Por exemplo, algoritmos como pegam um predicado unário que opera sobre os elementos de uma sequência. Algoritmos como sort, partial_sort, nth_element e todos os contêineres classificados usam um predicado binário que deve fornecer uma ordenação estritamente fraca , ou seja, deve se comportar como um teste de filiação em uma relação binária transitiva, não reflexiva e assimétrica . Se nenhum for fornecido, esses algoritmos e contêineres usam menos por padrão, que por sua vez chama o operador menor que <. find_if

Críticas

Qualidade de implementação de compiladores C ++

A Qualidade de Implementação (QoI) do compilador C ++ tem um grande impacto na usabilidade do STL (e código modelo em geral):

  • Mensagens de erro envolvendo modelos tendem a ser muito longas e difíceis de decifrar. Esse problema foi considerado tão grave que várias ferramentas foram escritas para simplificar e fazer uma impressão bonita das mensagens de erro relacionadas à STL para torná-las mais compreensíveis.
  • O uso descuidado de modelos pode levar ao inchaço do código . Isso foi combatido com técnicas especiais dentro de implementações STL (por exemplo, usando recipientes void * internamente e outras técnicas de "modelo de dieta") e aprimorando as técnicas de otimização dos compiladores. No entanto, esse sintoma é semelhante a copiar manualmente e ingenuamente um conjunto de funções para trabalhar com um tipo diferente, em que ambos podem ser evitados com cuidado e boa técnica.
  • A instanciação do modelo pode aumentar o tempo de compilação e o uso de memória, em troca da redução típica da tomada de decisão no tempo de execução (por exemplo, por meio de funções virtuais). Até que a tecnologia do compilador melhore o suficiente, esse problema pode ser eliminado apenas parcialmente por uma codificação cuidadosa, evitando certos idiomas e simplesmente não usando modelos onde eles não são apropriados ou onde o desempenho em tempo de compilação é priorizado.

Outros problemas

  • A inicialização de contêineres STL com constantes no código-fonte não é tão fácil quanto as estruturas de dados herdadas de C (endereçadas em C ++ 11 com listas de inicializadores ).
  • Os contêineres STL não devem ser usados ​​como classes base (seus destruidores são deliberadamente não virtuais); derivar de um contêiner é um erro comum.
  • O conceito de iteradores conforme implementado pelo STL pode ser difícil de entender no início: por exemplo, se um valor apontado pelo iterador for excluído, o próprio iterador não será mais válido. Esta é uma fonte comum de erros. A maioria das implementações do STL fornece um modo de depuração mais lento, mas pode localizar esses erros se usado. Um problema semelhante existe em outras linguagens, por exemplo Java . Os intervalos foram propostos como uma alternativa mais segura e flexível aos iteradores.
  • Certos padrões de iteração não são mapeados para o modelo de iterador STL. Por exemplo, APIs de enumeração de retorno de chamada não podem ser feitas para se ajustar ao modelo STL sem o uso de corrotinas , que são dependentes da plataforma ou indisponíveis, e estarão fora do padrão C ++ até C ++ 20.
  • A conformidade do compilador não garante que os objetos Allocator , usados ​​para gerenciamento de memória para contêineres , funcionarão com comportamento dependente de estado. Por exemplo, uma biblioteca portátil não pode definir um tipo de alocador que extrairá memória de diferentes pools usando diferentes objetos alocadores desse tipo. (Meyers, p. 50) (abordado em C ++ 11 ).
  • O conjunto de algoritmos não está completo: por exemplo, o algoritmo foi deixado de fora, embora tenha sido adicionado em C ++ 11 .copy_if

Implementações

Veja também

Notas

Referências

links externos