क्या वेक्टर की जटिलता :: स्पष्ट अनिर्दिष्ट है?

Question

Is `std::vector<primitive>::clear()` a constant time operation? से एक चर्चा के अनुसार, यह नोट किया गया था कि C++ मानक vector::clear के चल रहे समय को निर्दिष्ट करने के लिए प्रकट नहीं होता है।

यह list::clear (रैखिक; §23.3.5.4.5), .clear के क्रमशः दोनों आदेश (तालिका 102) और अनियंत्रित सहयोगी कंटेनर (तालिका 103) (दोनों रैखिक) के लिए चलने का समय निर्दिष्ट करता है। हालांकि, vector::clear गायब प्रतीत होता है (हालांकि अन्य vector सदस्य, जैसे .data और .swap में निर्दिष्ट जटिलता दिखाई देती है)।

क्या यह वास्तव में अनिर्दिष्ट है, या क्या मुझे कुछ याद आया?

Answer 1

क्या यह वास्तव में अनिर्दिष्ट है, या क्या मुझे कुछ याद आया?

हाँ। फिलहाल, यह वास्तव में अनिर्दिष्ट है।

There is an open library issue for this, जिसका टेक्स्ट स्टैक ओवरव्लो पर प्रासंगिक Q & ए के लिए एक लिंक है। उस प्रश्न पर Jonathan Wakely का उत्तर स्पष्ट करता है कि क्या हो रहा है।

लिंक किए गए प्रस्ताव के मुताबिक, clear() की जटिलता आवश्यकता रैखिक सभी अनुक्रम कंटेनरों के लिए बनाई जानी चाहिए। हालांकि, किसी को यह ध्यान में रखना चाहिए कि जटिलता आवश्यकताओं केवल ऊपरी सीमा हैं। सी ++ 11 पैरा के अनुच्छेद 17.5.1.4/7:

लाइब्रेरी खंडों में निर्दिष्ट जटिलता आवश्यकताओं ऊपरी सीमाएं हैं, और कार्यान्वयन जो बेहतर जटिलता गारंटी प्रदान करते हैं, आवश्यकताओं को पूरा करते हैं।

यह संभावित अनुकूलन के लिए की अनुमति देता है, लेकिन उन्हें जरूरी नहीं है।

जब भी लिंक प्रस्तावित स्वीकार किया जाएगा, तब भी हमें यह मानने की अनुमति नहीं दी जाएगी कि clear() में गैर-वर्ग तत्वों के अनुक्रम कंटेनरों के लिए ओ (1) जटिलता है, भले ही यह एक प्राकृतिक और सामान्य अनुकूलन रणनीति प्रतीत होती है (और dasblinkenlight से this question on SO द्वारा उत्तर इसकी पुष्टि करता है)।

क्रियान्वयन (17.5.1.4/7 प्रति) इस रणनीति को अपनाने के लिए अनुमति दी जाएगी, लेकिन वे की आवश्यकता नहीं होगी, ऐसा करने के लिए, क्योंकि कहीं नहीं स्टैंडर्ड में इस तरह की कोई समस्या है (और न ही यह होने के लिए प्रस्तावित किया गया है) निर्दिष्ट।