C++で実装する時間ベースのKey-Valueストア（TimeMap）の解説

時間ベースのKey-Valueストアとは

本記事では、時間ベースのKey-Valueストアである「TimeMap」クラスをC++で実装する方法を解説します。TimeMapは、次の2つの操作をサポートするデータ構造です。

• set(string key, string value, int timestamp)：キーと値を、指定されたタイムスタンプとともに保存します。
• get(string key, int timestamp)：以前に呼び出された set(key, value, timestamp_prev) のうち、timestamp_prev <= timestamp を満たす値を返します。

条件を満たす値が複数存在する場合は、その中で timestamp_prev が最も大きい（＝最新の）値を返します。該当する値がひとつも存在しない場合は、空文字列（""）を返します。

動作例

例えば、以下の順序でメソッドを呼び出した場合を考えてみましょう。

set("foo", "bar", 1)
get("foo", 1)
get("foo", 3)
set("foo", "bar2", 4)
get("foo", 4)
get("foo", 5)

このときの出力は [null, "bar", "bar", null, "bar2", "bar2"] となります。タイムスタンプ3の時点ではまだ bar2 が登録されていないため、直近の値である "bar" が返される点に注目してください。

解法のアプローチ：ハッシュマップ＋二分探索

この問題は、ハッシュマップ（unordered_map）と二分探索を組み合わせることで効率的に解けます。各キーに対してタイムスタンプは単調増加する前提があるため、二分探索が有効です。手順は以下の通りです。

1. マップ m を定義します。キーは文字列、値は「(タイムスタンプ, 値) のペア」を格納するベクトルです。
2. set() メソッド：m[key] に (timestamp, value) を追加します。
3. get() メソッド：次の手順で二分探索を行います。
   • ret := 空文字列
   • v := m[key]
   • low := 0、high := v のサイズ − 1
   • low <= high の間、以下を繰り返します。
     • mid := low + (high − low) / 2
     • v[mid] のタイムスタンプ <= timestamp ならば、ret := v[mid] の値とし、low := mid + 1
     • それ以外の場合は、high := mid − 1
   • 探索終了後、ret を返します。

この方法により、set() は O(1)、get() は O(log n) の計算量で処理できます。

C++による実装例

以下に実際のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class TimeMap {
public:
    /** データ構造をここで初期化 */
    unordered_map<string, vector<pair<int, string>>> m;
    TimeMap() {
        m.clear();
    }
    void set(string key, string value, int timestamp) {
        m[key].push_back({timestamp, value});
    }
    string get(string key, int timestamp) {
        string ret = "";
        vector<pair<int, string>>& v = m[key];
        int low = 0;
        int high = v.size() - 1;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(v[mid].first <= timestamp){
                ret = v[mid].second;
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return ret;
    }
};
main(){
    TimeMap ob;
    (ob.set("foo","bar",1));
    cout << (ob.get("foo", 1)) << endl;
    cout << (ob.get("foo", 3)) << endl;
    (ob.set("foo","bar2",4));
    cout << (ob.get("foo", 4)) << endl;
    cout << (ob.get("foo", 5)) << endl;
}

入力

初期化後、set と get を以下の順に呼び出します：
set("foo","bar",1)
get("foo", 1)
get("foo", 3)
set("foo","bar2",4)
get("foo", 4)
get("foo", 5)

出力

bar
bar
bar2
bar2

まとめ

時間ベースのKey-Valueストアは、「キーごとに履歴を保持し、指定時点の最新の状態を取得する」という要件を扱う典型的なデータ構造です。unordered_map でキーごとの履歴を管理し、二分探索で目的のタイムスタンプを素早く特定することで、高性能な TimeMap を簡潔に実装できます。バージョン管理システムや時系列データの参照など、さまざまな場面で応用できる考え方なので、ぜひ理解を深めておきましょう。