如何在多个排序列表上进行迭代？

这不是一个完整的答案

我已经实现了部分解决方案，以使其起作用。这不是符合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;
}