هل يبدأ تنفيذ C++/end/rbegin/rend في وقت ثابت لـ std::set، std::map، وما إلى ذلك؟

Question

بالنسبة لأنواع البيانات مثل std::set وstd::map حيث يحدث البحث في وقت لوغاريتمي، هل التنفيذ مطلوب للحفاظ على تكرارات البداية والنهاية؟هل يعني الوصول إلى البداية والنهاية إجراء بحث يمكن أن يحدث في وقت لوغاريتمي؟

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

شكرًا

Answer 1

أنها تحدث في وقت ثابت.أنا أنظر إلى الصفحة 466 من معيار ISO/IEC 14882:2003:

جدول 65 - متطلبات الحاويات

a.begin(); (التعقيد المستمر)

a.end(); (التعقيد المستمر)

الجدول 66 - متطلبات الحاوية القابلة للعكس

a.rbegin(); (التعقيد المستمر)

a.rend(); (التعقيد المستمر)

Answer 2

نعم بحسب http://www.cplusplus.com/reference/stl/, و begin() و end() وما إلى ذلك كلها O(1).

Answer 3

في معيار C++، يسرد الجدول 65 في 23.1 (متطلبات الحاوية) begin() و end() على أنهما يتطلبان وقتًا ثابتًا.إذا كان تنفيذك ينتهك هذا، فهو غير مطابق.

Answer 4

ما عليك سوى إلقاء نظرة على الكود، وهنا يمكنك رؤية التكرارات في std::map في GNU libstdc++

std::map

سترى أن كل نهاية تنتهي...يتم تنفيذها جميعا في وقت ثابت.

Answer 5

كن حذرًا مع hash_map بالرغم من ذلك.start () ليست ثابتة.

Answer 6

من أجل الأمراض المنقولة جنسيا :: مجموعة

يبدأ:ثابت، نهاية:ثابت ، rbegin:ثابت ، الاداء:ثابت،

من أجل الأمراض المنقولة جنسيا::map

هم أيضا ثابتون (جميعهم)

إذا كان لديك أي شك، فقط تحقق www.cplusplus.com