Time Based Key-Value Store Solutions in C++

// Source : https://leetcode.com/problems/time-based-key-value-store/
// Author : Hao Chen
// Date   : 2019-01-30



class TimeMap {
private:
    unordered_map<string, std::set<int>> key_time;
    unordered_map<int, string> time_value;
public:
    /** Initialize your data structure here. */
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        key_time[key].insert(timestamp);
        time_value[timestamp] = value;
    }
    
    string get(string key, int timestamp) {
        if ( key_time.find(key) == key_time.end() ) return "";
        auto it = key_time[key].lower_bound(timestamp);
        if ( *it == timestamp ) return time_value[*it];
        if ( it != key_time[key].begin() ) {
            it--;
            return time_value[*it];
        }
        return "";
    }
};


/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

/// Source : https://leetcode.com/problems/time-based-key-value-store/
/// Author : liuyubobobo
/// Time   : 2019-01-26

#include <iostream>
#include <unordered_map>
#include <set>


/// Using TreeSet to store (time, value) pair information for each key
/// Time Complexity: init: O(1)
///                  set: O(logn)
///                  get: O(logn)
/// Space Complexity: O(n)
class TimeMap {

private:
    std::unordered_map<std::string, std::set<std::pair<int, std::string>>> map; // key -> (time, value)

public:
    /** Initialize your data structure here. */
    TimeMap() {}

    void set(std::string key, std::string value, int timestamp) {
        map[key].insert(make_pair(timestamp, value));
    }

    std::string get(std::string key, int timestamp) {

        std::set<std::pair<int, std::string>>::iterator iter =
                map[key].lower_bound(std::make_pair(timestamp, ""));
        if(iter == map[key].end() || iter->first > timestamp){
            if(iter == map[key].begin()) return "";
            iter --;
        }
        return iter->second;
    }
};


int main() {

    TimeMap timeMap;
    timeMap.set("foo", "bar", 1);
    std::cout << timeMap.get("foo", 1) << std::endl;
    // bar

    std::cout << timeMap.get("foo", 3) << std::endl;
    // bar

    timeMap.set("foo", "bar2", 4);
    std::cout << timeMap.get("foo", 4) << std::endl;
    // bar2

    std::cout << timeMap.get("foo", 5) << std::endl;
    // bar2

    std::cout << timeMap.get("foo", 1) << std::endl;
    // bar

    return 0;
}

/// Source : https://leetcode.com/problems/time-based-key-value-store/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <unordered_map>
#include <map>

using namespace std;


/// Using TreeMap to store (time, value) pair information for each key
/// Time Complexity: init: O(1)
///                  set: O(logn)
///                  get: O(logn)
/// Space Complexity: O(n)
class TimeMap {

private:
    unordered_map<string, map<int, string>> timeMap; // key -> (time, value)

public:
    /** Initialize your data structure here. */
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        timeMap[key][timestamp] = value;
    }

    string get(string key, int timestamp) {

        map<int, string>::iterator iter =
                timeMap[key].lower_bound(timestamp);
        if(iter == timeMap[key].end() || iter->first > timestamp){
            if(iter == timeMap[key].begin()) return "";
            iter --;
        }
        return iter->second;
    }
};


int main() {

    TimeMap timeMap;
    timeMap.set("foo", "bar", 1);
    cout << timeMap.get("foo", 1) << endl;
    // bar

    cout << timeMap.get("foo", 3) << endl;
    // bar

    timeMap.set("foo", "bar2", 4);
    cout << timeMap.get("foo", 4) << endl;
    // bar2

    cout << timeMap.get("foo", 5) << endl;
    // bar2

    cout << timeMap.get("foo", 1) << endl;
    // bar

    return 0;
}

/// Source : https://leetcode.com/problems/time-based-key-value-store/
/// Author : liuyubobobo
/// Time   : 2019-01-28

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;


/// Since the timestamp is strictly increasing,
/// We can just use array to store all data
/// and use binary search directly for the array corresponding to each key
///
/// Time Complexity: init: O(1)
///                  set: O(1)
///                  get: O(logn)
/// Space Complexity: O(n)
class TimeMap {

private:
    unordered_map<string, vector<pair<int, string>>> timeMap; // key -> (time, value)

public:
    /** Initialize your data structure here. */
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        timeMap[key].push_back(make_pair(timestamp, value));
    }

    string get(string key, int timestamp) {

        vector<pair<int, string>>::iterator iter =
                lower_bound(timeMap[key].begin(), timeMap[key].end(), make_pair(timestamp, string("")));
        if(iter == timeMap[key].end() || iter->first > timestamp){
            if(iter == timeMap[key].begin()) return "";
            iter --;
        }
        return iter->second;
    }
};


int main() {

    TimeMap timeMap;
    timeMap.set("foo", "bar", 1);
    cout << timeMap.get("foo", 1) << endl;
    // bar

    cout << timeMap.get("foo", 3) << endl;
    // bar

    timeMap.set("foo", "bar2", 4);
    cout << timeMap.get("foo", 4) << endl;
    // bar2

    cout << timeMap.get("foo", 5) << endl;
    // bar2

    cout << timeMap.get("foo", 1) << endl;
    // bar

    return 0;
}