In questo articolo, abbiamo esplorato diversi modi per eseguire l'iterazione su Vector in C++ STL. Questi includono tecniche come l'indicizzazione, gli iteratori, il ciclo for basato su intervalli e molto altro.
I vettori sono contenitori di sequenza simili agli array dinamici. I vettori hanno la capacità di ridimensionarsi. I dati nei vettori sono memorizzati in modo contiguo. Quindi i dati non sono accessibili solo tramite iteratori e ma anche attraverso indici .
Quando scriviamo codice in C++ ci troviamo di fronte a un dilemma costante su come eseguire l'iterazione su una raccolta. Ovviamente dipende dal tipo di struttura dati su cui stiamo cercando di iterare. Ma la maggior parte di loro segue comunque la stessa struttura. Ora vedremo vari modi per scorrere un vettore in C++ STL. Quindi proveremo a stampare il contenuto dell'array usando i modi che esploriamo.
I diversi modi per eseguire l'iterazione su Vector in C++ STL sono:
- Esegui l'iterazione utilizzando l'indicizzazione
- Utilizzo degli iteratori
- Utilizzo del loop basato sull'intervallo
- Utilizzo di std::for_each
Esegui l'iterazione utilizzando l'indicizzazione
L'uso dell'indicizzazione è il modo da manuale per l'iterazione su un vettore utilizzando cicli normali. Ci consente di conoscere l'esatta posizione dell'indice degli elementi a cui stiamo accedendo. Il ciclo for può essere utilizzato per accedere al vettore da una posizione a un'ultima posizione.
Pseudocodice
- inizializza e popola un vettore
- loop da i =0 alla dimensione del vettore
- stampa l'elemento del vettore all'indice i
Complessità
- Alcune persone potrebbero esitare a utilizzare questo codice a causa della chiamata di vector::size su ogni iterazione, tuttavia ha una complessità temporale costante, quindi non c'è nulla di cui preoccuparsi
- Complessità temporale del caso peggiore:
Θ(n) - Complessità media dei casi:
Θ(n) - Complessità temporale nel migliore dei casi:
Θ(n) - Complessità dello spazio:
Θ(1)
Implementazione
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {7, 5, 2, 9, 4, 1};
for(int i = 0 ; i < v.size(); i++){
cout << v[i] << " " ;
}
}
Applicazioni
- Questo metodo può essere utile quando è necessario utilizzare l'indice (ad es. accedere all'elemento successivo/precedente, utilizzare l'indice a lato del ciclo)
- Questo metodo è ottimo anche quando hai bisogno di un passo diverso da 1, questo può essere modificato sostituendo la parte di aggiornamento del ciclo for con qualcosa come i +=2 per accedere solo a elementi alternativi.
Utilizzo degli iteratori
Gli iteratori vengono utilizzati per scorrere una raccolta di dati. Quando pensiamo agli iteratori, di solito pensiamo alla raccolta di dati e ai modi per scorrere su di essi. Usando vector::begin() e vector::end() permetterci di accedere rispettivamente ai puntatori all'inizio e alla fine del vettore. Anche vector::rbegin() e vector::rend() può essere utilizzato anche in modo simile.
Pseudocodice
- inizializza e popola un vettore
- ciclo da iter =vettore dall'inizio al vettore fine
- all'interno del loop puoi accedere ai singoli elementi dereferenziando iter
Complessità
vector::begin()evector::end()hanno una complessità diΘ(1)quindi non influiscono sulla complessità del tempo.- Complessità temporale del caso peggiore:
Θ(n) - Complessità media della durata del caso:
Θ(n) - Complessità temporale nel migliore dei casi:
Θ(n) - Complessità dello spazio:
Θ(1)
Implementazione
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {7, 5, 2, 9, 4, 1};
// here I used auto to declare it instead of std::vector::iterator
// to make the code easy to read and understand
for(auto it = v.begin(); it != v.end(); it++)
cout << *it << " ";
}
Applicazioni
- Simile a usare indeces anche qui possiamo controllare il passo in modo simile a quanto discusso in precedenza.
- L'uso degli iteratori ci offre un vantaggio significativo:consente l'astrazione. Ci consentirà di scrivere codice generico che può essere utilizzato con vari contenitori e non essere necessariamente limitato ai soli vettori, rendendo il nostro codice più riutilizzabile.
Utilizzo del ciclo basato sull'intervallo
I cicli for basati su intervalli sono stati introdotti in C++11 ed eseguono cicli for su un intervallo. I cicli for basati sull'intervallo aiutano a rendere il nostro codice più leggibile. Fornisce un modo elegante e pulito per accedere agli elementi. Una volta che guardi il codice, potrebbe sembrarti una stregoneria, ma sotto il cofano sta usando la logica che abbiamo visto sopra.
Pseudocodice
per (dichiarazione:intervallo)
espressione di ciclo
- dichiarazione è una variabile dello stesso tipo del tipo di dati del vettore a cui sono assegnati valori
- intervallo è l'espressione che mostra l'intervallo su cui eseguire il ciclo for
- Espressione di ciclo qui si riferisce al corpo del ciclo
Complessità
- Complessità temporale del caso peggiore:
Θ(n) - Complessità temporale media del caso:
Θ(n) - Complessità temporale nel migliore dei casi:
Θ(n) - Complessità dello spazio:
Θ(1)
Implementazioni
#include <vector>
#include <iostream>
using namespace std;
int main(){
vector<int> v = {7, 5, 2, 9, 4, 1};
for(int i : v){
cout << i << " " ;
}
}
Applicazioni
- Se non è necessario accedere all'indice e non è necessario scorrere il vettore in un ordine particolare. I cicli for basati su RAnge rendono il nostro codice più facile da capire
- quando abbiamo bisogno di iterare l'intero vettore, questi ci aiutano a scrivere in modo meno dettagliato.
Utilizzo di std::for_each
A parte gli algoritmi di loop generici, vale a dire for loop, while loop e do while loop. for_each ci consente di scorrere un array o una raccolta ed eseguire un blocco di istruzioni su ogni elemento della raccolta.
Pseudocodice
- Inizializza e popola un vettore
- for_each( inizio, fine, dichiarazioni)
inizio indica l'inizio dell'intervallo
fine indica la fine dell'intervallo
dichiarazioni fare riferimento alle funzioni da svolgere su ciascun elemento
Complessità
- Complessità temporale del caso peggiore:
Θ(nx) - Complessità temporale media del caso:
Θ(nx) - Complessità temporale nel migliore dei casi:
Θ(nx) - Complessità dello spazio:
Θ(ny) - Qui x è la migliore/media/peggiore complessità temporale delle affermazioni
- Qui y è la complessità spaziale delle affermazioni
Implementazioni
Per il codice singolo utilizzare il markdown come segue:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> v = {7, 5, 2, 9, 4, 1};
for_each(v.begin(), v.end(), [](int const& val){
cout << val << " " ;
});
return 0;
}
Applicazioni
- È generico e quindi non limitato a un tipo di contenitore, quindi scambiare il tipo di contenitore su cui esegue l'iterazione è indolore
- Ci consente di applicare effetti collaterali sull'oggetto funzione.