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

295

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ć?

Andrzej
źródło
7
mówisz, że chcesz wyodrębnić podwektor, ale wydaje mi się, że tak naprawdę chcesz widok / dostęp do podwektora - różnica polega na tym, że widok nie byłby kopiowany - old school C ++ użyłby wskaźnika początkowego i końcowego, Biorąc pod uwagę fakt, że mem na std :: vector jest ciągły, powinno być możliwe iterowanie za pomocą wskaźników i unikanie kopiowania, jednak jeśli nie przeszkadza ci kopiowanie, to po prostu zainicjuj nowy wektor z zakresem poprzedniego wektor
serup
Istnieje .data () ( cplusplus.com/reference/vector/vector/data ) od wersji c ++ 11. Jednak używanie wskaźników jest odradzane w kontenerach stl, patrz stackoverflow.com/questions/31663770/...
David Tóth,

Odpowiedzi:

371
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.

Greg Rogers
źródło
12
+1, także jest to O (YX), które jest mniejsze lub równe O (N) (aw jego przykładzie znacznie mniej)
orip
74
@orip Cóż, w końcu to O (N).
Johann Gerell
55
@GregRogers: Nie ma sensu używać notacji Big-O, gdzie N jest liczbą określoną. Big-O komunikuje tempo wzrostu w odniesieniu do tego, jak zmienia się N. Johann: Najlepiej nie używać jednej nazwy zmiennej na dwa sposoby. Zwykle powiedzielibyśmy albo O(Y-X)albo powiedzielibyśmy O(Z) where Z=Y-X.
Kaczka Mooing
2
@GregRogers Korzystając z tej metody, musimy zadeklarować nowy wektor. Czy istnieje sposób na zmianę oryginalnego wektora? coś takiego jak myVec (pierwszy, ostatni)? Wiem, że to źle, ale naprawdę potrzebuję rozwiązania, ponieważ chcę użyć rekurencji w swoich kodach i muszę wielokrotnie używać tego samego wektora (chociaż zmieniony). Dzięki!
ulyssis2
13
Dlaczego nie tylko vector<T> newVec(myVec.begin() + 100000, myVec.begin() + 101000);?
aquirdturtle
88

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]);
Martin York
źródło
2
Ok, nie zdawałem sobie sprawy, że tak łatwo było uzyskać iterator z dowolnego elementu wektorowego.
An̲̳̳drew
5
Podanie adresu tych elementów wektorowych jest nie do zniesienia włamaniem, które złamie się, jeśli pamięć wektora nie jest w rzeczywistości ciągła. Użyj begin () + 100000 itd.
j_random_hacker
2
Mój zły, najwyraźniej standard gwarantuje, że przechowywanie wektora jest ciągłe. Niemniej jednak złą praktyką jest praca z takimi adresami, ponieważ z pewnością nie gwarantuje się, że będzie działać dla wszystkich kontenerów obsługujących losowy dostęp, podczas gdy start () + 100000 jest.
j_random_hacker
33
@j_random_hacker: Przepraszamy, nie zgadzam się. Specyfikacja STL dla std :: vector została wyraźnie zmieniona, aby obsługiwać ten typ procedury. Również wskaźnik jest poprawnym typem iteratora. Spójrz w górę iterator_traits <>
Martin York
6
@ taktak004 Nie. Pamiętaj, że operator[]zwraca referencję. Tylko w miejscu, w którym czytasz lub piszesz odwołanie, może to stanowić naruszenie zasad dostępu. Ponieważ nie otrzymujemy ani adresu, ale zamiast niego otrzymujemy adres, nie wywołaliśmy UB.
Martin York
28

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

Anteru
źródło
1
Ponieważ Andrew próbuje skonstruować nowy wektor, poleciłbym „std :: vector foo (...” zamiast kopiować za pomocą „foo = std :: vector (...”
Drew Dormann,
4
Tak, oczywiście, ale to, czy wpiszesz std :: vector <int> foo = std :: vector (...) czy std :: vector <int> foo (...) nie powinno mieć znaczenia.
Anteru
19

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:

einpoklum
źródło
użyłby cbegini cendtylko dla zasady;) std::cbeginitp. nawet.
JHBonarius
1
@JHBonarius: Widząc, że ten kod nie jest wzorowany na wyborze kontenera, nie widzę żadnej szczególnej korzyści; kwestia gustu, jak sądzę.
einpoklum
10

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ę.

Zaćmienie
źródło
Jest to również dobre, jeśli chcesz połączyć oryginalny wektor i podwektor.
PyRulez
7

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;
David Tóth
źródło
6

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
MasterHD
źródło
2
Zastanawiam się, czy w przypadku -O3, „przy użyciu konstruktora” @ Anteru, std::vector(myVec.begin () + 100000, myVec.begin () + 150000);dłuższa wersja tego produktu nie tworzy dokładnie tego samego zestawu?
sandthorn
1
MSVC ++ 2015, na przykład, kompiluje std::vector<>(iter, iter)się memmove()w razie potrzeby (jeśli konstruktor jest trywialny, dla odpowiedniej definicji trywialnej).
Pablo H
1
Nie dzwoń memcpy. Wykonaj konstruktor std::copylub konstruktor, który akceptuje zakres (dwa iteratory), a kompilator i biblioteka std.li spiskują, aby wywołać, memcpygdy jest to właściwe.
Bulletmagnet
4

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);
Matheus Vinícius de Andrade
źródło
3

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

Yuval F.
źródło
Pozytywnie oceniany, ponieważ wskazał mi właściwy kierunek, ale rozumiem, dlaczego @LokiAstari sugeruje, że nie jest to właściwy wybór - ponieważ STL :: copy działa z dwiema tablicami std :: vector <T> tego samego rozmiaru i typu. Tutaj OP chce skopiować podsekcję do nowej, mniejszej tablicy, jak opisano tutaj w poście PO: „0 <= X <= Y <= N-1”
Andrew
@Andrew, patrz przykład przy użyciu std :: copy i std :: back_inserter
chrisg
@LokiAstari dlaczego nie?
chrisg
2
@LokiAstari Miałem na myśli edycję tego, która nie przetrwała recenzji, która stanowi przykład <br/> wektor <T> newvec; std :: copy (myvec.begin () + 10000, myvec.begin () +10100, std :: back_inserter (newvec)); <br/> w tym przypadku nie musisz najpierw budować miejsca docelowego, ale jasne, że bezpośrednia inicjalizacja jest bardziej ... bezpośrednia.
chrisg
1
@chrisg: To także dwie linie. Dodatkowo musisz włożyć trzecią linię, aby upewnić się, że jest wydajna. newvec.reserve(10100 - 10000);. Jest to zdecydowanie opcja i technicznie będzie działać. Ale z dwóch, które zamierzasz polecić?
Martin York,
1

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.

Daniel Spiewak
źródło
w c ++ można to zrobić za pomocą wektora shared_ptr na X zamiast wektora X, a następnie skopiowania SP, ale niestety nie sądzę, że jest to szybsze, ponieważ operacja atomowa związana z cpying SP. Lub oryginalny wektor może być stałą share_ptr wektora zamiast tego, a ty po prostu odwołujesz się do podzakresu w nim. oczywiście nie musisz robić z tego współużytkowanego wektora, ale masz problemy z życiem ... wszystko to jest poza moją głową, może się mylić ...
NoSenseEtAl
0

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

mrrgu
źródło
To nie wykonuje kopii.
Trilarion
0

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

Oto także implementacja jednego pliku: array_view .

myd7349
źródło
Prosimy dodać odpowiedź tutaj wraz z linkiem. Ponieważ zewnętrzny link może ulec zmianie w przyszłości
Panther
0

Ł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

Jishu Dohare
źródło
0

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));
JHBonarius
źródło