C++ में टाइम बेस्ड की-वैल्यू स्टोर

मान लीजिए कि हमें टाइममैप नामक एक टाइमबेस्ड की-वैल्यू स्टोर क्लास बनाना है, जो दो ऑपरेशनों का समर्थन करता है।

• सेट (स्ट्रिंग कुंजी, स्ट्रिंग मान, इंट टाइमस्टैम्प):यह दिए गए टाइमस्टैम्प के साथ कुंजी और मान को संग्रहीत करेगा।

• get (स्ट्रिंग कुंजी, इंट टाइमस्टैम्प):यह एक मान लौटाएगा जैसे कि सेट (कुंजी, मान, टाइमस्टैम्प_प्रेव) को पहले टाइमस्टैम्प_प्रेव <=टाइमस्टैम्प के साथ कहा जाता था।

अब यदि ऐसे कई मान हैं, तो उसे वह मान वापस करना होगा जहां टाइमस्टैम्प_प्रेव मान सबसे बड़ा है। यदि ऐसा कोई मान नहीं है, तो यह खाली स्ट्रिंग ("") लौटाता है। तो अगर हम नीचे दिए गए कार्यों को कहते हैं -

सेट ("फू", "बार", 1), प्राप्त करें ("फू", 1), प्राप्त करें ("फू", 3), सेट ("फू", "बार 2", 4), सेट ("फू", 4), सेट ("फू", 5), फिर आउटपुट होंगे:[नल, "बार", "बार", नल, "बार 2", "बार 2]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• नक्शा परिभाषित करें मी

• सेट () विधि इस तरह होगी

  • m[key]

    . में डालें (टाइमस्टैम्प, मान)

• प्राप्त () विधि निम्नानुसार काम करेगी

  • रिट:=एक खाली स्ट्रिंग

  • वी:=एम [कुंजी]

  • निम्न :=0 और उच्च :=v – 1 का आकार

  • जबकि कम <=उच्च

    • मध्य :=निम्न + (उच्च-निम्न)/2

    • अगर v[mid] <=टाइमस्टैम्प की कुंजी है, तो

      • ret :=v[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