c++ - 结束迭代器减量的应用及意义

Question

int get(int key) {
        if (m.count(key) == 0) return -1;
        freq[m[key].second].erase(iter[key]);      
        freq[m[key].second].push_back(key);        
        iter[key] = --freq[m[key].second].end();   
        if (freq[minFreq].size() == 0) ++minFreq;
        return m[key].first;
}

private:
    int cap, minFreq;
    unordered_map<int, pair<int, int>> m;
    unordered_map<int, list<int>> freq;
    unordered_map<int, list<int>::iterator> iter;

我在 Leetcode 问题之一上找到了这一系列的解决方案代码。这让我想知道在这种情况下，结束迭代器递减实际上意味着什么，以及在你编码时使用这种格式的时机是什么时候。作为一个 C++ 初学者，我认为如果它保持不变就好了

iter[key] = freq[m[key].second].end();

但是——真的让我很困惑。在上下文中，我们应该找到 LFU 缓存，并且该行应该是在频率列表中找到一个值的对应位置。

标签： c++stliterator

Answer 1

• --操作在实际语句之前执行。

---

重要的

• 在您进一步研究unordered_map解决方案之前（我也重新实现了该解决方案）：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <unordered_map>
#include <list>
#include <utility>

static const struct LFUCache {

    inline LFUCache(const int capacity) {
        this->capacity = capacity;
        size = 0;
    }

    inline const int get(const int key) {
        if (values.find(key) == values.end()) {
            return -1;
        }

        update(key);
        return values[key].first;
    }

    inline void put(const int key, const int value) {
        if (!capacity) {
            return;
        }

        if (values.find(key) != values.end()) {
            values[key].first = value;
            update(key);

        } else {
            if (size == capacity) {
                const ValueType evict = keys[least_freq_used].front();
                keys[least_freq_used].pop_front();
                values.erase(evict);
                iters.erase(evict);

            } else {
                size++;
            }

            values[key] = {value , 1};
            keys[1].emplace_back(key);
            iters[key] = --keys[1].end();
            least_freq_used = 1;
        }
    }

private:
    using ValueType = std::uint_fast16_t;
    ValueType capacity;
    ValueType size;
    ValueType least_freq_used = 0;
    std::unordered_map<ValueType, std::list<ValueType>> keys;
    std::unordered_map<ValueType, std::pair<ValueType, ValueType>> values;
    std::unordered_map<ValueType, std::list<ValueType>::iterator>iters;

    inline void update(const int key) {
        const ValueType freqency = values[key].second;
        const auto& iter = iters[key];
        values[key].second++;
        keys[freqency].erase(iter);
        keys[freqency + 1].emplace_back(key);
        iters[key] = --keys[freqency + 1].end();

        if (keys[least_freq_used].empty()) {
            least_freq_used++;
        }
    }
};

值得注意的是，双向链表是实现 LFU 缓存的正确方法。这是讨论板中基于 DLL 的有效解决方案之一：

struct DListNode {
    int key;
    int value;
    int freq;
    DListNode* prev;
    DListNode* next;

    DListNode(int k, int v) {
        key = k;
        value = v;
        freq = 1;
        prev = next = nullptr;
    }
};

struct DList {
    DListNode* sentinel;
    int size;

    DList() {
        size = 0;
        sentinel = new DListNode(-1, -1);
        sentinel->prev = sentinel->next = sentinel;
    }

    void prepend(DListNode* node) {
        node->next = sentinel->next;
        node->prev = sentinel;
        sentinel->next->prev = node;
        sentinel->next = node;
        ++size;
    }

    DListNode* pop(DListNode* node = nullptr) {
        if (size == 0) {
            return nullptr;
        }

        if (node == nullptr) {
            node = sentinel->prev;
        }

        node->prev->next = node->next;
        node->next->prev = node->prev;
        --size;
        return node;
    }
};

struct LFUCache {
    unordered_map<int, DListNode*> nodes;
    unordered_map<int, DList*> freqs;
    int capacity;
    int min_freq;

    LFUCache(int capacity) {
        this->capacity = capacity;
        min_freq = 0;
    }

    void _update(DListNode* node) {
        if (freqs.find(node->freq) == freqs.end()) {
            freqs[node->freq] = new DList();
        }

        if (freqs.find(node->freq + 1) == freqs.end()) {
            freqs[node->freq + 1] = new DList();
        }

        freqs[node->freq]->pop(node);

        if (min_freq == node->freq && freqs[node->freq]->size == 0) {
            ++min_freq;
        }

        ++node->freq;
        freqs[node->freq]->prepend(node);
    }

    int get(int key) {
        if (nodes.find(key) == nodes.end()) {
            return -1;
        }

        DListNode* node = nodes[key];

        _update(node);

        return node->value;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        if (nodes.find(key) != nodes.end()) {
            DListNode* node = nodes[key];
            _update(node);
            node->value = value;

        } else {
            if (nodes.size() == capacity) {
                if (freqs.find(min_freq) == freqs.end()) {
                    freqs[min_freq] = new DList();
                }

                DListNode* node = freqs[min_freq]->pop();

                if (node) {
                    nodes.erase(node->key);
                }
            }

            DListNode* node = new DListNode(key, value);
            nodes[key] = node;

            if (freqs.find(1) == freqs.end()) {
                freqs[1] = new DList();
            }

            freqs[1]->prepend(node);
            min_freq = 1;
        }
    }
};