كيف يكون الحذف العشوائي من std::vector أسرع من std::list؟

Question

كيف يكون هذا الحذف العشوائي من std::vector أسرع من std::list؟ما أفعله لتسريع الأمر هو تبديل العنصر العشوائي بالعنصر الأخير ثم حذف العنصر الأخير.كنت أعتقد أن القائمة ستكون أسرع لأن الحذف العشوائي هو ما تم إنشاؤه من أجله.

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}

النتائج (بالثواني):
حذف مبادلة Vec:0.00000909461232367903
قائمة الحذف العادي:0.00011785102105932310

Answer 1

ما تفعلونه ليس الحذف العشوائي على الرغم من. كنت حذف من النهاية، وهو ما يتم بناء ناقلات لل(من بين أمور أخرى).

وعندما مبادلة، تفعلونه عملية واحدة عشوائية الفهرسة، وهو <م> أيضا ما ناقلات جيدة في.

Answer 2

والفرق بين std::list وstd::vector ليس مجرد وصولا إلى الأداء. كما أن لديها مختلفة دلالات مكرر إبطال. إذا كنت محو عنصر من std::list، كل المكررات مشيرا إلى البنود الأخرى في القائمة لا تزال صالحة. ليس ذلك مع std::vector، حيث محو عنصر يبطل كل التكرارات لافتا بعد ذلك البند. (في بعض التطبيقات، قد لا يزال يخدم المكررات صالحة، ولكن وفقا لمعيار وهم الآن غير صالحة للاستعمال، ويجب تطبيق فحص لتأكيد إذا حاولت استخدامها).

وحتى اختيارك للحاوية هو أيضا علاقة مع ما دلالات تحتاج.

Answer 3

وهذا ليس عشوائي. محاولة vector1.erase (vector.begin () + راند ()٪ vector.size ())؛ بدلا من ذلك.

Answer 4

وقائمة erase سيؤدي إلى حذف عنصر قائمة تمحى، وهذا سوف استدعاء استدعاء مشغل delete. محو ناقلات يسبب مجرد تبادل وثم إنقاص عدد صحيح - وهذا هو أسرع كثيرا

Answer 5

في الواقع، إذا كنت تريد المزيد من التسريعات، فيجب عليك فهرسة العناصر الموجودة في المتجه عبر التكرارات.من المعروف أنها تتمتع بأداء أفضل لبعض البنى.