Hub Taller STL
Taller de Estructuras Dinámicas (STL) • Módulo 1

std::vector & Sort
Arreglos Dinámicos, Matrices y <algorithm>

Docente: Tomás Assenza

Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe

¿Qué es std::vector?

Conceptos Generales

• 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.

Ventajas Clave

• 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)
10
0
25
1
40
2
v.push_back(99)
Crece solo al final (size = 4)
10
0
25
1
40
2
99
3

Declaración, Inicialización y Acceso

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
                    

Funciones Integradas de std::vector

Consultas e Intercambio


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}
                            

Agregar, Quitar y Redimensionar


// 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();
                            

Ordenamiento con <algorithm> y sort()

1. Ordenamiento Estándar O(N log N)


#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.

2. Ordenar un 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);
                            

Comparación, Recorridos y Extremos

Comparación y Máximo/Mínimo


// 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());
                            

Dos Formas de Recorrer


// 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
                            

Extra: Matrices Dinámicas (vector<vector<T>>)

Declaración y Carga de Elementos


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 Clásico vs Por Elementos


// 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;
}
                            

Ejemplo de Aplicación: La Mediana

Práctica Vector

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.

Antes de resolver, simplificamos el problema:

"Para un conjunto de N números, ordenarlos de menor a mayor, calcular el valor central (o promedio de los dos centrales) y mostrarlos."

Resolución Paso a Paso: La Mediana


#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;
}
                        

Laboratorio en Vivo: Probá el Problema de la Mediana

OneCompiler - C++ Sandbox (Pasá datos en STDIN o ejecutá el caso de prueba)

¡Fin del Módulo 1!

Dominaste std::vector y sort(). En el próximo módulo pasamos a indexar por claves con std::map.

Módulo 0: Iteradores Volver al Hub Ir al Módulo 2: std::map