C++
std :: vector

Introducción

Observaciones

Inicializando un std :: vector

Un std::vector puede inicializarse de varias maneras mientras lo declara:

std::vector<int> v{ 1, 2, 3 };  // v becomes {1, 2, 3}

// Different from std::vector<int> v(3, 6)
std::vector<int> v{ 3, 6 };     // v becomes {3, 6}

// Different from std::vector<int> v{3, 6} in C++11
std::vector<int> v(3, 6);  // v becomes {6, 6, 6}

std::vector<int> v(4);     // v becomes {0, 0, 0, 0}

Un vector se puede inicializar desde otro contenedor de varias maneras:

Copiar construcción (solo de otro vector), que copia datos de v2 :

std::vector<int> v(v2);
std::vector<int> v = v2;

std::vector<int> v(std::move(v2));
std::vector<int> v = std::move(v2);

Construcción de copia de iterador (rango), que copia elementos en v :

// from another vector
std::vector<int> v(v2.begin(), v2.begin() + 3); // v becomes {v2[0], v2[1], v2[2]}

// from an array
int z[] = { 1, 2, 3, 4 };
std::vector<int> v(z, z + 3);                   // v becomes {1, 2, 3}

// from a list
std::list<int> list1{ 1, 2, 3 };
std::vector<int> v(list1.begin(), list1.end()); // v becomes {1, 2, 3}

// from another vector
std::vector<int> v(std::make_move_iterator(v2.begin()),
                   std::make_move_iterator(v2.end());

// from a list
std::list<int> list1{ 1, 2, 3 };
std::vector<int> v(std::make_move_iterator(list1.begin()),
                   std::make_move_iterator(list1.end()));

Con la ayuda de la función miembro assign() , un std::vector se puede reinicializar después de su construcción:

v.assign(4, 100);                      // v becomes {100, 100, 100, 100}

v.assign(v2.begin(), v2.begin() + 3);  // v becomes {v2[0], v2[1], v2[2]}

int z[] = { 1, 2, 3, 4 };
v.assign(z + 1, z + 4);                // v becomes {2, 3, 4}

Insertando Elementos

Anexando un elemento al final de un vector (copiando / moviendo):

struct Point {
  double x, y;
  Point(double x, double y) : x(x), y(y) {}
};
std::vector<Point> v;
Point p(10.0, 2.0);
v.push_back(p);  // p is copied into the vector.

std::vector<Point> v;
v.emplace_back(10.0, 2.0); // The arguments are passed to the constructor of the
                           // given type (here Point). The object is constructed
                           // in the vector, avoiding a copy.

Tenga en cuenta que std::vector no tiene una función miembro push_front() debido a razones de rendimiento. Al agregar un elemento al principio, se mueven todos los elementos existentes en el vector. Si desea insertar elementos con frecuencia al principio de su contenedor, puede usar std::list o std::deque .

Insertando un elemento en cualquier posición de un vector:

std::vector<int> v{ 1, 2, 3 };
v.insert(v.begin(), 9);          // v now contains {9, 1, 2, 3}

std::vector<int> v{ 1, 2, 3 };
v.emplace(v.begin()+1, 9);     // v now contains {1, 9, 2, 3}

Insertando otro vector en cualquier posición del vector:

std::vector<int> v(4);      // contains: 0, 0, 0, 0
std::vector<int> v2(2, 10); // contains: 10, 10
v.insert(v.begin()+2, v2.begin(), v2.end()); // contains: 0, 0, 10, 10, 0, 0

Insertando una matriz en cualquier posición de un vector:

std::vector<int> v(4); // contains: 0, 0, 0, 0
int a [] = {1, 2, 3}; // contains: 1, 2, 3
v.insert(v.begin()+1, a, a+sizeof(a)/sizeof(a[0])); // contains: 0, 1, 2, 3, 0, 0, 0

Use reserve() antes de insertar múltiples elementos si el tamaño del vector resultante se conoce de antemano para evitar múltiples reasignaciones (consulte el tamaño y la capacidad del vector ):

std::vector<int> v;
v.reserve(100);
for(int i = 0; i < 100; ++i)
    v.emplace_back(i);

Asegúrese de no cometer el error de llamar a resize() en este caso, o de lo contrario, creará un vector con 200 elementos en los que solo los últimos cien tendrán el valor deseado.

Iterando Sobre std :: vector

Puedes iterar sobre un std::vector de varias maneras. Para cada una de las siguientes secciones, v se define como sigue:

std::vector<int> v;

Iterando en la dirección hacia adelante

// Range based for
for(const auto& value: v) {
    std::cout << value << "\n";
}

// Using a for loop with iterator
for(auto it = std::begin(v); it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

// Using for_each algorithm, using a function or functor:
void fun(int const& value) {
    std::cout << value << "\n";
}

std::for_each(std::begin(v), std::end(v), fun);

// Using for_each algorithm. Using a lambda:
std::for_each(std::begin(v), std::end(v), [](int const& value) {
    std::cout << value << "\n";
});

// Using a for loop with iterator
for(std::vector<int>::iterator it = std::begin(v); it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

// Using a for loop with index
for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << "\n";
}

Iterando en la dirección inversa

// There is no standard way to use range based for for this.
// See below for alternatives.

// Using for_each algorithm
// Note: Using a lambda for clarity. But a function or functor will work
std::for_each(std::rbegin(v), std::rend(v), [](auto const& value) {
    std::cout << value << "\n";
});

// Using a for loop with iterator
for(auto rit = std::rbegin(v); rit != std::rend(v); ++rit) {
    std::cout << *rit << "\n";
}

// Using a for loop with index
for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[v.size() - 1 - i] << "\n";
}

Aunque no hay una forma integrada de usar el rango para revertir iteración; Es relativamente sencillo arreglar esto. El rango basado en los usos begin() y end() para obtener iteradores y, por lo tanto, simular esto con un objeto de envoltura puede lograr los resultados que requerimos.

template<class C>
struct ReverseRange {
  C c; // could be a reference or a copy, if the original was a temporary
  ReverseRange(C&& cin): c(std::forward<C>(cin)) {}
  ReverseRange(ReverseRange&&)=default;
  ReverseRange& operator=(ReverseRange&&)=delete;
  auto begin() const {return std::rbegin(c);}
  auto end()   const {return std::rend(c);}
};
// C is meant to be deduced, and perfect forwarded into
template<class C>
ReverseRange<C> make_ReverseRange(C&& c) {return {std::forward<C>(c)};}

int main() {
    std::vector<int> v { 1,2,3,4};
    for(auto const& value: make_ReverseRange(v)) {
        std::cout << value << "\n";
    }
}

Hacer cumplir elementos const

Desde C ++ 11, los cbegin() y cend() permiten obtener un iterador constante para un vector, incluso si el vector no es constante. Un iterador constante le permite leer pero no modificar los contenidos del vector, lo que es útil para imponer la corrección constante:

// forward iteration
for (auto pos = v.cbegin(); pos != v.cend(); ++pos) {
   // type of pos is vector<T>::const_iterator
   // *pos = 5; // Compile error - can't write via const iterator
}

// reverse iteration
for (auto pos = v.crbegin(); pos != v.crend(); ++pos) {
   // type of pos is vector<T>::const_iterator
   // *pos = 5; // Compile error - can't write via const iterator
}

// expects Functor::operand()(T&) 
for_each(v.begin(), v.end(), Functor());

// expects Functor::operand()(const T&)
for_each(v.cbegin(), v.cend(), Functor())

for (auto const& e : std::as_const(v)) {
  std::cout << e << '\n';
}

Esto es fácil de implementar en versiones anteriores de C ++:

template <class T>
constexpr std::add_const_t<T>& as_const(T& t) noexcept {
  return t;
}

Una nota sobre la eficiencia

Dado que la clase std::vector es básicamente una clase que administra una matriz contigua asignada dinámicamente, el mismo principio explicado aquí se aplica a los vectores C ++. El acceso al contenido del vector por índice es mucho más eficiente cuando se sigue el principio de orden de fila mayor. Por supuesto, cada acceso al vector también pone su contenido de administración en el caché, pero como se ha debatido muchas veces (especialmente aquí y aquí ), la diferencia en el rendimiento para iterar sobre un std::vector comparación con una matriz en bruto es despreciable. Por lo tanto, el mismo principio de eficiencia para matrices en bruto en C también se aplica para std::vector de C ++.

Elementos de acceso

Hay dos formas principales de acceder a los elementos en un std::vector

• acceso basado en índices
• iteradores

Acceso basado en índices:

Esto se puede hacer con el operador de subíndice [] o la función miembro at() .

Ambos devuelven una referencia al elemento en la posición respectiva en std::vector (a menos que sea un vector<bool> ), para que pueda leerse y modificarse (si el vector no es const ).

[] y at() difieren en que [] no se garantiza que realice ninguna comprobación de límites, mientras que at() hace. El acceso a los elementos donde index < 0 o index >= size es un comportamiento indefinido para [] , mientras que at() lanza una excepción std::out_of_range .

Nota: Los ejemplos a continuación utilizan la inicialización del estilo C ++ 11 para mayor claridad, pero los operadores se pueden usar con todas las versiones (a menos que estén marcados con C ++ 11).

std::vector<int> v{ 1, 2, 3 };

// using []
int a = v[1];    // a is 2
v[1] = 4;        // v now contains { 1, 4, 3 }

// using at()
int b = v.at(2); // b is 3
v.at(2) = 5;     // v now contains { 1, 4, 5 }
int c = v.at(3); // throws std::out_of_range exception

Debido a que el método at() realiza la verificación de límites y puede lanzar excepciones, es más lento que [] . Esto hace que [] código preferido donde la semántica de la operación garantice que el índice está dentro de los límites. En cualquier caso, los accesos a elementos de vectores se realizan en tiempo constante. Eso significa que acceder al primer elemento del vector tiene el mismo costo (en el tiempo) de acceder al segundo elemento, al tercer elemento y así sucesivamente.

Por ejemplo, considere este bucle

for (std::size_t i = 0; i < v.size(); ++i) {
    v[i] = 1;
}

Aquí sabemos que la variable de índice i siempre está dentro de los límites, por lo que sería una pérdida de ciclos de CPU comprobar que i está dentro de los límites para cada llamada al operator[] .

Las funciones de miembro front() y back() permiten un acceso de referencia fácil al primer y último elemento del vector, respectivamente. Estas posiciones se utilizan con frecuencia y los accesores especiales pueden ser más legibles que sus alternativas utilizando [] :

std::vector<int> v{ 4, 5, 6 }; // In pre-C++11 this is more verbose

int a = v.front();   // a is 4, v.front() is equivalent to v[0]
v.front() = 3;       // v now contains {3, 5, 6}
int b = v.back();    // b is 6, v.back() is equivalent to v[v.size() - 1]
v.back() = 7;        // v now contains {3, 5, 7}

Nota : es un comportamiento indefinido invocar front() o back() en un vector vacío. Debe verificar que el contenedor no esté vacío utilizando la función miembro empty() (que verifica si el contenedor está vacío) antes de llamar a front() o back() . A continuación se muestra un ejemplo simple del uso de 'empty ()' para probar un vector vacío:

int main ()
{
  std::vector<int> v;
  int sum (0);

  for (int i=1;i<=10;i++) v.push_back(i);//create and initialize the vector

  while (!v.empty())//loop through until the vector tests to be empty
  {
     sum += v.back();//keep a running total
     v.pop_back();//pop out the element which removes it from the vector
  }

  std::cout << "total: " << sum << '\n';//output the total to the user

  return 0;
}

El ejemplo anterior crea un vector con una secuencia de números del 1 al 10. Luego saca los elementos del vector hasta que el vector está vacío (usando 'vacío ()') para evitar un comportamiento indefinido. Luego, la suma de los números en el vector se calcula y se muestra al usuario.

std::vector<int> v{ 1, 2, 3, 4 }; // v contains {1, 2, 3, 4}
int* p = v.data(); // p points to 1
*p = 4;            // v now contains {4, 2, 3, 4}
++p;               // p points to 2
*p = 3;            // v now contains {4, 3, 3, 4}
p[1] = 2;          // v now contains {4, 3, 2, 4}
*(p + 2) = 1;      // v now contains {4, 3, 2, 1}

std::vector<int> v(4);
int* ptr = &(v.front()); // or &v[0]

Iteradores

Los iteradores se explican más detalladamente en el ejemplo "Iterando sobre std::vector " y el artículo Iteradores . En resumen, actúan de manera similar a los punteros a los elementos del vector:

std::vector<int> v{ 4, 5, 6 };

auto it = v.begin();
int i = *it;        // i is 4
++it; 
i = *it;            // i is 5
*it = 6;            // v contains { 4, 6, 6 }
auto e = v.end();   // e points to the element after the end of v. It can be 
                    // used to check whether an iterator reached the end of the vector:
++it; 
it == v.end();      // false, it points to the element at position 2 (with value 6)
++it;
it == v.end();      // true

Es consistente con el estándar que los iteradores de std::vector<T> realidad son T* s, pero la mayoría de las bibliotecas estándar no lo hacen. No hacer esto mejora los mensajes de error, atrapa el código no portátil y se puede usar para instrumentar los iteradores con las comprobaciones de depuración en las compilaciones no liberadas. Luego, en las compilaciones de lanzamiento, la clase que rodea el puntero subyacente se optimiza.

Puede persistir una referencia o un puntero a un elemento de un vector para el acceso indirecto. Estas referencias o punteros a elementos en el vector permanecen estables y el acceso permanece definido a menos que agregue / elimine elementos en o antes del elemento en el vector , o haga que cambie la capacidad del vector . Esta es la misma que la regla para invalidar iteradores.

std::vector<int> v{ 1, 2, 3 };
int* p = v.data() + 1;     // p points to 2
v.insert(v.begin(), 0);    // p is now invalid, accessing *p is a undefined behavior.
p = v.data() + 1;          // p points to 1
v.reserve(10);             // p is now invalid, accessing *p is a undefined behavior.
p = v.data() + 1;          // p points to 1
v.erase(v.begin());        // p is now invalid, accessing *p is a undefined behavior.

Usando std :: vector como una matriz C

Hay varias formas de usar un std::vector como una matriz de C (por ejemplo, para la compatibilidad con las bibliotecas de C). Esto es posible porque los elementos en un vector se almacenan de forma contigua.

std::vector<int> v{ 1, 2, 3 };
int* p = v.data();

Antes de C ++ 11, tomaría la dirección del primer elemento del vector para obtener un puntero equivalente, si el vector no está vacío, estos dos métodos son intercambiables:

int* p = &v[0];      // combine subscript operator and 0 literal

int* p = &v.front(); // explicitly reference the first element

Nota: Si el vector está vacío, v[0] y v.front() no están definidos y no se pueden usar.

Al almacenar la dirección base de los datos del vector, tenga en cuenta que muchas operaciones (como push_back , resize , etc.) pueden cambiar la ubicación de la memoria de datos del vector, lo que invalida los punteros de datos anteriores . Por ejemplo:

std::vector<int> v;
int* p = v.data();
v.resize(42);      // internal memory location changed; value of p is now invalid

Iterador / Invalidación de puntero

Los iteradores y los punteros que apuntan a un std::vector pueden volverse inválidos, pero solo cuando se realizan ciertas operaciones. El uso de iteradores / punteros no válidos resultará en un comportamiento indefinido.

Las operaciones que invalidan los iteradores / punteros incluyen:

• Cualquier operación de inserción que cambie la capacity del vector invalidará todos los iteradores / punteros:

  vector<int> v(5); // Vector has a size of 5; capacity is unknown.
  int *p1 = &v[0];
  v.push_back(2);   // p1 may have been invalidated, since the capacity was unknown.
  
  v.reserve(20);    // Capacity is now at least 20.
  int *p2 = &v[0];
  v.push_back(4);   // p2 is *not* invalidated, since the size of `v` is now 7.
  v.insert(v.end(), 30, 9); // Inserts 30 elements at the end. The size exceeds the
                            // requested capacity of 20, so `p2` is (probably) invalidated.
  int *p3 = &v[0];
  v.reserve(v.capacity() + 20); // Capacity exceeded, thus `p3` is invalid.
  

auto old_cap = v.capacity();
v.shrink_to_fit();
if(old_cap != v.capacity())
    // Iterators were invalidated.

• Cualquier operación de inserción, que no aumente la capacidad, todavía invalidará los iteradores / punteros que apuntan a los elementos en la posición de inserción y los pasan. Esto incluye el iterador end :

  vector<int> v(5);
  v.reserve(20);                 // Capacity is at least 20.
  int *p1 = &v[0];
  int *p2 = &v[3];
  v.insert(v.begin() + 2, 5, 0); // `p2` is invalidated, but since the capacity
                                 // did not change, `p1` remains valid.
  int *p3 = &v[v.size() - 1];
  v.push_back(10); // The capacity did not change, so `p3` and `p1` remain valid.
  

• Cualquier operación de eliminación invalidará los iteradores / punteros que apuntan a los elementos eliminados y a cualquier elemento más allá de los elementos eliminados. Esto incluye el iterador end :

  vector<int> v(10);
  int *p1 = &v[0];
  int *p2 = &v[5];
  v.erase(v.begin() + 3, v.end()); // `p2` is invalid, but `p1` remains valid.
  

• operator= (copiar, mover u otro) y clear() invalidarán todos los iteradores / punteros que apuntan al vector.

Borrando elementos

Eliminando el último elemento:

std::vector<int> v{ 1, 2, 3 };
v.pop_back();                           // v becomes {1, 2}

Eliminando todos los elementos:

std::vector<int> v{ 1, 2, 3 };
v.clear();                              // v becomes an empty vector

Eliminando elemento por índice:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(v.begin() + 3);                 // v becomes {1, 2, 3, 5, 6}

Nota: Para un vector elimina un elemento que no es el último elemento, todos los elementos más allá del elemento eliminado deben copiarse o moverse para llenar el espacio, consulte la nota a continuación y std :: list .

Borrar todos los elementos en un rango:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(v.begin() + 1, v.begin() + 5);  // v becomes {1, 6}

Nota: Los métodos anteriores no cambian la capacidad del vector, solo el tamaño. Ver Tamaño y Capacidad del Vector .

El método de erase , que elimina una gama de elementos, se utiliza a menudo como parte del lenguaje de borrado-eliminar . Es decir, primero std::remove mueve algunos elementos al final del vector, y luego erase cortes. Esta es una operación relativamente ineficiente para cualquier índice menor que el último índice del vector porque todos los elementos después de los segmentos borrados deben reubicarse en nuevas posiciones. Para aplicaciones críticas de velocidad que requieren la eliminación eficiente de elementos arbitrarios en un contenedor, vea std :: list .

Eliminando elementos por valor:

std::vector<int> v{ 1, 1, 2, 2, 3, 3 };
int value_to_remove = 2;
v.erase(std::remove(v.begin(), v.end(), value_to_remove), v.end()); // v becomes {1, 1, 3, 3}

Eliminando elementos por condición:

// std::remove_if needs a function, that takes a vector element as argument and returns true, 
// if the element shall be removed
bool _predicate(const int& element) {
    return (element > 3); // This will cause all elements to be deleted that are larger than 3
}
...
std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(std::remove_if(v.begin(), v.end(), _predicate), v.end()); // v becomes {1, 2, 3}

Eliminar elementos por lambda, sin crear una función de predicado adicional

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(std::remove_if(v.begin(), v.end(),
     [](auto& element){return element > 3;} ), v.end()
);

Borrar elementos por condición de un bucle:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
std::vector<int>::iterator it = v.begin();
while (it != v.end()) {
    if (condition)
        it = v.erase(it); // after erasing, 'it' will be set to the next element in v
    else
        ++it;             // manually set 'it' to the next element in v
}

Si bien es importante que no se incrementará it en caso de una eliminación, se debe considerar el uso de un método diferente cuando el entonces borrar repetidamente en un bucle. Considere remove_if para una manera más eficiente.

Eliminar elementos por condición de un bucle inverso:

std::vector<int> v{ -1, 0, 1, 2, 3, 4, 5, 6 };
typedef std::vector<int>::reverse_iterator rev_itr;
rev_itr it = v.rbegin();

while (it != v.rend()) { // after the loop only '0' will be in v
    int value = *it;
    if (value) {
        ++it;
        // See explanation below for the following line.
        it = rev_itr(v.erase(it.base()));
    } else
        ++it;
}

Note algunos puntos para el bucle anterior:

• Dado un iterador inverso it apunta a algún elemento, la base del método proporciona el iterador regular (no inverso) que apunta al mismo elemento.

• vector::erase(iterator) borra el elemento apuntado por un iterador y devuelve un iterador al elemento que siguió al elemento dado.

• reverse_iterator::reverse_iterator(iterator) construye un iterador inverso a partir de un iterador.

Poner en total, la línea it = rev_itr(v.erase(it.base())) dice: tomar el iterador inverso it , han v borrar el elemento señalado por su iterador regular; tomar el iterador resultante, construir un iterador inverso de ella, y asignarla al iterador inverso it .

Eliminar todos los elementos usando v.clear() no libera memoria (la capacity() del vector permanece sin cambios). Para reclamar espacio, usa:

std::vector<int>().swap(v);

v.shrink_to_fit();

shrink_to_fit no garantiza reclamar realmente el espacio, pero la mayoría de las implementaciones actuales lo hacen.

Encontrando un Elemento en std :: vector

La función std::find , definida en el encabezado <algorithm> , se puede usar para encontrar un elemento en un std::vector .

std::find usa el operator== para comparar elementos para la igualdad. Devuelve un iterador al primer elemento en el rango que se compara igual al valor.

Si no se encuentra el elemento en cuestión, std::find devuelve std::vector::end (o std::vector::cend si el vector es const ).

static const int arr[] = {5, 4, 3, 2, 1};
std::vector<int> v (arr, arr + sizeof(arr) / sizeof(arr[0]) );

std::vector<int>::iterator it = std::find(v.begin(), v.end(), 4);
std::vector<int>::difference_type index = std::distance(v.begin(), it);
// `it` points to the second element of the vector, `index` is 1

std::vector<int>::iterator missing = std::find(v.begin(), v.end(), 10);
std::vector<int>::difference_type index_missing = std::distance(v.begin(), missing);
// `missing` is v.end(), `index_missing` is 5 (ie. size of the vector)

std::vector<int> v { 5, 4, 3, 2, 1 };

auto it = std::find(v.begin(), v.end(), 4);
auto index = std::distance(v.begin(), it);
// `it` points to the second element of the vector, `index` is 1

auto missing = std::find(v.begin(), v.end(), 10);
auto index_missing = std::distance(v.begin(), missing);
// `missing` is v.end(), `index_missing` is 5 (ie. size of the vector)

Si necesita realizar muchas búsquedas en un vector grande, puede considerar ordenar primero el vector, antes de usar el algoritmo de binary_search .

Para encontrar el primer elemento en un vector que satisface una condición, se puede usar std::find_if . Además de los dos parámetros dados a std::find , std::find_if acepta un tercer argumento que es un objeto de función o puntero de función a una función de predicado. El predicado debe aceptar un elemento del contenedor como argumento y devolver un valor convertible a bool , sin modificar el contenedor:

bool isEven(int val) {
    return (val % 2 == 0); 
}

struct moreThan {
    moreThan(int limit) : _limit(limit) {}
    
    bool operator()(int val) {
        return val > _limit;
    }
    
    int _limit;
};

static const int arr[] = {1, 3, 7, 8};
std::vector<int> v (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    
std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), isEven);
// `it` points to 8, the first even element

std::vector<int>::iterator missing = std::find_if(v.begin(), v.end(), moreThan(10));
// `missing` is v.end(), as no element is greater than 10

// find the first value that is even
std::vector<int> v = {1, 3, 7, 8};
auto it = std::find_if(v.begin(), v.end(), [](int val){return val % 2 == 0;});
// `it` points to 8, the first even element

auto missing = std::find_if(v.begin(), v.end(), [](int val){return val > 10;});
// `missing` is v.end(), as no element is greater than 10

Convertir una matriz a std :: vector

Una matriz se puede convertir fácilmente en un std::vector usando std::begin y std::end :

int values[5] = { 1, 2, 3, 4, 5 }; // source array

std::vector<int> v(std::begin(values), std::end(values)); // copy array to new vector

for(auto &x: v)
    std::cout << x << " ";
std::cout << std::endl;

int main(int argc, char* argv[]) {
    // convert main arguments into a vector of strings.
    std::vector<std::string>  args(argv, argv + argc);
}

También se puede usar un inicializador de C ++ 11 <> para inicializar el vector a la vez

initializer_list<int> arr = { 1,2,3,4,5 };
vector<int> vec1 {arr};

for (auto & i : vec1)
    cout << i << endl;

vector : La excepción a tantas, tantas reglas

El estándar (sección 23.3.7) especifica que se proporciona una especialización del vector<bool> , que optimiza el espacio al empaquetar los valores bool , de modo que cada uno ocupa solo un bit. Dado que los bits no son direccionables en C ++, esto significa que varios requisitos en el vector no se colocan en el vector<bool> :

• No se requiere que los datos almacenados sean contiguos, por lo que no se puede pasar un vector<bool> a una API de C que espera una matriz bool .
• at() , operator [] y la anulación de referencias de los iteradores no devuelven una referencia a bool . Más bien, devuelven un objeto proxy que (de manera imperfecta) simula una referencia a un bool al sobrecargar sus operadores de asignación. Como ejemplo, es posible que el siguiente código no sea válido para std::vector<bool> , porque al eliminar la referencia a un iterador no se devuelve una referencia:

std::vector<bool> v = {true, false};
for (auto &b: v) { } // error

De manera similar, las funciones que esperan un bool& argumento no se pueden usar con el resultado del operator [] o at() aplicado al vector<bool> , o con el resultado de la desreferenciación de su iterador:

  void f(bool& b);
  f(v[0]);             // error
  f(*v.begin());       // error

La implementación de std::vector<bool> depende tanto del compilador como de la arquitectura. La especialización se implementa empaquetando n booleanos en la sección más baja de la memoria. Aquí, n es el tamaño en bits de la memoria direccionable más baja. En la mayoría de los sistemas modernos esto es de 1 byte u 8 bits. Esto significa que un byte puede almacenar 8 valores booleanos. Esta es una mejora sobre la implementación tradicional donde 1 valor booleano se almacena en 1 byte de memoria.

Nota: el siguiente ejemplo muestra los posibles valores bitwise de bytes individuales en un vector<bool> tradicional vs. optimizado. Esto no siempre será cierto en todas las arquitecturas. Sin embargo, es una buena manera de visualizar la optimización. En los ejemplos siguientes, un byte se representa como [x, x, x, x, x, x, x, x].

Tradicional std::vector<char> almacena 8 valores booleanos:

std::vector<char> trad_vect = {true, false, false, false, true, false, true, true};

Representación bitwise:

[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1]

Specialized std::vector<bool> almacena 8 valores booleanos:

std::vector<bool> optimized_vect = {true, false, false, false, true, false, true, true};

Representación bitwise:

[1,0,0,0,1,0,1,1]

Observe en el ejemplo anterior, que en la versión tradicional de std::vector<bool> , 8 los valores booleanos ocupan 8 bytes de memoria, mientras que en la versión optimizada de std::vector<bool> , solo usan 1 byte de memoria. Esta es una mejora significativa en el uso de la memoria. Si necesita pasar un vector<bool> a una API de estilo C, es posible que deba copiar los valores a una matriz o encontrar una mejor manera de usar la API, si la memoria y el rendimiento están en riesgo.

Tamaño y capacidad del vector

El tamaño del vector es simplemente el número de elementos en el vector:

1. El tamaño del vector actual es consultado por la función miembro size() . La función empty() conveniencia devuelve true si el tamaño es 0:

   vector<int> v = { 1, 2, 3 }; // size is 3
   const vector<int>::size_type size = v.size();
   cout << size << endl; // prints 3
   cout << boolalpha << v.empty() << endl; // prints false
   

2. El vector construido predeterminado comienza con un tamaño de 0:

   vector<int> v; // size is 0
   cout << v.size() << endl; // prints 0
   

3. La adición de N elementos al vector aumenta el tamaño en N (por ejemplo, mediante las push_back() , insert() o resize() ).

4. La eliminación de N elementos del vector disminuye el tamaño en N (por ejemplo, mediante las pop_back() , erase() o clear() ).

5. Vector tiene un límite superior específico de la implementación en su tamaño, pero es probable que se quede sin RAM antes de alcanzarla:

   vector<int> v;
   const vector<int>::size_type max_size = v.max_size();
   cout << max_size << endl; // prints some large number
   v.resize( max_size ); // probably won't work
   v.push_back( 1 ); // definitely won't work
   

Error común: el tamaño no es necesariamente (o incluso generalmente) int :

// !!!bad!!!evil!!!
vector<int> v_bad( N, 1 ); // constructs large N size vector
for( int i = 0; i < v_bad.size(); ++i ) { // size is not supposed to be int!
    do_something( v_bad[i] );
}

La capacidad del vector difiere del tamaño . Mientras que el tamaño es simplemente cuántos elementos tiene el vector actualmente, la capacidad es para cuántos elementos asignó / reservó la memoria. Esto es útil porque las (re) asignaciones demasiado frecuentes de tamaños demasiado grandes pueden ser costosas.

1. La capacidad vectorial actual es consultada por la función miembro de capacity() . La capacidad es siempre mayor o igual al tamaño :

   vector<int> v = { 1, 2, 3 }; // size is 3, capacity is >= 3
   const vector<int>::size_type capacity = v.capacity();
   cout << capacity << endl; // prints number >= 3
   

2. Puede reservar la capacidad manualmente mediante la función de reserve( N ) (cambia la capacidad del vector a N ):

   // !!!bad!!!evil!!!
   vector<int> v_bad;
   for( int i = 0; i < 10000; ++i ) {
       v_bad.push_back( i ); // possibly lot of reallocations
   }
   
   // good
   vector<int> v_good;
   v_good.reserve( 10000 ); // good! only one allocation
   for( int i = 0; i < 10000; ++i ) {
       v_good.push_back( i ); // no allocations needed anymore
   }
   

3. Puede solicitar la liberación del exceso de capacidad mediante shrink_to_fit() (pero la implementación no tiene que obedecerle). Esto es útil para conservar la memoria usada:

   vector<int> v = { 1, 2, 3, 4, 5 }; // size is 5, assume capacity is 6
   v.shrink_to_fit(); // capacity is 5 (or possibly still 6)
   cout << boolalpha << v.capacity() == v.size() << endl; // prints likely true (but possibly false)
   

Vector, en parte, administra la capacidad automáticamente, cuando agrega elementos, puede decidir crecer. A los implementadores les gusta usar 2 o 1.5 para el factor de crecimiento (la proporción de oro sería el valor ideal, pero no es práctico debido a que es un número racional). Por otro lado, el vector generalmente no se encoge automáticamente. Por ejemplo:

vector<int> v; // capacity is possibly (but not guaranteed) to be 0
v.push_back( 1 ); // capacity is some starter value, likely 1
v.clear(); // size is 0 but capacity is still same as before!

v = { 1, 2, 3, 4 }; // size is 4, and lets assume capacity is 4.
v.push_back( 5 ); // capacity grows - let's assume it grows to 6 (1.5 factor)
v.push_back( 6 ); // no change in capacity
v.push_back( 7 ); // capacity grows - let's assume it grows to 9 (1.5 factor)
// and so on
v.pop_back(); v.pop_back(); v.pop_back(); v.pop_back(); // capacity stays the same

Vectores de concatenacion

One std::vector se puede agregar a otro usando la función miembro insert() :

std::vector<int> a = {0, 1, 2, 3, 4};
std::vector<int> b = {5, 6, 7, 8, 9};

a.insert(a.end(), b.begin(), b.end());

Sin embargo, esta solución falla si intenta anexarse ​​un vector a sí mismo, porque el estándar especifica que los iteradores dados a insert() no deben ser del mismo rango que los elementos del objeto receptor.

a.insert(std::end(a), std::begin(b), std::end(b));

Si el orden de los elementos en el vector receptor no importa, considerando la cantidad de elementos en cada vector puede evitar operaciones de copia innecesarias:

if (b.size() < a.size())
  a.insert(a.end(), b.begin(), b.end());
else
  b.insert(b.end(), a.begin(), a.end());

Reduciendo la capacidad de un vector

Un std::vector aumenta automáticamente su capacidad al insertarse según sea necesario, pero nunca reduce su capacidad después de la eliminación del elemento.

// Initialize a vector with 100 elements
std::vector<int> v(100);

// The vector's capacity is always at least as large as its size
auto const old_capacity = v.capacity();
// old_capacity >= 100

// Remove half of the elements
v.erase(v.begin() + 50, v.end());  // Reduces the size from 100 to 50 (v.size() == 50),
                                   // but not the capacity (v.capacity() == old_capacity)

Para reducir su capacidad, podemos copiar el contenido de un vector en un nuevo vector temporal. El nuevo vector tendrá la capacidad mínima necesaria para almacenar todos los elementos del vector original. Si la reducción de tamaño del vector original fue significativa, entonces es probable que la reducción de capacidad para el nuevo vector sea significativa. Luego podemos intercambiar el vector original con el temporal para conservar su capacidad minimizada:

std::vector<int>(v).swap(v);

v.shrink_to_fit();

Uso de un vector ordenado para la búsqueda rápida de elementos

El encabezado <algorithm> proporciona una serie de funciones útiles para trabajar con vectores ordenados.

Un requisito previo importante para trabajar con vectores ordenados es que los valores almacenados sean comparables con < .

Un vector sin clasificar se puede ordenar usando la función std::sort() :

std::vector<int> v;
// add some code here to fill v with some elements
std::sort(v.begin(), v.end());

Los vectores std::lower_bound() permiten una búsqueda eficiente de elementos usando la función std::lower_bound() . A diferencia de std::find() , esto realiza una búsqueda binaria eficiente en el vector. El inconveniente es que solo proporciona resultados válidos para rangos de entrada ordenados:

// search the vector for the first element with value 42
std::vector<int>::iterator it = std::lower_bound(v.begin(), v.end(), 42);
if (it != v.end() && *it == 42) {
    // we found the element!
}

Nota: Si el valor solicitado no es parte del vector, std::lower_bound() devolverá un iterador al primer elemento que sea mayor que el valor solicitado. Este comportamiento nos permite insertar un nuevo elemento en su lugar correcto en un vector ya ordenado:

int const new_element = 33;
v.insert(std::lower_bound(v.begin(), v.end(), new_element), new_element);

Si necesita insertar muchos elementos a la vez, podría ser más eficiente llamar a push_back() para todos ellos primero y luego llamar a std::sort() una vez que se hayan insertado todos los elementos. En este caso, el aumento del costo de la clasificación puede compensar el costo reducido de insertar nuevos elementos al final del vector y no en el medio.

Si su vector contiene múltiples elementos del mismo valor, std::lower_bound() intentará devolver un iterador al primer elemento del valor buscado. Sin embargo, si necesita insertar un nuevo elemento después del último elemento del valor buscado, debe usar la función std::upper_bound() ya que esto causará un menor desplazamiento de los elementos:

v.insert(std::upper_bound(v.begin(), v.end(), new_element), new_element);

Si necesita los iteradores de límite superior e inferior, puede usar la función std::equal_range() para recuperar ambos de manera eficiente con una llamada:

std::pair<std::vector<int>::iterator,
          std::vector<int>::iterator> rg = std::equal_range(v.begin(), v.end(), 42);
std::vector<int>::iterator lower_bound = rg.first;
std::vector<int>::iterator upper_bound = rg.second;

Para probar si un elemento existe en un vector ordenado (aunque no es específico de los vectores), puede usar la función std::binary_search() :

bool exists = std::binary_search(v.begin(), v.end(), value_to_find);

Funciones que devuelven grandes vectores

#include <vector>
#include <iostream>

// If the compiler is unable to perform named return value optimization (NRVO)
// and elide the move altogether, it is required to move from v into the return value.
std::vector<int> fillVector(int a, int b) {
    std::vector<int> v;
    v.reserve(b-a+1);
    for (int i = a; i <= b; i++) {
        v.push_back(i);
    }
    return v; // implicit move
}

int main() { // declare and fill vector
    std::vector<int> vec = fillVector(1, 10);

    // print vector
    for (auto value : vec)
        std::cout << value << " "; // this will print "1 2 3 4 5 6 7 8 9 10 "

    std::cout << std::endl;

    return 0;
}

#include <vector>
#include <iostream>

// passing a std::vector by reference
void fillVectorFrom_By_Ref(int a, int b, std::vector<int> &v) {
    assert(v.empty());
    v.reserve(b-a+1);
    for (int i = a; i <= b; i++) {
        v.push_back(i);
    }
}

int main() {// declare vector
    std::vector<int> vec;
    
    // fill vector
    fillVectorFrom_By_Ref(1, 10, vec);
    // print vector
    for (std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it)
        std::cout << *it << " "; // this will print "1 2 3 4 5 6 7 8 9 10 "
    std::cout << std::endl;
    return 0;
}

Encuentre el elemento máximo y mínimo y el índice respectivo en un vector

Para encontrar el elemento más grande o más pequeño almacenado en un vector, puede usar los métodos std::max_element y std::min_element , respectivamente. Estos métodos se definen en el encabezado <algorithm> . Si varios elementos son equivalentes al elemento más grande (el más pequeño), los métodos devuelven el iterador al primer elemento de este tipo. Devuelve v.end() para vectores vacíos.

std::vector<int> v = {5, 2, 8, 10, 9}; 
int maxElementIndex = std::max_element(v.begin(),v.end()) - v.begin();
int maxElement = *std::max_element(v.begin(), v.end());

int minElementIndex = std::min_element(v.begin(),v.end()) - v.begin();
int minElement = *std::min_element(v.begin(), v.end());

std::cout << "maxElementIndex:" << maxElementIndex << ", maxElement:" << maxElement << '\n';
std::cout << "minElementIndex:" << minElementIndex << ", minElement:" << minElement << '\n';

Salida:

maxElementIndex: 3, maxElement: 10
minElementIndex: 1, minElement: 2

std::vector<int> v = {5, 2, 8, 10, 9}; 
auto minmax = std::minmax_element(v.begin(), v.end());

std::cout << "minimum element: " << *minmax.first << '\n';
std::cout << "maximum element: " << *minmax.second << '\n';

Matrices usando vectores

Los vectores se pueden utilizar como una matriz 2D definiéndolos como un vector de vectores.

Una matriz con 3 filas y 4 columnas con cada celda inicializada como 0 puede definirse como:

std::vector<std::vector<int> > matrix(3, std::vector<int>(4));

  std::vector<std::vector<int>> matrix = { {0,1,2,3},
                                           {4,5,6,7}, 
                                           {8,9,10,11}
                                         };

Se puede acceder a los valores en un vector similar a una matriz 2D

int var = matrix[0][2];

La iteración en toda la matriz es similar a la de un vector normal pero con una dimensión adicional.

for(int i = 0; i < 3; ++i)
{
    for(int j = 0; j < 4; ++j)
    {
        std::cout << matrix[i][j] << std::endl;
    }
}

for(auto& row: matrix)
{
    for(auto& col : row)
    { 
        std::cout << col << std::endl;
    }
}

Un vector de vectores es una forma conveniente de representar una matriz, pero no es el más eficiente: los vectores individuales están dispersos alrededor de la memoria y la estructura de datos no es compatible con el caché.

Además, en una matriz adecuada, la longitud de cada fila debe ser la misma (este no es el caso de un vector de vectores). La flexibilidad adicional puede ser una fuente de errores.