C++でキュー内の最初の一意な整数を取得するFirstUniqueクラスの実装

整数のキューが与えられたとき、その中で重複していない（一意な）整数のうち最初に現れるものを取り出したい場面を考えてみましょう。この問題は、FirstUniqueというクラスを実装することで解決できます。

FirstUniqueクラスは次の2つの操作を提供します。

• コンストラクタ：初期状態のキューとなる整数の配列を受け取って初期化します。
• showFirstUnique()：キューの中で最初に現れる一意な整数の値を返します。一意な整数が存在しない場合は -1 を返します。
• add(value)：指定した値をキューに追加します。

動作例

例えば、[2, 3, 5] で初期化し、以下の順にメソッドを呼び出した場合を考えます。

• showFirstUnique()
• add(5)
• showFirstUnique()
• add(2)
• showFirstUnique()
• add(3)
• showFirstUnique()

このとき、出力はそれぞれ 2, 2, 3, -1 となります。

• 初期状態では 2 が最初の一意な整数です。
• 5 を追加しても 2 のままです。
• 2 を追加すると 2 が重複するため、次の一意な整数である 3 が答えになります。
• 3 を追加するとすべての値が重複するため、-1 を返します。

アルゴリズムの考え方

この問題を解くために、キューとマップ（カウンタ）を組み合わせたアプローチを使います。

1. 整数用のキュー q を用意します。
2. 各値の出現回数を記録するマップ cnt を用意します。
3. コンストラクタでは、渡された配列に対して以下を行います。
   • まず全要素 i について cnt[i] を1増やします。
   • 次にもう一度全要素を走査し、cnt[i] が1（＝まだ重複していない）であれば q に挿入します。
4. showFirstUnique() では以下を行います。
   • キューが空でなく、先頭要素の出現回数が1より大きい（＝すでに重複している）間、先頭要素を削除し続けます。
   • キューが空になった場合は -1 を、そうでなければ先頭要素を返します。
5. add(value) では以下を行います。
   • cnt[value] を1増やします。
   • cnt[value] が1（＝初めて追加された値）であれば、value を q に挿入します。

この方式のポイントは、重複した値を即座に削除せず、参照された時点で遅延的に除去することです。これにより、add() 操作は常に高速に処理でき、全体として効率的な実装になります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class FirstUnique {
public:
    queue <int> q;
    map <int, int> cnt;
    FirstUnique(vector<int>& nums) {
        for (int i : nums) {
            cnt[i]++;
        }
        for (int i : nums) {
            if (cnt[i] == 1) {
                q.push(i);
            }
        }
    }
    int showFirstUnique() {
        while (!q.empty() && cnt[q.front()] > 1) q.pop();
        return q.empty() ? -1 : q.front();
    }
    void add(int value) {
        cnt[value]++;
        if (cnt[value] == 1)
            q.push(value);
    }
};
main(){
    vector<int> v = {2,3,5};
    FirstUnique ob(v);
    cout << (ob.showFirstUnique()) << endl;
    ob.add(5);
    cout << (ob.showFirstUnique()) << endl;
    ob.add(2);
    cout << (ob.showFirstUnique()) << endl;
    ob.add(3);
    cout << (ob.showFirstUnique()) << endl;
}

入力

{2,3,5}
ob.showFirstUnique();
ob.add(5);
ob.showFirstUnique();
ob.add(2);
ob.showFirstUnique();
ob.add(3);
ob.showFirstUnique();

出力

2
2
3
-1

計算量の評価

• 時間計算量：add() はO(log n)（マップへの挿入）、showFirstUnique() は償却O(1)程度で動作します。各要素はキューに高々1度追加され、高々1度削除されるためです。
• 空間計算量：キューとマップに最大でO(n)の領域が必要です。

このように、キューとハッシュマップ（ここでは map）を組み合わせることで、データの追加と「最初の一意な値の参照」を効率よく両立できるのが、この実装の大きな特徴です。