जब हम वेक्टर पर अद्वितीय फ़ंक्शन का उपयोग करते हैं तो स्थानांतरण कैसे काम करता है?

Question

तो, मैं वर्तमान में कुछ सी ++ सामानों पर पढ़ रहा हूं और मैं इस उदाहरण में cppreference पर आया और मुझे समझ में नहीं आया कि शिफ्ट कैसे काम करता है।

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

int main() 
{ 
    std::vector<int> v{1, 2, 2, 2, 3, 3, 2, 2, 1}; 
    std::vector<int>::iterator last; 

    last = std::unique(v.begin(), v.end()); // 1 2 3 2 1 3 2 2 1 
              //   ^
    for (std::vector<int>::iterator it = v.begin(); it != last; ++it) { 
     std::cout << *it << " "; 
    } 
    std::cout << "\n"; 
} 

मैं समझता हूँ कि जब हम अद्वितीय का उपयोग यह बातों पर बदलाव, फिर भी मैं यकीन नहीं कैसे हम अनुक्रम v.end() को last से हमें दिए गए प्राप्त कर रहा हूँ।

कागज पर अपने खुद के चित्र के माध्यम से मैं समझता हूँ कि हम कैसे अनुक्रम v.begin() से v.last() को v.last() से v.end() के रूप में उल्लेख किया प्राप्त है, लेकिन नहीं अनुक्रम।

यहां reference site है।

Answer 1

std:unique वास्तव में आवश्यकतानुसार शुरुआत की ओर तत्वों को बदल देता है। शिफ्ट ऐसा नहीं है जैसा आप सोच रहे हों। इसे कुछ प्रचारित एक-तत्व-पर-समय-चीज़ होने की आवश्यकता नहीं है। यह आवश्यक हो सकता है कि तत्व चाल-असाइन करने योग्य होना आवश्यक हो। तत्व-स्थानांतरित होने के बाद, चाल-असाइनमेंट की परिभाषा के अनुसार, इसकी पूर्व सामग्री अनिर्दिष्ट है। आपके मामले में, यह केवल "मान" रखता है, लेकिन यह निर्दिष्ट मान नहीं है।

संक्षेप में, आप जो देख रहे बचे हुए मूल्यों है, और उनमें से कुछगैर विशिष्ट हो सकता है।

निम्नलिखित आपके डेटा का उपयोग कर एक सरल डेमो है। प्रारंभ में हमारे पास दो स्लॉट स्थान हैं, आर, और डब्ल्यू। मैं एल्गोरिदम std::unique (मैं ईमानदारी से नहीं जानता) द्वारा उपयोग किए जाने वाले कोई वारंट नहीं करता है।

तुच्छ मामले (0 या 1-लंबाई अनुक्रम), जब एक मूल्य रखा यह डब्ल्यू ऊपर अगले स्लॉट में ले जाने से सौंपा है, और डब्ल्यू उन्नत है हो रहा है बाहर आवरण। भले ही इसे रखा गया हो या नहीं, आर हमेशा उन्नत है। पूरा होने पर, स्लॉट पिछले डब्ल्यू last है (यानी स्लॉट पर बाईं ओर पहला, जिनमें से कुछ अनिर्दिष्ट मान हो सकते हैं)।

अपने डेटा को देखते हुए, अनुक्रम कुछ इस तरह होगा:

1, 2, 2, 2, 3, 3, 2, 2, 1 - different, since the write target 
W R      is the same as the read-point, do nothing, 
          and advance both R and W 

1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
    W R      

1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
    W  R      

1, 2, 2, 2, 3, 3, 2, 2, 1 - different, move the 3 to the next write 
    W  R    point and advance both R and W 

1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
     W  R 

1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 2 to the next write 
     W   R   slot and advance both R and W 

1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
     W   R  

1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 1 to the next write 
     W    R slot and advance both R and W 

1, 2, 3, 2, 1, 3, 2, 2, 1 - read is at end-of-sequence 
      W    R 

इस बिंदु पर, पाठक समाप्त हो गया है। डब्ल्यू का पहला स्लॉट last है क्योंकि एल्गोरिदम जाता है (और वास्तव में end हो सकता है यदि मूल अनुक्रम में कोई डुप्लीकेट नहीं था)। मैं आपको यह निर्धारित करने की चुनौती देता हूं कि यह करने के बाद "अनिर्दिष्ट" राज्य में कौन से तत्व (3,2,2,1) हैं।

_{संकेत: क्या स्थानांतरित किया गया था? क्या छोड़ा गया था? क्या ओवरराइट किया गया था? इससे क्या फर्क पड़ता है? कुछ भी ले जाया गया और देखते हैं कि last से end के अनुक्रम में बचे हुए है कि पढ़ने के स्लॉट पर 0 लिखने की कोशिश करें।}

Answer 2

अद्वितीय कलन विधि बहुत सरल है। एक सीमा को देखते हुए, [पहले, अंतिम), तो आप दो iterators, In और Out लगातार डुप्लिकेट को निकालने के लिए उपयोग करें।In और Out प्रारंभ में अनुक्रम में पहले तत्व को असाइन किया गया है।

In = Out = First 

एल्गोरिथ्म तो इस प्रकार आगे बढ़ता है, बशर्ते कि सीमा रिक्त नहीं है।

while (++In != Last) 
{ 
    if (*In != *Out) 
    { 
     ++Out; 
     *Out = *In; 
    } 
} 

अब तक जारी रखें जब तक कि सीमा सीमा के अंत तक नहीं पहुंच जाती। फिर हम ++Out लौटते हैं।

Out मूल रूप से एक ही श्रेणी में अद्वितीय तत्वों को लिखने वाला आउटपुट इटरेटर है, इसलिए हम उपरोक्त एल्गोरिदम समाप्त होने के बाद अंतिम पुनरावर्तक को पुनः प्राप्त करके पुनर्प्राप्त कर सकते हैं।

अगर आप के मामले में इसके बारे में नहीं लगता स्थानांतरण लेकिन करने के लिए outputting (और अधिलेखन) है यह आसान है एक ही श्रेणी। एकमात्र मुश्किल हिस्सा यह है कि हम उसी श्रेणी को ओवरराइट कर रहे हैं जिसे हम पढ़ रहे हैं। एल्गोरिदम को समझना बहुत आसान है यदि आप अद्वितीय तत्वों को एक अलग अनुक्रम में वापस दबा रहे हैं और उस अनुक्रम को वापस कर रहे हैं। अब आप जो भी पढ़ रहे हैं उसे ओवरराइट करके अलग आउटपुट रेंज की आवश्यकता से बचने के लिए बस एक छोटा ऑप्टिमाइज़ेशन लागू करें।

यहां एक त्वरित कार्यान्वयन है जिसे मैंने चाबुक किया है जो विक्रेता संस्करणों से समझना थोड़ा आसान हो सकता है। यह इनपुट इटरेटर के रूप में पुन: उपयोग 'पहली' की तरह हमेशा की तरह फुलाना से कुछ से रहित है,, (! और == के बजाय) ऑपरेटर का उपयोग करता है! = आदि

template <class Iterator> 
Iterator my_unique(Iterator first, Iterator last) 
{ 
    if (first != last) 
    { 
     Iterator in = first; 
     Iterator out = first; 
     while (++in != last) 
     { 
      if (*in != *out) 
      { 
       ++out; 
       *out = *in; 
      } 
     } 
     return ++out; 
    } 
    return last; 
}