如何在多个排序列表上创建迭代器？

Question

好的,所以这是我得到的一个面试问题,当时只进行了平庸的讨论.我想知道最佳解决方案是什么以及如何最好地实施.

您将得到多个分类列表,构建的东西,使我们能够遍历所有这些从最小的名单最大的元素.

例:

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


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

更新:

在SO聊天#c-questions-and-answers和@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;
}