C++ Hash Map + Vector
It\'s similar to 981. Time Based Key-Value Store.\n\nFor each index, we store values in the map for each snap id. We maintain the current snap id and use it in 
It\'s similar to [981. Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/discuss/226664/C%2B%2B-3-lines-hash-map-%2B-map).\n\nFor each index, we store values in the map for each snap id. We maintain the current snap id and use it in ```set```. When we do ```snap```, we just increase snap id. Therefore, our map will only contain snap ids when the value was set.\n\nFor ```get```, we use binary search to find the most recent value for the requested snap id.\n\n> Note that we can achieve O(1) complexity for the get operation, but it won\'t be memory-efficient if we populate all indices and then make a lot of snaps (without modifying much).\n\n**C++**\n```\nunordered_map<int, map<int, int>> a;\nint cur_snap = 0;\nSnapshotArray(int length) {}\nint snap() { return cur_snap++; }\nvoid set(int index, int val) { \n  a[index][cur_snap] = val; \n}\nint get(int index, int snap_id) {\n  auto it = a[index].upper_bound(snap_id);\n  return it == begin(a[index]) ? 0 : prev(it)->second;\n}\n```\nSince our timestamps are only increasing, we can use a vector instead of a map, though it\'s not as concise.\n\n**C++**\n```\nvector<vector<pair<int, int>>> m;\nint cur_snap = 0;\nSnapshotArray(int length) {\n    m = vector<vector<pair<int, int>>>(length);\n}\nint snap() { return cur_snap++; }\nvoid set(int index, int val) {\n  if (m[index].empty() || m[index].back().first != cur_snap)\n    m[index].push_back({ cur_snap, val });\n  else m[index].back().second = val;\n}\nint get(int index, int snap_id) {\n  auto it = upper_bound(begin(m[index]), end(m[index]), pair<int, int>(snap_id, INT_MAX));\n  return it == begin(m[index]) ? 0 : prev(it)->second;\n}};\n```\n# Complexity analysis\nAssuming ```n``` is the number of ```set``` + ```snap``` operations, and ```m``` is the number of get operations:\n> Note: for the complexity analysis, we consider  ```set``` + ```snap``` as one operation. Otherwise, neither ```set``` nor ```snap``` alone increases the number of values we need to consider for the ```get``` operation.\n\n- Time Complexity: \n    - Set: ```O(1)``` single operation, and total ```O(n)```.\n    - Get: ```O(log n)``` for a single operation, and total ```O(m log n)```.\n- Space Complexity: ```O(n)```
[]