std :: set :: insert, मैं कितना बुरा संकेत दे सकता हूं?

Question

मैं std::pair<int, int> के std::set में बहुत सारे और बहुत सारे आवेषण कर रहा हूं, और मुझे लगता है कि यह अधिक समय ले रहा है। जब मैंने कोड लिखा था तो मुझे लगा कि मैं बाद में डालने के संकेत संकेतक फॉर्म का उपयोग कर देखना चाहूंगा यदि यह एक बाधा बन गया हो; अच्छा, अब यह प्रोफाइल है और यह एक बाधा है। तो मैं इटरेटर संकेत का उपयोग करना चाहता हूँ।

हालांकि, मैं हमेशा अपने जोड़ों को सम्मिलित करने के लिए एक अच्छी स्थिति नहीं जानता हूं। मैं आम तौर पर बैच में डालता हूं (इस मामले में एक बैच कुल इनपुट आकार के 0.01% के क्रम में है, डुप्लीकेट शामिल है), लेकिन जब बैच डाला जाता है, तो मुझे नहीं पता कि अगला व्यक्ति कहां चाहिए प्रारंभ। संकेत का उपयोग कैसे किया जाता है? क्या सुझाव दिया गया स्थिति से बाइनरी खोज की तरह कुछ करता है? एक बुरा संकेत का उपयोग करना कितना बुरा होगा, आमतौर पर?

Answer 1

मैं सुझाव देता हूं कि संकलक क्या पढ़ता है: #include <set> के लिए हेडर फ़ाइल। अपने सिस्टम पर (जीएनयू ++ 4.5.1 libstdc) मैं निम्नलिखित आत्म व्याख्यात्मक पाठ पढ़ सकते हैं:

/** 
    * @brief Attempts to insert an element into the %set. 
    * @param position An iterator that serves as a hint as to where the 
    *     element should be inserted. 
    * @param x Element to be inserted. 
    * @return An iterator that points to the element with key of @a x (may 
    *   or may not be the element passed in). 
    * 
    * This function is not concerned about whether the insertion took place, 
    * and thus does not return a boolean like the single-argument insert() 
    * does. Note that the first parameter is only a hint and can 
    * potentially improve the performance of the insertion process. A bad 
    * hint would cause no gains in efficiency. 
    * 
    * For more on @a hinting, see: 
    * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 
    * 
    * Insertion requires logarithmic time (if the hint is not taken). 
    */ 
    iterator 
    insert(iterator __position, const value_type& __x) 
    { return _M_t._M_insert_unique_(__position, __x); } 

Takeaway:

1. एक बुरा संकेत दक्षता
2. प्रविष्टि में कोई लाभ का कारण होता है O(log n)
3. आप insertion hints in the GNU libstdc++ manual के बारे में और भी पढ़ सकते हैं।

Answer 2

एक संकेत अच्छा है अगर यह सही संकेत है - एक प्रविष्टि के लिए उपयोग करने की स्थिति। काम करता है अगर आप क्रमशः वस्तुओं को सम्मिलित करते हैं, उदाहरण के लिए।

यदि संकेत सही नहीं है, तो इसका कोई प्रभाव नहीं पड़ता है और आपको एक गैर-संकेतित डालने मिलता है।

Answer 3

आप फ़ाइल bits/stl_tree.h चेक करते हैं (जीएनयू libstdC++ में), आप मिल जाएगा एक संकेत तर्क के साथ _M_insert_unique सदस्य समारोह एक नोड संकेत के बाईं ओर सही करने के लिए एक नोड बुला लिए चूक लग रहा है कि, तो, तो सामान्य सम्मिलित दिनचर्या।

यह कम से कम एक बार (यदि सेट खाली नहीं है) और अधिकतर तीन बार key_compare पर कॉल करता है। एक नोड से अगले या पिछले तक जाकर एक सूचक का पालन करना है (आईआईआरसी) std::set और दोस्तों threaded trees हैं।

तो, खराब संकेत कितना बुरा है तुलनात्मक दिनचर्या पर निर्भर करता है, और क्या आपके std::set के आवंटक को स्मृति में बंद नोड्स पैक करता है या नहीं।

Answer 4

यदि आप इसका उपयोग करने से पहले एक बार सेट सेट कर रहे हैं, तो आप इसके बजाय वेक्टर का उपयोग कर सकते हैं और इसका उपयोग करने से पहले इसे सॉर्ट कर सकते हैं। आप तेजी से लुकअप के लिए क्रमबद्ध वेक्टर पर binary_search, lower_bound, upper_bound, और equal_range एल्गोरिदम का उपयोग कर सकते हैं। सॉर्ट किए गए वैक्टरों को जोड़ने के लिए आप merge या inplace_merge का उपयोग भी कर सकते हैं, और set_difference, set_intersection, और set_union अन्य सामान्य सेट ऑपरेशंस करने के लिए भी उपयोग कर सकते हैं।