真心求教iterator of iterator

最近刷G面经的时候经常看到一个高频题是iterator of iterator，
原题大概就是说有一个list的迭代器,写一个wrapper iterator可以遍历那个list中的所有迭代器？

想请问下各位大大能不能给一下思路？比如需要具体实现一些什么功能？ 就是相当于一堆指针的指针吗？
另外想问问地里有没有人总结了G家onsite高频题的帖子，十分急需一个link  谢谢大家了

这种题一般都是先给定一个接口，通常是类似于Java中的Iterator<E>接口。所以你就算主语言是C++，做这题最好也先切换到Java思维。

interface Iterator<E> {
  public E next();
  public boolean hasNext();
}

然后这个题里给的输入很可能是这个样子的
Iterator<Iterator<Integer> > iterOfIter;
也就是说，我现在有N个容器，比如List，然后对应地有N个List.Iterator。再把这N个Iterator放在一个大容器里，iterOfIter就是这个大容器的总的Iterator。

那么你要写的是这样一个类：
1. 实现Iterator<E>接口，
2. 包装iterOfIter，
3. 功能是将iterOfIter中所有iterator的内容顺次取出（展平），也就是：

class FlatteneddIterator<E> implements Iterator<E> {
   // 包装一个Iterator<Iterator<Integer> > iterOfIter;
   // 实现构造函数FlattenedIterator()
   // 实现hasNext();
   // 实现next();
}

特别要注意的坑是：
1. iterOfIter可以是null
2. iterOfIter中的iter可以是空（尤其是这一条，此题区分度应该主要在这一点上）。

写完可以和面试官提一下，这本质上是用到了设计模式中的Decorator Pattern。

你先实际写写看。完整代码不会很长，但是思维要严密些。

stellari 发表于 2016-4-2 23:38
我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话，还是上来就给ite ...

我写了个zigzag用iterator的解法，感觉除了需要一个STL存iterator，还是需要把input的container都存一下的，
比如我用的是

1. queue<vector<int>::iterator> zigIt

复制代码

和

1. queue<vector<int>> numbers

复制代码

，
剩下的思路跟我之前说的那个queue的差不多，
判定hasNext需要把queue里等于当前container end()的都pop掉，return是否不为空，
next函数就取zigIt里front指向的数据，然后在numbers里把这个数删掉，再把这个vector移到numbers的队尾，最后再处理下zigIt。这个的话我感觉跟LRU cache思路有点接近

1. 
   
2.         queue<vector<int>::iterator> zit;
   
3.         queue<vector<int>> number;
   
4.         zigzagIter(vector<vector<int>>& nums) {
   
5.                
   
6.                 for (vector<int> n : nums){
   
7.                         number.push(n);
   
8.                         zit.push(number.back().begin());
   
9.                 }
   
10.         }
    
11.         bool hasNext(){
    
12.                 if (zit.empty())return false;
    
13.                 while (!zit.empty() && zit.front() == number.front().end()){
    
14.                         zit.pop();
    
15.                         number.pop();
    
16.                 }
    
17.                 if (zit.empty())return false;
    
18.                 else return true;
    
19.         }
    
20.         int next(){
    
21.                 int res = *zit.front();
    
22.                 number.front().erase(zit.front());
    
23.                 zit.pop();
    
24.                 number.push(number.front());
    
25.                 number.pop();
    
26.                 zit.push(number.back().begin());
    
27.                
    
28.                 return res;
    
29.         }

复制代码

所以我感觉复制vector也是难以避免吧（当然C++里一般是用vector，所以类型确实是绑定的，JAVA会有更general点的container可以包含各种object）
因为一方面iterator需要指向实际存在的成员，不然都会变成null吧
然后每个iterator要判定他是不是到当前container的end()的指针时候要是不知道container的ref貌似没办法判定。不过这里应该还是会有更好的办法，我这块知识有限，要是有知道的大神也麻烦给点思路。

stellari 发表于 2016-4-2 06:46
不客气。代码写出来的话，交流一下？我很想看看别人是怎么写的。

你是说zigzag iter的代码吗？
我用c++写的
目前试了两种，但其实都还没真正用到iterator，正准备试试的
第一种是用一个queue保存所有list， 构造函数里初始化queue
next函数返回queue的第一个list的第一个元素，然后把元素从list里删掉，再把list移到queue尾部。
hasNext直接返回queue是否不为空就行了。
这种就是代码比较少，几行就搞定了

然后第二种我直接贴上来吧，

1. class zzIter{
   
2. public:
   
3.         int x, y;
   
4.         bool getfirst;
   
5.         unordered_set<int> row;
   
6.         vector<vector<int>> nums;
   
7. 
   
8.         zzIter(vector<vector<int>>& n){
   
9.                 nums = n;
   
10.                 int len = nums.size();
    
11.                 for (int i = 0; i < len; i++)row.insert(i);
    
12.                 x =y= 0;
    
13.                 getfirst=false;
    
14.         }
    
15.         bool hasNext(){
    
16.                 return !row.empty();
    
17.         }
    
18.         int next(){
    
19.                 if (!getfirst){
    
20.                         getfirst = true;
    
21.                         return nums[x][y];
    
22.                 }
    
23.                 x++;
    
24.                 modify();
    
25.                 if (y == nums[x].size()-1)row.erase(x);
    
26.                 return nums[x][y];
    
27.         }
    
28.         void modify(){
    
29.                 while (row.find(x)==row.end()&&x<nums.size()){
    
30.                         x++;                       
    
31.                 }
    
32.                 if (x == nums.size()){
    
33.                         x = 0;
    
34.                         y++;
    
35.                         modify();
    
36.                 }
    
37.         }
    
38. };

复制代码

这个就是要调整当前元素的position，多了一个modify的函数。

另外正准备写个用iterator实现的，按理应该效率会比上面两种高。

stellari 发表于 2016-4-1 21:54
这种题一般都是先给定一个接口，通常是类似于Java中的Iterator接口。所以你就算主语言是C++，做这题最好也 ...

太感谢你了， 说的特别详细。

看了一下你的描述大概能了解意思了， 是不是有点类似于leetcode里的一个zigzag iterator的题目？
总的来说就是design一个iterator结构， 它能通过内部多个容器的iterator然后依某种顺序访问每个元素，然后总的iterator可以为null， 每一个容器中的iterator也可以是null。是这个意思不？

然后有个小问题就是你说的第二个坑是不是意思是比如一个list遍历完了那么这个list的iter就只会返回null了？

mymax2009 发表于 2016-4-2 01:48
太感谢你了， 说的特别详细。

看了一下你的描述大概能了解意思了， 是不是有点类似于leetcode里的一个 ...

是的，就是类似于ZigzagIterator。我面G的时候就是挂在Zigzag这道题上，所以特别怨念。

我列的坑1和2合起来的意思是说，每个'iterator对应的容器都可能处于三种状态：null，空（0个元素），非空（1个以上元素）。你的代码必须能够合理地处理这三种情况才行。

stellari 发表于 2016-4-2 02:41
是的，就是类似于ZigzagIterator。我面G的时候就是挂在Zigzag这道题上，所以特别怨念。

我列的坑1和2 ...

明白意思了，清晰又详细，十分感谢！

mymax2009 发表于 2016-4-2 04:02
明白意思了，清晰又详细，十分感谢！

不客气。代码写出来的话，交流一下？我很想看看别人是怎么写的。

stellari 发表于 2016-4-2 06:46
不客气。代码写出来的话，交流一下？我很想看看别人是怎么写的。

忘了说，第一个用queue的next方法里稍做个判断，如果list已经空了就不添加到queue尾了

mymax2009 发表于 2016-4-2 13:19
你是说zigzag iter的代码吗？
我用c++写的
目前试了两种，但其实都还没真正用到iterator，正准备试试的 ...

我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话，还是上来就给iterator实现的好。现在的这种写法是和vector类型绑定死的，而且出现了vector复制，效率不乐观。这两点很容易被面试官抓住攻击。

期待C++写法。