Il modo migliore per estrarre un subvector da un vettore?

StackOverflow https://stackoverflow.com/questions/421573

  •  05-07-2019
  •  | 
  •  

Domanda

Supponiamo che io abbia un std::vector (chiamiamolo myVec) di dimensioni N. Qual è il modo più semplice per costruire un nuovo vettore costituito da una copia degli elementi da X a Y, dove 0 & Lt; = X & Lt; = Y & Lt; = N-1? Ad esempio, da myVec [100000] a myVec [100999] in un vettore di dimensioni 150000.

Se ciò non può essere fatto in modo efficiente con un vettore, esiste invece un altro tipo di dati STL che dovrei usare?

È stato utile?

Soluzione 

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

È un'operazione O (N) per costruire il nuovo vettore, ma non c'è davvero un modo migliore.

Altri suggerimenti

Usa semplicemente il costruttore vettoriale. 

std::vector<int>   data();
// Load Z elements into data so that Z > Y > X

std::vector<int>   sub(&data[100000],&data[101000]);

std::vector(input_iterator, input_iterator), nel tuo caso foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, vedi ad esempio qui

In questi giorni, usiamo span s! Quindi scriveresti: 

#include <gsl/span>

...
auto start_pos = 100000;
auto length = 1000;
auto my_subspan = gsl::make_span(myvec).subspan(start_pos, length);

per ottenere un intervallo di 1000 elementi dello stesso tipo di myvec. Ora, questo non è non una copia, è solo una vista dei dati nel vettore, quindi fai attenzione. Se vuoi una copia reale, puoi farlo: 

std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());

Note:

Se entrambi non verranno modificati (nessuna aggiunta / eliminazione di elementi - la modifica di quelli esistenti va bene fintanto che si presta attenzione ai problemi di threading), è possibile passare semplicemente data.begin() + 100000 e data.begin() + 101000 e fingere che sono i begin() e end() di un vettore più piccolo.

Oppure, poiché l'archiviazione vettoriale è garantita contigua, puoi semplicemente passare un array di 1000 elementi: 

T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;

Entrambe queste tecniche richiedono tempo costante, ma richiedono che la lunghezza dei dati non aumenti, innescando una riallocazione.

Non hai menzionato il tipo std::vector<...> myVec, ma se si tratta di un tipo o struttura / classe semplice che non include i puntatori e desideri la massima efficienza, puoi fare una copia di memoria diretta (che io pensa che sarà più veloce delle altre risposte fornite). Ecco un esempio generale di std::vector<type> myVec dove type in questo caso è int: 

typedef int type; //choose your custom type/struct/class
int iFirst = 100000; //first index to copy
int iLast = 101000; //last index + 1
int iLen = iLast - iFirst;
std::vector<type> newVec;
newVec.resize(iLen); //pre-allocate the space needed to write the data directly
memcpy(&newVec[0], &myVec[iFirst], iLen*sizeof(type)); //write directly to destination buffer from source buffer

Puoi utilizzare copia STL con prestazioni O (M) quando M è la dimensione del subvector.

L'unico modo per proiettare una collezione che non è tempo lineare è farlo pigramente, dove il " risultante; vettore " è in realtà un sottotipo che delega alla raccolta originale. Ad esempio, il metodo List#subseq di Scala crea una sottosequenza a tempo costante. Tuttavia, questo funziona solo se la raccolta è immutabile e se la lingua sottostante mette in mostra la raccolta dei rifiuti.

Ok. Questa è una discussione piuttosto vecchia. Ma ho appena scoperto qualcosa di pulito:

slice_array - Potrebbe essere un'alternativa veloce ? Non l'ho provato.

Pubblicando questo post in ritardo solo per gli altri ... Scommetto che il primo programmatore è già pronto. Per semplici tipi di dati non è necessaria alcuna copia, è sufficiente ripristinare i vecchi metodi del codice C. 

std::vector <int>   myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;

Quindi passa il puntatore p e una len a tutto ciò che necessita di un subvector.

notelen deve essere !! len < myVec.size()-start

Forse il array_view / span nella libreria GSL è una buona opzione.

Ecco anche un'implementazione di un singolo file: array_view .

Copia facilmente gli elementi da un vettore all'altro
In questo esempio, sto usando un vettore di coppie per facilitarne la comprensione
`

vector<pair<int, int> > v(n);

//we want half of elements in vector a and another half in vector b
vector<pair<lli, lli> > a(v.begin(),v.begin()+n/2);
vector<pair<lli, lli> > b(v.begin()+n/2, v.end());


//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
//then a = [(1, 2), (2, 3)]
//and b = [(3, 4), (4, 5), (5, 6)]

//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
//then a = [(1, 2), (2, 3), (3, 4)]
//and b = [(4, 5), (5, 6), (6, 7)]

'
Come puoi vedere, puoi facilmente copiare elementi da un vettore a un altro, se per esempio vuoi copiare elementi dall'indice 10 al 16, allora useremmo 

vector<pair<int, int> > a(v.begin()+10, v.begin+16);

e se vuoi elementi dall'indice 10 a qualche indice dalla fine, allora in quel caso 

vector<pair<int, int> > a(v.begin()+10, v.end()-5);

spero che questo aiuti, ricordati solo nell'ultimo caso v.end()-5 > v.begin()+10

Ancora un'altra opzione: Utile ad esempio quando ci si sposta tra un thrust::device_vector e un thrust::host_vector, dove non è possibile utilizzare il costruttore. 

std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));

Dovrebbe anche essere la complessità O (N)

Puoi combinarlo con il codice anwer superiore 

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));

Potresti semplicemente usare insert 

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top