C++
std :: vector

introduzione

Osservazioni

Inizializzazione di un vettore std ::

Un std::vector può essere inizializzato in vari modi pur dichiarandolo:

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 vettore può essere inizializzato da un altro contenitore in diversi modi:

Copia la costruzione (solo da un altro vettore), che copia i dati dalla 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);

Iterator (range) copy-construction, che copia elementi in 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 l'aiuto della funzione membro assign() , un std::vector può essere reinizializzato dopo la sua costruzione:

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}

Inserimento di elementi

Aggiunta di un elemento alla fine di un vettore (copiando / spostando):

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.

Si noti che std::vector non ha una funzione membro push_front() causa di motivi di prestazioni. L'aggiunta di un elemento all'inizio fa muovere tutti gli elementi esistenti nel vettore. Se si desidera inserire spesso elementi all'inizio del contenitore, è possibile utilizzare invece std::list o std::deque .

Inserimento di un elemento in qualsiasi posizione di un vettore:

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}

Inserimento di un altro vettore in qualsiasi posizione del vettore:

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

Inserimento di un array in qualsiasi posizione di un vettore:

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

Utilizzare reserve() prima di inserire più elementi se la dimensione vettoriale risultante è nota in anticipo per evitare riallocazioni multiple (vedere dimensioni e capacità del vettore ):

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

Assicurati di non commettere l'errore di chiamare resize() in questo caso, altrimenti creerai inavvertitamente un vettore con 200 elementi in cui solo gli ultimi cento avranno il valore desiderato.

Iterating Over std :: vector

È possibile eseguire iterazioni su un std::vector in diversi modi. Per ciascuna delle seguenti sezioni, v è definito come segue:

std::vector<int> v;

Iterating nella direzione di andata

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

Iterazione nella direzione 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";
}

Anche se non esiste un modo integrato per utilizzare l'intervallo in base a per invertire l'iterazione; è relativamente semplice risolvere questo problema. L'intervallo basato sugli usi begin() e end() per ottenere gli iteratori e quindi simulare questo con un oggetto wrapper può ottenere i risultati che richiediamo.

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

Imporre elementi const

Dal C ++ 11 i cbegin() e cend() consentono di ottenere un iteratore costante per un vettore, anche se il vettore non è const. Un iteratore costante consente di leggere ma non modificare il contenuto del vettore che è utile per applicare la correttezza const:

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

È facile da implementare nelle versioni precedenti di C ++:

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

Una nota sull'efficienza

Poiché la classe std::vector è fondamentalmente una classe che gestisce una matrice contigua allocata dinamicamente, lo stesso principio spiegato qui si applica ai vettori C ++. L'accesso al contenuto del vettore per indice è molto più efficiente quando si segue il principio dell'ordine delle righe principali. Ovviamente, ogni accesso al vettore mette anche il suo contenuto di gestione nella cache, ma come è stato discusso molte volte (in particolare qui e qui ), la differenza di prestazioni per iterare su un std::vector rispetto a un array raw è trascurabile. Quindi lo stesso principio di efficienza per le matrici raw in C vale anche per lo std::vector di C ++.

Accesso agli elementi

Esistono due modi principali per accedere agli elementi in un std::vector

• accesso basato su indice
• iteratori

Accesso basato su indice:

Questo può essere fatto sia con l'operatore pedice [] , sia con la funzione membro at() .

Entrambi restituiscono un riferimento all'elemento nella rispettiva posizione in std::vector (a meno che non sia un vector<bool> ), in modo che possa essere letto e modificato (se il vettore non è const ).

[] e at() differiscono per il fatto che [] non è garantito il controllo dei limiti, mentre at() fa. Accedere agli elementi in cui index < 0 o index >= size è un comportamento non definito per [] , mentre at() genera un'eccezione std::out_of_range .

Nota: gli esempi seguenti utilizzano l'inizializzazione in stile C ++ 11 per chiarezza, ma gli operatori possono essere utilizzati con tutte le versioni (a meno che non sia contrassegnato 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

Poiché il metodo at() esegue il controllo dei limiti e può generare eccezioni, è più lento di [] . Questo rende [] codice preferito in cui la semantica dell'operazione garantisce che l'indice sia limitato. In ogni caso, gli accessi agli elementi dei vettori vengono eseguiti in tempo costante. Ciò significa che l'accesso al primo elemento del vettore ha lo stesso costo (nel tempo) dell'accesso al secondo elemento, al terzo elemento e così via.

Ad esempio, considera questo ciclo

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

Qui sappiamo che la variabile indice i è sempre in perenne, quindi sarebbe uno spreco di cicli della CPU per verificare che i limiti per ogni chiamata operator[] .

Le funzioni membro front() e back() consentono un facile accesso di riferimento al primo e all'ultimo elemento del vettore, rispettivamente. Queste posizioni sono usate frequentemente e gli accessor speciali possono essere più leggibili delle loro alternative usando [] :

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 : è un comportamento indefinito invocare front() o back() su un vettore vuoto. È necessario verificare che il contenitore non sia vuoto usando la funzione membro empty() (che controlla se il contenitore è vuoto) prima di chiamare front() o back() . Segue un semplice esempio dell'uso di "empty ()" per verificare un vettore vuoto:

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

L'esempio sopra crea un vettore con una sequenza di numeri da 1 a 10. Quindi apre gli elementi del vettore fino a quando il vettore non è vuoto (usando 'empty ()') per impedire un comportamento indefinito. Quindi la somma dei numeri nel vettore viene calcolata e visualizzata all'utente.

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]

iteratori:

Gli iteratori sono spiegati in modo più dettagliato nell'esempio "Iterating over std::vector " e l'articolo Iterators . In breve, agiscono in modo simile ai puntatori agli elementi del vettore:

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

È coerente con lo standard che gli iteratori di std::vector<T> siano in realtà T* s, ma la maggior parte delle librerie standard non lo fa. Non farlo migliora entrambi i messaggi di errore, cattura codice non portabile e può essere usato per strumentare gli iteratori con controlli di debug in build non a rilascio. Quindi, in build di rilascio, la classe che avvolge il puntatore sottostante viene ottimizzata.

È possibile mantenere un riferimento o un puntatore a un elemento di un vettore per l'accesso indiretto. Questi riferimenti o puntatori agli elementi nel vector rimangono stabili e l'accesso rimane definito a meno che non si aggiungano / rimuovano elementi ao prima dell'elemento nel vector o si provochi la modifica della capacità del vector . Questa è la stessa regola per invalidare gli iteratori.

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 come array C

Esistono diversi modi per utilizzare un std::vector come un array C (ad esempio, per la compatibilità con le librerie C). Questo è possibile perché gli elementi in un vettore sono memorizzati in modo contiguo.

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

Prima di C ++ 11, dovresti prendere l'indirizzo del primo elemento del vettore per ottenere un puntatore equivalente, se il vettore non è vuoto, questi due metodi sono intercambiabili:

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

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

Nota: se il vettore è vuoto, v[0] e v.front() non sono definiti e non possono essere utilizzati.

Quando si memorizza l'indirizzo di base dei dati del vettore, si noti che molte operazioni (come push_back , resize , ecc.) Possono modificare la posizione della memoria di dati del vettore, invalidando così i puntatori di dati precedenti . Per esempio:

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

Iterator / Pointer Invalidation

Iteratori e puntatori che puntano in un std::vector possono diventare non validi, ma solo quando si eseguono determinate operazioni. L'utilizzo di iteratori / puntatori non validi comporterà un comportamento indefinito.

Le operazioni che invalidano gli iteratori / i puntatori includono:

• Qualsiasi operazione di inserimento che modifichi la capacity del vector invaliderà tutti gli iteratori / puntatori:

  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.

• Qualsiasi operazione di inserimento, che non aumenta la capacità, invalida ancora iteratori / puntatori che puntano agli elementi nella posizione di inserimento e oltre. Questo include l'iteratore 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.
  

• Qualsiasi operazione di rimozione invaliderà iteratori / puntatori che puntano agli elementi rimossi e a qualsiasi elemento oltre gli elementi rimossi. Questo include l'iteratore 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= (copia, sposta o altrimenti) e clear() invalideranno tutti gli iteratori / puntatori che puntano nel vettore.

Eliminazione di elementi

Eliminazione dell'ultimo elemento:

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

Eliminazione di tutti gli elementi:

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

Eliminazione elemento per indice:

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

Nota: per un vector cancella un elemento che non è l'ultimo elemento, tutti gli elementi oltre l'elemento eliminato devono essere copiati o spostati per riempire il vuoto, vedere la nota sotto e std :: list .

Eliminazione di tutti gli elementi in un intervallo:

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

Nota: i metodi sopra riportati non modificano la capacità del vettore, ma solo la dimensione. Vedi Dimensioni e capacità del vettore .

Il metodo di erase , che rimuove un intervallo di elementi, viene spesso utilizzato come parte dell'idioma di cancellazione-rimozione . Cioè, prima std::remove mosse alcuni elementi alla fine del vettore, e quindi erase costolette di dosso. Si tratta di un'operazione relativamente inefficiente per qualsiasi indice inferiore all'ultimo indice del vettore, in quanto tutti gli elementi dopo i segmenti cancellati devono essere trasferiti in nuove posizioni. Per applicazioni critiche che richiedono la rimozione efficiente di elementi arbitrari in un contenitore, vedere std :: list .

Eliminazione di elementi in base al valore:

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}

Eliminazione di elementi in base alla condizione:

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

Eliminazione di elementi di lambda, senza creare una funzione di predicato aggiuntiva

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

Eliminazione di elementi in base alla condizione da un ciclo:

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
}

Mentre è importante non incrementare it in caso di cancellazione, si dovrebbe considerare l'utilizzo di un metodo diverso quando poi cancellare più volte in un ciclo. Considerare remove_if per un modo più efficiente.

Eliminazione di elementi in base alla condizione da un ciclo 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;
}

Nota alcuni punti per il ciclo precedente:

• Dato un iteratore inverso it punta a qualche elemento, il metodo base fornisce l'iteratore regolare (non inverso) che punta allo stesso elemento.

• vector::erase(iterator) cancella l'elemento puntato da un iteratore e restituisce un iteratore all'elemento che ha seguito l'elemento specificato.

• reverse_iterator::reverse_iterator(iterator) costruisce un iteratore inverso da un iteratore.

Mettere tutto, la linea it = rev_itr(v.erase(it.base())) dice: prendere l'iteratore inverso it , hanno v cancellare l'elemento puntato dal suo iteratore regolare; prendere l'iteratore risultante, costruire un iteratore inverso da esso, e assegnare all'iteratore contrario it .

L'eliminazione di tutti gli elementi mediante v.clear() non libera la memoria (la capacity() del vettore rimane invariata). Per recuperare spazio, utilizzare:

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

v.shrink_to_fit();

Il shrink_to_fit non garantisce di reclamare realmente lo spazio, ma la maggior parte delle implementazioni attuali lo fanno.

Trovare un elemento in std :: vector

La funzione std::find , definita nell'intestazione <algorithm> , può essere utilizzata per trovare un elemento in un std::vector .

std::find utilizza l' operator== per confrontare gli elementi per l'uguaglianza. Restituisce un iteratore al primo elemento nell'intervallo che è uguale al valore.

Se l'elemento in questione non viene trovato, std::find restituisce std::vector::end (o std::vector::cend se il vettore è 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)

Se è necessario eseguire molte ricerche in un vettore di grandi dimensioni, è consigliabile prendere in considerazione l'ordinamento del vettore prima di utilizzare l'algoritmo binary_search .

Per trovare il primo elemento in un vettore che soddisfa una condizione, può essere utilizzato std::find_if . Oltre ai due parametri dati a std::find , std::find_if accetta un terzo argomento che è un oggetto funzione o un puntatore a funzione di un predicato. Il predicato dovrebbe accettare un elemento dal contenitore come argomento e restituire un valore convertibile in bool , senza modificare il contenitore:

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

Convertire una matrice in std :: vector

Un array può essere facilmente convertito in un file std::vector usando std::begin e 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);
}

È anche possibile utilizzare un inizializzatore_list C ++ 11 <> per inizializzare il vettore in una sola volta

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

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

vettore : L'eccezione a così tante, tante regole

Lo standard (sezione 23.3.7) specifica che viene fornita una specializzazione del vector<bool> , che ottimizza lo spazio impacchettando i valori bool , in modo che ciascuno occupi solo un bit. Poiché i bit non sono indirizzabili in C ++, ciò significa che diversi requisiti sul vector non sono posti sul vector<bool> :

• Non è necessario che i dati memorizzati siano contigui, quindi un vector<bool> non può essere passato a un'API C che si aspetta un array bool .
• at() , operator [] e dereferenziazione di iteratori non restituiscono un riferimento a bool . Piuttosto restituiscono un oggetto proxy che simula (imperfettamente) un riferimento a un bool sovraccaricando i suoi operatori di assegnazione. Ad esempio, il seguente codice potrebbe non essere valido per std::vector<bool> , perché il dereferenziamento di un iteratore non restituisce un riferimento:

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

Allo stesso modo, le funzioni che prevedono un bool& argomento non possono essere usate con il risultato operator [] o at() applicato al vector<bool> , o con il risultato del dereferenziamento del suo iteratore:

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

L'implementazione di std::vector<bool> dipende sia dal compilatore che dall'architettura. La specializzazione viene implementata comprimendo n Booleani nella sezione di memoria più bassa indirizzabile. Qui, n è la dimensione in bit della memoria indirizzabile più bassa. Nella maggior parte dei sistemi moderni questo è 1 byte o 8 bit. Ciò significa che un byte può memorizzare 8 valori booleani. Questo è un miglioramento rispetto all'implementazione tradizionale in cui 1 valore booleano è memorizzato in 1 byte di memoria.

Nota: l'esempio seguente mostra i possibili valori bit a bit dei singoli byte in un vector<bool> tradizionale vs ottimizzato vector<bool> . Questo non sarà sempre valido in tutte le architetture. È, tuttavia, un buon modo di visualizzare l'ottimizzazione. Negli esempi seguenti un byte è rappresentato come [x, x, x, x, x, x, x, x].

Tradizionale std::vector<char> memorizzando 8 valori booleani:

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

Rappresentazione bit a bit:

[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]

Specializzato std::vector<bool> memorizzando 8 valori booleani:

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

Rappresentazione bit a bit:

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

Nota nell'esempio sopra, che nella versione tradizionale di std::vector<bool> , 8 valori booleani occupano 8 byte di memoria, mentre nella versione ottimizzata di std::vector<bool> , usano solo 1 byte di memoria. Questo è un miglioramento significativo sull'utilizzo della memoria. Se è necessario passare un vector<bool> a un'API in stile C, potrebbe essere necessario copiare i valori in un array o trovare un modo migliore di utilizzare l'API, se la memoria e le prestazioni sono a rischio.

Dimensioni e capacità del vettore

La dimensione del vettore è semplicemente il numero di elementi nel vettore:

1. La dimensione del vettore corrente viene interrogata dalla funzione membro size() . La funzione di convenienza empty() restituisce true se la dimensione è 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. Il vettore predefinito costruito inizia con una dimensione di 0:

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

3. L'aggiunta di N elementi al vettore aumenta la dimensione di N (ad es. Con le push_back() , insert() o resize() ).

4. La rimozione di N elementi dal vettore diminuisce le dimensioni di N (ad es. Con pop_back() , erase() o clear() ).

5. Vector ha un limite superiore specifico per l'implementazione sulla sua dimensione, ma è probabile che si esaurisca la RAM prima di raggiungerla:

   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
   

Errore comune: la dimensione non è necessariamente (o anche di solito) 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 capacità del vettore differisce dalle dimensioni . Mentre la dimensione è semplicemente il numero di elementi attualmente presenti nel vettore, la capacità è per il numero di elementi per cui è stata allocata / riservata la memoria. Ciò è utile perché allocazioni troppo frequenti (ri) di dimensioni troppo grandi possono essere costose.

1. La capacità vettoriale corrente viene interrogata dalla funzione membro capacity() . La capacità è sempre maggiore o uguale alla taglia :

   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. È possibile prenotare manualmente la capacità mediante la funzione di reserve( N ) (cambia la capacità del vettore in 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. Puoi richiedere il rilascio della capacità in eccesso da shrink_to_fit() (ma l'implementazione non deve shrink_to_fit() ). Questo è utile per conservare la memoria utilizzata:

   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)
   

Il vettore in parte gestisce automaticamente la capacità, quando aggiungi elementi che potrebbero decidere di crescere. Agli implementatori piace usare 2 o 1.5 per il fattore di crescita (il rapporto aureo sarebbe il valore ideale - ma non è pratico a causa del numero razionale). D'altra parte il vettore di solito non si riduce automaticamente. Per esempio:

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

Vettori concatenanti

Uno std::vector può essere aggiunto a un altro utilizzando la funzione membro 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());

Tuttavia, questa soluzione non riesce se si tenta di aggiungere un vettore a se stesso, poiché lo standard specifica che gli iteratori dati a insert() non devono essere dello stesso intervallo degli elementi dell'oggetto destinatario.

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

Se l'ordine degli elementi nel vettore ricevente non ha importanza, considerando il numero di elementi in ciascun vettore è possibile evitare operazioni di copia non necessarie:

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

Ridurre la capacità di un vettore

Un std::vector aumenta automaticamente la sua capacità al momento dell'inserimento, ma non riduce mai la sua capacità dopo la rimozione degli elementi.

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

Per ridurre la sua capacità, possiamo copiare il contenuto di un vettore in un nuovo vettore temporaneo. Il nuovo vettore avrà la capacità minima necessaria per memorizzare tutti gli elementi del vettore originale. Se la riduzione delle dimensioni del vettore originale era significativa, è probabile che la riduzione della capacità per il nuovo vettore sia significativa. Possiamo quindi scambiare il vettore originale con quello temporaneo per mantenere la sua capacità minima:

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

v.shrink_to_fit();

Utilizzo di un vettore ordinato per la ricerca rapida degli elementi

L'intestazione <algorithm> fornisce un numero di funzioni utili per lavorare con vettori ordinati.

Un importante prerequisito per lavorare con vettori ordinati è che i valori memorizzati sono paragonabili a < .

Un vettore non ordinato può essere ordinato usando la funzione std::sort() :

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

I vettori ordinati consentono una ricerca efficiente degli elementi utilizzando la funzione std::lower_bound() . A differenza di std::find() , questo esegue un'efficiente ricerca binaria sul vettore. Lo svantaggio è che dà solo risultati validi per gli intervalli di input ordinati:

// 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: se il valore richiesto non è parte del vettore, std::lower_bound() restituirà un iteratore al primo elemento che è maggiore del valore richiesto. Questo comportamento ci consente di inserire un nuovo elemento nella sua giusta posizione in un vettore già ordinato:

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

Se è necessario inserire molti elementi contemporaneamente, potrebbe essere più efficiente chiamare prima push_back() per tutti e quindi chiamare std::sort() una volta che tutti gli elementi sono stati inseriti. In questo caso, l'aumento del costo dell'ordinamento può ripagare il costo ridotto di inserire nuovi elementi alla fine del vettore e non nel mezzo.

Se il vettore contiene più elementi dello stesso valore, std::lower_bound() tenterà di restituire un iteratore al primo elemento del valore cercato. Tuttavia, se è necessario inserire un nuovo elemento dopo l'ultimo elemento del valore cercato, è necessario utilizzare la funzione std::upper_bound() quanto ciò causerà meno spostamento di elementi:

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

Se sono necessari entrambi gli iteratori del limite superiore e del limite inferiore, è possibile utilizzare la funzione std::equal_range() per recuperarli entrambi in modo efficiente con una chiamata:

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;

Per verificare se un elemento esiste in un vettore ordinato (sebbene non specifico per i vettori), puoi utilizzare la funzione std::binary_search() :

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

Funzioni che restituiscono vettori di grandi dimensioni

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

Trova l'elemento massimo e minimo e l'indice rispettivo in un vettore

Per trovare l'elemento più grande o più piccolo memorizzato in un vettore, puoi usare rispettivamente i metodi std::max_element e std::min_element . Questi metodi sono definiti nell'intestazione <algorithm> . Se diversi elementi sono equivalenti all'elemento più grande (il più piccolo), i metodi restituiscono l'iteratore al primo di tali elementi. Restituisce v.end() per i vettori vuoti.

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';

Produzione:

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';

Matrici che usano i vettori

I vettori possono essere usati come una matrice 2D definendoli come vettori di vettori.

Una matrice con 3 righe e 4 colonne con ogni cella inizializzata come 0 può essere definita come:

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

È possibile accedere ai valori in tale vettore in modo simile a un array 2D

int var = matrix[0][2];

L'iterazione su tutta la matrice è simile a quella di un vettore normale ma con una dimensione extra.

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 vettore di vettori è un modo conveniente per rappresentare una matrice ma non è il più efficiente: i singoli vettori sono sparsi nella memoria e la struttura dei dati non è cache-friendly.

Inoltre, in una matrice appropriata, la lunghezza di ogni riga deve essere uguale (non è il caso di un vettore di vettori). La flessibilità aggiuntiva può essere fonte di errori.