Najlepszy sposób na wyodrębnienie subvektora z wektora?

Załóżmy, że mam std::vector(nazwijmy to myVec) rozmiar N. Jaki jest najprostszy sposób na zbudowanie nowego wektora składającego się z kopii elementów od X do Y, gdzie 0 <= X <= Y <= N-1? Na przykład, myVec [100000]za pomocą myVec [100999]w wektorze wielkości 150000.

Jeśli nie można tego zrobić skutecznie za pomocą wektora, czy istnieje inny typ danych STL, którego powinienem użyć?

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

Jest to operacja O (N), aby skonstruować nowy wektor, ale tak naprawdę nie ma lepszego sposobu.

Wystarczy użyć konstruktora wektorowego.

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

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

std::vector<T>(input_iterator, input_iterator), w twoim przypadku foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, patrz na przykład tutaj

Obecnie używamy spans! Więc napisałbyś:

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

aby uzyskać rozpiętość 1000 elementów tego samego typu co myvec's. Lub bardziej zwięzła forma:

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

(ale nie podoba mi się to tak bardzo, ponieważ znaczenie każdego argumentu liczbowego nie jest do końca jasne; i gorzej, jeśli długość i początkowe pozycje są tego samego rzędu wielkości).

W każdym razie pamiętaj, że to nie jest kopia, to tylko widok danych w wektorze, więc bądź ostrożny. Jeśli chcesz rzeczywistą kopię, możesz:

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

Uwagi:

• gsloznacza bibliotekę obsługi wytycznych. Aby uzyskać więcej informacji gsl, zobacz: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library .
• Dla jednej implementacji gslpatrz: https://github.com/Microsoft/GSL
• C ++ 20 zapewnia implementację span. Wolałbyś użyć std::spani #include <span>zamiast #include <gsl/span>.
• Aby uzyskać więcej informacji o zakresach, zobacz: Co to jest „zakres” i kiedy powinienem go użyć?
• std::vector ma konstruktorów gazillionowych, bardzo łatwo wpaść w taki, którego nie zamierzałeś używać, więc bądź ostrożny.

Jeśli oba nie zostaną zmodyfikowane (bez dodawania / usuwania elementów - modyfikowanie istniejących jest w porządku tak długo, jak zwracać uwagę na kwestie gwintowania), można po prostu przejść wokół data.begin() + 100000i data.begin() + 101000, i udawać, że są begin()i end()mniejszej wektorze.

Lub, ponieważ gwarantuje się, że miejsce na wektor jest ciągłe, możesz po prostu przekazać około 1000 elementów tablicy:

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

Obie te techniki wymagają stałego czasu, ale wymagają, aby długość danych nie zwiększała się, powodując realokację.

Ta dyskusja jest dość stara, ale najprostsza nie została jeszcze wspomniana, z inicjalizacją listy :

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

Wymaga c ++ 11 lub nowszego.

Przykładowe użycie:

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

Wynik:

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;

Nie wspomniałeś o tym, jaki std::vector<...> myVecjest typ , ale jeśli jest to prosty typ lub struktura / klasa, która nie zawiera wskaźników, i chcesz uzyskać najlepszą wydajność, możesz wykonać bezpośrednią kopię pamięci (co moim zdaniem będzie szybsze niż inne udzielone odpowiedzi). Oto ogólny przykład tego, std::vector<type> myVecgdzie typew tym przypadku jest 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

Możesz po prostu użyć insert

vector<type> myVec { n_elements };

vector<type> newVec;

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

Możesz użyć kopiowania STL z wydajnością O (M), gdy M jest rozmiarem subvektora.

Jedynym sposobem na wyświetlenie kolekcji, która nie jest czasem liniowym, jest zrobienie tego leniwie, gdzie powstały „wektor” jest tak naprawdę podtypem, który przekazuje do oryginalnej kolekcji. Na przykład List#subseqmetoda Scali tworzy podsekwencję w stałym czasie. Działa to jednak tylko wtedy, gdy kolekcja jest niezmienna i jeśli w podstawowym języku jest używane czyszczenie pamięci.

Publikowanie tego spóźnienia tylko dla innych. Założę się, że pierwszy programista jest już gotowy. W przypadku prostych typów danych nie jest wymagana kopia, wystarczy przywrócić stare dobre metody kodu C.

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

Następnie przekaż wskaźnik p i soczewkę do czegokolwiek, co wymaga subvektora.

notelen musi być !! len < myVec.size()-start

Może dobrym rozwiązaniem jest opcja array_view / span w bibliotece GSL.

Oto także implementacja jednego pliku: array_view .

Łatwe kopiowanie elementów z jednego wektora na drugi
W tym przykładzie używam wektora par, aby ułatwić zrozumienie
`

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

„
Jak widać, możesz łatwo kopiować elementy z jednego wektora do drugiego, jeśli na przykład chcesz skopiować elementy z indeksu 10 do 16, wówczas użyjemy

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

a jeśli chcesz elementy od indeksu 10 do jakiegoś indeksu od końca, to w takim przypadku

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

mam nadzieję, że to pomoże, pamiętaj tylko w ostatnim przypadku v.end()-5 > v.begin()+10

Jeszcze inna opcja: Przydatna na przykład podczas przechodzenia między thrust::device_vectora a thrust::host_vector, gdzie nie można użyć konstruktora.

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

Powinny również być złożoności O (N)

Możesz to połączyć z górnym kodem odpowiedzi

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