1146. Snapshot Array

Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

class SnapshotArray {
    int snapShot;
    unordered_map<int, vector<pair<int, int>>> ml;
public:
    SnapshotArray(int length) : snapShot(0) {    }

    void set(int index, int val) {
        if(ml[index].empty() || ml[index].back().first < snapShot)
            ml[index].push_back({snapShot, val});
        else
            ml[index].back().second = val;
    }

    int snap() {
        return snapShot++;
    }

    int get(int index, int snap_id) {
        auto it = upper_bound(ml[index].begin(), ml[index].end(), pair<int, int>(snap_id, INT_MAX));
        return it == ml[index].begin() ? 0 : prev(it)->second;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */