Ежедневный бит(е) C++ | O(1) ранжирующая структура данных

Ежедневный бит (е) C ++ # 35, Общая проблема интервью C ++: структура данных ранжирования all-O (1)

Реализуйте структуру данных O(1), то есть структуру данных, в которой все операции выполняются за O(1) (амортизированное) время.

Структура данных должна хранить ключи и их целочисленные значения и предлагать следующий интерфейс.

• increment(key)
  увеличить значение ключа, если он существует, или вставить ключ со значением 1, если он не существует
• decrement(key)
  уменьшить значение ключа, если он существует, или, если значение уже равно 1, удалить его
• min()
  вернуть один из минимальных ключей или пустую строку, если ключей нет
• max()
  вернуть один из максимальных ключей или пустую строку, если ключей нет

Прежде чем продолжить чтение решения, попробуйте решить его самостоятельно. Вот ссылка на проводник компилятора с коротким тестовым примером: https://compiler-explorer.com/z/vaPsGsxze.

Решение

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

Для операций min() и max() нам нужно будет сохранить нашу структуру данных в каком-то отсортированном порядке. Это связано с тем, что у нас нет возможности пересчитать минимум после удаления элемента min или max.

В связи с этим у нас есть дополнительное требование. Увеличение (или уменьшение) ключа может потребовать перемещения ключа перед многими другими ключами с тем же значением. Только одна структура данных поддерживает такую ​​операцию, std::list.

Чтобы сохранить ключи отсортированными, мы можем сгруппировать ключи по значению в сегменты. Каждое увеличение или уменьшение может привести к созданию новой корзины или, если целевая корзина уже существует, к простому перемещению.

Наконец, нам нужен способ перехода к определенной клавише. std::list предоставляет стабильные итераторы, поэтому нам нужно только сопоставление ключа с конкретным итератором. Мы можем использовать std::unordered_map для этого.

struct ConstantRanking {
    // Increment a key
    // - if the key doesn't exists, insert it with value 1 instead
    void increment(const std::string& key) {
        // Check if the key exists
        auto it = lookup.find(key);
        if (it == lookup.end()) {
            push_front(key); // insert
            return;
        }
        auto [it_item, it_bucket] = it->second;
        int value = it_item->second;
        // Get/create a bucket for value+1
        auto next = next_bucket(it_bucket);
        // Remove from the bucket for value
        remove(it_bucket, it_item);
        // Add it to the bucket for value+1
        add(next, key, value + 1);
    }
    
    // Decrement a key
    // - if the key already has value 1, remove it
    void decrement(const std::string& key) {
        // Check if the key exists
        auto it = lookup.find(key);
        if (it == lookup.end()) {
            return;
        }
        auto [it_item, it_bucket] = it->second;
        int value = it_item->second;
        if (value == 1) {
            // Key already at value 1, remove
            lookup.erase(key);
            remove(it_bucket, it_item);
        } else {
            // Get/create a bucket for value-1
            auto prev = prev_bucket(it_bucket);
            // Remove from the bucket for value
            remove(it_bucket, it_item);
            // Add it to the bucket for value-1
            add(prev, key, value - 1);
        }
    }

    // Get (one of) the maximum keys
    // - if empty, return an empty string
    std::string max() const {
        if (storage.empty()) return "";
        return storage.back().back().first;
    }
    
    // Get (one of) the minimum keys
    // - if empty, return an empty string
    std::string min() const {
        if (storage.empty()) return "";
        return storage.front().front().first;
    }

private:
    using Item = std::pair<std::string, int>;
    using Bucket = std::list<Item>;
    using ItemIt = std::list<Item>::iterator;
    using BucketIt = std::list<Bucket>::iterator;
    std::list<Bucket> storage;
    std::unordered_map<std::string, std::pair<ItemIt, BucketIt>> lookup;

    // Helper: get (or make) next bucket
    BucketIt next_bucket(BucketIt it) {
        int value = it->front().second;
        auto next = std::next(it);
        // There is no next bucket or the next bucket
        // doesn't contain value + 1 items.
        if (next == storage.end() || 
            next->front().second != value + 1)
            return storage.insert(next,Bucket{});
        return next;
    }

    // Helper: get (or make) previous bucket
    BucketIt prev_bucket(BucketIt it) {
        int value = it->front().second;
        // There is no previous bucket or the previous bucket
        // doesn't contain value - 1 items.
        if (it == storage.begin() || 
            std::prev(it)->front().second != value - 1)
            return storage.insert(it,Bucket{});
        return std::prev(it);
    }

    // Helper: remove item from bucket
    void remove(BucketIt bucket, ItemIt item) {
        bucket->erase(item);
        if (bucket->empty())
            storage.erase(bucket);
    }

    // Helper: add item to bucket
    void add(BucketIt bucket, const std::string& key, int value) {
        bucket->push_front(Item{key,value});
        lookup[key] = std::pair{bucket->begin(), bucket};
    }

    // Helper: add a new item with value 1
    void push_front(const std::string& key) {
        if (storage.size() == 0 || storage.front().front().second != 1)
            storage.push_front(std::list<Item>{});
        add(storage.begin(), key, 1);
    }
};

Откройте решение в Compiler Explorer.