क्या std::list::size() वास्तव में आधुनिक कार्यान्वयन में O(n) है?

हाल ही में, कुछ डेवलपर्स ने सुझाव दिया है कि std::list::size() में एक रैखिक समय जटिलता (O(n)) है। हालाँकि, सी मानक के अनुसार, जटिलता परिभाषित नहीं है और कार्यान्वयन के आधार पर भिन्न हो सकती है।

सी मानक (सी 03) के पुराने संस्करणों में, आकार() ऑपरेशन को निरंतर जटिलता रखने की सिफारिश की गई थी (ओ(1)). हालाँकि, C 11 की शुरूआत के साथ, यह सभी मानक कंटेनरों के लिए एक आवश्यकता बन गई। सी 11 मानक की तालिका 96 स्पष्ट रूप से बताती है कि .size() में सभी कंटेनरों के लिए निरंतर जटिलता होनी चाहिए।

ऐतिहासिक रूप से, GCC की libstdc लाइब्रेरी ने std::distance(begin) का उपयोग करके जटिलता O(n) के साथ size() लागू किया (), अंत()), जैसा कि आपके द्वारा उद्धृत ब्लॉग प्रविष्टि में वर्णित है। हालाँकि, 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();}

GCC 5.0 और इसके बाद के संस्करण में, size() फ़ंक्शन तत्वों की संख्या पर नज़र रखने के लिए एक आंतरिक डेटा संरचना का उपयोग करता है, जिससे ऑपरेशन प्रभावी ढंग से O(1) हो जाता है। यह सभी मानक कंटेनरों के लिए सी 11 आवश्यकता के अनुरूप है।

यह ध्यान रखना महत्वपूर्ण है कि कुछ विशिष्ट उपयोग के मामले अभी भी आकार() के लिए ओ(एन) जटिलता का कारण बन सकते हैं, लेकिन अधिकांश उपयोगकर्ताओं के लिए, संचालन निरंतर समय होना चाहिए।