Algoritmos e estruturas de dados em C++: guia prático para desenvolvedores

Algoritmos e estruturas de dados em C++: da teoria aos projetos reais

Dominar algoritmos e estruturas de dados é a base que diferencia um programador iniciante de um engenheiro profissional. Em C++, uma das linguagens mais poderosas e eficientes, entender esses conceitos permite escrever não apenas código funcional, mas rápido, escalável e confiável. Neste artigo, abordaremos as principais estruturas de dados e algoritmos na prática, com exemplos prontos que você pode usar imediatamente em seus projetos.

Não vamos nos aprofundar em teoria abstrata — cada seção contém código C++ específico e explicações de como e por que cada construção funciona. O material é voltado para desenvolvedores que já conhecem a sintaxe do C++, mas desejam sistematizar seus conhecimentos sobre algoritmos.

1. Estruturas de dados básicas: arrays, listas e estruturas dinâmicas

Vamos começar com o essencial. Em C++, a biblioteca padrão (STL) fornece contêineres poderosos, mas entender seu funcionamento interno é fundamental para a otimização.

Array dinâmico (std::vector)

std::vector é o contêiner mais usado. Ele representa um array dinâmico que se expande automaticamente ao adicionar elementos. No entanto, é importante lembrar da complexidade amortizada: inserção no final é O(1) na média, mas inserção no meio é O(n).

#include <iostream>#include <vector>

int main() {    std::vector<int> numbers = {10, 20, 30, 40};        // Adicionar ao final    numbers.push_back(50);        // Inserir no início (operação cara)    numbers.insert(numbers.begin(), 5);        // Remover o último elemento    numbers.pop_back();        for (int num : numbers) {        std::cout << num << " ";    }    // Saída: 5 10 20 30 40    return 0;}

Lista encadeada (std::list)

Ao contrário do vector, std::list é implementado como uma lista duplamente encadeada. É ideal quando você insere ou remove elementos com frequência no meio do contêiner — essas operações são executadas em O(1). O custo é a ausência de acesso direto por índice.

#include <list>

std::list<std::string> tasks = {"Escrever código", "Realizar testes"};tasks.push_front("Planejar arquitetura");tasks.push_back("Documentar");

// Inserir no meioauto it = tasks.begin();std::advance(it, 2); // Move o iterador para o 2º elementotasks.insert(it, "Refatoração");

Pilha e fila (std::stack, std::queue)

São adaptadores de contêiner que limitam a funcionalidade do contêiner base. A pilha funciona pelo princípio LIFO (Last In, First Out), a fila pelo FIFO (First In, First Out).

#include <stack>#include <queue>

// Pilhastd::stack<int> st;st.push(1);st.push(2);st.pop(); // Remove 2

// Filastd::queue<int> q;q.push(10);q.push(20);q.pop(); // Remove 10 (primeiro)

2. Algoritmos de ordenação e busca: do bubble sort à busca binária

Ordenação é um problema clássico, mas na prática é importante saber quando usar algoritmos embutidos e quando escrever os seus próprios.

QuickSort — implementação em C++

A STL usa ordenação introspeciva (um híbrido de QuickSort, HeapSort e InsertionSort). Mas para entender, vamos escrever o QuickSort clássico:

#include <iostream>#include <vector>

int partition(std::vector<int>& arr, int low, int high) {    int pivot = arr[high];    int i = low - 1;        for (int j = low; j < high; j++) {        if (arr[j] < pivot) {            i++;            std::swap(arr[i], arr[j]);        }    }    std::swap(arr[i + 1], arr[high]);    return i + 1;}

void quickSort(std::vector<int>& arr, int low, int high) {    if (low < hi