Der beste Weg, um einen Subvektor aus einem Vektor zu extrahieren?

295

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

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

An̲̳̳drew
quelle
7
Sie sagen, Sie möchten einen Subvektor extrahieren, aber es scheint mir, dass Sie wirklich eine Ansicht / einen Zugriff auf den Subvektor wünschen - der Unterschied besteht darin, dass eine Ansicht nicht kopiert werden würde - C ++ der alten Schule würde darin bestehen, Startzeiger und Endzeiger zu verwenden. Angesichts der Tatsache, dass mem auf einem std :: -Vektor zusammenhängend ist, sollte es Ihnen möglich sein, mithilfe von Zeigern zu iterieren und dadurch das Kopieren zu vermeiden. Wenn Ihnen das Kopieren jedoch nichts ausmacht, initialisieren Sie einfach einen neuen Vektor mit dem Umfang Ihres vorherigen Vektor
Serup
Seit c ++ 11 gibt es .data () ( cplusplus.com/reference/vector/vector/data ). Es wird jedoch davon abgeraten, Zeiger in stl-Containern zu verwenden (siehe stackoverflow.com/questions/31663770/…
David Tóth,

Antworten:

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

Es ist eine O (N) -Operation, um den neuen Vektor zu konstruieren, aber es gibt keinen besseren Weg.

Greg Rogers
quelle
12
+1, auch es ist O (YX), was kleiner oder gleich O (N) ist (und in seinem Beispiel viel weniger)
orip
74
@orip Na dann ist es doch O (N).
Johann Gerell
55
@ GregRogers: Es ist nicht sinnvoll, die Big-O-Notation zu verwenden, bei der N eine bestimmte Zahl ist. Big-O gibt die Wachstumsrate in Bezug darauf an, wie sich N ändert. Johann: Es ist am besten, einen Variablennamen nicht auf zwei Arten zu verwenden. Normalerweise würden wir entweder sagen O(Y-X)oder wir würden sagen O(Z) where Z=Y-X.
Mooing Duck
2
@ GregRogers Auf diese Weise müssen wir einen neuen Vektor deklarieren. Gibt es eine Möglichkeit, den ursprünglichen Vektor zu ändern? so etwas wie myVec (zuerst, zuletzt)? Ich weiß, dass dies falsch ist, aber ich brauche wirklich die Lösung, da ich Rekursion in meinen Codes verwenden möchte und wiederholt denselben Vektor verwenden muss (obwohl geändert). Vielen Dank!
ulyssis2
13
Warum nicht einfach vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);?
Aquirdturtle
88

Verwenden Sie einfach den Vektorkonstruktor.

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

std::vector<int>   sub(&data[100000],&data[101000]);
Martin York
quelle
2
Ok, ich wusste nicht, dass es so einfach ist, einen Iterator aus einem beliebigen Vektorelement zu erhalten.
Andrew
5
Das Adressieren dieser Vektorelemente ist ein nicht portierbarer Hack, der unterbrochen wird, wenn der Vektorspeicher tatsächlich nicht zusammenhängend ist. Verwenden Sie begin () + 100000 usw.
j_random_hacker
2
Mein schlechtes, anscheinend garantiert der Standard, dass die Vektorspeicherung zusammenhängend ist. Trotzdem ist es eine schlechte Praxis, mit solchen Adressen zu arbeiten, da es sicherlich nicht garantiert ist, dass sie für alle Container funktionieren, die Direktzugriff unterstützen, während begin () + 100000 ist.
j_random_hacker
33
@j_random_hacker: Sorry muss nicht zustimmen. Die STL-Spezifikation für std :: vector wurde explizit geändert, um diese Art von Prozedur zu unterstützen. Auch ein Zeiger ist ein gültiger Iteratortyp. Nachschlagen iterator_traits <>
Martin York
6
@ taktak004 Nein. Denken Sie daran, dass operator[]eine Referenz zurückgegeben wird. Nur an dem Punkt, an dem Sie die Referenz lesen oder schreiben, wird dies zu einer Zugriffsverletzung. Da wir beides nicht tun, sondern stattdessen die Adresse erhalten, haben wir UB nicht aufgerufen.
Martin York
28

std::vector<T>(input_iterator, input_iterator), in Ihrem Fall foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, sehen Sie zum Beispiel hier

Anteru
quelle
1
Da Andrew versucht, einen neuen Vektor zu konstruieren, würde ich "std :: vector foo (..." empfehlen, anstatt mit "foo = std :: vector (..." zu kopieren
Drew Dormann
4
Ja, natürlich, aber ob Sie std :: vector <int> foo = std :: vector (...) oder std :: vector <int> foo (...) eingeben, sollte keine Rolle spielen.
Anteru
19

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

#include <gsl/span>

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

um eine Spanne von 1000 Elementen des gleichen Typs wie myvec's zu erhalten. Oder eine knappere Form:

auto my_subspan = gsl::make_span(myvec).subspan(1000000, 1000);

(aber ich mag das nicht so sehr, da die Bedeutung jedes numerischen Arguments nicht ganz klar ist; und es wird schlimmer, wenn die Länge und start_pos in der gleichen Größenordnung liegen.)

Denken Sie jedoch daran, dass dies keine Kopie ist, sondern nur eine Ansicht der Daten im Vektor. Seien Sie also vorsichtig. Wenn Sie eine tatsächliche Kopie wünschen, können Sie Folgendes tun:

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

Anmerkungen:

einpoklum
quelle
würde verwenden cbeginund cendnur für das Prinzip;) std::cbeginetc sogar.
JHBonarius
1
@JHBonarius: Angesichts der Tatsache, dass dieser Code nicht für die Auswahl des Containers vorgesehen ist, sehe ich keinen besonderen Vorteil. eine Geschmackssache, nehme ich an.
Einpoklum
10

Wenn beide nicht geändert werden sollen (kein Hinzufügen / Löschen von Elementen - das Ändern vorhandener Elemente ist in Ordnung, solange Sie auf Threading-Probleme achten), können Sie einfach data.begin() + 100000und weitergeben data.begin() + 101000und so tun, als wären sie das begin()und end()eines kleineren Vektors.

Da die Vektorspeicherung garantiert zusammenhängend ist, können Sie einfach ein Array mit 1000 Elementen übergeben:

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

Beide Techniken benötigen eine konstante Zeit, erfordern jedoch, dass die Datenlänge nicht zunimmt, was eine Neuzuweisung auslöst.

Finsternis
quelle
Dies ist auch gut, wenn der ursprüngliche Vektor und der Subvektor verknüpft werden sollen.
PyRulez
7

Diese Diskussion ist ziemlich alt, aber die einfachste erwähnte noch nicht, mit list-Initialisierung :

 vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2}; 

Es erfordert c ++ 11 oder höher.

Anwendungsbeispiel:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    vector<int> big_vector = {5,12,4,6,7,8,9,9,31,1,1,5,76,78,8};
    vector<int> subvector = {big_vector.begin() + 3, big_vector.end() - 2};

    cout << "Big vector: ";
    for_each(big_vector.begin(), big_vector.end(),[](int number){cout << number << ";";});
    cout << endl << "Subvector: ";
    for_each(subvector.begin(), subvector.end(),[](int number){cout << number << ";";});
    cout << endl;
}

Ergebnis:

Big vector: 5;12;4;6;7;8;9;9;31;1;1;5;76;78;8;
Subvector: 6;7;8;9;9;31;1;1;5;76;
David Tóth
quelle
6

Sie haben nicht erwähnt, um welchen Typ es sich std::vector<...> myVechandelt, aber wenn es sich um einen einfachen Typ oder eine Struktur / Klasse handelt, die keine Zeiger enthält, und Sie die beste Effizienz erzielen möchten, können Sie eine direkte Speicherkopie erstellen (die meiner Meinung nach schneller ist als die andere Antworten). Hier ist ein allgemeines Beispiel dafür, std::vector<type> myVecwo typein diesem Fall ist 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
MasterHD
quelle
2
Ich frage mich, ob mit -O3, @ Anterus "using constructor" std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, die längere Version dieses Modells nicht genau dieselbe Assembly ergeben würde.
Sanddorn
1
MSVC ++ 2015 beispielsweise Kompilierungen std::vector<>(iter, iter)zu memmove()gegebenenfalls (wenn Konstruktor ist trivial, für eine geeignete Definition trivial).
Pablo H
1
Ruf nicht an memcpy. std::copyWenn Sie einen oder einen Konstruktor ausführen, der einen Bereich akzeptiert (zwei Iteratoren), verschwören sich der Compiler und die std.library, um memcpygegebenenfalls aufzurufen .
Bulletmagnet
4

Sie könnten einfach verwenden insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);
Matheus Vinícius de Andrade
quelle
3

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

Yuval F.
quelle
Upvoted, weil es mich in die richtige Richtung wies, aber ich kann sehen, warum @LokiAstari vorschlägt, dass es nicht die richtige Wahl ist - da die STL :: copy mit zwei std :: vector <T> -Arrays gleicher Größe und gleichen Typs funktioniert. Hier möchte das OP einen Unterabschnitt in ein neues, kleineres Array kopieren, wie hier im Beitrag des OP beschrieben: "0 <= X <= Y <= N-1"
Andrew
@ Andrew, siehe Beispiel mit std :: copy und std :: back_inserter
chrisg
@LokiAstari warum nicht?
Chrisg
2
@LokiAstari Ich bezog mich auf eine Bearbeitung, die die Peer Review nicht überlebte und das Beispiel <br/> vector <T> newvec darstellte. std :: copy (myvec.begin () + 10000, myvec.begin () +10100, std :: back_inserter (newvec)); <br/> In diesem Fall müssen Sie das Ziel nicht zuerst erstellen, aber die direkte Initialisierung ist sicher ... direkter.
Chrisg
1
@chrisg: Es sind auch zwei Zeilen. Zusätzlich müssen Sie eine dritte Zeile einfügen, um sicherzustellen, dass sie effizient ist. newvec.reserve(10100 - 10000);. Es ist definitiv eine Option und technisch wird es funktionieren. Aber welche der beiden empfehlen Sie?
Martin York
1

Die einzige Möglichkeit, eine Sammlung zu projizieren, die keine lineare Zeit ist, besteht darin, dies träge zu tun, wobei der resultierende "Vektor" tatsächlich ein Subtyp ist, der an die ursprüngliche Sammlung delegiert. Zum Beispiel erstellt die List#subseqMethode von Scala eine Teilsequenz in konstanter Zeit. Dies funktioniert jedoch nur, wenn die Sammlung unveränderlich ist und wenn die zugrunde liegende Sprache eine Speicherbereinigung enthält.

Daniel Spiewak
quelle
In C ++ wäre dies ein Vektor von shared_ptr nach X anstelle eines Vektors von X und dann das Kopieren von SPs, aber leider glaube ich nicht, dass dies schneller ist, da die atomare Operation mit dem Kopieren von SP verbunden ist. Oder der ursprüngliche Vektor könnte stattdessen ein const shared_ptr des Vektors sein, und Sie verweisen nur auf den darin enthaltenen Unterbereich. ofc Sie müssen es nicht zu einem shared_ptr des Vektors machen, aber dann haben Sie lebenslange Probleme ... all dies ist aus meinem Kopf, könnte falsch sein ...
NoSenseEtAl
0

Ich wette, der erste Codierer ist jetzt fertig. Für einfache Datentypen ist keine Kopie erforderlich. Setzen Sie einfach auf gute alte C-Code-Methoden zurück.

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

Übergeben Sie dann den Zeiger p und a len an alles, was einen Subvektor benötigt.

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

mrrgu
quelle
Dies führt keine Kopie durch.
Trilarion
0

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

Hier ist auch eine einzelne Dateiimplementierung : array_view .

myd7349
quelle
Bitte fügen Sie hier zusammen mit dem Link eine Antwort hinzu. Da sich der externe Link in Zukunft ändern könnte
Panther
0

Kopieren Sie Elemente von einem Vektor zu einem anderen leicht
In diesem Beispiel verwende ich einen Vektor von Paaren zu machen , leicht 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 sehen, können Sie Elemente problemlos von einem Vektor in einen anderen kopieren. Wenn Sie beispielsweise Elemente aus Index 10 bis 16 kopieren möchten, verwenden wir diese

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

und wenn Sie Elemente von Index 10 bis zu einem Index von Ende möchten, dann in diesem Fall

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

Ich hoffe, das hilft. Denken Sie nur an den letzten Fall v.end()-5 > v.begin()+10

Jishu Dohare
quelle
0

Noch eine Option: Nützlich zum Beispiel beim Wechseln zwischen a thrust::device_vectorund a thrust::host_vector, wo Sie den Konstruktor nicht verwenden können.

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

Sollte auch Komplexität O (N) sein

Sie können dies mit dem oberen Antwortcode 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));
JHBonarius
quelle