एक साहचर्य कंटेनर से बाहर ले जाने से तत्व

Question

बस मस्ती के लिए, मैं सबसे सरल छँटाई एल्गोरिथ्म कल्पना को लागू किया है मैं इस कदम अर्थ विज्ञान के साथ प्रदर्शन में सुधार करना चाहता था:

template<typename Iterator> 
void treesort(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type element_type; 

    // move data into the tree 
    std::multiset<element_type> tree(std::make_move_iterator(begin), 
            std::make_move_iterator(end)); 
    // move data out of the tree 
    std::move(tree.begin(), tree.end(), begin); 
} 

लेकिन यह एक महत्वपूर्ण तरीके से प्रदर्शन को प्रभावित नहीं किया है, भले ही मैं कर रहा हूँ सॉर्टिंग std::string एस।

तब मैं याद आया कि साहचर्य कंटेनरों बाहर से लगातार कर रहे हैं, कि, std::move है और std::copy यहाँ एक ही बात करना होगा :(वहाँ पेड़ से डेटा स्थानांतरित करने के लिए किसी भी अन्य रास्ता नहीं है?

Answer 1

std::set और std::multiset केवल अपने तत्वों को const पहुँच प्रदान करते हैं। इसका मतलब है आप सेट से कुछ नहीं ले जा सकते। आप आइटम बाहर स्थानांतरित कर सकता है (या बिल्कुल उन्हें संशोधित), तो आप आइटम के सॉर्ट क्रम बदलकर सेट तोड़ सकते थे। तो सी ++ 11 यह रोकता है।

तो अपने प्रयास 0 उपयोग करने के लिएएल्गोरिदम सिर्फ कॉपी कन्स्ट्रक्टर का आह्वान करेगा।

Answer 2

मेरा मानना ​​है कि आप multiset के लिए एक कस्टम आवंटक (3 टेम्पलेट तर्क) का उपयोग करने के लिए एक कस्टम आवंटक बना सकते हैं जो वास्तव में उपयोगकर्ता के कंटेनर पर destroy विधि में तत्वों को स्थानांतरित करता है। फिर सेट में प्रत्येक तत्व को मिटा दें और इसके विनाश के दौरान इसे अपनी स्ट्रिंग को मूल कंटेनर पर वापस ले जाना चाहिए। मुझे लगता है कि कस्टम संभाजक 2 चरण निर्माण के लिए की आवश्यकता होगी (पारित यह आपके treesort समारोह के लिए पारित एक सदस्य के रूप धारण करने के लिए इटरेटर शुरू करते हैं, लेकिन नहीं निर्माण के दौरान क्योंकि यह डिफ़ॉल्ट constructible हो गया है)।

स्पष्ट रूप से यह विचित्र होगा और सेट/मल्टीसेट में pop विधि नहीं होने के लिए मूर्खतापूर्ण कामकाज है। लेकिन यह संभव होना चाहिए।

Answer 3

मैं एक फ्रीकी संभाजक कि प्रत्येक चाल के निर्माण वस्तु के स्रोत को याद रखता है और स्वचालित रूप से विनाश पर वापस ले जाता है के डेव विचार पसंद है, मैं उस करने का कभी नहीं सोचा था!

लेकिन यहाँ अपने मूल प्रयास करने के लिए एक जवाब के करीब है:

template<typename Iterator> 
void treesort_mv(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type element_type; 

    // move the elements to tmp storage 
    std::vector<element_type> tmp(std::make_move_iterator(begin), 
            std::make_move_iterator(end)); 
    // fill the tree with sorted references 
    typedef std::reference_wrapper<element_type> element_ref; 
    std::multiset<element_ref, std::less<element_type>> tree(tmp.begin(), tmp.end()); 

    // move data out of the vector, in sorted order 
    std::move(tree.begin(), tree.end(), begin); 
} 

इस संदर्भ उपस्थित multiset सॉर्ट करता है, इसलिए वे पेड़ से स्थानांतरित करने की जरूरत नहीं है।

हालांकि, मूल सीमा में वापस जाने के दौरान, कदम असाइनमेंट स्वयं-असाइनमेंट के लिए जरूरी नहीं हैं, इसलिए मैंने उन्हें पहले वेक्टर में स्थानांतरित कर दिया, ताकि जब उन्हें मूल सीमा पर फिर से असाइन किया जाए तो वहां नहीं होगा स्वयं कार्य।

यह मार्जिनली मेरे परीक्षणों में आपके मूल संस्करण की तुलना में तेज़ है। यह शायद दक्षता खो देता है क्योंकि इसे वेक्टर के साथ-साथ सभी पेड़ नोड आवंटित करना पड़ता है। वह और तथ्य यह है कि मेरा कंपाइलर गाय स्ट्रिंग्स का उपयोग करता है, इसलिए किसी भी तरह की प्रतिलिपि बनाने से कहीं ज्यादा तेज नहीं है।