std :: set start() और std :: सेट iterator O (logn)

Question

के बीच दूरी मुझे std :: set में किसी तत्व की अनुक्रमणिका ढूंढने की आवश्यकता है। इस सूचकांक को शुरुआत से हीटरेटर की दूरी के रूप में देखा जा सकता है। एक तरीका यह हो सकता है:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i); 

यह स्पष्ट रूप से हे (एन) समय लगता है। लेकिन हम जानते हैं कि आंतरिक रूप से सेट द्वारा कार्यान्वित एक बाइनरी खोज पेड़ में रूट से दूरी ओ (लॉग एन) समय में पाई जा सकती है।

क्या सी ++ सेट में ओ (लॉग एन) समय में इंडेक्स को खोजने के लिए इसे लागू करने का कोई तरीका है?

Answer 1

आप हल कर उपयोग कर सकते हैं std::vector<int> । यदि इसे सॉर्ट किया गया है, तो आप O(log n) में तत्व पा सकते हैं। और आप निरंतर समय O(1) में दूरी पा सकते हैं।

क्रमबद्ध वेक्टर से मेरा मतलब है कि हर प्रविष्टि के बाद (या कई सम्मिलन के बाद) आप std::sort(v.begin(), v.end());

करते हैं std::set<T> के अंदर अपने प्रकार int की तरह प्रकाश के रूप में नहीं है - तुम दोनों रख सकते - std::set<T> और iterators std::vector<std::set<T>::iterator> के वेक्टर अनुसार क्रमबद्ध । लेकिन इन संरचनाओं को सिंक में रखना मुश्किल नहीं हो सकता था। शायद आप T पर कुछ स्थिति जोड़ सकते हैं? या std::set<std::pair<T,int>, comp_first_of_pair<T>> रखें जहां comp_first_of_pair है set केवल T द्वारा क्रमबद्ध है और दूसरा int सेट में स्थिति रखने के लिए है?

बस कुछ विचार - यहां तक ​​कि O(1) दूरी समय तो कंप्यूटिंग सूचकांक वास्तव में अपने टोंटी है के लिए ...

Answer 2

आप std::set<>::find फ़ंक्शन का उपयोग x तत्व की खोज के लिए कर सकते हैं और distance को सेट के पहले पुनरावर्तक पर गणना कर सकते हैं।

std::distance(s.begin(), s.find(x)) 

हालांकि, टिप्पणियों के अनुसार दूरी का रनटाइम इंगित करने वाले इटरेटर के प्रकार पर निर्भर करता है। एक सेट के मामले में यह एक द्विपक्षीय इटरेटर है और दूरी ओ (एन) है।

Answer 3

आप बिडरेक्शनल इटरेटर्स के साथ मेटामैटिक्स का उपयोग नहीं कर सकते हैं। तो केवल स्वीकार्य तरीका है कि आप स्वयं को गिनें (कितने int सेट में डाले गए एक्स से कम)।

लेकिन, यदि आप सफाई से अलग किया है "डेटा संग्रह" और "डेटा के उपयोग" चरणों - शायद इसके लायक को बदलने के लिए है std :: क्रमबद्ध std :: वेक्टर साथ निर्धारित किया है। इसके रेख करने में कठिन है, लेकिन इटरेटर matematics सहित अपने लाभ, है (ताकि आप std :: binary_search साथ हे (लॉग एन) और ओ के साथ दूरी के साथ खोज प्राप्त कर सकते हैं (1))

Answer 4

, तो मैं 2 विकल्प देखें:

• स्टोर सूचकांक। या तो स्वयं नोड्स में या एक अलग std::map में। बेशक इसका मतलब है कि आपको यह कैश अपडेट करना होगा।
• std::vector का उपयोग करें। यह उतना बुरा नहीं है जितना कि यह पहले देख सकता है। यदि आप हमेशा वेक्टर को सॉर्ट करते हैं तो आप इसे set जैसे उपयोग कर सकते हैं। प्रदर्शन set के समान होगा। सबसे बड़ी कमी यह है कि नोड की प्रतिलिपि बनाई जा सकती है। (इसे पॉइंटर्स, boost:shared_ptr या std::unique_ptr [C++ 11 केवल])
  एक तत्व को देखने के लिए आप std::lower_bound का उपयोग करके मुआवजा दिया जा सकता है।
  डालने/पुश_बैक के बजाय आप करते हैं: insert(lower_bound(b,e,x), x)