C++ algorithm implementation doesn't work

Question

Имеется задача реализовать структуру данных "исторический массив".
Исторический массив изначально имеет размер n и заполнен нулями.
Он поддерживает следующие операции:
set(index, value) - присвоить элементу на позиции i значение value
begin_new_era(era_id) - эта операция начинает новую эру с номером era_id. В каждый момент времени активна единственная эра. Изначальная эра имеет индекс era_id=0. Когда начинается новая эра, предыдущая заканчивается.
get(index, era_id) - получить значение элемента на позиции index на момент окончания эры era_id.

Ограничения:
n(1≤n≤100000)
set index value ( 0≤index≤n−1, 0≤value≤10^9)
begin_new_era era_id (1≤era_id≤10^9)
get index era_id (0≤index≤n−1, 0≤era_id≤10^9)
Гарантируется, что при запросе значения из конкретной эры эта эра уже успела закончиться.
Гарантируется, что при создании эры с идентификатором era_id этот индентификатор еще не был использован.

Написал реализацию:

struct HistoricalArray {
    unsigned long long int size;

    unsigned long long int currentEra;
    unordered_map<unsigned long long int,vector<unsigned long long int>> era;

    HistoricalArray(unsigned long long int n) : size(n),currentEra(0) {
        era[currentEra].resize(n);
        std::fill(era[currentEra].begin(), era[currentEra].end(), 0);
    }
    
    void beginNewEra(int eraId) {
        currentEra = eraId;
        era[currentEra].resize(size);
        std::fill(era[currentEra].begin(), era[currentEra].end(), 0);
    }

    void set(unsigned long long int index, unsigned long long int value) {
        era.at(currentEra)[index] = value;
    }

    unsigned long long int get(unsigned long long int index, unsigned long long int eraId) {
        return era.at(eraId)[index];
    }
};

Однако данная реализация на некоторых юнит-тестах не работает.

Подскажите, что здесь не так с реализацией?

Answer 1

Здесь не очень удачное описание структуры, которую требуется реализовать.

Будет проще, если воспринимать "эру" как "версию" значения, хранимого под индексом index.

Причём надо учитывать, что значение эры (версии) не обязано возрастать с каждым новым началом.

То есть нужно дополнительно сохранить порядок, в котором начинаются эры.

Вот рабочий код:

#include <vector>
#include <map>

using namespace std;
struct HistoricalArray {
    int cur_era_indx;
    vector<map<int, int>> data;
    map<int, int> eras;
    HistoricalArray(int n) : data(n) {
        beginNewEra(0);
    }

    void beginNewEra(int eraId) {
        cur_era_indx = eras.size();
        eras[eraId] = cur_era_indx;
    }

    void set(int index, int value) {
        data[index][cur_era_indx] = value;
    }

    int get(int index, int eraId) {
        int era_indx = eras[eraId];
        while (era_indx >= 0) {
            if (data[index].contains(era_indx)) {
                return data[index][era_indx];
            }
            --era_indx;
        }
        return 0;
    }
};

БЛОГ НА HUSL

C++ algorithm implementation doesn't work

Ответы (1 шт):