Design a Last Value Map in C++

Implement a data structure LastValueMap which has the following methods:

• void set(int key, int value) which associates key with value.
• void remove(int key) which removes key and its associated value.
• int getLast() which returns the value of the last added key. If a key is updated with a value, it should become last. You can assume that there is always a last value.

Constraints
0 ≤ n ≤ 200,000 where n is the number of method calls
Example 1
Input
methods = [“constructor”, “set”, “set”, “getLast”, “set”, “getLast”, “remove”, “getLast”]
arguments = [[], [1, 2], [2, 3], [], [1, 9], [], [1], []]`
Output
[null, null, null, 3, null, 9, null, 3]
Explanation

1 2 3 4 5 6 7 8

x = LastValueMap() x.set(1, 2) x.set(2, 3) x.getLast() == 3 x.set(1, 9) x.getLast() == 9 x.remove(1) x.getLast() == 3

x = LastValueMap()
x.set(1, 2)
x.set(2, 3)
x.getLast() == 3
x.set(1, 9)
x.getLast() == 9
x.remove(1)
x.getLast() == 3

Design a Last Value Map in C++ using List Iterator

We can either use a Double-Linked List or use a STL:list – which is easier to implement. We need a hash map to be able to locate the list::iterator then we can move it to the end by first erase it from the list O(1) and moving to the end O(1).

The getLast would be simply returning the previous of the end iterator of the list which is also O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class LastValueMap {
public:
    LastValueMap() {
 
    }
 
    void set(int key, int value) {
        if (data.count(key)) {
            auto item = data[key];
            *item = value;
            arr.erase(item);
            arr.push_back(*item);
            data[key] = item;
        } else {
            arr.push_back(value);
            data[key] = prev(end(arr));
        }
    }
 
    void remove(int key) {
        auto item = data[key];
        data.erase(key);
        arr.erase(item);
    }
 
    int getLast() {
        return *prev(end(arr));
    }
 
private:
    unordered_map<int, list<int>::iterator> data;
    list<int> arr;
};

class LastValueMap {
public:
    LastValueMap() {

    }

    void set(int key, int value) {
        if (data.count(key)) {
            auto item = data[key];
            *item = value;
            arr.erase(item);
            arr.push_back(*item);
            data[key] = item;
        } else {
            arr.push_back(value);
            data[key] = prev(end(arr));
        }
    }

    void remove(int key) {
        auto item = data[key];
        data.erase(key);
        arr.erase(item);
    }

    int getLast() {
        return *prev(end(arr));
    }

private:
    unordered_map<int, list<int>::iterator> data;
    list<int> arr;
};

–EOF (The Ultimate Computing & Technology Blog) —