Ordenação

Por padrão, todos os elementos são ordenados em ordem crescente. Para inverter essa ordem, utiliza-se o functor greater<T>. Também é possível definir regras personalizadas de ordenação através de estruturas.

struct Comparador {
    bool operator()(const Tipo& a, const Tipo& b) const {
        // Definição da lógica de ordenação
        return a.algumCampo < b.algumCampo;
    }
};

Container Vector

O vector é um array dinâmico que oferece flexibilidade no gerenciamento de elementos.

std::vector<int> numeros;
numeros.push_back(10);    // Insere elemento no final
numeros.pop_back();       // Remove o último elemento
numeros.size();           // Retorna quantidade de elementos

// Verifica existência de elemento
bool existe = std::find(numeros.begin(), numeros.end(), valor) != numeros.end();

// Remove elemento em posição específica
numeros.erase(numeros.begin() + indice);

// Troca conteúdo entre containers
std::vector<int> outro = {1, 2, 3};
numeros.swap(outro);

Operações de Manipulação

#include <algorithm>

// Inverte a ordem dos elementos
std::reverse(numeros.begin(), numeros.end());

// Remove duplicatas (requer ordenação prévia)
std::sort(numeros.begin(), numeros.end());
numeros.erase(std::unique(numeros.begin(), numeros.end()), numeros.end());

Função sort

A função sort utiliza o padrão left-inclusive, right-exclusive:

std::sort(numeros.begin() + inicio, numeros.begin() + fim, Comparador());
// Intervalo: [inicio, fim)

Busca Binária

binary_search

bool encontrado = std::binary_search(inicio, fim, chave, Comparador());

Observações importatnes:

• O comparator utilizado deve ser consistente com a ordenação
• "Igual" significa que nem (a < b) nem (b < a) são verdadeiros
• O valor encontrado pode não ser exatamente igual à chave

Lower Bound - Limite Inferior

Retorna iterador para o primeiro elemento maior ou igual à chave:

// Para container ordenado crescentemente
auto* p = std::lower_bound(arranjo + inicio, arranjo + fim, valor);

// Com comparador customizado
auto* p = std::lower_bound(inicio, fim, valor, Comparador());
// *p é o elemento com menor índice que pode ser posicionado após "valor"

Se não encontrar, retorna ponteiro para posição fim.

Upper Bound - Limite Superior

Retorna iterador para o primeiro elemento estritamente maior que a chave:

// Para container ordenado crescentemente
auto* p = std::upper_bound(arranjo + inicio, arranjo + fim, valor);

// Com comparador customizado
auto* p = std::upper_bound(inicio, fim, valor, Comparador());
// *p é o elemento com menor índice que deve estar após "valor"

Estruturas de Árvore Binária Balanceada

Multiset

Container que mantém elementos ordenados，允许 elementos duplicados. Complexidade: O(log n).

std::multiset<int> conjunto;

// Inserção
conjunto.insert(42);

// Busca - retorna iterador ou end() se não encontrar
auto it = conjunto.find(42);

// Remoção
conjunto.erase(it);           // Remove elemento específico
conjunto.erase(42);           // Remove todas ocorrências

// Contagem
int qtd = conjunto.count(42);

// Tamanho
size_t total = conjunto.size();

Iteradores

std::multiset<int>::iterator iterador;

iterador = conjunto.begin();  // Primeiro elemento
iterador = conjunto.end();    // Após o último

// Operações válidas: ++, --, ==, !=
// Operações inválidas: <, >, +, -, subtração entre iteradores

Métodos de Busca

// Lower bound: primeiro elemento maior que chave
auto it1 = conjunto.lower_bound(chave);

// Upper bound: primeiro elemento maior ou igual que chave
auto it2 = conjunto.upper_bound(chave);

Set

Similar ao multiset, mas não permite elementos duplicados.

std::set<int> conjuntoUnico;

// Retorna pair<iterador, bool>
auto resultado = conjuntoUnico.insert(42);

if (!resultado.second) {
    // Inserção falhou - elemento já existe
}

Multimap

Container associativo que aramzena pares (chave, valor), permitindo chaves duplicadas.

typedef std::multimap<std::string, int> MapaMulti;

// Inserção
mapa.insert(std::make_pair("chave", valor));

Os elementos são ordenados pela chave (first) utilizando first < first.

Map

Container associativo com chaves únicas e acesso direto por índice.

std::map<std::string, int> dicionario;

// Inserção/atualização via operador []
dicionario["palavra"] = 42;

// Acesso ao valor
int valor = dicionario["palavra"];

O operador [] retorna a referência ao valor (second) correspondente à chave.