ที่เก็บคีย์-ค่าตามเวลาใน C++

สมมติว่าเราต้องสร้างคลาสที่เก็บคีย์-ค่าตามเวลาที่เรียกว่า TimeMap ซึ่งรองรับการทำงานสองอย่าง

• 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]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ ม

• วิธี set() จะเป็นแบบนี้

  • แทรก (ประทับเวลา, ค่า) ลงใน m[คีย์]

• เมธอด get() จะทำงานดังนี้

  • ret :=สตริงว่าง

  • v :=m[คีย์]

  • ต่ำ :=0 และสูง :=ขนาดของ v – 1

  • ในขณะที่ต่ำ <=สูง

    • กลาง :=ต่ำ + (สูง – ต่ำ) / 2

    • ถ้าคีย์ของ v[mid] <=timestamp แล้ว

      • ret :=ค่าของ v[mid] และตั้งค่าต่ำ :=mid + 1

    • สูงอย่างอื่น :=กลาง – 1

  • รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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