Jak zrobić iterator na kilku posortowanych listach?

Question

OK, więc to jest pytanie, które dostałem, i tylko wtedy wykonywałem mierne wyniki. Zastanawiam się, jakie jest optymalne rozwiązanie i jak najlepiej je wdrożyć.

Dostaniesz wiele klasyfikowane list skonstruować coś która pozwala nam iteracyjne nad wszystkie te listy od najmniejszego do największego elementu.

Przykład:

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


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

Aktualizacja:

Przy odrobinie pomocy z tak chat # c-pytania-i-odpowiedzi i @Nican w szczególności stałam ten statek jakoś latać. Umieściłem mój działający kod jako odpowiedź, aby umożliwić również inne rozwiązania.

Odpowiedź, którą zamieściłem poniżej, jest nadal niepoprawna, aw szczególności nie zaimplementowałem poprawnie == i! =. Nadal potrzebuję pomocy w tych sprawach.

Uzasadnienie to pytanie

Znalezienie czyste i minimalistyczne niestandardowe implementacje iteratorów w Internecie nie jest tak powszechne. Wierzę, że to pytanie może stanowić dobry punkt wyjścia dla innych, aby lepiej zrozumieć iteratory i najlepsze praktyki.

Answer 1

To nie jest pełna odpowiedź

I zostały wdrożone częściowo rozwiązanie do tego stopnia, że ​​to działa. To nie jest kompletna, ani poprawna implementacja w liniach z wymaganiami input_iteratora. Ilustruje to punkt, a pozostała noga zależy od tego, kto czuje wezwanie.

-

właśnie odebrał to znowu z moich notatek i wysiłków wczoraj. Dostałem naprawdę dobrą pomoc od Nican.

Używam sterty do przechowywania list wewnątrz mojej struktury. (Które ma uzasadnioną krytykę, że wymyślam "priority_queue"). Jest kilka rzeczy, nadal brakuje tu między innymi:

• Konstruktor kopiujący
• post-fix ++ operator
• Odpowiednie == = rozmiar i realizacja, mam tylko porównanie!.
• To może łatwo być forward_iterator.

Doszedłem do punktu, w którym zbudowałem moje rozumienie iteratorów. I to jest tak daleko, jak to zamierzam wziąć tym razem.

#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

myślę że SortedListsIter::iterator powinien zawierać kopię wszystkich elementów, zamiast odniesienia, dzięki czemu można być ForwardIterator zamiast InputIterator.Również uniknąć dangling odniesienia w iterator end (co może być domyślną skonstruowane iterator, jak iterator::iterator(std::vector<SortedListIterItem<Iter> > _items = {}) : m_items(_items){};)

Dwa stosy mogą się różnić w kolejności elementów, więc używamy std::is_permutation do ustalenia równości

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++ 11 alternatywa (4 wersja iterator, który sprawdza, odległość nie jest dostępny):

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

równość Rzecz jest prosta:

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