# Standard Template Library

A Standard Template Library (STL; em português: Biblioteca de Modelos Padrão) é uma biblioteca de rotinas da linguagem de programação C++, que descreve containers, iteradores, algoritmos e functores.
A biblioteca padrão do C++ foi vastamente influenciada pela STL, tendo incorporado, ao longo dos anos, um grande número dos algoritmos desta. Note, porém, que a Standard Template Library (STL) é, a rigor, uma biblioteca distinta da Biblioteca Padrão.

## Visão geral

A STL tem sido um grande auxiliador para programadores C++. Ela fornece ao desenvolvedor um conjunto de classes de uso genérico, que podem ser usados com qualquer tipo de dado (inclusive próprios) desde que suporte determinadas operações básicas.
Ela consegue esse resultado através do vasto uso de templates. Esse método é muito poderoso, fornecendo polimorfismo em tempo de compilação, o que geralmente é mais eficiente à versão em tempo de execução. Compiladores modernos de C++ são otimizados para minimizar o impacto da abstração utilizada pelo STL.
A STL foi criada primeiramente como uma biblioteca de algoritmos genéricos e estruturas de dados, com quatro conceitos presentes: programação genérica, abstração sem perda de eficiência, o modelo computacional de Von Neumann e valores semânticos.

## História

A arquitetura da biblioteca é em sua maioria criação de uma pessoa, Alexander Stepanov. Em 1979 ele iniciou desenvolvendo ideias iniciais em programação genérica e explorando seu potencial para revolucionar o desenvolvimento de sistemas computacionais. Ainda que Dave Musser tenha desenvolvido e discutido alguns aspectos de programação genérica em 1971, suas ideias eram limitadas a algumas áreas específicas de desenvolvimento.
Stepanov percebeu o grande potencial de programação genérica e convenceu seu colegas da época na General Electric (incluindo Dave Musser e Deepak Kapur) que programação genérica deveria ser compreendida como base do desenvolvimento de sistemas computacionais. Na época não havia suporte real em nenhuma linguagem de programação para o paradigma.
A primeira grande linguagem a fornecer tal suporte foi Ada, com suas facilidades de unidades genéricas. Em 1987, Stepanov e Musser haviam desenvolvido e publicado uma biblioteca em Ada para processamento de listas que possuíam embutidas o resultado de suas pesquisas em programação genérica. Entretanto, Ada não atingiu ampla aceitação da indústria e C++ se mostrou mais interessante, ainda que a linguagem estava imatura (ela ainda não fornecia suporte a templates, adicionado posteriormente). Outro motivo para usar C++ que Stepanov percebeu posteriormente foi que o modelo computacional do C/C++, que permite muita flexibilidade para acessar dados por ponteiros, o que é crucial para obter desenvolvimento genérico sem perder eficiência.
Muita pesquisa e experimentação era necessária, não somente para desenvolver componentes individuais, mas para desenvolver uma arquitetura para um biblioteca de componentes baseada em programação genérica. Primeiramente no Bell Labs e depois nos laboratórios de pesquisa da HP, Stepanov experimentou várias definições arquiteturais e algorítmicas, primeiro em C e depois em C++. Musser colaborou nessa pesquisa e em 1992 Meng Lee se uniu ao projeto de Stepanov na HP, se tornando um grande colaborador.
Esse trabalho teria sido continuado por algum tempo somente como um projeto de pesquisa, ou teria se tornado uma biblioteca proprietária da HP, se Andrew Koenig do Bell Labs não tivesse tomado conhecimento do trabalho e convidado Stepanov a apresentar suas ideias na reunião de 1993 do comitê ANSI/ISO de padronização do C++. A resposta do comitê foi muito favorável e resultou na requisição de Koenig para uma proposta formal a tempo da reunião de 1994. Apesar da grande pressão devido ao tempo, Alex e Meng conseguiram produzir o rascunho de uma proposta que recebeu aprovação preliminar nessa reunião.
O comitê possuía várias requisições de mudanças e extensões, e um pequeno grupo de seus membros se reuniu com Stepanov e Lee para ajudar na definição dos detalhes. Os requisitos para a extensão mais significativa (containers associativos) deveriam se mostrar consistentes, tarefa essa que Stepanov delegou a Musser. Stepanov e Lee produziram uma proposta que recebeu aprovação final na reunião de 1994 do comitê ANSI/ISO.
Apesar do sucesso da STL com o comitê, restou a dúvida se a STL se tornaria utilizável. Com os requisitos da STL sendo parte da parte pública do padrão da linguagem, fabricantes de compiladores e produtores independentes de bibliotecas poderiam desenvolver suas próprias implementações da biblioteca.

## Conteúdo
### Containers

A STL contém containers sequenciais (como vector, string e deque) e containers associativos (como set, multiset, map e multimap).
O vector é um vetor ao estilo de C (capacidade de acesso aleatório) com a habilidade de automaticamente redimensionar a si mesmo ao inserir e remover elementos. Inserção e remoção de elementos possui complexidade linear, exceto no início ou final do vetor, que possui complexidade constante. Já o set é um conjunto, de forma que a inserção e remoção de elementos não invalida iteradores apontando para o container. Este, fornece operações como união, intersecção, diferença, diferença simétrica e teste de inclusão.
Bibliotecas que implementam STL geralmente incluem variantes para tabelas de dispersão: hash_set, hash_multiset, hash_map e hash_multimap. Tais variantes não fazem parte da biblioteca padrão, e por isso são definidas em espaços de nome diversos ao std.

### Iteradores

A STL implementa cinco diferentes tipos de iteradores. Os iteradores de entrada só podem ser usados para ler uma sequência de valores, enquanto os iteradores de saída só podem ser usados para escrever uma sequência de valores. Já iteradores de avanço podem serem lidos, escritos e avançados, enquanto iteradores bidirecionais são como iteradores de avanço, mas também podem ser retrocedidos. Por fim, iteradores de acesso aleatório podem ser movidos livremente por distâncias maiores que um elemento em uma única operação.
É possível usar iteradores bidirecionais para acesso aleatório, já que avançar dez elementos pode ser feito avançando dez vezes a distância de um elemento. Mas possuir iteradores distintos proporciona vantagens ao otimizar o código.
Iteradores são os maiores auxiliadores para a programação genérica em STL. Por exemplo, um algoritmo de inversão de uma sequência pode ser implementado utilizando iteradores bidirecionais, e a mesma implementação pode ser usada em listas e vetores. Containers criados pelo desenvolvedor podem usufruir de todos os algoritmos da STL desde que implementem pelo menos um dos iteradores descritos acima.
O caráter genérico também implica algumas consequências. Por exemplo, ao realizar uma busca em um container associativo (como um conjunto) pode ser muito mais lento pelo método de iteradores que através de funções membro oferecidas pelo próprio container. Isso porque um container associativo possui a vantagem de conhecer sua estrutura interna enquanto iteradores não possuem tamanha robustez.

### Algoritmos

Uma série de algoritmos para busca e classificação são fornecidos pela STL. Cada um requer um tipo de iterador, logo, funciona para qualquer container que forneça uma interface através de iteradores.

### Functores

A STL fornece classes que sobrecarregam o operador de função (operator). Tais classes são chamadas functores ou funções-objeto. São úteis para manter e obter informação em funções passadas para outras funções.

## Críticas

Uma crítica recorrente com o uso de templates, inclusive os da STL, são as mensagens de erro em compiladores, que tendem a ser bastante longas e difíceis de serem decifradas. Tal problema é considerado tão severo que um número de ferramentas foram escritas para simplificar e classificar as mensagens de erro relativas à templates, a fim de torná-las mais compreensíveis. Esperava-se que esse problema fosse resolvido com o C++14, com a inclusão do modelo de conceitos nos algoritmos, de forma a melhorar e simplificar as mensagens de erro produzidas. No entanto o modelo não foi aprovado. Uma moção para incluir conceitos na versão C++17 também não teve êxito. Uma versão inicial foi aprovada no projeto (draft) da norma C++20. O compilador GCC 6 possui suporte conforme a norma ISO/IEC TS 19217:2015.
Outra crítica argumenta que como o código é produzido na compilação, alguns ambientes de programação possuem pouco suporte ao rastrear erros no próprio código fonte, causando depuração lenta. Em relação à orientação a objeto, os containers STL não devem ser usados como classe base pois seus destrutores não são virtuais. Além disso, templates instanciados um grande número de vezes tendem a aumentar o tempo de compilação e o uso de memória.