Birkaç sıralı liste üzerinde bir yineleyici nasıl yapılır?

Question

Tamam, bu benim aldığım bir röportaj sorusudur ve o sırada sadece vasatlık yapmıştır. En uygun çözümün ne olduğunu ve nasıl en iyi şekilde uygulandığını merak ediyorum.

Birden çok sıralı listelenirsiniz, 'u, tüm bu listelerden en küçükten en büyük öğeye kadar yinelememizi sağlayan bir yapı oluşturursunuz.

Örnek:

Güncelleme

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


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

: SO sohbet # c-soru-cevap ve özellikle @Nican yardım biraz da

, bu geminin ele verdik bir şekilde uçmak için. Çalışma kodumu diğer çözümlere de izin vermek için bir cevap olarak gönderdim.

Aşağıda verdiğim cevap hala dağınık ve özellikle de uygulanmadım == ve! = Doğru. Onlara hala yardıma ihtiyacım var. Online temiz ve minimalist özel yineleyici uygulamalarını bulma Bu soruya

için

Gerekçe bu yaygın değildir. Ve bu sorunun diğerlerinin tekrarlayıcıları ve en iyi uygulamaları anlamalarını geliştirmek için iyi bir başlangıç ​​noktası olarak kullanılabileceğine inanıyorum.

Answer 1

Bu benim çalıştığını noktaya kısmen çözüm uyguladık tam bir cevap

değildir. Bu, bir input_iterator gereksinimine sahip satırlarda eksiksiz veya doğru bir uygulama değildir. Bu, noktayı gösterir ve geriye kalan ayak işi, çağrıyı hisseden kişi olur.

-

dün notlarımı ve çabaları tekrar bunu getirdi. Nican'dan gerçekten güzel bir yardım aldım.

Listelerimi yapmamın içinde tutmak için bir yığın kullanıyorum. (Hangi priority_queue yeniden icat ettiğim geçerli eleştiriye sahip).

• Kopya yapıcı
• Sonrası düzeltme ++ operatörü
• Uygun == ve = uygulama, sadece karşılaştırıyorum boyutu:! Hala diğer şeyler arasında, Burada eksik birkaç şey vardır.
• Bu kolayca bir forward_iterator olabilir.

Yineleyici bilgilerimi oluşturduğum noktaya geldim. Ve bu, bu sefer etrafta kalacağım kadar uzak.

#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

Sana ForwardIterator yerine InputIterator olabilir, böylece SortedListsIter::iterator yerine referans yerine, tüm öğelerin bir kopyasını içermelidir düşünüyorum.Ayrıca

iki yığın elemanlarının sırayla farklı olabilir

( iterator::iterator(std::vector<SortedListIterItem<Iter> > _items = {}) : m_items(_items){}; gibi varsayılan inşa yineleyici olabilir) uç yineleyici sarkan referans önlemek, bu eşitlik

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

C belirlemek için std::is_permutation kullanımı ++ 11 alternatif (mesafeyi kontrol eder 4 yineleyici sürümü mevcut değildir):

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()); } 

Öğe eşitlik basittir:

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