C ++中基于时间的键值存储
假设我们必须创建一个名为TimeMap的基于时间的键值存储类，该类支持两种操作。
set（stringkey，stringvalue，inttimestamp）：这将存储键和值以及给定的时间戳。
get（stringkey，inttimestamp）：这将返回一个值，使得先前调用过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()方法将如下工作
中：=低+（高–低）/2
如果v[mid]的键<=时间戳，则
否则高：=中–1
ret：=v[mid]的值并设置为低：=mid+1
ret：=一个空字符串
v：=m[key]
低：=0，高：=v–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