981. 基于时间的键值存储 力扣（中等） 又学到了map新用法，lower_bound()

题目描述： 

创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：

1. set(string key, string value, int timestamp)

存储键 key、值 value，以及给定的时间戳 timestamp。
2. get(string key, int timestamp)

返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp。
如果有多个这样的值，则返回对应最大的  timestamp_prev 的那个值。
如果没有值，则返回空字符串（""）。

示例 1：

输入：inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
输出：[null,null,"bar","bar",null,"bar2","bar2"]
解释： 
TimeMap kv;  
kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1  
kv.get("foo", 1); // 输出 "bar"  
kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"）  
kv.set("foo", "bar2", 4);  
kv.get("foo", 4); // 输出 "bar2"  
kv.get("foo", 5); // 输出 "bar2"  

题源：https://leetcode-cn.com/problems/time-based-key-value-store/

学点：

1、for(auto i: map)  这种情况下，取值用   i.first  或   i.second

     但是，如果是map<，>::iterator i情况，应该用  i->first,  i->second

2、lower_bound，和upper_bound都是二分查找，效率高。

STL--map中的用法：std::map::lower_bound与td::map::upper_bound

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。

lower_bound 返回值是一个指向容器中第一个元素的迭代器，该容器中的元素满足不在k的前面，（返回元素的键值>=k）

upper_bound返回值是一个指向容器中第一个元素的迭代器，该容器中的元素满足在k的后面，（返回元素的键值>k）

STL中的用法：std::lower_bound与std::upper_bound

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)

返回一个非递减序列[first, last)中的第一个>= 值val的位置。

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)

返回一个非递减序列[first, last)中的第一个>值val的位置。

代码：

class TimeMap {
public:
    /** Initialize your data structure here. */
    map<string,map<int,string>> mp;
    TimeMap() {

    }
    
    void set(string key, string value, int timestamp) {
        mp[key][timestamp]=value;
        return;
    }
    
    string get(string key, int timestamp) {
        if (mp.find(key)==mp.end()) return "";   // 如果都不存在key
        if (mp[key].begin()->first>timestamp) return ""; //如果存在key，但是时间均大于timestamp,这里只能用  ->fisrt，.first会报错
        if (mp[key].find(timestamp)!=mp[key].end()) return mp[key][timestamp];  //  如果存在key，且，存在等于timestamp，直接返回即可
        /*string res="";   // 下面这段代码tle，需要二分查找
        int maxtime;
            for(auto j : mp[key])
                if (j.first<=timestamp)
                {
                    maxtime=j.first;
                    res=j.second;
                } else break;
        return res;*/
        map<int, string>::iterator ii=mp[key].upper_bound(timestamp);
        ii--;
        return ii->second;
    }
};

/**
 * 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);
 */