如何在幾個已排序的列表上創建一個迭代器？

Question

好的，所以這是我得到的一個面試問題，並且只在當時表現平平。我想知道最佳解決方案是什麼以及如何最好地實施。

給你多個排序列表，構造東西，它允許我們遍歷從最小元素到最大元素的所有這些列表。

例子：

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


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

更新：

隨着從SO聊天＃C-問題 - 和 - 答案和@Nican特別是一些幫助，我收到了此船以某種方式飛行。我已經發布了我的工作代碼作爲允許其他解決方案的答案。

我在下面發佈的答案仍然很混亂，尤其是我沒有正確實現==和！=。我仍然需要幫助。

理由爲這個問題

尋找乾淨，簡約定製迭代器實現在線是並不常見。我相信這個問題可能成爲其他人加強對迭代器和最佳實踐的理解的良好起點。

Answer 1

這不是一個完整的答案

我已經實現了一個部分的解決方案，它的作品的地步。這與input_iterator的要求並不完全一致，也不正確。這說明了這一點，剩下的工作由誰來決定。

-

我只是從我的筆記和努力昨天就撿起一次。我從Nican得到了一些很好的幫助。

我正在使用堆來保存我的結構中的列表。 （其中有對我重新創建priority_queue的有效批評）。有幾件事情仍然缺少在這裏，除其他事項外：

• 複製構造
• 後修復++運算符
• 正確的==和=的實現，我只是比較大小！
• 這可能很容易成爲forward_iterator。

我已經到了建立我對迭代器的理解的地步。這就是我將要採取這一次。

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