std :: तरह हमेशा std :: स्वैप

Question

निम्नलिखित कोड पर विचार करें फोन नहीं करता है:

#include <algorithm> 
#include <iostream> 
#include <vector> 

namespace my_space 
{ 

struct A 
{ 
    double a; 
    double* b; 
    bool operator<(const A& rhs) const 
    { 
     return this->a < rhs.a; 
    } 
}; 

void swap(A& lhs, A& rhs) 
{ 
    std::cerr << "My swap.\n"; 
    std::swap(lhs.a, rhs.a); 
    std::swap(lhs.b, rhs.b); 
} 

} 

int main() 
{ 
    const int n = 20; 
    std::vector<my_space::A> vec(n); 
    for (int i = 0; i < n; ++i) { 
     vec[i].a = -i; 
    } 

    for (int i = 0; i < n; ++i) { 
     std::cerr << vec[i].a << " "; 
    } 
    std::cerr << "\n"; 
    std::sort(vec.begin(), vec.end()); 
    for (int i = 0; i < n; ++i) { 
     std::cerr << vec[i].a << " "; 
    } 
    std::cerr << "\n"; 
} 

अगर मैं n=20 का उपयोग, कस्टम स्वैप समारोह कहा जाता है और सरणी सॉर्ट हो जाता है। लेकिन अगर मैं n=4 का उपयोग करता हूं, तो सरणी को सही ढंग से क्रमबद्ध किया जाता है, लेकिन कस्टम स्वैप फ़ंक्शन नहीं कहा जाता है। ऐसा क्यों है? क्या होगा यदि मेरी वस्तुओं की प्रतिलिपि बनाना वास्तव में महंगा है?

इस परीक्षण के लिए, मैं जीसीसी 4.5.3 का उपयोग कर रहा था।

Answer 1

छोटे श्रेणियों के लिए, जीसीसी के stdlibc में std::sort कार्यान्वयन ++ (और अन्य मानक पुस्तकालय कार्यान्वयन) प्रदर्शन के कारणों के लिए प्रविष्टि प्रकार के फिर से होता है (यह सबसे तेज़ है छोटी सी सीमाओं पर quicksort/introsort)।

जीसीसी का सम्मिलन क्रम कार्यान्वयन बदले में std::swap के माध्यम से स्वैप नहीं करता है - इसके बजाय, यह अलग-अलग स्वैपिंग के बजाय, मूल्यों की पूरी श्रृंखला को एक साथ चलाता है, इस प्रकार संभावित रूप से प्रदर्शन को बचाता है। प्रासंगिक हिस्सा यहाँ है (bits/stl_algo.h:2187, जीसीसी 4.7.2):

typename iterator_traits<_RandomAccessIterator>::value_type 
    __val = _GLIBCXX_MOVE(*__i); 
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 
*__first = _GLIBCXX_MOVE(__val); 

_GLIBCXX_MOVEstd::move से सी ++ 11 के रूप में ही है और _GLIBCXX_MOVE_BACKWARD3std::move_backward है - हालांकि, यह केवल मामला है अगर __GXX_EXPERIMENTAL_CXX0X__ परिभाषित किया गया है; यदि नहीं, तो इन परिचालनों को स्थानांतरित करने की बजाए प्रतिलिपि बनाना है!

यह क्या करता है एक अस्थायी भंडारण के लिए वर्तमान स्थिति (__i) में मूल्य ले जाते हैं, तो __first से __i एक अप करने के लिए सभी पिछले मूल्यों ले जाते हैं, और उसके बाद __first पर अस्थायी मूल्य फिर से सम्मिलित है। तो यह करता है एक ऑपरेशन में n स्वैप बजाय एक अस्थायी स्थान पर n मूल्यों स्थानांतरित करने के लिए:,

first   i 
+---+---+---+---+---+---+ 
| b | c | d | e | a | f | 
+---+---+---+---+---+---+ 
        | 
    <---------------+ 


    first   i 
+---+---+---+---+---+---+ 
| --> b-> c-> d-> e-> f | 
+---+---+---+---+---+---+ 


    first   i 
+---+---+---+---+---+---+ 
| a | b | c | d | e | f | 
+---+---+---+---+---+---+ 
^

Answer 2

मैंने कोड को और अधिक वर्बोज़ में संशोधित किया। 20 तत्वों के लिए सॉर्टिंग कई स्वैप का उपयोग करता है, असाइनमेंट एंड कॉपी का उपयोग करता है। 4 तत्वों के लिए छंटनी केवल असाइनमेंट और कॉपी का उपयोग करती है। चश्मे के बारे में नहीं जानते, लेकिन यह कुछ हो सकता है।

#include <algorithm> 
#include <iostream> 
#include <vector> 

namespace my_space 
{ 

struct A 
{ 
    double a; 
    double* b; 
    A() 
     : a(0) 
     , b(NULL) 
    { } 
    A(const A &rhs) 
     : a(rhs.a) 
     , b(rhs.b) 
    { 
     std::cerr << "copy" << std::endl; 
    } 
    A& operator=(A const &rhs) 
    { 
     if(this==&rhs) 
       return *this; 
     a = rhs.a; 
     b = rhs.b; 
     std::cerr << "=" << std::endl; 
     return *this; 
    } 
    bool operator<(const A& rhs) const 
    { 
     return this->a < rhs.a; 
    } 
}; 

void swap(A& lhs, A& rhs) 
{ 
    std::cerr << "My swap.\n"; 
    std::swap(lhs.a, rhs.a); 
    std::swap(lhs.b, rhs.b); 
} 

} // namespace my_space 

int main() 
{ 
    const int n = 20; 

     std::cerr << "=== TEST CASE: n = " << n << std::endl; 
    std::cerr << "=== FILL ===" << std::endl; 
    std::vector<my_space::A> vec(n); 
    for (int i = 0; i < n; ++i) { 
     vec[i].a = -i; 
    } 

    std::cerr << "=== PRINT ===" << std::endl; 
    for (int i = 0; i < n; ++i) { 
     std::cerr << vec[i].a << " "; 
    } 
    std::cerr << "\n"; 

    std::cerr << "=== SORT ===" << std::endl; 
    std::sort(vec.begin(), vec.end()); 

    std::cerr << "=== PRINT ===" << std::endl; 
    for (int i = 0; i < n; ++i) { 
     std::cerr << vec[i].a << " "; 
    } 
    std::cerr << "\n"; 
} 

आउटपुट

=== TEST CASE: n = 4 
=== FILL === 
copy 
copy 
copy 
copy 
=== PRINT === 
0 -1 -2 -3 
=== SORT === 
copy 
= 
= 
copy 
= 
= 
= 
copy 
= 
= 
= 
= 
=== PRINT === 
-3 -2 -1 0 

और

=== TEST CASE: n = 20 
=== FILL === 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
=== PRINT === 
0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 
=== SORT === 
copy 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
= 
copy 
= 
copy 
= 
copy 
= 
=== PRINT === 
-19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 

Answer 3

प्रकार के आधार पर (गमागमन एक कदम-असाइनमेंट की तुलना में अधिक महंगा हो सकता है C++ 98 एक साधारण असाइनमेंट)। मानक पुस्तकालय में इन मामलों का पता लगाने का कोई तरीका नहीं है। कम से कम सी ++ 11 में समाधान स्पष्ट है: सभी वर्गों के लिए एक चाल-असाइनमेंट ऑपरेटर लागू करें जहां आप स्वैप लागू करते हैं।