C++ STL: a biblioteca de containers e algoritmos

Você já usou std::vector, std::array e std::string. Eles fazem parte de um conjunto maior, que todo programador C++ usa todo dia: a STL. Ela traz prontas as estruturas para guardar dados (listas, filas, dicionários) e dezenas de algoritmos para trabalhar com eles (ordenar, procurar, contar). Esta aula é o mapa: as três peças da STL, como elas se encaixam e qual "caixa" escolher para cada problema. As próximas aulas visitam cada peça com calma.

Todos os programas desta aula foram compilados com o g++ 15.2 na máquina fictícia da Ana, na pasta ~/cpp/stl, com g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa. É bom já conhecer std::vector e Templates de Classe.

O nome: Standard Template Library

STL é a sigla de Standard Template Library, "biblioteca padrão de templates". Ela foi criada nos anos 1990 por Alexander Stepanov e Meng Lee, e entrou no primeiro padrão do C++, o C++98 (aula Versões do C++). Hoje ela é uma parte da biblioteca padrão do C++, que também tem std::string, std::cout, <cmath> e muito mais. Na prática, as pessoas dizem "STL" querendo dizer "os containers e os algoritmos da biblioteca padrão", e é nesse sentido que o guia usa o nome.

"De templates" porque tudo nela é template: std::vector<int>, std::map<std::string, int>. É por isso que você estudou templates antes: agora os <…> fazem sentido.

A ideia: a cozinha

Pense numa cozinha. Há potes de vários formatos (pote de vidro, saco, caixa de ovos). Há receitas (bater, separar, contar). E há as mãos, que pegam as coisas de dentro de qualquer pote, uma por uma, e entregam para a receita. A receita "contar quantos ovos estão quebrados" não depende do pote: funciona na caixa de ovos e na tigela, porque as mãos sabem tirar os ovos dos dois.

A STL é organizada exatamente assim:

1. As três partes num programa só

A Ana tem as notas da turma num vetor. Ela quer ordenar e contar quantos tiraram 10:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 10, 4, 9, 10, 6};

    std::sort(notas.begin(), notas.end());

    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';

    auto dez = std::count(notas.begin(), notas.end(), 10);
    std::cout << "Notas 10: " << dez << '\n';
}

#include <algorithm>

O cabeçalho dos algoritmos (sort, count, find…).

std::vector<int> notas{…};

O container: o pote com seis notas.

notas.begin(), notas.end()

Dois iteradores: um aponta a primeira nota, o outro aponta o lugar depois da última (aula Iteradores). Juntos, dizem "do começo ao fim".

std::sort(…)

Um algoritmo: ordena a faixa que você deu, do menor para o maior.

std::count(…, 10)

Outro algoritmo: conta quantos itens da faixa são iguais a 10.

$ g++ -std=c++23 -Wall -Wextra tres-partes.cpp -o tres-partes
$ ./tres-partes
4 6 7 9 10 10
Notas 10: 2

Repare: o std::sort não é um método do vetor (não é notas.sort()). Ele é uma função solta, que recebe o começo e o fim. Os algoritmos têm aula própria: Algoritmos.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 10, 4, 9, 10, 6};

    std::sort(notas.begin(), notas.end());

    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';

    auto dez = std::count(notas.begin(), notas.end(), 10);
    std::cout << "Notas 10: " << dez << '\n';
}

2. Por que separar em três partes: um algoritmo, vários containers

A grande ideia da STL: o algoritmo não sabe (nem quer saber) em que container os dados estão. Ele só precisa de iteradores. O mesmo std::count funciona num vector, numa list e num array:

#include <algorithm>
#include <array>
#include <iostream>
#include <list>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> compras{"arroz", "café", "leite"};
    std::list<std::string> tarefas{"lavar", "café", "estudar"};
    std::array<std::string, 3> cores{"azul", "verde", "café"};

    std::cout << std::count(compras.begin(), compras.end(), "café") << '\n';
    std::cout << std::count(tarefas.begin(), tarefas.end(), "café") << '\n';
    std::cout << std::count(cores.begin(), cores.end(), "café") << '\n';
}

$ g++ -std=c++23 -Wall -Wextra mesmo-algoritmo.cpp -o mesmo-algoritmo
$ ./mesmo-algoritmo
1
1
1

Pense na conta: são uns 10 containers e mais de 100 algoritmos. Se cada container tivesse seu próprio "contar", "procurar", "ordenar"…, seriam mais de mil funções. Com os iteradores no meio, cada algoritmo é escrito uma vez e serve para todos. E se você criar o seu próprio container com iteradores, ganha os 100 algoritmos de graça.

3. O que todos os containers têm em comum

Os containers foram desenhados para se parecerem. Aprendeu num, sabe o básico de todos:

#include <iostream>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 10};
    std::list<std::string> fila{"Ana", "Bruno"};
    std::set<char> letras{'a', 'b', 'a', 'c'};
    std::map<std::string, int> estoque{{"maçã", 12}, {"pera", 5}};

    std::cout << notas.size() << ' ' << fila.size() << ' '
              << letras.size() << ' ' << estoque.size() << '\n';

    notas.clear();
    std::cout << std::boolalpha << notas.empty() << ' ' << fila.empty() << '\n';
}

$ g++ -std=c++23 -Wall -Wextra comum.cpp -o comum
$ ./comum
3 2 3 2                  « o set guardou só a, b, c: ele não aceita repetidos
true false

4. Os containers: qual usar quando

A STL organiza os containers em três famílias:

• Sequências: guardam os itens na ordem em que você os pôs, como uma fila de pessoas. vector, array, list, deque.
• Associativos: guardam os itens organizados por uma chave, para achar rápido. map, set e as versões unordered_.
• Adaptadores: uma "capa" sobre outro container, que deixa usar só algumas operações. stack, queue.

Um roteiro para escolher

Na dúvida, faça estas perguntas, nesta ordem:

1. Vou procurar valores por um nome ou código (como "quantas maçãs tem no estoque?")? Use std::map. Se a ordem não importa, std::unordered_map.
2. Só preciso saber se algo está na coleção, sem repetidos? Use std::set (ou std::unordered_set).
3. Só uso o último que entrou, ou o primeiro que entrou? Use std::stack ou std::queue.
4. O tamanho é fixo e conhecido? Use std::array.
5. Nenhum dos casos acima? Use std::vector. Só troque por list ou deque se tiver um motivo claro.

5. Os cabeçalhos

Cada container mora no seu cabeçalho, com o mesmo nome. Os algoritmos ficam quase todos em <algorithm>; os de conta (somar tudo, por exemplo) ficam em <numeric>.

Esquecer o cabeçalho é um erro comum. A boa notícia: o g++ 15 costuma dizer qual falta.

#include <iostream>

int main() {
    std::list<int> fila{1, 2, 3};
    std::cout << fila.size() << '\n';
}

$ g++ -std=c++23 -Wall -Wextra sem-include.cpp -o sem-include
sem-include.cpp: In function ‘int main()’:
sem-include.cpp:4:10: error: ‘list’ is not a member of ‘std’
    4 |     std::list<int> fila{1, 2, 3};
      |          ^~~~
sem-include.cpp:2:1: note: ‘std::list’ is defined in header ‘<list>’; this is probably fixable by adding ‘#include <list>’
    1 | #include <iostream>
  +++ |+#include <list>
    2 |
sem-include.cpp:4:15: error: expected primary-expression before ‘int’
    4 |     std::list<int> fila{1, 2, 3};
      |               ^~~
sem-include.cpp:5:18: error: ‘fila’ was not declared in this scope
    5 |     std::cout << fila.size() << '\n';
      |                  ^~~~

error: ‘list’ is not a member of ‘std’

"list não é membro de std": o compilador não conhece std::list, porque ninguém incluiu o cabeçalho dela.

note: ‘std::list’ is defined in header ‘<list>’

A dica de ouro: "std::list fica no cabeçalho <list>; provavelmente se conserta com #include <list>". As linhas com +++ |+ mostram onde ele colocaria.

os outros dois erros

Consequência do primeiro. Conserte o primeiro e compile de novo.

No editor do guia, o Clang diz no member named 'list' in namespace 'std' ("não há membro chamado list no namespace std"), sem a dica do cabeçalho. Use a tabela acima.

Quando dá errado

Referência rápida

Exercícios

Missão final: a lista de compras arrumada

arroz café café feijão leite
café aparece 2 vezes

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> compras{"leite", "café", "arroz", "feijão", "café"};

    // ordene aqui

    for (const auto& item : compras) {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    // conte os cafés aqui e mostre "café aparece N vezes"
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> compras{"leite", "café", "arroz", "feijão", "café"};

    std::sort(compras.begin(), compras.end());

    for (const auto& item : compras) {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    auto cafes = std::count(compras.begin(), compras.end(), "café");
    std::cout << "café aparece " << cafes << " vezes\n";
}

Resumo

• A STL (Standard Template Library) é a parte da biblioteca padrão com containers, iteradores e algoritmos. Tudo nela é template.
• Containers guardam; algoritmos trabalham; iteradores ligam um ao outro. Por isso um algoritmo escrito uma vez serve para vários containers.
• Todos os containers têm size() e empty(); quase todos têm clear(), begin() e end().
• Escolha: chave → valor, map/unordered_map; sem repetidos, set; último/primeiro que entrou, stack/queue; tamanho fixo, array; o resto, vector.
• Cada container tem seu cabeçalho com o mesmo nome; os algoritmos estão em <algorithm>. Inclua sempre o que usa.
• Próximo passo: as "mãos" da STL, em Iteradores.