std::vector & SortDocente: Tomás Assenza
Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe
std::vector?• Es una lista o arreglo dinámico contiguo en memoria.
• Su tamaño físico es igual a su tamaño lógico y puede crecer o achicarse durante la ejecución.
• Aunque existe std::array para arreglos estáticos, vector cuenta con muchas más funciones por ser dinámico.
• No necesitás adivinar un TAM_FISICO = 1000 fijo antes de leer N.
• Acceso instantáneo O(1) a cualquier posición mediante v[i].
• Inicializa automáticamente en 0 los elementos creados por tamaño.
vector<int> v {10, 25, 40}; (size = 3)
Primero incluimos la cabecera: #include <vector>
// 1. DECLARACION
vector<int> nombreDelVector; // Vector vacio (tamaño 0)
vector<int> nombreDelVector2(5, 0); // Vector de tamaño 5: {0, 0, 0, 0, 0}
// Formato: vector<T> v(tamaño, valorInicial);
// 2. INICIALIZACION DIRECTA CON VALORES
vector<int> v {10, 20, 30}; // Vector {10, 20, 30} de tamaño 3
// 3. ACCESO Y MODIFICACION DE ELEMENTOS — O(1)
v[0] = 99; // Operador [] tradicional (rapido)
v.at(1) = 50; // Alternativa .at() con chequeo de rango
std::vector
vector<int> v1 {1, 2, 3};
vector<int> v2 {4, 5, 6};
// Primer y ultimo elemento:
cout << v1.front(); // Imprime 1
cout << v1.back(); // Imprime 3
// Estado y cantidad de elementos:
cout << v1.empty(); // 0 (false, tiene datos)
cout << v1.size(); // 3 (tamaño actual)
// Intercambiar dos vectores en O(1):
v1.swap(v2);
// v1 pasa a {4,5,6} y v2 a {1,2,3}
// Insertar al final (aumenta size en 1):
v1.push_back(10);
// Eliminar el ultimo (reduce size en 1):
v1.pop_back();
// Cambiar el tamaño (rellena nuevos con 0):
v1.resize(8);
// Insertar en una posicion intermedia:
v1.insert(v1.begin() + 2, 99);
// Vaciar por completo (size pasa a 0):
v1.clear();
<algorithm> y sort()
#include <vector>
#include <algorithm>
vector<int> v {3, 1, 2};
// De menor a mayor (ascendente):
sort(v.begin(), v.end());
// v pasa a ser {1, 2, 3}
// De mayor a menor (descendente):
sort(v.begin(), v.end(), greater<int>());
// v pasa a ser {3, 2, 1}
Tip Competitiva: Pasar const quimico &a por referencia constante evita copiar todo el struct en cada comparación del sort.
vector de struct
struct quimico {
int numero;
int ganancia;
};
// Ordenar por numero asc, y si empatan, ganancia asc:
bool miComparacion(const quimico &a, const quimico &b) {
if (a.numero != b.numero) return a.numero < b.numero;
return a.ganancia < b.ganancia;
}
vector<quimico> quimicos {q1, q2, q3};
sort(quimicos.begin(), quimicos.end(), miComparacion);
// Comparacion puntual de dos celdas:
if (vector1[0] == vector2[5]) { ... }
// Comparacion total lexicografica:
if (vector1 == vector2) {
// True si tienen igual tamaño y todos
// sus elementos coinciden uno a uno
}
// Encontrar maximo y minimo en O(N):
int maximo = *max_element(v.begin(), v.end());
int minimo = *min_element(v.begin(), v.end());
// 1. Recorrido clasico por indice:
for (size_t i = 0; i < vector1.size(); i++) {
cout << vector1[i] << " ";
}
// 2. Recorrido por elementos (range-for):
for (int elemento : vector1) {
cout << elemento << " ";
}
// Si es un vector de structs, accedemos
// a sus campos: elemento.campo
vector<vector<T>>)
vector<vector<int>> matriz; // Matriz vacia
matriz.resize(cantFilas);
int numeroIngreso;
for (int i = 0; i < cantFilas; i++) {
for (int j = 0; j < cantColumnas; j++) {
cin >> numeroIngreso;
matriz[i].push_back(numeroIngreso);
}
}
// Recorrido clasico por indices [i][j]:
for (size_t i = 0; i < matriz.size(); i++) {
for (size_t j = 0; j < matriz[i].size(); j++)
cout << matriz[i][j] << " ";
cout << endl;
}
// Recorrido por elementos:
for (const auto &fila : matriz) {
for (int elemento : fila)
cout << elemento << " ";
cout << endl;
}
Definimos a la mediana como el valor en la posición central de un conjunto de datos ordenados.
Escribir un programa que reciba un número N que representa una cantidad de mediciones; luego, leer N mediciones e indicar cuál es la mediana. Finalmente, imprimir los valores ordenados.
Aclaración: si N es par, la mediana es el promedio entre los dos valores centrales.
"Para un conjunto de N números, ordenarlos de menor a mayor, calcular el valor central (o promedio de los dos centrales) y mostrarlos."
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> mediciones;
int n, medicion;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> medicion;
mediciones.push_back(medicion);
}
sort(mediciones.begin(), mediciones.end());
cout << "Mediana: ";
int mitad = mediciones.size() / 2;
if (n % 2 != 0) cout << mediciones[mitad] << endl;
else cout << (mediciones[mitad - 1] + mediciones[mitad]) / 2.0 << endl;
cout << "Arreglo: ";
for (int elemento : mediciones) cout << elemento << " ";
cout << endl;
}
Dominaste std::vector y sort(). En el próximo módulo pasamos a indexar por claves con std::map.