Cuando trabajas con contenedores como std::vector, es tentador pensar que std::remove elimina elementos de la secuencia. Sin embargo, esto es un error conceptual que causa bugs difíciles de rastrear. std::remove y std::remove_if no modifican el tamaño del contenedor; lo que hacen es reordenar los elementos, moviendo aquellos que cumplen el criterio hacia el principio del rango y devolviendo un iterador que apunta al “nuevo final” lógico. Si no llamas a un método .erase() de tu contenedor para recortar el tamaño real, tu vector mantendrá el tamaño original, dejando “basura” (elementos duplicados o en estados indeterminados) al final.
Estos algoritmos funcionan mediante el movimiento de valores para compactar la secuencia de forma eficiente ($O(n)$). El erase-remove idiom es la combinación clásica donde std::remove reorganiza los elementos y container.erase() ajusta el tamaño físico del contenedor. Con C++20 [C++20], este proceso se ha simplificado mediante funciones no miembros como std::erase y std::erase_if, que encapsulan este proceso en una única llamada limpia y segura.
Deberías usar std::unique cuando necesites eliminar duplicados consecutivos, pero recuerda que para eliminar todos los duplicados de un rango, primero debes ordenarlo con std::sort. Si necesitas reordenar elementos según una condición sin necesidad de un orden total, std::partition es tu herramienta, optando por std::stable_partition si necesitas preservar el orden relativo de los elementos que quedan. Para optimizaciones de rendimiento, utiliza std::nth_element si solo necesitas encontrar el elemento que ocuparía una posición específica (como la mediana) sin ordenar todo el rango, o std::partial_sort si solo te interesan los primeros $K$ elementos de una lista grande.
Si usas std::remove sin erase, tu programa no fallará inmediatamente, pero el tamaño del contenedor será incorrecto, lo que provocará comportamientos erráticos en bucles que dependan de .size() o en lógica de negocio que procese el contenedor completo.
#include <algorithm>
#include <iostream>
#include <list>
#include <string>
#include <vector>
struct Tarea {
int id;
int prioridad; // 1 a 10
bool completada;
std::string nombre;
// Necesario para std::unique si definimos igualdad por ID
bool operator==(const Tarea& otra) const { return id == otra.id; }
};
int main() {
std::vector<Tarea> tareas = {
{1, 5, true, "Limpiar"},
{2, 8, false, "Compilar"},
{3, 2, false, "Debug"},
{4, 8, false, "Documentar"}, // Duplicado de prioridad 8
{5, 1, true, "Revisar"},
{6, 10, false, "Deploy"},
{7, 3, false, "Test"},
{8, 8, false, "Refactor"} // Otro de prioridad 8
};
// 1. Borrado moderno (C++20): Eliminamos tareas completadas
// std::erase_if es más limpio y evita el olvido del .erase()
std::erase_if(tareas, [](const Tarea& t) { return t.completed; });
// 2. std::unique: Eliminamos duplicados consecutivos de tareas con el mismo ID
// Primero ordenamos por ID para que std::unique sea efectivo en todo el rango
std::sort(tareas.begin(), tareas.end(), [](const Tarea& a, const Tarea& b) {
return a.id < b.id;
});
tareas.erase(std::unique(tareas.begin(), tareas.end()), tareas.end());
// 3. std::partition: Separamos tareas de alta prioridad (> 5) de las bajas
// Los elementos que cumplen la condición irán al principio.
// El orden relativo no está garantizado.
auto it_particion = std::partition(tareas.begin(), tareas.end(), [](const Tarea& t) {
return t.prioridad > 5;
});
// 4. std::nth_element: Encontramos la tarea que estaría en la posición
// central si estuviéramos totalmente ordenados por prioridad.
// Es O(n) en promedio, mucho más rápido que un std::sort completo.
if (!tareas.empty()) {
auto it_mediana = tareas.begin() + (tareas.size() / 2);
std::nth_element(tareas.begin(), it_mediana, tareas.end(), [](const Tarea& a, const Tarea& b) {
return a.prioridad < b.prioridad;
});
std::cout << "Mediana de prioridad (id): " << it_mediana->id << "\n";
}
// 5. std::partial_sort: Obtenemos solo las 2 tareas de mayor prioridad
// Ordena parcialmente el rango [begin, begin + 2)
std::partial_sort(tareas.begin(), tareas.begin() + 2, tareas.end(), [](const Tarea& a, const Tarea& b) {
return a.prioridad > b.prioridad;
});
std::cout << "Top 2 prioridades:\n";
for (int i = 0; i < 2; ++i) {
std::cout << " - " << tareas[i].nombre << " (P: " << tareas[i].prioridad << ")\n";
}
return 0;
}
Análisis del funcionamiento
En el ejemplo, std::erase_if realiza una operación de “recolocación” interna: desplaza las tareas que no están completadas al frente del std::vector y, al terminar, actualiza el size() del contenedor de forma segura. Esto evita que el vector mantenga elementos “fantasma” al final.
Cuando aplicamos std::unique después de std::sort, el algoritmo compara cada elemento con su sucesor. Si son iguales (según el operador == sobre id), el segundo se considera duplicado y se “salta” en la reorganización. Es crucial entender que std::unique no borra el elemento del contenedor, solo lo mueve; por eso seguimos necesitando la llamada a .erase() para reducir el tamaño real del vector.
La función std::partition utiliza un algoritmo de dos punteros que intercambia elementos para asegurar que todos los que devuelven true en el predicado queden antes que los que devuelven false. Es altamente eficiente pero “inestable”, lo que significa que el orden original de las tareas de alta prioridad no se mantiene. Si ese orden fuera vital, usaríamos std::stable_partition.
Para la mediana, std::nth_element es la elección técnica correcta. A diferencia de std::sort, que tiene una complejidad de $O(n \log n)$, este algoritmo utiliza una variante de Quickselect para garantizar que el elemento en la posición it_mediana sea el que correspondería si el rango estuviera ordenado, con una complejidad promedio de $O(n)$. El resto de los elementos alrededor quedan particionados, pero no necesariamente ordenados entre sí. Finalmente, std::partial_sort es ideal para tableros de puntuación o listas de “top N”, ya que solo invierte el costo de ordenación en la porción necesaria del rango, siendo más eficiente que ordenar todo el contenedor.
El error frecuente
Un error clásico es intentar usar std::remove para limpiar un contenedor sin llamar a .erase().
std::vector<int> v = {1, 2, 3, 2, 4};
// El usuario espera que v sea {1, 3, 4} y que v.size() sea 3
std::remove(v.begin(), v.end(), 2);
// ERROR: v sigue teniendo size 5. El contenido de v es {1, 3, 4, 3, 4}
// (o valores similares/indeterminados dependiendo de la implementación del move).
std::cout << v.size(); // Imprime 5
Este bug es especialmente peligroso porque no genera un error de compilación. Si usas un iterador basado en v.size() para procesar los elementos, estarás procesando datos corruptos o duplicados. AddressSanitizer podría no detectarlo necesariamente como un error de memoria, ya que el acceso es válido, pero la lógica de negocio fallará.
N° 73