0981-Time-Based-Key-Value-Store

Problem Description

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

• TimeMap() Initializes the object of the data structure.
• void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
• String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Constraints:

• key and value consist of lowercase English letters and digits.
• All the timestamps timestamp of set are strictly increasing.

Solution

核心觀念：constraints 那句 「All the timestamps timestamp of set are strictly increasing」是整題的關鍵禮物——它保證同一個 key 的 timestamp 是按呼叫順序遞增的，所以 push_back 進 vector 就天然有序，完全不需要排序。剩下的查詢語意是「找最後一個 timestamp ≤ target」，而這正是 upper_bound 退一格。

key = "foo"
  timestamp    1       4       9
  value       bar     bar2    bar3

  get("foo", 7)：找最後一個 timestamp ≤ 7
    upper_bound(7) ──→ 指向 9（第一個 > 7）
    prev 退一格    ──→ 指向 4  → 回傳 "bar2"

  get("foo", 0)：upper_bound(0) 指向 1，剛好 == begin()
                 代表沒有任何 timestamp ≤ 0 → 回傳 ""

方法一：vector + STL 二分 — set O(1)／get O(log n)（推薦）

// Time: set O(1) 均攤，get O(log n)
// Space: O(n)
class TimeMap {
 public:
  void set(string key, string value, int timestamp) {
    data_[key].push_back({move(value), timestamp});
  }

  string get(const string& key, int timestamp) const {
    if (!data_.contains(key)) return "";
    const auto& vec = data_.at(key);
    auto it = ranges::upper_bound(vec, timestamp, {}, &pair<string, int>::second);
    if (it == vec.begin()) return "";
    return prev(it)->first;
  }

 private:
  unordered_map<string, vector<pair<string, int>>> data_;  // key -> (value, timestamp)
};

方法二：map<int, string> — set O(log n)／get O(log n)

把每個 key 的歷史直接存成 map<int, string>，時間戳就是 map 的 key。這樣根本不需要 comparator 或 projection，因為要搜的東西本身就是容器的 key：

// Time: set O(log n)，get O(log n)
// Space: O(n)
class TimeMap {
 public:
  void set(string key, string value, int timestamp) {
    data_[key][timestamp] = move(value);
  }

  string get(const string& key, int timestamp) const {
    if (!data_.contains(key)) return "";
    const auto& hist = data_.at(key);
    auto it = hist.upper_bound(timestamp);
    if (it == hist.begin()) return "";
    return prev(it)->second;
  }

 private:
  unordered_map<string, map<int, string>> data_;  // key -> (timestamp -> value)
};

兩者的取捨很清楚：

附錄：lower_bound / upper_bound 的 comp 與 proj

這題最容易踩的其實不是演算法，是 STL 介面。

語意（前提：區間已依同一個序排好）

std::lower_bound(v, 4)  ->  comp(元素 b, 值 4)     元素在前
std::upper_bound(v, 4)  ->  comp(值 4, 元素 b)     值在前

error: request for member 'second' in 'p', which is of non-class type 'const int'

projection 是什麼

ranges 演算法的最後一個參數，作用是「比較之前先把元素變換一次」。comp 留 {} 表示沿用預設的 ranges::less：

ranges::upper_bound(vec, timestamp, {}, &pair<string, int>::second);
//                                  ↑        ↑
//                          comp 用預設   proj 指定「拿 .second 去比」

掛 log 看實際順序：

ranges::upper_bound(v, 4, comp, proj)
    proj(b) -> 4
  comp(值 4, proj(元素) 4)
    proj(c) -> 9
  comp(值 4, proj(元素) 9)

proj 可以是成員指標、成員函式指標，或任何一元可呼叫物：

ranges::sort(people, {}, &Person::age);                     // 依 age 排序
ranges::max_element(v, {}, &pair<string, int>::second);     // 依 second 找最大
ranges::find(people, "bob", &Person::name);                 // 依 name 找
ranges::sort(words, greater{}, [](const string& s) { return s.size(); });  // comp + proj 併用

std:: 與 std::ranges:: 對照

Related Problems

Binary-Search-Templates — 本題的查詢語意是「找最後一個 ≤ target」，屬模板二，但外包給 upper_bound + prev；手寫版的取整配對規則見該篇
0034-Find-First-and-Last-Position-of-Element-in-Sorted-Array — 手寫 lower_bound / upper_bound 的練習題，正好就是這對函式的定義本身
0035-Search-Insert-Position — 就是 lower_bound 本人，理解「第一個 ≥ x」語意的最短路徑
0704-Binary-Search — 模板一原型，對照「有明確出口」與本題「找邊界」的差別
0146-LRU-Cache — 同為 design 題，難度一樣不在演算法而在容器組合的選擇
STL-Pitfalls — 本篇附錄講的是 comp 與 proj 的用法；那篇收的是「編得過但複雜度或語意錯」的各類陷阱