Обратное индексирование или обнуление массива за O(1)

В общем виде задача формулируется так:

Нужно создать структуру данных поддерживающую 3 вида операций на массиве:
1) set(i,value) – инициализация i-ого элемента значением value
2) get(i) – получение значение i-ого элемента
3) clear() – обнуление массива.

Каждая операция должна выполняться за O(1).

Первое, что мне пришло в голову было это:

1. struct ARRAY {
2.   vector<int> val;
3.   vector<int> met;
4.   int cur;
5.   int lastClear;
6.   ARRAY():cur(0), lastClear(0){}
7.   ARRAY(int size):cur(0), lastClear(0) {
8.     val.resize(size,0);
9.     met.resize(size,0);
10.   }
11.   void set(int pos, int value) {
12.     val[pos] = value;
13.     met[pos] = ++cur;
14.   }
15.   int get(int pos) {
16.     if (met[pos] > lastClear)
17.       return val[pos];
18.     return 0;
19.   }
20.   void clear() {
21.     lastClear = ++cur;
22.   }
23. };

* This source code was highlighted with Source Code Highlighter.

Но как это все уж больно по-пацаняче. С более изящным решением меня познакомил Кирилл Цыганов. Оно основано на принципе обратного индексирования:

1. const int MAX_REQ = 1000; // максимальное количество запросов set между вызовами clear
2. struct ARRAY {
3.   vector<int> A; // key - индекс; val - значение
4.   vector<int> S; //key - порядковый номер элемента при добавлении; val - индекс элемента в A
5.   vector<int> ID;//key - индекс элемента в A; val - порядковый номер элемента при добавлении
6.   int amount;
7.   ARRAY():amount(1){}
8.   ARRAY(int N):amount(1) {
9.     A.resize(N);
10.     S.resize(MAX_REQ);
11.     ID.resize(MAX_REQ);
12.   }
13.   void set(int pos, int value) {
14.     A[pos] = value;
15.     S[amount] = pos;
16.     ID[pos] = amount++;
17.   }
18.   int get(int pos) {
19.     if (ID[pos] > amount) // попали в мусор (после clear)
20.       return 0;
21.     if (S[ID[pos]] != pos) // обращение к неинициализированному элементу
22.       return 0;
23.     return A[S[ID[pos]]];
24.   }
25.   void clear() {
26.     amount = 0;
27.   }
28. };

* This source code was highlighted with Source Code Highlighter.