Cel mai bun mod de a extrage un subvector dintr-un vector? (Programare, C++, Stl, Vector, Interval)

An̲̳̳̳ a desenat a intrebat.

Să presupunem că am un std::vector (să îl numim myVec) de dimensiune N. Care este cel mai simplu mod de a construi un nou vector format dintr-o copie a elementelor X prin Y, unde 0 <= X <= Y <= N-1? De exemplu, myVec [100000] prin myVec [100999] într-un vector de dimensiune 150000.

Dacă acest lucru nu se poate face eficient cu un vector, există un alt tip de date STL pe care ar trebui să îl folosesc în schimb?

Comentarii

  • spuneți că doriți să extrageți un subvector, dar mi se pare că ceea ce doriți cu adevărat este o vizualizare / acces la subvector – diferența fiind că o vizualizare nu ar copia – vechea școală C++ ar fi să folosiți pointerul de început și pointerul de sfârșit, având în vedere faptul că memoria pe un vector std::vector este contiguă, atunci ar trebui să vă fie posibil să iterați folosind pointeri și astfel să evitați copierea, totuși, dacă nu vă deranjează copierea, atunci doar inițializați un nou vector cu domeniul de aplicare al vectorului anterior.  > Por serup.
  • Există .data()(cplusplus.com/reference/vector/vector/vector/data) începând cu c++11. Cu toate acestea, utilizarea pointerilor este descurajată în cadrul containerelor stl , vezi stackoverflow.com/questions/31663770/… –  > Por David Tóth.
14 răspunsuri
Greg Rogers
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

Este o operație O(N) pentru a construi noul vector, dar nu există o modalitate mai bună.

Comentarii

  • +1, de asemenea, este O(Y-X), care este mai mic sau egal cu O(N) (și în exemplul său mult mai mic) –  > Por orip.
  • 83

  • @orip Ei bine, atunci este O(N) până la urmă. –  > Por Johann Gerell.
  • 57

  • @GregRogers: Nu are sens să folosim notația big-O în cazul în care N este un număr specific. Big-O comunică rata de creștere în raport cu modul în care se modifică N. Johann: Cel mai bine este să nu folosiți un nume de variabilă în două moduri. În mod normal, am spune fie O(Y-X), , fie am spune O(Z) where Z=Y-X. –  > Por Mooing Duck.
  • @GregRogers Utilizând acest mod, trebuie să declarăm un nou vector. Există o modalitate de a schimba vectorul original? ceva de genul myVec(first, last)? Știu că acest lucru este greșit, dar chiar am nevoie de soluție, deoarece vreau să folosesc recursivitatea în codurile mele și trebuie să folosesc în mod repetat același vector (deși schimbat). Vă mulțumesc! –  > Por ulyssis2.
  • 17

  • De ce nu doar vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);? –  > Por aquirdturtle.
Martin York

Folosiți doar constructorul vectorial.

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

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

Comentarii

  • Bine, nu mi-am dat seama că este atât de simplu să obții un iterator dintr-un element vectorial arbitrar. –  > Por An̲̳̳̳drew.
  • Luarea adresei acelor elemente vectoriale este un hack neportabil care se va strica dacă stocarea vectorială nu este, de fapt, contiguă. Folosiți begin() + 100000 etc. –  > Por j_random_hacker.
  • Greșeala mea, se pare că standardul garantează că stocarea vectorială este contiguă. Cu toate acestea, este o practică proastă să lucrezi cu astfel de adrese, deoarece cu siguranță nu este garantat să funcționeze pentru toate containerele care acceptă accesul aleatoriu, în timp ce begin() + 100000 este. –  > Por j_random_hacker.
  • 35

  • @j_random_hacker: Îmi pare rău, trebuie să nu fiu de acord. Specificația STL pentru std::vector a fost modificată în mod explicit pentru a suporta acest tip de procedură. De asemenea, un pointer este un tip valid de iterator. Căutați iterator_traits<> –  > Por Martin York.
  • @taktak004 Nu. Amintiți-vă că operator[] returnează o referință. Doar în momentul în care citiți sau scrieți referința, aceasta ar deveni o încălcare a accesului. Din moment ce nu facem niciuna dintre ele, dar în schimb obținem adresa, nu am invocat UB,. –  > Por Martin York.
Anteru

std::vector<T>(input_iterator, input_iterator), , în cazul dvs. foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, , vezi de exemplu aici

Comentarii

  • Din moment ce Andrew încearcă să construiască un nou vector, aș recomanda „std::vector foo(…” în loc să copiezi cu „foo = std::vector(…” –  > Por Drew Dormann.
  • Da, bineînțeles, dar nu ar trebui să conteze dacă se tastează std::vector<int> foo = std::vector(…) sau std::vector<int> foo (…). –  > Por Anteru.
einpoklum

În zilele noastre, folosim spans! Deci, ați scrie:

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

pentru a obține un interval de 1000 de elemente de același tip cu myvec‘s. Sau o formă mai laconică:

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

(dar nu-mi place la fel de mult, deoarece semnificația fiecărui argument numeric nu este pe deplin clară; și devine mai rău dacă lungimea și start_pos sunt de același ordin de mărime).

Oricum, nu uitați că aceasta este nu este o copie, ci doar o vizualizare a datelor din vector, așa că aveți grijă. Dacă doriți o copie reală, ați putea face:

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

Note:

  • gsl reprezintă Guidelines Support Library (Biblioteca de asistență pentru ghiduri). Pentru mai multe informații despre gsl, , consultați: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library.
  • Există mai multe gsl implementări . De exemplu: https://github.com/martinmoene/gsl-lite
  • C++20 oferă o implementare a span. Ați putea utiliza std::span și #include <span> în loc de #include <gsl/span>.
  • Pentru mai multe informații despre intervale, consultați: Ce este un „span” și când ar trebui să folosesc unul?
  • std::vector are un miliard de constructori, este foarte ușor să te lovești de unul pe care nu ai intenționat să îl folosești, așa că ai grijă.

Comentarii

  • ar folosi cbegin și cend doar pentru principiu 😉 std::cbegin etc., chiar și. –  > Por JHBonarius.
  • @JHBonarius: Văzând cum acest cod nu este templat pe alegerea containerului, nu văd că există un beneficiu deosebit; o chestiune de gust, presupun. –  > Por einpoklum.
David Tóth

Această discuție este destul de veche, dar cel mai simplu nu este menționat încă, cu list-initialization:

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

Este nevoie de c++11 sau mai sus.

Exemplu de utilizare:

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

Rezultat:

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;

Eclipse

Dacă ambele nu vor fi modificate (fără adăugare/ștergere de elemente – modificarea celor existente este în regulă, atâta timp cât țineți cont de problemele de threading), puteți pur și simplu să treceți în jur de data.begin() + 100000 și data.begin() + 101000, , și să vă prefaceți că acestea sunt begin() și end() ale unui vector mai mic.

Sau, deoarece stocarea vectorială este garantată a fi contiguă, puteți pur și simplu să treceți o matrice de 1000 de elemente:

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

Ambele tehnici au un timp constant, dar necesită ca lungimea datelor să nu crească, declanșând o realocare.

Comentarii

  • Acest lucru este, de asemenea, bun dacă doriți ca vectorul original și subvectorul să fie legate. –  > Por PyRulez.
MasterHD

Nu ați menționat ce tip std::vector<...> myVec este, dar dacă este un tip simplu sau o structură/clasă care nu include pointeri și doriți cea mai bună eficiență, atunci puteți face o copie directă în memorie (care cred că va fi mai rapidă decât celelalte răspunsuri furnizate). Iată un exemplu general pentru std::vector<type> myVec unde type în acest caz este 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

Comentarii

  • Mă întreb dacă, cu -O3, „folosind constructorul” lui @Anteru, „folosind constructorul” std::vector(myVec.begin () + 100000, myVec.begin () + 150000); , nu ar produce versiunea mai lungă a acestuia în exact același ansamblu? –  > Por sandthorn.
  • MSVC++ 2015, de exemplu, compilează std::vector<>(iter, iter) la memmove(), , dacă este cazul (dacă constructorul este trivial, pentru o definiție adecvată a termenului trivial). –  > Por Pablo H.
  • Nu apelați memcpy. Faceți un std::copy sau un constructor care acceptă un interval (doi iteratori), iar compilatorul și biblioteca std.library vor conspira pentru a apela memcpy atunci când este cazul. –  > Por Bulletmagnet.
Matheus Vinícius de Andrade

Ați putea să folosiți pur și simplu insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);

Yuval F

Puteți folosi Copie STL cu o performanță O(M) atunci când M este dimensiunea subvectorului.

Comentarii

  • Upvoted pentru că m-a îndreptat în direcția corectă, dar înțeleg de ce @LokiAstari sugerează că nu este alegerea corectă – din moment ce STL::copy funcționează cu două matrice std::vector<T> de aceeași dimensiune și tip. Aici, OP dorește să copieze o subsecțiune într-o matrice nouă, mai mică, așa cum este descris aici în postul OP: „0 <= X <= Y <= N-1” –  > Por Andrew.
  • @Andrew, vezi exemplul folosind std::copy și std::back_inserter –  > Por chrisg.
  • @LokiAstari de ce nu? –  > Por chrisg.
  • @LokiAstari Mă refeream la o editare a acestui lucru care nu a supraviețuit revizuirii de către colegi, care a pus exemplul <br/> vector<T> newvec; std::copy(myvec.begin()+10000, myvec. begin() +10100, std::back_inserter(newvec)); <br/> în acest caz, nu este nevoie să construiți mai întâi destinația, dar sigur, inițializarea directă este mai… directă. –  > Por chrisg.
  • @chrisg: Este, de asemenea, două linii. În plus, trebuie să băgați o a treia linie pentru a vă asigura că este eficient. newvec.reserve(10100 - 10000);. ITs cu siguranță o opțiune și, din punct de vedere tehnic, va funcționa. Dar dintre cele două, pe care o vei recomanda? –  > Por Martin York.
Daniel Spiewak

Singura modalitate de a proiecta o colecție care nu este un timp liniar este de a face acest lucru în mod leneș, unde „vectorul” rezultat este de fapt un subtip care deleagă colecția originală. De exemplu, Scala’s List#subseq creează o subsecvență în timp constant. Cu toate acestea, acest lucru funcționează numai dacă colecția este imuabilă și dacă limbajul de bază sport garbage collection.

Comentarii

  • în c++, o modalitate de a face acest lucru ar fi să avem un vector de shared_ptr la X în loc de vector de X și apoi să copiem SP, dar, din păcate, nu cred că este mai rapid, deoarece operațiunea atomică implicată în copierea SP. Sau vectorul original ar putea fi în schimb un const shared_ptr of vector și ar trebui doar să luați referința la subrange în el. desigur, nu este necesar să îl faceți un shared_ptr of vector, dar atunci aveți probleme cu durata de viață… toate acestea sunt doar idei care îmi vin din capul locului, s-ar putea să mă înșel… –  > Por NoSenseEtAl.
myd7349

Poate că array_view/span din biblioteca GSL este o opțiune bună.

Aici este, de asemenea, o implementare într-un singur fișier: array_view.

Comentarii

  • Vă rugăm să adăugați răspunsul aici împreună cu linkul. Deoarece link-ul extern s-ar putea schimba în viitor –  > Por Pantera.
Jishu Dohare

Copierea elementelor dintr-un vector în altul cu ușurință
În acest exemplu, folosesc un vector de perechi pentru a fi mai ușor de înțeles
`

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


După cum puteți vedea, puteți copia cu ușurință elemente dintr-un vector în altul, dacă doriți să copiați elemente de la indexul 10 la 16, de exemplu, atunci vom folosi

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

iar dacă doriți elemente de la indexul 10 până la un anumit index de la capăt, atunci în acest caz

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

sperăm că acest lucru vă va fi de ajutor, dar nu uitați că în ultimul caz v.end()-5 > v.begin()+10

JHBonarius

Încă o opțiune: Utile de exemplu atunci când se trece de la un fișier thrust::device_vector și un thrust::host_vector, , unde nu se poate folosi constructorul.

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

Ar trebui să fie, de asemenea, complexitatea O(N)

Ați putea combina acest lucru cu codul de răspuns de top

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

mrrgu

Postarea acestui târziu doar pentru alții…Pun pariu că primul programator a terminat până acum. pentru tipurile de date simple nu este nevoie de copie, doar reveniți la metodele bune și vechi de cod C.

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

Apoi, treceți pointerul p și un len la orice lucru care are nevoie de un subvector.

notelen trebuie să fie!!! len < myVec.size()-start

Comentarii

  • Acest lucru nu realizează o copie. –  > Por Trilarion.