Der beste Weg, einen subvector von einem Vektor zu extrahieren?

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

  •  05-07-2019
  •  | 
  •  

Frage

Angenommen, ich eine std::vector haben (nennen wir es myVec) der Größe N. Was ist der einfachste Weg, um einen neuen Vektor, bestehend aus einer Kopie von Elementen X durch Y, wobei 0 <= X <= Y <= N-1 zu konstruieren? Zum Beispiel myVec [100000] durch myVec [100999] in einem Vektor der Größe 150000.

Wenn dies nicht effizient mit einem Vektor durchgeführt werden, gibt es einen anderen STL-Datentyp, dass ich sollte stattdessen verwenden?

War es hilfreich?

Lösung 

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

Es ist ein O (N) den Betrieb des neuen Vektor zu konstruieren, aber es gibt nicht wirklich einen besseren Weg.

Andere Tipps

Sie einfach den Vektor Konstruktor verwenden. 

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), in Ihrem Fall foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, siehe zum Beispiel: hier

In diesen Tagen, verwenden wir spans! Also würden Sie schreiben: 

#include <gsl/span>

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

eine Spannweite von 1000 Elementen des gleichen Typs wie myvec ist zu bekommen. Nun, dies ist keine Kopie, es ist nur eine Ansicht der Daten in dem Vektor, so vorsichtig sein. Wenn Sie eine aktuelle Kopie möchten, können Sie tun: 

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

Weitere Informationen:

Wenn beide nicht geändert gehen werden (kein Hinzufügen / Löschen von Elementen - Änderung bestehende Ordnung ist, solange Sie ermahnen lassen Fragen Threading), können Sie einfach um data.begin() + 100000 passieren und data.begin() + 101000, und behaupten, dass sie die begin() sind und end() eines kleineren Vektor.

Oder, da Vektor-Speicher gewährleistet ist zusammenhängend sein, können Sie einfach um ein 1000 passieren Element Array: 

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

Diese beiden Techniken nehmen konstante Zeit, erfordern aber, dass die Länge der Daten nicht erhöht, eine Umverteilung ausgelöst wird.

Sie erwähnte nicht, welche Art std::vector<...> myVec ist, aber wenn es eine einfache Art oder Struktur / Klasse ist, die Zeiger nicht enthält, und Sie wollen die beste Leistung, dann können Sie eine direkte Speicherkopie tun (was ich denke, schneller als die anderen Antworten zur Verfügung gestellt). Hier ist ein allgemeines Beispiel für std::vector<type> myVec wo type in diesem Fall int ist: 

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

Sie können mit STL Kopie mit O (M) Leistung, wenn M ist die Größe des subvector.

Der einzige Weg, um eine Sammlung zu projizieren, die nicht lineare Zeit ist so faul zu tun, wo die resultierende „Vektor“ ist eigentlich ein Subtyp, welche Delegierten auf die ursprüngliche Sammlung. Erstellen Sie zum Beispiel Scala List#subseq Methode eine Untersequenz in konstanter Zeit. Dies funktioniert jedoch nur, wenn die Sammlung unveränderlich ist und wenn die zugrunde liegende Sprache Sport Garbage Collection.

Ok. Dies ist eine ziemlich alte Diskussion. Aber ich entdeckte, nur etwas ordentlich:

slice_array - Könnte dies eine schnelle Alternative sein ? Ich habe es nicht getestet.

Posting so spät nur für others..I Wette der erste Codierer inzwischen erfolgt. Für einfache Datentypen keine Kopie benötigt wird, kehrt nur zu guten alten C-Code-Methoden. 

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

Dann passieren die Zeiger p und eine len alles, ein subvector benötigen.

notelen muss sein !! len < myVec.size()-start

Vielleicht ist der array_view / span in der GSL-Bibliothek ist eine gute Option.

Hier ist auch eine einzelne Datei Implementierung. array_view

Kopieren Elemente von einem Vektor zu einem anderen leicht
In diesem Beispiel habe ich einen Vektor von Paaren bin mit, um es einfach zu verstehen,
`

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

‘
Wie Sie können Sie ganz einfach kopieren Elemente von einem Vektor zu einem anderen sehen können, wenn Sie Elemente aus dem Index 10 bis 16 beispielsweise kopieren wollen, dann würden wir benutzen 

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

und wenn Sie Elemente aus dem Index 10 bis zu einem gewissen Index von Ende, dann in diesem Fall 

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

hoffe, das hilft, nur im letzten Fall v.end()-5 > v.begin()+10 erinnern

Eine weitere Option: Nützlich zum Beispiel, wenn zwischen einem thrust::device_vector und einem thrust::host_vector bewegen, wo man nicht den Konstruktor verwenden kann. 

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

Wenn auch die Komplexität O (N) sein

Sie können dies mit Top-anwer Code kombinieren 

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

Sie könnten nur verwenden insert 

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top