C++での時間ベースのKey-Valueストア

2つの操作をサポートするTimeMapと呼ばれる時間ベースのKey-Valueストアクラスを作成する必要があるとします。

• 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）、set（ "foo"、 4）、set（ "foo"、5）の場合、出力は次のようになります：[null、 "bar"、 "bar"、null、 "bar2"、 "bar2]

これを解決するには、次の手順に従います-

• マップを定義するm

• set（）メソッドは次のようになります

  • （タイムスタンプ、値）をm [key]

    に挿入します

• get（）メソッドは次のように機能します

  • ret：=空の文字列

  • v：=m [key]

  • 低：=0および高：=vのサイズ– 1

  • 低<=高

    • 中：=低+（高–低）/ 2

    • v [mid] <=タイムスタンプのキーの場合、

      • ret：=v [mid]の値とlowに設定：=mid + 1

    • それ以外の場合は高い：=中– 1

  • retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class TimeMap {
   public:
   /** Initialize your data structure here. */
   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;
}

入力

Initialize it then call set and get methods as follows:
set("foo","bar",1))
get("foo", 1))
get("foo", 3))
set("foo","bar2",4))
get("foo", 4))
get("foo", 5))

出力

bar
bar
bar2
bar2