Cara terbaik untuk mengekstrak subvektor dari vektor?

Misalkan saya memiliki ukuran std::vector(sebut saja myVec) N. Apa cara paling sederhana untuk membuat vektor baru yang terdiri dari salinan elemen X hingga Y, di mana 0 <= X <= Y <= N-1? Misalnya myVec [100000]melalui myVec [100999]dalam ukuran vektor 150000.

Jika ini tidak dapat dilakukan secara efisien dengan vektor, apakah ada tipe data STL lain yang harus saya gunakan?

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

Ini adalah operasi O (N) untuk membangun vektor baru, tetapi sebenarnya tidak ada cara yang lebih baik.

Cukup gunakan konstruktor vektor.

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), dalam kasus Anda foo = std::vector<T>(myVec.begin () + 100000, myVec.begin () + 150000);, lihat misalnya di sini

Hari ini, kami menggunakan spans! Jadi, Anda akan menulis:

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

untuk mendapatkan rentang 1000 elemen dari jenis yang sama dengan myvec's. Atau bentuk yang lebih singkat:

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

(tapi saya tidak terlalu suka ini, karena arti dari setiap argumen numerik tidak sepenuhnya jelas; dan akan menjadi lebih buruk jika panjang dan start_pos memiliki urutan yang sama besarnya.)

Ngomong-ngomong, ingat bahwa ini bukan salinan, itu hanya tampilan data dalam vektor, jadi hati-hati. Jika Anda ingin salinan yang sebenarnya, Anda dapat melakukan:

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

Catatan:

• gslkependekan dari Guidelines Support Library. Untuk informasi lebih lanjut tentang gsl, lihat: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library .
• Untuk satu implementasi gsl, lihat: https://github.com/Microsoft/GSL
• C ++ 20 menyediakan implementasi dari span. Anda akan menggunakan std::spandan #include <span>bukannya #include <gsl/span>.
• Untuk informasi lebih lanjut tentang rentang, lihat: Apa itu "rentang" dan kapan saya harus menggunakannya?
• std::vector memiliki trilyun konstruktor, sangat mudah untuk jatuh ke dalam yang Anda tidak ingin gunakan, jadi hati-hati.

Jika keduanya tidak akan dimodifikasi (tidak ada penambahan / penghapusan item - memodifikasi yang sudah ada baik-baik saja selama Anda memperhatikan masalah threading), Anda dapat dengan mudah berkeliling data.begin() + 100000dan data.begin() + 101000, dan berpura-pura bahwa itu adalah begin()dan end()dari vektor yang lebih kecil.

Atau, karena penyimpanan vektor dijamin bersebelahan, Anda bisa dengan mudah memberikan 1000 item array:

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

Kedua teknik ini membutuhkan waktu konstan, tetapi mengharuskan panjang data tidak meningkat, memicu realokasi.

Diskusi ini cukup lama, tetapi yang paling sederhana belum disebutkan, dengan inisialisasi daftar :

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

Ini membutuhkan c ++ 11 atau lebih tinggi.

Contoh penggunaan:

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

Hasil:

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;

Anda tidak menyebutkan tipe apa std::vector<...> myVec, tetapi jika itu tipe sederhana atau struct / kelas yang tidak menyertakan pointer, dan Anda menginginkan efisiensi terbaik, maka Anda dapat melakukan salinan memori langsung (yang saya pikir akan lebih cepat daripada jawaban lain disediakan). Berikut ini adalah contoh umum untuk std::vector<type> myVecdi mana typedalam hal ini adalah 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

Anda bisa menggunakannya insert

vector<type> myVec { n_elements };

vector<type> newVec;

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

Anda dapat menggunakan salin STL dengan kinerja O (M) ketika M adalah ukuran subvektor.

Satu-satunya cara untuk memproyeksikan koleksi yang bukan waktu linear adalah melakukannya dengan malas, di mana "vektor" yang dihasilkan sebenarnya adalah subtipe yang mendelegasikan ke koleksi asli. Sebagai contoh, List#subseqmetode Scala membuat sub-urutan dalam waktu yang konstan. Namun, ini hanya berfungsi jika koleksi tersebut tidak berubah dan jika bahasa yang mendasari olahraga pengumpulan sampah.

Posting ini terlambat hanya untuk orang lain .. Aku yakin koder pertama selesai sekarang. Untuk tipe data sederhana salinan tidak diperlukan, cukup kembali ke metode kode C lama yang baik.

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

Kemudian berikan pointer p dan len ke apa pun yang membutuhkan subvektor.

notelen pasti !! len < myVec.size()-start

Mungkin array_view / span di pustaka GSL adalah pilihan yang baik.

Berikut ini juga implementasi file tunggal: array_view .

Menyalin elemen dari satu vektor ke yang lain dengan mudah
Dalam contoh ini, saya menggunakan vektor pasangan untuk membuatnya mudah dimengerti
`

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

'
Seperti yang Anda lihat, Anda dapat dengan mudah menyalin elemen dari satu vektor ke yang lain, jika Anda ingin menyalin elemen dari indeks 10 hingga 16 misalnya maka kita akan menggunakan

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

dan jika Anda ingin elemen dari indeks 10 ke beberapa indeks dari akhir, maka dalam hal itu

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

Semoga ini bisa membantu, ingat saja dalam kasus terakhir v.end()-5 > v.begin()+10

Namun pilihan lain: Berguna misalnya ketika bergerak antara a thrust::device_vectordan a thrust::host_vector, di mana Anda tidak dapat menggunakan konstruktor.

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

Seharusnya juga kompleksitas O (N)

Anda dapat menggabungkan ini dengan kode jawaban teratas

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