Kho khóa-giá trị dựa trên thời gian trong C ++

Giả sử chúng ta phải tạo một lớp lưu trữ khóa-giá trị dựa trên thời gian được gọi là TimeMap, hỗ trợ hai hoạt động.

• set (khóa chuỗi, giá trị chuỗi, dấu thời gian int):Điều này sẽ lưu trữ khóa và giá trị, cùng với dấu thời gian đã cho.

• get (string key, int timestamp):Giá trị này sẽ trả về một giá trị mà tập (key, value, timestamp_prev) đã được gọi trước đó, với timestamp_prev <=timestamp.

Bây giờ nếu có nhiều giá trị như vậy, nó phải trả về giá trị mà giá trị timestamp_prev là lớn nhất. Nếu không có giá trị nào như vậy, nó trả về chuỗi rỗng (""). Vì vậy, nếu chúng ta gọi các hàm như bên dưới -

set ("foo", "bar", 1), get ("foo", 1), get ("foo", 3), set ("foo", "bar2", 4), set ("foo", 4), set ("foo", 5), thì kết quả đầu ra sẽ là:[null, "bar", "bar", null, "bar2", "bar2]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định bản đồ m

• Phương thức set () sẽ giống như

  • chèn (dấu thời gian, giá trị) vào m [key]

• Phương thức get () sẽ hoạt động như sau

  • ret:=một chuỗi trống

  • v:=m [key]

  • thấp:=0 và cao:=kích thước của v - 1

  • trong khi thấp <=cao

    • giữa:=low + (cao - thấp) / 2

    • khóa if của v [mid] <=timestamp, then

      • ret:=giá trị của v [mid] và đặt low:=mid + 1

    • nếu không thì cao:=mid - 1

  • trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
}

Đầu vào

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))

Đầu ra

bar
bar
bar2
bar2