複数のソート済みリストのイテレータを作成するには？

Question

だから、これは私が得たインタビューの質問であり、当時は普通にしか実行されていませんでした。私は最適なソリューションが何であり、どのように実装されているのが最適かを考えています。

複数の並べ替えられたリストが与えられています。のいずれかという構造を使用して、最小の要素から最大の要素まですべてのリストを繰り返し処理できます。

例：

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


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

を更新：

特にSOのチャット＃のC-質問-と-答えと@Nicanからの助けのビットが、私はこの船を得ています何とか飛ぶ。私は、他のソリューションも可能にするための答えとして私の作業コードを掲載しました。

私が下に投稿した答えは、まだまだ厄介です。特に、==と！=を正しく実装していません。私はまだそれらの助けが必要です。オンラインクリーンでミニマルなカスタムイテレータの実装を見つけるこの質問

ため

正当化は、一般的ではありません。そして、私は、この質問がイテレータとベストプラクティスの理解を高めるための出発点として役立つと考えています。

Answer 1

これは、私はそれが動作するポイントに、部分的にソリューションを実装しました完全な答え

ではありません。これは、input_iteratorの要件を満たす行では完全ではなく、正しい実装ではありません。これはポイントを示しており、残っているレグワークは誰でもコールを感じるものです。

-

私はちょうど昨日、私のノートと努力から、再びこれを拾いました。私はニカンから本当に素晴らしい助けを得ました。

ヒープを使用してリストを自分の構造内に保持しています。 （これは私が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

私はあなたがForwardIterator代わりのInputIteratorできるようSortedListsIter::iteratorは、むしろ参照よりも、すべてのアイテムのコピーを含めるべきだと思います。あなたは、ヒープは、要素の順序が異なる場合があり、私たちは平等

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を決定するためにstd::is_permutationを使用する2つの

（ iterator::iterator(std::vector<SortedListIterItem<Iter> > _items = {}) : m_items(_items){};としてイテレータを構築デフォルトすることができます）エンドイテレータでダングリング参照をも避けます++ 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); }