कई क्रमबद्ध सूचियों पर एक इटरेटर कैसे बनाएं?

Question

ठीक है, तो यह एक साक्षात्कार प्रश्न है जो मुझे मिला, और उस समय केवल मध्यस्थ प्रदर्शन किया। मैं सोच रहा हूं कि इष्टतम समाधान क्या है और यह कैसे सर्वोत्तम रूप से कार्यान्वित किया जाता है।

आपको कई क्रमबद्ध सूचियां दी गई हैं, कुछ बनाएं जो हमें इन सभी सूचियों को सबसे छोटे से सबसे बड़े तत्व में पुन: सक्रिय करने की अनुमति देती है।

उदाहरण:

{ -2, 5, 10} 
{ 2, 9, 11} 
{ -5, 9} 


-> -5, -2, 2, 5, 9, 9, 10, 11 

अद्यतन:

से # सी सवाल और जवाब और विशेष रूप से @Nican अतः चैट मदद का एक सा के साथ

, मैं इस जहाज मिल गया है किसी भी तरह उड़ने के लिए। मैंने अपने समाधान कोड को अन्य समाधानों की अनुमति देने के उत्तर के रूप में भी पोस्ट किया है।

मैंने जो पोस्ट नीचे पोस्ट किया है वह अभी भी गन्दा है, और विशेष रूप से मैंने == और! = सही ढंग से लागू नहीं किया है। मुझे अभी भी उन पर मदद चाहिए। इस सवाल का

स्वच्छ और minimalistic कस्टम इटरेटर कार्यान्वयन ऑनलाइन ढूँढना के लिए

औचित्य है कि आम नहीं है। और मेरा मानना ​​है कि यह प्रश्न दूसरों के लिए इटेटर और सर्वोत्तम प्रथाओं की समझ को बढ़ाने के लिए एक अच्छा प्रारंभिक बिंदु के रूप में कार्य कर सकता है।

Answer 1

यह एक पूरा जवाब

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

-

मैं सिर्फ यह फिर से मेरे नोट और प्रयासों से कल उठाया। मुझे निकन से कुछ वाकई अच्छी मदद मिली है।

मैं अपनी संरचना के अंदर सूचियों को रखने के लिए एक ढेर का उपयोग कर रहा हूं। (जिसमें वैध आलोचना है कि मैं प्राथमिकता_क्यू को पुनर्निर्मित कर रहा हूं)।

• कॉपी निर्माता
• के बाद ठीक ++ ऑपरेटर
• उचित == और = कार्यान्वयन, मैं सिर्फ तुलना कर रहा हूं आकार: कई चीज़ें हैं जिन्हें अभी भी यहाँ याद आ रही, अन्य बातों के अलावा हैं।
• यह आसानी से आगे_इटरेटर हो सकता है।

मुझे उस बिंदु पर पहुंचा जहां मैंने इटरेटर की अपनी समझ बनाई है। और यह वह जगह है जहां तक ​​मैं इसे इस बार ले जा रहा हूं।

#include <algorithm> 
#include <forward_list> 
#include <iostream> 
#include <iterator> 
#include <string> 
#include <vector> 

template <typename Iter> 
struct SortedListIterItem { 
    Iter it_beg; 
    Iter it_end; 
    /* Used by the heap to sort ascending */ 
    bool operator<(const SortedListIterItem<Iter>& other) { 
    return *it_beg > *other.it_beg; 
    } 
    bool operator==(const SortedListIterItem<Iter>& other) { 
    return it_beg == other.it_begin && it_end == *other.it_beg; 
    } 
    SortedListIterItem<Iter>(Iter _begin, Iter _end) 
     : it_beg(_begin), it_end(_end){}; 
}; 

template <typename Iter> 
class SortedListsIter { 
    // member typedefs provided through inheriting from std::iterator 
    class iterator { 
    std::vector<SortedListIterItem<Iter> > m_items; 

    public: 
    iterator(std::vector<SortedListIterItem<Iter> > _items = {}) 
     : m_items(_items){}; 
    iterator& operator++() { 
     std::pop_heap(m_items.begin(), m_items.end()); 
     SortedListIterItem<Iter>& largest = m_items.back(); 

     if (++largest.it_beg == largest.it_end) { 
     m_items.pop_back(); 
     } else { 
     std::push_heap(m_items.begin(), m_items.end()); 
     } 
     return *this; 
    } 
    // iterator traits 
    using value_type = typename Iter::value_type; 
    using pointer = typename Iter::pointer; 
    using reference = typename Iter::reference; 
    using iterator_category = std::input_iterator_tag; 
    /** A simplified comparator, which is not a correct implementation. 
    * While it does work for regular for loops. */ 
    bool operator!=(iterator other) { 
     return (m_items.size() != other.m_items.size()); 
    } 
    value_type operator*() const { 
     return *(m_items.front().it_beg); 
    }; 
    }; 
    std::vector<SortedListIterItem<Iter> > m_items; 

public: 
    void add_list(Iter it_begin, Iter it_end) { 
    if (it_begin != it_end) { 
     m_items.push_back(SortedListIterItem<Iter>(it_begin, it_end)); 
     std::push_heap(m_items.begin(), m_items.end()); 
    } 
    // Ignore empty lists. 
    } 
    iterator begin() { return iterator(m_items); }; 
    iterator end() { 
    std::vector<SortedListIterItem<Iter> > _items; 
    return iterator(_items); 
    }; 
}; 

int main(int argc, char** argv) { 
    std::forward_list<std::string> animals = {"Cat", "Dog", "Horse"}; 
    std::forward_list<std::string> fish = {"Dolphin", "Mermaid", "Shark"}; 
    std::forward_list<std::string> birds = {"Crow", "Duck", "Eagle"}; 
    SortedListsIter<std::forward_list<std::string>::iterator> my_string_iter; 
    my_string_iter.add_list(fish.begin(), fish.end()); 
    my_string_iter.add_list(animals.begin(), animals.end()); 
    my_string_iter.add_list(birds.begin(), birds.end()); 

    for (auto i : my_string_iter) { 
    std::cout << " " << i << ","; 
    } 
    std::cout << std::endl; 
    for (auto i : my_string_iter) { 
    std::cout << " " << i << ","; 
    } 
    std::cout << std::endl; 

    std::vector<int> l4 = {1, 2, 99}; 
    std::vector<int> l5 = {-11, -4, 3}; 
    std::vector<int> l6 = {-5, 1}; 

    SortedListsIter<std::vector<int>::iterator> my_iter2; 
    my_iter2.add_list(l4.begin(), l4.end()); 
    my_iter2.add_list(l5.begin(), l5.end()); 
    my_iter2.add_list(l6.begin(), l6.end()); 

    for (auto i : my_iter2) { 
    std::cout << " " << i << ","; 
    } 
    std::cout << std::endl; 

    return 0; 
} 

Answer 2

मुझे लगता है कि SortedListsIter::iterator बल्कि संदर्भ से सभी वस्तुओं की एक प्रति होनी चाहिए, ताकि आप ForwardIterator बजाय InputIterator हो सकता है।तुम भी झूलने (iterator::iterator(std::vector<SortedListIterItem<Iter> > _items = {}) : m_items(_items){}; के रूप में जो एक डिफ़ॉल्ट का निर्माण इटरेटर हो सकता है,) अंत इटरेटर में संदर्भ

दो ढेर तत्वों के क्रम में अलग हो सकता है से बचने, तो हम std::is_permutation का उपयोग समानता

bool SortedListsIter::iterator::operator==(iterator other) 
{ return std::is_permutation(m_items.begin(), m_items.end(), other.m_items.begin(), other.m_items.end()); } 

निर्धारित करने के लिए

सी ++ 11 विकल्प (4 इटरेटर संस्करण है कि दूरी की जाँच करता है उपलब्ध नहीं है):

bool SortedListsIter::iterator::operator==(iterator other) 
{ return (std::distance(m_items.begin(), m_items.end()) == std::distance(other.m_items.begin(), other.m_items.end())) 
     && std::is_permutation(m_items.begin(), m_items.end(), other.m_items.begin()); } 

आइटम समानता सरल है:

bool SortedListIterItem::operator==(SortedListIterItem other) 
{ return (it_beg == other.it_beg) && (it_end == other.it_end); }