std :: प्रतिलिपि निर्माण

Question

बिना प्रकार मान लें कि मैं वस्तुओं के लिए जहां का एक वेक्टर है:

• प्रतिलिपि निर्माण और कार्य महंगा
• डिफ़ॉल्ट निर्माण और दो वस्तुओं की अदला-बदली सस्ता है।

यह बड़े डेटा के संदर्भ वाले वस्तुओं के लिए काफी मानक लगता है - उदाहरण के लिए वेक्टरों का एक वेक्टर।

प्रश्न: वहाँ मानक लाइब्रेरी से यह वेक्टर std::sort का उपयोग कर, या कुछ अन्य छँटाई दिनचर्या सॉर्ट करने के लिए एक तरह से इतना है कि कोई नकल जगह लेता है, लेकिन स्वैप के बजाय प्रयोग किया जाता है है? मैं एक प्री -c++0x समाधान (कोई चाल semantics) के लिए देख रहा हूँ।

std::swap ओवरलोडिंग पहले प्राकृतिक प्रयास की तरह लग रहा था, और यह थोड़ा सा मदद करता है, लेकिन यह प्रतिलिपि के केवल एक छोटे से हिस्से से छुटकारा पाता है।

नोट: जीसीसी व्यवहार

का उदाहरण 100 81 64 49 36 25 16 9 4 1 0 1 4 9 16 25 36 49 64 81, मेरे जीसीसी std :: प्रकार 19 प्रति कंस्ट्रक्टर्स, 92 कार्य, और 6 स्वैप में कॉल क्रमबद्ध करने के लिए।

Answer 1

// C++03 solution won't work with arrays and some other custom containers. 
// Mostly drop this block: 
#include <type_traits> 
#include <vector> 
#include <algorithm> 
#include <iostream> 
namespace aux { 
    using std::begin; using std::end; 
    template<typename C> auto adl_begin(C&& c)->decltype(begin(c)); 
    template<typename C> auto adl_end(C&& c)->decltype(end(c)); 

    template<typename C> 
    struct container_traits: 
    std::iterator_traits< typename std::decay< decltype(aux::adl_begin(*(C*)nullptr)) >::type > 
    { 
    typedef typename std::decay< decltype(adl_begin(*(C*)nullptr)) >::type iterator_type; 
    }; 
} 

// C++03 solution won't work with arrays. Inside std::less, use Container::value_type: 
template< 
    typename Container, 
    typename Comparison = std::less< 
    typename aux::container_traits<Container>::value_type 
    > 
> 
void indirect_sort_then_swap(Container& c, Comparison&& comp = Comparison()) { 
    typedef aux::container_traits<Container> con_traits; 
    typedef typename con_traits::value_type value_type; 
    typedef typename con_traits::iterator_type iterator_type; 
    std::vector<iterator_type> indirect; 
    { 
    // C++03 solution can use c.begin(), but will not work with arrays: 
    using std::begin; using std::end; 
    auto begin_ = begin(c); 
    auto end_ = end(c); 
    for(auto it = begin_; it != end_; ++it) { 
     indirect.push_back(it); 
    } 
    } 
    // In C++03, write a functor class that does this: 
    auto indirect_sort = [&comp](iterator_type const& left, iterator_type const& right)->bool { 
    return comp(*left, *right); 
    }; 
    std::sort(indirect.begin(), indirect.end(), indirect_sort); 
    // at this point, indirect is a vector with the contents of c sorted by iterator: 
    // a hard part remains, namely to take this information and sort c with minimal swaps 
    // That is hard. I will instead create an easy approach, namely create an empty 
    // copy of c full of empty elements, and directly swap the correct entry of c into 
    // each slot, then I swap c with its copy. 
    // the downside is that my container now needs to support push_back. Oh well. 
    Container c2; 
    // C++03 solution cannot use auto here. But we know the type of indirect: 
    for (auto it = indirect.begin(); it != indirect.end(); ++it) { 
    // See previous comment 
    auto itv = *it; 
    c2.push_back(value_type()); 
    using std::swap; 
    swap(*itv, c2.back()); 
    } 
    // by this point, the contents of c have been swap-moved to c2 
    // swap them back: 
    { 
    using std::swap; 
    swap(c, c2); 
    } 
} 

int main() { 
    std::vector<int> foo; 
    foo.push_back(7); 
    foo.push_back(3); 
    indirect_sort_then_swap(foo); 
    for (auto i:foo) { 
     std::cout << i << "\n"; 
    } 
} 

उपरोक्त की तरह कुछ एक व्यावहारिक दृष्टिकोण है। मैंने सी ++ 11 में इसका एक गुच्छा लिखा, लेकिन अतिरिक्त सी ++ 11 सामान को बाहर निकालने के तरीके पर टिप्पणियां शामिल कीं (यह वास्तव में कुछ मामलों में कोड को सरल बनाती है, लेकिन कुछ कंटेनर जैसी चीज़ों को संभालने की क्षमता को हटा देती है)।

मूल विचार के vector को अपने मूल कंटेनर में सॉर्ट करना है। फिर हम एक अस्थायी कंटेनर बनाते हैं, सामान value_type एस, swap उन छोटे छोटे value_type एस मूल कंटेनर से सही डेटा के साथ (vector द्वारा क्रमबद्ध एस द्वारा निर्धारित) के साथ, swap हमारे मूल कंटेनर के लिए यह अस्थायी कंटेनर बनाते हैं।

बहुत सारे आवंटन हैं, लेकिन उम्मीद है कि सस्ते सामान की उम्मीद है।

इसके लिए काम करने के लिए, जो डेटा आप सॉर्ट कर रहे हैं वह छोटी रचनात्मक होनी चाहिए। इसके लिए कुशल होने के लिए, जिस डेटा के साथ आप काम कर रहे हैं, वह छोटे से सस्ता होने की आवश्यकता है, और swap को कुशल होने की आवश्यकता है।

मैंने इसे एडीएल के अनुकूल बनाने के रूप में बनाने का प्रयास किया, क्योंकि मुझे लगता है कि यह अच्छा अभ्यास है।

Answer 2

Heap-sort एक स्वैप-केवल क्रम है जो स्थिर नहीं है (सॉर्टिंग के दौरान बराबर तत्वों का क्रम बदल सकता है)। मैंने other similar question का उत्तर दिया जहां मैंने स्वयं हीप-सॉर्ट (PasteBin) लागू किया, लेकिन आपको वहां बेहतर और अधिक लचीला कार्यान्वयन मिल सकता है।

निष्कर्ष यह था कि जी ++ के std::sort ने 20 तत्वों के लिए 35 प्रतिलिपि, 1 9 असाइनमेंट, 10 स्वैप और 35 डिलीट (99 ऑपरेशंस पूरी तरह से) का इस्तेमाल किया था, मेरे ढेर प्रकार 62 स्वैप का इस्तेमाल करते थे और कुछ भी नहीं।

मैं बस एक स्थिर प्रकार में घुस गया जो केवल here on stackoverflow स्वैप का उपयोग करता है। मैंने इसे गहराई से नहीं देखा।