Funciones esenciales de <algorithm>

Generación de permutaciones: std::next_permutation y std::prev_permutation

Función: produce, en orden lexicográfico, la siguiente o anterior permutación mutando el contenedor; devuelve false si no existe.

Complejidad: O(n).

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::sort(nums.begin(), nums.end());
    do {
        for (int x : nums) std::cout << x << ' ';
        std::cout << '\n';
    } while (std::next_permutation(nums.begin(), nums.end()));
    return 0;
}

Usos: enumerar permutaciones, problemas de orden lexicográfico.

Ordenamiento: std::sort

Función: ordena un rango; admite comparador personlaizado.

Complejidad: O(n log n).

#include <vector>
#include <algorithm>
#include <functional>

struct Item { int a, b; };

std::vector<Item> items = {{3, 1}, {1, 4}, {2, 2}};
std::sort(items.begin(), items.end(), [](const Item& p, const Item& q) {
    if (p.a != q.a) return p.a < q.a;
    return p.b > q.b;          // a ascendente, b descendente
});

std::vector<int> v = {5, 1, 4};
std::sort(v.begin(), v.end(), std::greater<int>());

Inversión: std::reverse

Complejidad: O(n).

std::string s = "abcdef";
std::reverse(s.begin(), s.end());  // "fedcba"

std::vector<int> a = {10, 20, 30};
std::reverse(a.begin(), a.end());  // {30, 20, 10}

Eliminación de duplicados: std::unique + std::vector::erase

Función: compacta los elementos repetidos adyacentes; requiere orden previo.

Complejidad: O(n) tras el ordenamiento.

std::vector<int> a = {4, 2, 4, 1, 2, 2, 3};
std::sort(a.begin(), a.end());
auto fin = std::unique(a.begin(), a.end());
a.erase(fin, a.end());  // {1, 2, 3, 4}

Búsqueda binaria: std::lower_bound y std::upper_bound

Complejidad: O(log n).

std::vector<int> a = {1, 3, 5, 7, 9};

auto it1 = std::lower_bound(a.begin(), a.end(), 6); // primer elemento >= 6 -> 7
auto it2 = std::upper_bound(a.begin(), a.end(), 3); // primer elemento > 3 -> 5

int cnt = std::upper_bound(a.begin(), a.end(), 5)
        - std::lower_bound(a.begin(), a.end(), 5);

Reducción: std::accumulate

Complejidad: O(n).

#include <numeric>
#include <functional>

std::vector<int> a = {1, 2, 3, 4};
int suma = std::accumulate(a.begin(), a.end(), 0);

int producto = std::accumulate(a.begin(), a.end(), 1, std::multiplies<int>());

std::vector<std::string> palabras = {"Hola", " ", "Mundo"};
std::string frase = std::accumulate(palabras.begin(), palabras.end(), std::string());

Predicados de rango

Complejidad: O(n).

std::vector<int> a = {2, 4, 6, 8};
bool todosPares  = std::all_of (a.begin(), a.end(), [](int x){ return x % 2 == 0; });
bool algunoMayor = std::any_of (a.begin(), a.end(), [](int x){ return x > 5; });
bool ningunNeg   = std::none_of(a.begin(), a.end(), [](int x){ return x < 0; });

Otras funciones útiles

Función	Ejemplo	Complejidad	Uso típico
std::find	find(a.begin(), a.end(), 5)	O(n)	Buscar en rango desordanado
std::count	count(a.begin(), a.end(), 3)	O(n)	Contar apariciones
std::max_element	*max_element(a.begin(), a.end())	O(n)	Encontrar el mayor
std::nth_element	nth_element(a.begin(), a.begin()+k, a.end())	O(n) promedio	k-ésimo menor
std::swap_ranges	swap_ranges(a.begin(), a.end(), b.begin())	O(n)	Intercambiar dos rangos

Contenedores frecuentes

std::vector

Complejidades: inserción/eliminación al final O(1) amortizado, en medio O(n), acceso aleatorio O(1), búsqueda O(n).

std::vector<int> v;
v.push_back(10);
v.emplace_back(20);
int primero = v.front();
v.erase(v.begin() + 1);

std::queue

Complejidad: push/pop/front O(1).

std::queue<int> cola;
cola.push(1);
int f = cola.front();
cola.pop();

std::stack

Complejidad: push/pop/top O(1).

std::stack<int> pila;
pila.push(2);
int c = pila.top();
pila.pop();

std::priority_queue

Complejidad: inserción/eliminación O(log n), consulta del tope O(1).

#include <queue>
#include <functional>

std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

maxHeap.push(3); maxHeap.push(1); maxHeap.push(2);
while (!maxHeap.empty()) {
    std::cout << maxHeap.top() << ' ';  // 3 2 1
    maxHeap.pop();
}

std::unordered_map y std::unordered_set

Complejidad: O(1) promedio, O(n) peor caso.

#include <unordered_map>
#include <unordered_set>

std::unordered_map<int, int> freq;
freq[7]++;

std::unordered_set<int> visto;
visto.insert(5);
if (visto.count(5)) { /* presente */ }

std::map y std::set

Complejidad: O(log n) en inserción, búsqueda y borrado.

std::map<int, std::string> dicc;
dicc[2] = "dos";
dicc[1] = "uno";          // iteración ordenada por clave

std::set<int> conj = {3, 1, 2};   // {1, 2, 3}
auto it = conj.lower_bound(2);    // apunta a 2

std::string

std::string s = "hola";
s += " mundo";
std::string sub = s.substr(5, 5);  // "mundo"
size_t pos = s.find("la");       // 2

std::deque

Complejidad: inserción/eliminación en ambos extremos O(1), en medio O(n).

std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_back();
dq.pop_front();

Utilidades adicionales

Manejo de caracteres y subcadenas

#include <cctype>

char ch = 'a';
bool digito = std::isdigit(ch);
char may = std::toupper(ch);

std::string s = "abc123";
std::string num = s.substr(3, 3);
size_t p = s.find("bc");

Conjunto de bits: std::bitset

Complejidad: O(N / palabra de máquina).

#include <bitset>

std::bitset<8> flags;
flags.set(2);
flags.reset(2);
bool encendido = flags.test(2);
flags <<= 1;

std::pair y std::tuple

#include <utility>
#include <tuple>

std::pair<int, int> punto = {3, 4};
int x = punto.first, y = punto.second;

std::tuple<int, std::string, double> datos = {1, "a", 3.14};
int id = std::get<0>(datos);
std::string nombre = std::get<1>(datos);

Comparadores personalizados

std::sort(v.begin(), v.end(), std::greater<int>());

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

struct Nodo { int x, y; };
std::vector<Nodo> nodos = {{1, 2}, {1, 3}, {2, 1}};
std::sort(nodos.begin(), nodos.end(), [](const Nodo& p, const Nodo& q) {
    if (p.x != q.x) return p.x < q.x;
    return p.y > q.y;
});

Constantes de límites enteros

#include <climits>

int maxInt = INT_MAX;
int minInt = INT_MIN;