ما الفرق بين deque و القائمة الخاصة بلبنان الحاويات ؟

Question

ما هو الفرق بين الاثنين ؟ أعني الأساليب هي كل نفس.لذا على المستخدم ، أنها تعمل بشكل مماثل.

هل هذا الصحيح ؟ ؟

Answer 1

ومن (بتاريخ لكن لا تزال مفيدة جدا) SGI ملخص STL من <أ href = ل "http://www.sgi.com/tech/stl/Deque.html" يختلط = "noreferrer"> deque :

<اقتباس فقرة>   

وهناك صف مزدوج الذيل تشبه إلى حد كبير متجه: مثل ناقلات، بل هو تسلسل التي تدعم الوصول العشوائي إلى العناصر، ثابت الإدراج الوقت وإزالة عناصر في نهاية التسلسل، والخطي الإدراج الوقت وإزالة العناصر في الوسط.

     

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

وفيما يلي ملخص عن list من نفس الموقع:

<اقتباس فقرة>   

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

في ملخص الحاويات قد تقاسمت الروتينية ولكن الضمانات وقتا لأولئك الروتينية تختلف من الحاويات إلى حاوية . وهذا أمر مهم جدا عند النظر في أي من هذه الحاويات لاستخدامها في مهمة: مع مراعاة <م> كيف الحاوية سوف تستخدم في معظم الأحيان (على سبيل المثال، أكثر للبحث من أجل إدراج / حذف) يقطع شوطا طويلا في توجيهك إلى الحاوية الصحيحة.

Answer 2

اسمحوا لي أسفل قائمة الاختلافات:

• Deque تمكن عناصرها مع مجموعة ديناميكية, يوفر عشوائية الوصول, و تقريبا نفس واجهة كناقل.
• قائمة تمكن عناصرها كما قائمة مرتبطة مضاعف و لا توفر وصول عشوائي.

---

• Deque يوفر سرعة الإدراج والحذف في كل نهاية وبداية.إدراج وحذف العناصر في وسط بطيئة نسبيا بسبب جميع العناصر إلى أي من كل ينتهي قد تكون انتقلت إلى جعل الغرفة أو ملء الفجوة.
• في قائمة, إدراج وإزالة عناصر سريع في كل موقف ، بما في ذلك كلا الطرفين.

---

• Deque:أي إدراج أو حذف العناصر في بداية أو نهاية يبطل كل المؤشرات ، المراجع ، و التكرار التي تشير إلى عناصر من deque.
• قائمة:إدراج وحذف العناصر لا لا يبطل المؤشرات ، المراجع ، و التكرار إلى عناصر أخرى.

---

تعقيد

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

Answer 3

std::list هو في الأساس قائمة مرتبطة على نحو مضاعف.

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

Answer 4

ولا. A صف مزدوج الذيل يعتمد فقط O (1) الإدراج والحذف في الأمام والخلف. قد، على سبيل المثال، يتم تنفيذه في ناقلات مع التفاف حولها. لأنه يضمن أيضا O (1) وصول عشوائي، يمكنك أن تكون على يقين من انها لا تستخدم (فقط) قائمة مرتبطة على نحو مضاعف.

Answer 5

مهم آخر هو الضمان الطريق كل حاوية مختلفة يقوم بتخزين البيانات في الذاكرة:

• ناقلات هي واحدة متجاورة كتلة الذاكرة.
• أ deque مجموعة من ربط كتل الذاكرة ، حيث أكثر من عنصر واحد يتم تخزينها في كل كتلة الذاكرة.
• قائمة مجموعة من العناصر المشتتة في الذاكرة ، أي:عنصر واحد فقط يتم تخزينها في الذاكرة "كتلة".

علما بأن deque صمم في محاولة التوازن بين مزايا كل من ناقلات قائمة دون كل منهما عيوب.فمن خصيصا للاهتمام الحاويات في الذاكرة محدود من المنصات ، على سبيل المثال ، ميكروكنترولر.

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

Answer 6

ولقد تم شرح الاختلافات أداء جيدا قبل الآخرين. أردت فقط أن أضيف أن واجهات مماثلة أو حتى متطابقة شائعة في البرمجة كائنية التوجه - جزء من المنهجية العامة للكتابة البرمجيات وجوه المنحى. يجب أن IN NO WAY نفترض أن فئتين تعمل بنفس الطريقة لأنهم ببساطة تنفيذ نفس واجهة، أي أكثر من يجب أن نفترض أن حصان يعمل مثل الكلب لأنهم على حد سواء تنفيذ هجوم () وmake_noise ().