أفضل طريقة لاستخراج ناقل فرعي من المتجه؟

Question

لنفترض أن لدي std::vector (دعونا نسميها myVec) من الحجم N.ما هي أبسط طريقة لإنشاء متجه جديد يتكون من نسخة من العناصر X إلى Y، حيث 0 <= X <= Y <= N-1؟على سبيل المثال، myVec [100000] خلال myVec [100999] في ناقلات الحجم 150000.

إذا لم يكن من الممكن القيام بذلك بكفاءة باستخدام ناقل، فهل هناك نوع بيانات STL آخر يجب أن أستخدمه بدلاً من ذلك؟

Answer 1

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

وانها O (N) عملية لبناء ناقلات جديدة، ولكن ليس هناك حقا وسيلة أفضل.

Answer 2

ومجرد استخدام منشئ النواقل.

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

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

Answer 3

وstd::vector(input_iterator, input_iterator)، في حالة foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000); الخاص بك، انظر على سبيل المثال <لأ href = "https://web.archive.org/web/20120120235758/http://www.dinkumware.com/manuals/default.aspx؟manual= اكمل & صفحة = vector.html "يختلط =" noreferrer "> هنا

Answer 4

في هذه الأيام نستخدم spanس!لذلك سوف تكتب:

#include <gsl/span>

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

للحصول على مدى 1000 عنصر من نفس النوع myvec'س.الآن، هذا هو ليست نسخة، إنها مجرد وجهة نظر من البيانات الموجودة في المتجه، لذا كن حذرًا.إذا كنت تريد نسخة فعلية، يمكنك القيام بما يلي:

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

ملحوظات:

• gsl لتقف على مكتبة دعم المبادئ التوجيهية.لمزيد من المعلومات حول gsl, ، يرى: http://www.modernescpp.com/index.php/c-core-guideline-the-guidelines-support-library.
• لتنفيذ واحد من gsl, ، يرى: https://github.com/Microsoft/GSL
• يوفر C++ 20 تنفيذًا لـ span.سوف تستخدم std::span و #include <span> بدلا من #include <gsl/span>.
• لمزيد من المعلومات حول الامتدادات، راجع: ما هو "الامتداد" ومتى يجب أن أستخدمه؟
• std::vector لديها عدد كبير من المُنشئات، ومن السهل جدًا الوقوع في واحدة لم تكن تنوي استخدامها، لذا كن حذرًا.

Answer 5

إذا كلاهما لن يتم تعديل (أي إضافة / حذف البنود - تعديل القائم منها على ما يرام طالما كنت الالتفات إلى خيوط القضايا)، يمكنك تمرير ببساطة حول data.begin() + 100000 وdata.begin() + 101000، والتظاهر بأنهم begin() وend() من ناقلات أصغر.

وأو، منذ مكفول تخزين متجه لتكون متجاورة، يمكنك تمرير ببساطة حول 1000 عنصر مجموعة:

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

وكل هذه التقنيات وقتا ثابتا، ولكنها تحتاج إلى أن طول البيانات لا تزيد مما تسبب في إعادة توزيع.

Answer 6

وأنت لم تذكر ما std::vector<...> myVec نوع هو، ولكن اذا كان نوع بسيط أو بنية / فئة لا يتضمن مؤشرات، وتريد أفضل كفاءة، ثم يمكنك أن تفعل نسخة المباشر للذاكرة (الذي أعتقد أنه سوف يكون أسرع من الإجابات الأخرى المقدمة). هنا هو مثال عام لstd::vector<type> myVec حيث type في هذه الحالة هو 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

Answer 7

ويمكنك استخدام نسخة STL مع O (M) الأداء عند M هو حجم subvector.

Answer 8

والطريقة الوحيدة لإبراز مجموعة غير الزمن الخطي هو أن تفعل ذلك بتكاسل، حيث نتج عن ذلك "ناقلات" هو في الواقع نوع فرعي التي مندوبين لجمع الأصلي. على سبيل المثال، طريقة List#subseq سكالا لإنشاء تسلسل الفرعي في وقت ثابت. ومع ذلك، وهذا يعمل فقط إذا كان جمع غير قابل للتغيير، وإذا جمع القمامة الرياضة لغة الأساسي.

Answer 9

نعم.هذه مناقشة قديمة جدًا.لكنني اكتشفت للتو شيئًا أنيقًا:

صفيف_الشريحة - هل يمكن أن يكون هذا بديلا سريعا؟لم أختبره بعد.

Answer 10

ونشر هذا في وقت متأخر لمجرد رهان others..I يتم المبرمج الأول الآن. لأنواع البيانات بسيطة هو لم يكن هناك نسخة، مجرد العودة إلى أساليب كود C الخوالي.

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

وبعد ذلك تمر ع مؤشر وليون إلى أي شيء تحتاج إلى subvector.

ويجب أن يكون notelen !! len < myVec.size()-start

Answer 11

وربما array_view / SPAN في المكتبة GSL هو خيار جيد.

وهنا أيضا تنفيذ ملف واحد: array_view

Answer 12

نسخ العناصر من متجه إلى آخر بسهولة
في هذا المثال، أستخدم متجهًا للأزواج لتسهيل الفهم
`

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

'
كما ترون، يمكنك بسهولة نسخ العناصر من متجه إلى آخر، إذا كنت تريد نسخ العناصر من الفهرس 10 إلى 16 على سبيل المثال، فسنستخدم

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

وإذا كنت تريد عناصر من الفهرس 10 إلى بعض الفهرس من النهاية، ففي هذه الحالة

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

نأمل أن يساعد هذا، فقط تذكر في الحالة الأخيرة v.end()-5 > v.begin()+10

Answer 13

ولكن هناك خيار آخر: مفيد على سبيل المثال عند الانتقال بين thrust::device_vector وthrust::host_vector، حيث لا يمكنك استخدام منشئ.

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

وينبغي أن يكون أيضا تعقيد O (N)

هل يمكن الجمع بين هذا مع كبار كود انور

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

Answer 14

هل يمكن استخدام فقط insert

vector<type> myVec { n_elements };

vector<type> newVec;

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