C++ এ সময় ভিত্তিক কী-ভ্যালু স্টোর

ধরুন আমাদের টাইমম্যাপ নামে একটি টাইম-ভিত্তিক কী-মানের স্টোর ক্লাস তৈরি করতে হবে, যা দুটি ক্রিয়াকলাপ সমর্থন করে৷

• সেট(স্ট্রিং কী, স্ট্রিং মান, int টাইমস্ট্যাম্প):এটি প্রদত্ত টাইমস্ট্যাম্প সহ কী এবং মান সংরক্ষণ করবে।

• get(string key, int টাইমস্ট্যাম্প):এটি একটি মান ফিরিয়ে দেবে যেমন সেট(কী, মান, টাইমস্ট্যাম্প_প্রেভ) পূর্বে টাইমস্ট্যাম্প_প্রেভ <=টাইমস্ট্যাম্প সহ কল ​​করা হয়েছিল।

এখন যদি এই ধরনের একাধিক মান থাকে তবে এটি অবশ্যই সেই মানটি ফেরত দেবে যেখানে টাইমস্ট্যাম্প_প্রেভ মানটি সবচেয়ে বড়। যদি এই ধরনের কোন মান না থাকে তবে এটি খালি স্ট্রিং ("") প্রদান করে। তাই যদি আমরা নিচের মত ফাংশন কল −

সেট("foo","বার",1), get("foo",1), get("foo",3), সেট("foo","bar2",4), সেট("foo", 4), সেট("foo",5), তারপর আউটপুট হবে:[null, “bar”, “bar”, null, “bar2”, “bar2]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• সেট() পদ্ধতির মত হবে

  • m[key]

    -এ (টাইমস্ট্যাম্প, মান) সন্নিবেশ করান

• get() পদ্ধতিটি নিম্নরূপ কাজ করবে

  • ret :=একটি খালি স্ট্রিং

  • v :=m[কী]

  • কম :=0 এবং উচ্চ :=v – 1

    এর আকার

  • যখন কম <=উচ্চ

    • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2

    • যদি v[mid] <=টাইমস্ট্যাম্পের কী, তাহলে

      • 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