Simple C++ solutions|| map & set
Intuition\n Describe your first thoughts on how to solve this problem. \nTwo different solutions are provided, each using a different data structure. One soluti
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTwo different solutions are provided, each using a different data structure. One solution utilizes the C++ map data structure, while the other uses the set data structure. Both of these data structures have a defined order, i.e. "<". This allows the binary search function lower_bound to work correctly. In contrast, the unordered versions of these data structures (unordered_map and unordered_set) do not have a defined order, which makes it impossible to use lower_bound for binary search\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe set version needs an extra parameter for recording the sequence number for set() method, so tuple<int, int, int> is used.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SnapshotArray {\n   int id=0; \n   vector<map<int, int>> id_v;\n\npublic:\n    SnapshotArray(int length) { \n        id_v.assign(length, {{0,0}});   \n    }\n    \n    void set(int index, int val) {\n        id_v[index][id]=val;\n    }\n    \n    int snap() {\n       return id++; \n    }\n    \n    int get(int index, int snap_id) {\n        if (id_v[index].count(snap_id)==0){\n            auto it=prev(id_v[index].lower_bound(snap_id));\n            return it->second;\n        }\n        return  id_v[index][snap_id];\n    }\n};\n\n/**\n * Your SnapshotArray object will be instantiated and called as such:\n * SnapshotArray* obj = new SnapshotArray(length);\n * obj->set(index,val);\n * int param_2 = obj->snap();\n * int param_3 = obj->get(index,snap_id);\n */\n```\n\n```\nclass SnapshotArray {\n   int id=0;\n   int set_seq=0; \n   vector<set<tuple<int, int, int>>> id_v;\n\npublic:\n    SnapshotArray(int length) { \n        id_v.assign(length, {{0,0,0}});   \n    }\n    \n    void set(int index, int val) {\n        id_v[index].insert({id, set_seq++, val});\n    }\n    \n    int snap() {\n       return id++; \n    }\n    \n    int get(int index, int snap_id) { \n        auto it=prev(id_v[index].lower_bound({snap_id,set_seq,INT_MAX}));\n        auto [id, _, v]=*it;\n    //    cout<< id<<","<<set_seq<<","<<v<<endl;\n        return v;\n    }\n};\n\n/**\n * Your SnapshotArray object will be instantiated and called as such:\n * SnapshotArray* obj = new SnapshotArray(length);\n * obj->set(index,val);\n * int param_2 = obj->snap();\n * int param_3 = obj->get(index,snap_id);\n */\n```
['Hash Table', 'Binary Search', 'C++']