# 251 Flatten 2D Vector

[
 [1,2],
 [3],
 [4,5,6]
]

把2D vector攤平，變成

[1,2,3,4,5,6]

由於剛修完Data structure，使用大量C++ STL，對C++的vector iterator還蠻熟悉的，

followup要我們只用C++ iterator或java iterator實作，我想應該是沒問題。

和一般iterator一樣，要實作constructor, next, hasNext三個function。

• idea:
  用兩個iterator，一個是在2d vector上跑，另一個在1d vector上跑，另外，當然需要把input 2d vector存起來。

• code(C++):
  實作時遇到的問題第一個問題是vec_itr++要在next還是hasNext，如果寫在hasNext，會跳過第一個元素，改寫到next就好了。
  第二個問題是第一行comment寫的edge case，在hasNext裡面處理掉了，上次寫iterator也是有卡在這種空input的edge case，下次要更注意！

  //edge case: [], [[],[],[]]
  class Vector2D {
  public:
      vector<vector<int>> vector2d;
      vector<vector<int>>::iterator vec2d_itr;
      vector<int>::iterator vec_itr;
  
      Vector2D(vector<vector<int>>& vec2d) {
          vector2d = vec2d;
          vec2d_itr = vector2d.begin();
          if(vec2d_itr != vector2d.end())
              vec_itr = (*vec2d_itr).begin();
      }
  
      int next() {
          int res = (*vec_itr);
          vec_itr++;
          return res;
      }
  
      bool hasNext() {
          if(vector2d.size() == 0)
              return false;
  
          //current subarray still has element left.
          if(vec_itr != (*vec2d_itr).end()){
              return true;
          }
  
          //move to next valid subarray
          vec2d_itr++;
          for(; vec2d_itr != vector2d.end(); vec2d_itr++){
              vec_itr = (*vec2d_itr).begin();
              if(vec_itr != (*vec2d_itr).end())
                  return true;
          }
  
          return false;
      }
  };
  
  /**
   * Your Vector2D object will be instantiated and called as such:
   * Vector2D i(vec2d);
   * while (i.hasNext()) cout << i.next();
   */
  

後來看了別人的解法，發現不用存整個2d vector，只要存begin和end就好了。

然後有些人會在next裡面呼叫hasNext，但我不太喜歡這種寫法，

覺的hasNext應該是要讓使用者call，call完後next就可以保證印出正確的值這樣比較合理。

但我的主要面試語言是Java，所以等等需要再寫一下java的版本，順便把java的iterator熟悉一下。

• code(Java):
  C++的iterator是用begin()和end()表示iteration的開始和結束，iterator的值不可能是null。而Java的iterator沒有這種東西，只有next()跟hasNext()而已，iterator在沒有initialize的時候是null。

  //用兩個iterator，一個是在2d vector上跑，另一個在1d vector上跑
  public class Vector2D implements Iterator<Integer> {
      private Iterator<List<Integer>> list2d_itr;
      private Iterator<Integer> list_itr;
  
      public Vector2D(List<List<Integer>> vec2d) {
          //check the size of 2d list
          if(vec2d.size() == 0 || vec2d == null) return;
          //add an iterator to 2d list
          list2d_itr = vec2d.iterator();
          //we have already checked that 2d list has at least 1 sublist, so assign an iterator to the first sublist.
          list_itr = list2d_itr.next().iterator();
      }
  
      @Override
      public Integer next() {
          return list_itr.next();
      }
  
      @Override
      public boolean hasNext() {
          if(list2d_itr == null) return false;
  
          //the current sublist still has element left
          if(list_itr.hasNext()){
              return true;
          }
  
          //move to the next valid sublist
          while(list2d_itr.hasNext()){
              list_itr = list2d_itr.next().iterator();
              if(list_itr.hasNext()){
                  return true;
              }
          }
          return false;
  
      }
  }
  
  /**
   * Your Vector2D object will be instantiated and called as such:
   * Vector2D i = new Vector2D(vec2d);
   * while (i.hasNext()) v[f()] = i.next();
   */