Containers da STL

Parte da seção Programação Orientada a Objetos do Journey de C++ da Coddy — lição 71 de 104.

Contêineres STL são classes template que armazenam e organizam coleções de objetos. Cada tipo de contêiner é otimizado para diferentes padrões de acesso e operações. Escolher o contêiner certo para suas necessidades pode impactar significativamente o desempenho do seu programa.

Contêineres de sequência mantêm os elementos em uma ordem específica:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Array dinâmico, acesso aleatório rápido
vec.push_back(4);                   // Adicionar ao final: O(1) amortizado
int x = vec[2];                     // Acesso por índice: O(1)

std::list<int> lst = {1, 2, 3};    // Lista duplamente encadeada
lst.push_front(0);                  // Adicionar ao início: O(1)
lst.push_back(4);                   // Adicionar ao final: O(1)

Contêineres associativos armazenam elementos em ordem ordenada para busca rápida:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Elementos únicos ordenados: {1, 3, 4}
s.insert(2);                        // Inserção: O(log n)
bool found = s.count(3);            // Verificar existência: O(log n)

std::map<std::string, int> ages;   // Pares chave-valor, ordenados pela chave
ages["Alice"] = 25;                 // Inserir/atualizar: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Acesso: O(log n)

Contêineres não ordenados usam tabelas hash para buscas em caso médio ainda mais rápidas:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Inserção: O(1) em média
scores["player2"] = 200;
std::cout << scores["player1"];    // Acesso: O(1) em média

Use vector quando você precisar de acesso aleatório rápido, list para inserções frequentes no meio, map/set quando você precisar de dados ordenados e unordered_map quando a velocidade de busca for crítica e a ordem não importar.

Desafio

Fácil

Vamos construir um sistema de gerenciamento de notas de alunos que demonstra como diferentes containers da STL servem a propósitos distintos. Você usará múltiplos tipos de containers para organizar os dados dos alunos de forma eficiente, escolhendo o container certo para cada tarefa.

Você criará dois arquivos para organizar seu código:

GradeManager.h: Defina uma classe GradeManager que utiliza múltiplos containers da STL para gerenciar informações de alunos.
Sua classe deve usar:
- Um std::vector<std::string> para armazenar os nomes dos alunos na ordem em que foram adicionados
- Um std::map<std::string, int> para associar o nome de cada aluno à sua nota
- Um std::set<int> para rastrear todas as notas únicas que foram atribuídas
Implemente estes métodos:
- addStudent(const std::string& name, int grade) — adiciona um aluno com sua nota aos três containers
- getGrade(const std::string& name) — retorna a nota de um determinado nome de aluno usando o mapa
- printRoster() — imprime todos os nomes dos alunos na ordem em que foram adicionados (do vetor), cada um em uma nova linha
- printGrades() — imprime todos os alunos com suas notas em ordem alfabética (o mapa lida com isso automaticamente), formatado como name: grade em cada linha
- printUniqueGrades() — imprime todas as notas únicas em ordem crescente (o conjunto lida com isso), separadas por espaços seguidos de uma nova linha
main.cpp: Leia as entradas e demonstre como cada tipo de container serve a um propósito diferente.
Leia seis entradas (cada uma em uma linha separada):
1. Nome do primeiro aluno
2. Nota do primeiro aluno (inteiro)
3. Nome do segundo aluno
4. Nota do segundo aluno (inteiro)
5. Nome do terceiro aluno
6. Nota do terceiro aluno (inteiro)
Crie um GradeManager e adicione os três alunos. Em seguida, demonstre os diferentes comportamentos dos containers:
1. Imprima Roster (insertion order): seguido pela chamada de printRoster()
2. Imprima Grades (alphabetical): seguido pela chamada de printGrades()
3. Imprima Unique grades: seguido pela chamada de printUniqueGrades()
4. Procure a nota do segundo aluno e imprima <name>'s grade: <grade>

Por exemplo, com as entradas Charlie, 85, Alice, 90, Bob, 85:

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

Observe como o vetor preserva a ordem de inserção (Charlie, Alice, Bob), o mapa ordena automaticamente pela chave (Alice, Bob, Charlie) e o conjunto armazena apenas valores únicos em ordem crescente (85 aparece uma vez, não duas). Cada tipo de container se destaca em tarefas diferentes!

Folha de consulta

Os containers da STL são classes template para armazenar e organizar coleções de objetos. Cada tipo é otimizado para diferentes operações.

Containers de Sequência

Mantêm os elementos em uma ordem específica:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Array dinâmico, acesso aleatório rápido
vec.push_back(4);                   // Adicionar ao final: O(1) amortizado
int x = vec[2];                     // Acesso por índice: O(1)

std::list<int> lst = {1, 2, 3};    // Lista duplamente encadeada
lst.push_front(0);                  // Adicionar ao início: O(1)
lst.push_back(4);                   // Adicionar ao final: O(1)

Containers Associativos

Armazenam elementos em ordem classificada para busca rápida:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Elementos únicos ordenados: {1, 3, 4}
s.insert(2);                        // Inserção: O(log n)
bool found = s.count(3);            // Verificar existência: O(log n)

std::map<std::string, int> ages;   // Pares chave-valor, ordenados pela chave
ages["Alice"] = 25;                 // Inserir/atualizar: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Acesso: O(log n)

Containers Não Ordenados

Utilizam tabelas hash para busca mais rápida no caso médio:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Inserção: O(1) médio
scores["player2"] = 200;
std::cout << scores["player1"];    // Acesso: O(1) médio

Escolhendo o Container Certo

vector: Acesso aleatório rápido
list: Inserções frequentes no meio
map/set: Necessidade de dados ordenados
unordered_map: Velocidade de busca crítica, a ordem não importa

Experimente você mesmo

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // Lê as entradas para três alunos
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Criar um objeto GradeManager
    
    // TODO: Adicionar todos os três alunos ao GradeManager
    
    // TODO: Imprimir "Roster (insertion order):" e chamar printRoster()
    
    // TODO: Imprimir "Grades (alphabetical):" e chamar printGrades()
    
    // TODO: Imprimir "Unique grades:" e chamar printUniqueGrades()
    
    // TODO: Buscar a nota do segundo aluno e imprimir "<name>'s grade: <grade>"
    
    return 0;
}