Vector ( std::vector<T>) es un patrón de programación genérico estándar de C++ que implementa una matriz dinámica .
La plantilla vectorse encuentra en el archivo de cabecera <vector>. Como todos los componentes estándar, se encuentra en el std . Esta interfaz emula el funcionamiento de una matriz C estándar (por ejemplo, acceso aleatorio rápido a los elementos), así como algunas características adicionales, como el cambio de tamaño automático de un vector cuando se insertan o eliminan elementos.
Todos los elementos de un vector deben ser del mismo tipo. Por ejemplo, no puede almacenar datos char e int juntos en la misma instancia de vector. La clase vector tiene un conjunto estándar de métodos para acceder a elementos, agregar y eliminar elementos y obtener la cantidad de elementos para almacenar.
Un vector se puede inicializar con cualquier tipo que tenga un constructor de copia y esté definido operator=y cumpla las siguientes condiciones [1] :
| Expresión | tipo de retorno | Condición |
|---|---|---|
| t = u | T& | tequivalenteu |
| T(t) | tequivalenteT(t) | |
| T(u) | uequivalenteT(u) | |
| &u | const T* | muestra la direcciónu |
| t.~T() |
Aquí T , es el tipo con el que se inicializa el vector, t es una variable de tipo T, u es una variable de tipo (posiblemente const) T.
Por ejemplo:
vector < int > miVector ; // Un vector vacío de elementos de tipo int vector < float > myVector ( 10 ); // Un vector de 10 floats vector < char > myVector ( 5 , ' ' ); // Vector que consta de 5 espacios clase T { ... }; entero n = 10 ; vector < T > miVector ( n ); // Vector de 10 elementos de tipo personalizado TSe puede acceder a un elemento individual de un vector utilizando las operaciones descritas en la siguiente tabla. Por convención de C y C++ , el primer elemento tiene índice 0y el último elemento tiene índice size() - 1[2] .
| Expresión | tipo de retorno | control fronterizo? |
|---|---|---|
| v.at(i) | T&o const T¶ el elemento i | Lanzar una excepción es posibleout_of_range |
| v[i] | T&o const T¶ el elemento i | Comportamiento indefinido cuandoi >= v.size() |
| v.front() | T&o const T¶ el primer elemento | Comportamiento indefinido cuandov.empty() == true |
| v.back() | T&o const T¶ el último elemento | Comportamiento indefinido cuandov.empty() == true |
Donde v es un objeto de tipo (posiblemente const) vector<T>y i es el índice del elemento requerido del vector.
Una clase vector es un contenedor. Según el estándar de C++, cualquier contenedor debe contener los métodos begin(), end(), size(), max_size(), empty()y swap().
A continuación se muestra una breve lista de los métodos disponibles con una descripción y una indicación de la complejidad .
| Método | Descripción | Complejidad | |
|---|---|---|---|
| Constructores | vector::vector | El constructor predeterminado. No toma argumentos, crea una nueva instancia de vector | O(1)(realiza en tiempo constante) |
| vector::vector(const vector& c) | El constructor de copia predeterminado. Crea una copia del vector.c | O(n)(realiza en tiempo lineal proporcional al tamaño del vector c) | |
| vector::vector(size_type n, const T& val = T()) | Crea un vector con nobjetos. Si valse declara, cada uno de estos objetos se inicializará con su valor; de lo contrario, los objetos obtendrán un valor de constructor predeterminado de tipo T. | O(n) | |
| vector::vector(input_iterator start, input_iterator end) | Crea un vector de elementos entre startyend | O(n) | |
| Incinerador de basuras | vector::~vector | Destruye el vector y sus elementos. | |
| Operadores | vector::operator= | Copia el valor de un vector a otro. | O(n) |
| vector::operator== | Comparación de dos vectores | O(n) | |
| Acceso a elementos |
vector::at | Acceso a un elemento con comprobación fuera de límites | O(1) |
| vector::operator[] | Acceder a un elemento específico | O(1) | |
| vector::front | Accediendo al primer elemento | O(1) | |
| vector::back | Accediendo al último elemento | O(1) | |
| iteradores | vector::begin | Devuelve un iterador al primer elemento del vector. | O(1) |
| vector::end | Devuelve un iterador después del último elemento del vector. | O(1) | |
| vector::rbegin | Vuelve reverse_iteratoral final del vector actual. | O(1) | |
| vector::rend | Vuelve reverse_iteratoral principio del vector. | O(1) | |
| Trabajar con tamaño vectorial |
vector::empty | Devuelve truesi el vector está vacío | O(1) |
| vector::size | Devuelve el número de elementos en el vector. | O(1) | |
| vector::max_size | Devuelve el máximo número posible de elementos en un vector | O(1) | |
| vector::reserve | Establece el número mínimo posible de elementos en un vector | O(n) | |
| vector::capacity | Devuelve el número de elementos que puede contener el vector antes de que necesite asignar más espacio. | O(1) | |
| vector::shrink_to_fit | Reduce la cantidad de memoria utilizada al liberar la memoria no utilizada ( C++11 ) | O(1) | |
| Modificadores | vector::clear | Elimina todos los elementos del vector. | O(n) |
| vector::insert | Insertar elementos en un vector | Inserción al final, siempre que la memoria no sea reasignada - O(1), a un lugar arbitrario -O(n) | |
| vector::erase | Elimina los elementos vectoriales especificados (uno o más) | O(n) | |
| vector::push_back | Insertar un elemento al final de un vector | O(1) | |
| vector::pop_back | Eliminar el último elemento del vector | O(1) | |
| vector::resize | Cambia el tamaño del vector por la cantidad dada | O(n) | |
| vector::swap | Intercambiar el contenido de dos vectores | O(1) | |
| Otros metodos | vector::assign | Asocia valores dados con un vector | O(n), si se establece el tamaño de vector deseado, O(n*log(n))al reasignar memoria |
| vector::get_allocator | Devuelve el asignador utilizado para asignar memoria | O(1) |
Además de las funciones de acceso directo a elementos descritas anteriormente, se puede acceder a los elementos de un vector mediante iteradores .
Los iteradores generalmente se usan en pares, uno de los cuales se usa para indicar la iteración actual y el segundo se usa para indicar el final del contenedor. Los iteradores se crean utilizando métodos estándar begin()como end(). La función begin()devuelve un puntero al primer elemento y devuelve un puntero a un end() elemento imaginario inexistente que sigue al último.
El vector utiliza el tipo de iterador más rico en funciones, RandomAccessIterator (iterador de acceso aleatorio), que le permite recorrer el contenedor en cualquier orden, así como cambiar el contenido del vector en el proceso de recorrido. Sin embargo, si el vector cambia, el iterador puede volverse inválido.
Un ejemplo de cálculo de la suma de elementos vectoriales usando iteradores:
#incluir <iostream> #incluir <vector> #include <iterador> utilizando el espacio de nombres estándar ; int principal () { vector < int > el_vector ; vector < int >:: iterador the_iterator ; para ( int yo = 0 ; yo < 10 ; yo ++ ) { el_vector . retroceder ( yo ); } entero total = 0 ; el_iterador = el_vector . comenzar (); while ( el_iterador != el_vector . end ()) { total += * the_iterator ++ ; } cout << "summa= " << total << endl ; devolver 0 ; } vector < int > el_vector ; vector < int >:: iterador the_iterator ; para ( int yo = 0 ; yo < 10 ; yo ++ ) { el_vector . retroceder ( yo ); } entero total = 0 ; el_iterador = el_vector . comenzar (); while ( el_iterador != el_vector . end ()) { total += * el_iterador ; /* Tenga en cuenta que se puede acceder al elemento eliminando la referencia del iterador */ ++ el_iterador ; } cout << "Total=" << total << endl ;Resultado:
Total=45
Una implementación de vector típica es un puntero a una matriz dinámica. El tamaño de un vector es el número real de elementos y el tamaño es la cantidad de memoria que utiliza.
Si, al insertar nuevos elementos en un vector, su tamaño se vuelve mayor que su volumen, se reasigna la memoria. Por lo general, esto hará que el vector asigne una nueva área de almacenamiento, moviendo los elementos y liberando áreas antiguas a la nueva ubicación de memoria.
Debido a que las direcciones de los elementos cambian durante este proceso, cualquier referencia o iterador de elementos en el vector puede volverse inválido. El uso de referencias no válidas da como resultado un comportamiento indefinido. Ejemplo:
#incluir <vector> int principal () { estándar :: vector < int > v ( 1 ); // Cree un vector con un elemento int cuyo valor sea 0 int & first = * v . comenzar (); // Crea un enlace al primer elemento v . insertar ( v . fin (), v . capacidad (), 0 ); // Agrega nuevos elementos int i = first ; // Comportamiento indefinido. El enlace puede no ser válido }El método reserve()se utiliza para evitar la reasignación de memoria innecesaria. Después de llamar reserve(n), se garantiza que el tamaño del vector no será inferior a n. Ejemplo:
#incluir <vector> int principal () { estándar :: vector < int > v ( 1 ); // Crea un vector que consta de un solo elemento de tipo int cuyo valor es 0 v . reserva ( 10 ); // Reservar espacio int & first = * v . comenzar (); // Crea un enlace al primer elemento v . insertar ( v . fin (), 5 , 0 ); // Agregar elementos al vector int i = first ; // OK ya que no hubo reasignación de memoria }Un vector mantiene un orden específico de sus elementos, de modo que cuando se inserta un nuevo elemento al principio o en medio del vector, los elementos subsiguientes se mueven hacia atrás en términos de su operador de asignación y constructor de copia. Por lo tanto, se invalidan las referencias a elementos y los iteradores después del punto de inserción. Ejemplo:
#incluir <vector> int principal () { estándar :: vector < int > v ( 2 ); // Crea un vector que consta de dos elementos de tipo Int // Crea referencias a ambos elementos int & first = v . frente (); int & último = v . atrás (); v . insertar ( v . comenzar () + 1 , 1 , 1 ); // Agrega nuevos elementos al medio del vector int i = first ; // Comportamiento indefinido si una inserción provocó una reasignación int j = last ; // Comportamiento indefinido, según el estándar C++, §23.2.4.3/1 }La biblioteca estándar de C++ define una especialización de plantilla vectorial para bool. Según la especialización, el vector debe empaquetar los elementos para que cada elemento del tipo bооluse solo un bit de memoria [3] . Esto es llamado un error por muchos [4] [5] porque no cumple con los requisitos del vector<bool>contenedor de la biblioteca estándar de C++ . Por ejemplo, el contenedor <T>::referencedebe ser verdadero lvaluedel tipo T. Este no es el caso con c vector<bool>::reference, que es un marcador de posición convertible a bool[6] . Además, vector<bool>::iteratorno da bool&a la desreferencia. Existe un acuerdo entre el comité de estandarización de C++ y el equipo de desarrollo de la biblioteca de que vector<bool>debe quedar obsoleto y luego eliminarse de la biblioteca estándar y la funcionalidad se restaurará, pero con un nombre diferente. [7]
Los programas de C++ que usan un vector deben incluir un archivo de encabezado <vector>:
#incluir <vector> // Después de eso, puede inicializar la variable std :: vector < T > myVector ;Aquí T , el tipo de datos que se almacenarán en el contenedor y myVector la variable que se utilizará. Tpuede ser cualquier tipo de datos, incluido un tipo de datos definido por el usuario.
En C y C++ , una matriz son datos en bloques de memoria contiguos. Luego, a cada bloque se le asigna un índice, y el contenido de cada bloque se puede encontrar conociendo su índice. Todos los elementos de una matriz deben ser del mismo tipo.
Un vector es similar a una matriz dinámica, pero un vector puede cambiar de tamaño. Además, no hay necesidad de liberar memoria manualmente.
Dado que los elementos de un vector se almacenan de forma contigua, la dirección del primer elemento del vector se puede pasar a la función como una matriz (puntero al primer elemento). El siguiente ejemplo ilustra cómo se puede usar un vector con las funciones de biblioteca estándar de C memcpyy printf:
#include <cstring> // memcpy #incluir <vector> #incluir <cstdio> // printf int principal () { utilizando el espacio de nombres estándar ; const char arr [] = "1234567890" ; // Crea un vector con 11 '\0' vector < char > vec ( sizeof arr ); // Copia 11 elementos de tipo 'char' en un vector memcpy ( vec . data (), arr , sizeof arr ); // Imprime "1234567890" printf ( "%s" , vec . data ()); }Tenga en cuenta que se desaconseja el uso de memcpyy printf, a favor de alternativas más seguras de la biblioteca estándar de C++
El siguiente ejemplo demuestra varias técnicas que involucran un vector y algoritmos de biblioteca estándar de C++ , como barajar, clasificar, encontrar el elemento más grande y eliminar de un vector usando el idioma erase-remove.
#incluir <iostream> #incluir <vector> #incluir <algoritmo> // ordenar, max_element, random_shuffle, remove_if, lower_bound #include <funcional> // mayor, bind2nd // Usado por conveniencia. En programas reales, use con cuidado el uso de namespace std ; int principal () { int arr [ 4 ] = { 1 , 2 , 3 , 4 }; // Inicializar un vector usando una matriz vector < int > numeros ( arr , arr + 4 ); // Agrega números al vector de números . retroceder ( 5 ); numeros _ empujar_retroceder ( 6 ); numeros _ empujar_retroceder ( 7 ); numeros _ empujar_retroceder ( 8 ); // Ahora el vector se ve así: {1, 2, 3, 4, 5, 6, 7, 8} // Mezcla aleatoriamente los elementos random_shuffle ( numbers . begin (), numbers . end ()); // Obtener el elemento máximo, complejidad O(n) vector < int >:: const_iterator mayor = max_element ( numbers . begin (), numbers . end () ); cout << "elemento mayor" << * mayor << endl ; cout << "Índice de este elemento" << números - mayores . comenzar () << endl ; // Ordenar los elementos, complejidad O(n log n) sort ( numbers . begin (), numbers . end ()); // Encuentra la posición del número 5 en el vector, complejidad O(log n) vector < int >:: const_iterator cinco = límite_inferior ( números . comienzo (), números . fin (), 5 ); cout << "El número 5 está en el índice" << cinco números . comenzar () << endl ; // Elimina todos los elementos mayores de 4 números . erase ( remove_if ( numeros . comenzar (), numeros . fin (), bind2nd ( mayor < int > (), 4 )), numeros . fin () ); // Imprime el resto para ( vector < int >:: const_iterator it = numeros . begin (); it != numeros . end (); ++ it ) { cout << * it << ' ' ; } devolver 0 ; }La salida contendrá:
Elemento más grande 8
El índice de este elemento es 6 (depende de la implementación)
El número 5 se encuentra debajo del índice 4.
1 2 3 4
Un ejemplo de un vector dinámico bidimensional, así como un ejemplo de acceso y modificación.
typedef std :: vector < std :: vector < int > > pxMP ; función vacía () { int tamañoX , tamañoY ; // especificar el tamaño sobre la marcha. pxMP pxMap ( tamañoX , std :: vector < int > ( tamañoY )); // matriz de píxeles de tamaño X/Y 0.1. mapapx [ 0 ][ 5 ] = 1 ; /* acceso */ // elimina las columnas izquierda y derecha de pxMap . pop_back (); pxMapa . borrar ( pxMap.begin ( ) ); // elimine las filas superior e inferior de todas las columnas, primero cree algunas herramientas para esto: std :: vector < std :: vector < int > >:: iterator iterlvl2 ; // iterador para la segunda dimensión. std :: vector < int >:: iterador iterlvl1 ; // iterador para la primera dimensión // Profundice en ( iterlvl2 = pxMap . begin (); iterlvl2 != pxMap . end (); iterlvl2 ++ ) { iterlvl1 = ( * iterlvl2 ). comenzar (); // Solo con fines de demostración ( * iterlvl2 ). pop_back (); ( * iterlvl2 ). borrar (( * iterlvl2 ) .begin ()); // ¿Dónde estamos? tamañoY = ( * iterlvl2 ). tamaño (); // Establecer sizeY mientras estamos en este nivel. Entonces no podremos hacerlo } }Un ejemplo de un vector dinámico unidimensional, ordenando y eliminando duplicados:
#incluir <vector> #incluir <cadena> #include <algorithm> // Para usar los algoritmos std::sort, std::unique int principal () { estándar :: vector < estándar :: cadena > v_str ; //Vector vacío v_str v_str . push_back ( "zz" ); // {"zz"} v_str . push_back ( "aa" ); // {"zz", "aa"} v_str . push_back ( "bb" ); // {"zz", "aa", "bb"} v_str . push_back ( "aa" ); // {"zz", "aa", "bb", "aa"} v_str . retroceder ( "xx" ); // {"zz", "aa", "bb", "aa", "xx"} v_str . push_back ( "dd" ); // {"zz", "aa", "bb", "aa", "xx", "dd"} v_str . retroceder ( "xx" ); // {"zz", "aa", "bb", "aa", "xx", "dd", "xx"} //Ordenar todos los elementos del vector std :: sort ( v_str . begin ()), v_str.end ( ) ); //Resultado de la clasificación de vectores: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"} // Eliminar duplicados v_str . borrar ( std :: único ( v_str . begin (), v_str . end () ), v_str . end () ); //Resultado de eliminar duplicados: {"aa","bb","dd","xx","zz"} return 0 ; }