هل std::list::size() حقًا O(n) في التطبيقات الحديثة؟

في الآونة الأخيرة، اقترح بعض المطورين ذلك std::list::size() لها تعقيد زمني خطي (O(n)). ومع ذلك، وفقًا لمعيار C، لم يتم تعريف التعقيد وقد يختلف اعتمادًا على التنفيذ.

في الإصدارات السابقة من معيار C (C 03)، يوصى باستخدام عملية size() لتكون ذات تعقيد ثابت. (س(1)). ومع ذلك، مع إدخال C 11، أصبح مطلبًا لجميع الحاويات القياسية. ينص الجدول 96 من معيار C 11 صراحةً على أن .size() يجب أن يكون له تعقيد ثابت لجميع الحاويات.

تاريخيًا، نفذت مكتبة libstdc في دول مجلس التعاون الخليجي size() مع التعقيد O(n) باستخدام std::distance(begin) ()، end())، كما هو موضح في إدخال المدونة الذي استشهدت به. ومع ذلك، في وضع C 11، تغير هذا السلوك:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

في الإصدار 5.0 من دول مجلس التعاون الخليجي والإصدارات الأحدث، تستخدم الدالة size() بنية بيانات داخلية لتتبع عدد العناصر، مما يجعل العملية O(1) فعالة. يتوافق هذا مع متطلبات C 11 لجميع الحاويات القياسية.

من المهم ملاحظة أن بعض حالات الاستخدام المتخصصة قد تؤدي إلى تعقيد O(n) لـ size()، ولكن بالنسبة للغالبية العظمى من المستخدمين، فإن يجب أن تكون العملية بوقت ثابت.