Contêineres da STL

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

Os contêineres da STL são classes de modelo 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 adequado às suas necessidades pode impactar significativamente o desempenho do seu programa.

Contêineres de sequência mantêm 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 classificada para uma 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;                 // Inserção/atualização: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Acesso: O(log n)

Unordered containers usam tabelas hash para uma busca média ainda mais rápida:

#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 precisar de acesso aleatório rápido, list para inserções frequentes no meio, map/set quando precisar de dados ordenados e unordered_map quando a velocidade de consulta for fundamental e a ordem não importar.

Desafio

Fácil

Vamos criar um sistema de gerenciamento de notas de alunos que demonstra como diferentes contêineres da STL servem a diferentes propósitos. Você usará vários tipos de contêineres para organizar os dados dos alunos com eficiência, escolhendo o contêiner adequado para cada tarefa.

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

GradeManager.h: defina uma classe GradeManager que use vários contêineres da STL para gerenciar as informações dos 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 cada nome de aluno à sua nota
- Um std::set<int> para acompanhar todas as notas exclusivas atribuídas
Implemente estes métodos:
- addStudent(const std::string& name, int grade): adiciona um aluno com sua nota aos três contêineres
- getGrade(const std::string& name): retorna a nota de um determinado aluno usando o mapa
- printRoster(): imprime todos os nomes dos alunos na ordem em que foram adicionados (a partir do vetor), cada um em uma nova linha
- printGrades(): imprime todos os alunos com suas notas em ordem alfabética (o mapa faz isso automaticamente), no formato name: grade em cada linha
- printUniqueGrades(): imprime todas as notas exclusivas em ordem crescente (o conjunto cuida disso), separadas por espaços e seguidas por uma quebra de linha
main.cpp: leia as entradas e demonstre como cada tipo de contêiner 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 contêineres:
1. Imprima Roster (insertion order): e, em seguida, chame printRoster()
2. Imprima Grades (alphabetical): e, em seguida, chame printGrades()
3. Imprima Unique grades: e, em seguida, chame printUniqueGrades()
4. Consulte 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 classifica automaticamente pelas chaves (Alice, Bob, Charlie) e o conjunto armazena apenas valores exclusivos em ordem classificada (85 aparece uma vez, não duas). Cada tipo de contêiner se destaca em tarefas diferentes!

Experimente você mesmo

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

using namespace std;

int main() {
    // Ler 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: Print "Roster (insertion order):" and call printRoster()
    
    // TODO: Print "Grades (alphabetical):" and call printGrades()
    
    // TODO: Print "Unique grades:" and call printUniqueGrades()
    
    // TODO: Buscar a nota do segundo aluno e imprimir "<name>'s grade: <grade>"
    
    return 0;
}