C++で2次元ベクトルを平坦化するイテレータの設計と実装

2次元ベクトル（vector of vectors）が与えられたとき、それを平坦化して1つずつ要素を取り出せるようにするイテレータを設計・実装することを考えます。このイテレータには、主に次の2つのメソッドを実装します。

• next() — 現在位置の次の要素を返します。
• hasNext() — 次の要素がまだ存在するかどうかを判定します。

動作例

たとえば、入力が [[1,2],[3],[4]] の場合、メソッドを次の順序で呼び出すとします。

iterator.next();
iterator.next();
iterator.next();
iterator.hasNext();
iterator.hasNext();
iterator.next();
iterator.hasNext();

このときの出力は [1, 2, 3, true, true, 4, false] となります。内側のベクトルの長さが異なっていても、あたかも1次元のリストであるかのように要素を順番に走査できるのがポイントです。

アルゴリズムの考え方

この問題は、「行ポインタ」と「列ポインタ」の2つのインデックスを使って現在位置を管理するのが定石です。手順は以下の通りです。

1. 2次元配列 v を保持するメンバ変数を用意します。
2. 2次元配列を受け取るコンストラクタを定義し、rowPointer = 0、colPointer = 0、n = v.size() で初期化します。
3. 初期化時に、先頭が空の行だった場合に備え、rowPointer < n かつ colPointer ≥ v[rowPointer].size() の間 rowPointer を進めて空行をスキップします。
4. next(): 現在位置の値 x = v[rowPointer][colPointer] を取得し、colPointer を1進めます。行末に達したら colPointer を0に戻して rowPointer を進め、再び空行をスキップします。最後に x を返します。
5. hasNext(): rowPointer == n（すべての行を読み終えた）なら false、そうでなければ true を返します。

空の行を都度スキップすることで、{} のような空ベクトルが混在していても正しく動作する堅牢な実装になります。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Vector2D {
public:
    int rowPointer, colPointer;
    int n;
    vector<vector<int>> v;
    Vector2D(vector<vector<int>>& v){
        this->v = v;
        rowPointer = 0;
        colPointer = 0;
        n = v.size();
        // 先頭の空行をスキップ
        while (rowPointer < n && colPointer >= v[rowPointer].size()){
            rowPointer++;
        }
    }
    int next(){
        int x = v[rowPointer][colPointer];
        colPointer++;
        if (colPointer == v[rowPointer].size()) {
            colPointer = 0;
            rowPointer++;
            // 次の非空行へスキップ
            while (rowPointer < n && colPointer >= v[rowPointer].size()) {
                rowPointer++;
            }
        }
        return x;
    }
    bool hasNext(){
        return !(rowPointer == n);
    }
};
main(){
    vector<vector<int>> v = {{1,2},{3},{4}};
    Vector2D ob(v);
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext());
}

入力

ob.next()
ob.next()
ob.next()
ob.hasNext()
ob.next()
ob.hasNext()

出力

1
2
3
1
4
0

true/false は整数として 1/0 に出力されます。この実装では、各要素へのアクセスは O(1)、全体の走査は O(N)（N は全要素数）で完了するため、効率的です。また、遅延評価方式のため、コンストラクタでデータをコピーせず参照で渡すことでメモリ効率も向上できます。