Visão Geral do std::forward_list
O std::forward_list é um contêiner sequencial da Standard Template Libray (STL) do C++ que implementa uma lista simplesmente encadeaad. Diferentemente do std::list, que utiliza encadeamento duplo, o forward_list mantém apenas um ponteiro para o próximo nó. Essa arquitetura minimiza o consumo de memória por elemento e otimiza operações de inserção e remoção no início da estrutura. Vale destacar que, por padrão, este contêiner não armazena o número total de elementos, não possuindo o método size(), o que garante complexidade O(1) estrita para modificações na cabeça da lista.
- Construtores
A inicialização do forward_list pode ser feita de diversas formas, suportando construção padrão, preenchimento, intervalos, listas de inicialização, cópia e movimentação.
#include <forward_list>
#include <iostream>
void demonstrar_construtores() {
std::forward_list<int> lista_padrao;
std::forward_list<int> lista_preenchida(5, 42); // 5 elementos com valor 42
std::forward_list<int> lista_intervalo(lista_preenchida.begin(), lista_preenchida.end());
std::forward_list<int> lista_inicializacao = {10, 20, 30, 40};
std::forward_list<int> lista_copia(lista_inicializacao);
std::forward_list<int> lista_movida(std::move(lista_copia)); // lista_copia torna-se vazia
}
- Operações de Atribuição
O contêiner permite a substituição completa de seu conteúdo através do operador de atribuição (operator=) ou do método assign, que aceita contagem e valor, intervalos de iteradores ou listas de inicialização.
void demonstrar_atribuicao() {
std::forward_list<int> lista_a = {1, 2, 3};
std::forward_list<int> lista_b;
lista_b = lista_a; // Atribuição por cópia
lista_b = {100, 200, 300}; // Atribuição por lista de inicialização
lista_a.assign(4, 99); // Substitui por 4 elementos de valor 99
int arr[] = {5, 10, 15};
lista_b.assign(std::begin(arr), std::end(arr)); // Substitui por intervalo
}
- Iteradores e o Conceito de before_begin
Como é uma lista simplesmente encadeada, a iteração ocorre apenas no sentido direto. O método before_begin() é exclusivo do forward_list e retorna um iterador para uma posição fictícia anterior ao primeiro elemento. Isso é essencial para inserir ou remover o próprio primeiro elemento usando as funções com sufixo _after.
void demonstrar_iteradores() {
std::forward_list<int> lista = {1, 2, 3};
// Inserindo no início usando before_begin
auto it_before = lista.before_begin();
lista.insert_after(it_before, 0); // A lista agora é {0, 1, 2, 3}
// Iteração padrão
for (auto it = lista.begin(); it != lista.end(); ++it) {
std::cout << *it << " ";
}
}
- Capacidade e Acesso a Elementos
Devido à ausência de rastreamento de tamanho, as únicas verificações de capacidade são empty() e max_size(). O acesso direto é restrito ao primeiro eleemnto através de front().
void demonstrar_capacidade_acesso() {
std::forward_list<int> lista = {10, 20, 30};
bool esta_vazia = lista.empty(); // false
auto capacidade_maxima = lista.max_size();
int& primeiro = lista.front();
primeiro = 99; // Modifica o primeiro elemento para 99
}
- Modificadores
As operações de modificação incluem adição e remoção no início (push_front, emplace_front, pop_front), além de inserções, construções in-place e remoções após um iterador específico (insert_after, emplace_after, erase_after). Também estão disponíveis swap, resize e clear.
void demonstrar_modificadores() {
std::forward_list<int> lista = {2, 3};
lista.push_front(1); // {1, 2, 3}
lista.emplace_front(0); // {0, 1, 2, 3}
lista.pop_front(); // {1, 2, 3}
auto it = lista.begin();
lista.insert_after(it, 99); // Insere 99 após o primeiro elemento: {1, 99, 2, 3}
lista.erase_after(it); // Remove o 99: {1, 2, 3}
lista.resize(5, 0); // Expande para 5 elementos, preenchendo com 0
lista.clear(); // Remove todos os elementos
}
- Operações Específicas da Lista
O forward_list possui algoritmos integrados otimizados para sua estrutura de ponteiros, como merge (fusão de listas ordenadas), splice_after (transferência de nós sem cópia), remove, remove_if, reverse, unique e sort.
void demonstrar_operacoes() {
std::forward_list<int> lista_a = {1, 3, 5};
std::forward_list<int> lista_b = {2, 4, 6};
lista_a.merge(lista_b); // Fusão: {1, 2, 3, 4, 5, 6}. lista_b fica vazia.
lista_a.remove_if([](int x){ return x % 2 == 0; }); // Remove pares: {1, 3, 5}
std::forward_list<int> lista_c = {3, 1, 2, 2, 1};
lista_c.sort(); // {1, 1, 2, 2, 3}
lista_c.unique(); // Remove duplicatas adjacentes: {1, 2, 3}
lista_c.reverse(); // Inverte a ordem: {3, 2, 1}
}
- Funções Não-Membro e C++20
Além dos operadores de comparação e do std::swap, o C++20 introduziu std::erase e std::erase_if, que fornecem uma interface uniforme para remoção de elementos em contêineres da STL, retornando o número de elementos removidos.
void demonstrar_cpp20() {
std::forward_list<int> lista = {1, 2, 3, 2, 4, 2, 5};
// Remove todas as ocorrências do valor 2
auto removidos = std::erase(lista, 2);
// Remove elementos maiores que 3
auto removidos_cond = std::erase_if(lista, [](int x){ return x > 3; });
}
- Exemplo Prático Completo: Gerenciamento de Tarefas
O exemplo abaixo demonstra a aplicação do std::forward_list em um cenário real, utilizando uma classe personalizada Tarefa para ilustrar construção, inserção, remoção condicional, ordenação e fusão de listas.
#include <iostream>
#include <forward_list>
#include <string>
#include <functional>
#include <iterator>
class Tarefa {
public:
Tarefa() = default;
Tarefa(std::string titulo, int prioridade)
: titulo_(std::move(titulo)), prioridade_(prioridade) {}
Tarefa(const Tarefa&) = default;
Tarefa(Tarefa&&) noexcept = default;
Tarefa& operator=(const Tarefa&) = default;
Tarefa& operator=(Tarefa&&) noexcept = default;
const std::string& getTitulo() const { return titulo_; }
int getPrioridade() const { return prioridade_; }
bool operator==(const Tarefa& outra) const {
return titulo_ == outra.titulo_ && prioridade_ == outra.prioridade_;
}
bool operator<(const Tarefa& outra) const { return prioridade_ < outra.prioridade_; }
bool operator>(const Tarefa& outra) const { return prioridade_ > outra.prioridade_; }
friend std::ostream& operator<<(std::ostream& os, const Tarefa& t) {
os << "[Prioridade: " << t.prioridade_ << "] " << t.titulo_;
return os;
}
private:
std::string titulo_;
int prioridade_ = 0;
};
template <typename T>
void exibir_lista(const std::forward_list<T>& lista, const std::string& contexto) {
std::cout << contexto << ":\n";
for (const auto& item : lista) {
std::cout << " - " << item << "\n";
}
std::cout << std::endl;
}
int main() {
std::forward_list<Tarefa> tarefas_principais;
// 1. Inserção no início (O(1))
tarefas_principais.emplace_front("Configurar ambiente", 2);
tarefas_principais.emplace_front("Escrever testes", 3);
tarefas_principais.emplace_front("Revisar código", 4);
exibir_lista(tarefas_principais, "Lista inicial (ordem de inserção inversa)");
// 2. Inserção após um nó específico
auto it = tarefas_principais.begin();
std::advance(it, 1); // Avança para o segundo elemento
tarefas_principais.emplace_after(it, "Documentar API", 3);
exibir_lista(tarefas_principais, "Após inserir 'Documentar API'");
// 3. Remoção condicional (remover tarefas com prioridade < 3)
tarefas_principais.remove_if([](const Tarefa& t) {
return t.getPrioridade() < 3;
});
exibir_lista(tarefas_principais, "Após remover prioridades baixas");
// 4. Ordenação por prioridade (decrescente)
tarefas_principais.sort([](const Tarefa& a, const Tarefa& b) {
return a.getPrioridade() > b.getPrioridade();
});
exibir_lista(tarefas_principais, "Ordenada por prioridade (maior para menor)");
// 5. Inversão da lista
tarefas_principais.reverse();
exibir_lista(tarefas_principais, "Lista invertida (menor para maior prioridade)");
// 6. Fusão com outra lista (merge exige que ambas estejam ordenadas)
std::forward_list<Tarefa> tarefas_secundarias = {
Tarefa("Atualizar dependências", 2),
Tarefa("Otimizar queries", 4)
};
// Ordena a secundária com o mesmo critério antes do merge
tarefas_secundarias.sort([](const Tarefa& a, const Tarefa& b) {
return a.getPrioridade() < b.getPrioridade();
});
tarefas_principais.merge(tarefas_secundarias, [](const Tarefa& a, const Tarefa& b) {
return a.getPrioridade() < b.getPrioridade();
});
exibir_lista(tarefas_principais, "Após fusão com tarefas secundárias");
return 0;
}