unordered_queue

unordered_queue 是一个用于存储元素的数据结构，它类似于队列（queue），但是不保证元素的顺序。也就是说，当你从 unordered_queue 中取出元素时，你无法确定你会得到哪个元素。

unordered_queue 的特点是插入和删除操作的时间复杂度都是 O(1)，即常数时间。这是因为 unordered_queue 使用了哈希表（hash table）来存储元素，哈希表的插入和删除操作都可以在常数时间内完成。

unordered_queue 适用于那些对元素顺序没有要求，只关心插入和删除性能的场景。如果你需要保证元素按照特定顺序进行访问，你可以考虑使用其他数据结构，比如有序队列（ordered queue）或者链表（linked list）。

相关问题

用priority_queue unordered_map实现lfu

LFU（Least Frequently Used）是一种缓存淘汰算法，它会淘汰最不经常使用的缓存块，以腾出空间给更频繁使用的缓存块。

在实现 LFU 算法时，可以使用一个哈希表（unordered_map）来存储缓存块及其对应的使用次数，使用一个优先队列（priority_queue）来按照使用次数从小到大排列缓存块。当需要淘汰缓存块时，从优先队列中取出使用次数最小的缓存块，如果有多个缓存块使用次数相同，则取最久未使用的缓存块。

下面是使用 priority_queue 和 unordered_map 实现 LFU 算法的示例代码：

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

struct CacheNode {
    int key;
    int value;
    int freq; // 使用次数
    int timestamp; // 最后使用时间
    CacheNode(int k, int v, int f, int t) : key(k), value(v), freq(f), timestamp(t) {}
};

// 定义优先队列的比较函数
struct CacheNodeCompare {
    bool operator() (const CacheNode& a, const CacheNode& b) {
        if (a.freq == b.freq) {
            return a.timestamp > b.timestamp;
        } else {
            return a.freq > b.freq;
        }
    }
};

class LFUCache {
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        timestamp = 0;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        } else {
            CacheNode node = cache[key];
            node.freq++;
            node.timestamp = ++timestamp;
            cache[key] = node;
            freq_queue.push(node);
            return node.value;
        }
    }

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

        if (cache.find(key) == cache.end()) {
            if (cache.size() == capacity) {
                while (!freq_queue.empty() && cache.find(freq_queue.top().key) == cache.end()) {
                    freq_queue.pop();
                }
                if (!freq_queue.empty()) {
                    CacheNode node = freq_queue.top();
                    freq_queue.pop();
                    cache.erase(node.key);
                }
            }
            CacheNode node(key, value, 1, ++timestamp);
            cache[key] = node;
            freq_queue.push(node);
        } else {
            CacheNode node = cache[key];
            node.value = value;
            node.freq++;
            node.timestamp = ++timestamp;
            cache[key] = node;
            freq_queue.push(node);
        }
    }

private:
    int capacity;
    int timestamp;
    unordered_map<int, CacheNode> cache;
    priority_queue<CacheNode, vector<CacheNode>, CacheNodeCompare> freq_queue;
};

int main() {
    LFUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 输出 1
    cache.put(3, 3);
    cout << cache.get(2) << endl; // 输出 -1
    cout << cache.get(3) << endl; // 输出 3
    cache.put(4, 4);
    cout << cache.get(1) << endl; // 输出 -1
    cout << cache.get(3) << endl; // 输出 3
    cout << cache.get(4) << endl; // 输出 4
    return 0;
}

在上面的代码中，我们定义了一个 `CacheNode` 结构体，用来存储缓存块的键值、使用次数和最后使用时间。我们还定义了一个 `CacheNodeCompare` 结构体，用来定义优先队列的比较函数，按照使用次数从小到大排列缓存块，如果使用次数相同，则按照最后使用时间从小到大排列。最后，我们使用一个 `unordered_map` 来存储缓存块，使用一个 `priority_queue` 来按照使用次数从小到大排列缓存块。

在 `get` 方法中，如果缓存中不存在指定的键，则返回 -1；否则，将缓存块的使用次数加一，最后使用时间更新，并将缓存块重新加入优先队列中，然后返回缓存块的值。

在 `put` 方法中，如果缓存中不存在指定的键，则需要判断缓存是否已满，如果已满，则从优先队列中取出使用次数最小的缓存块，并从缓存中删除它。然后创建一个新的缓存块，并将它加入缓存和优先队列中。如果缓存中存在指定的键，则更新缓存块的值、使用次数和最后使用时间，并将缓存块重新加入优先队列中。

最后，我们在 `main` 函数中测试了 LFU 算法的实现。当缓存容量为 2 时，我们先将键值对 (1, 1) 和 (2, 2) 存入缓存中，然后从缓存中取出键为 1 的值，输出 1。接着，我们再将键值对 (3, 3) 存入缓存中，此时键为 2 的缓存块已经被淘汰了。接下来，我们分别从缓存中取出键为 2 和 3 的值，都能够返回 -1 和 3，说明 LFU 算法的实现是正确的。

上面代码不使用#include <queue> #include <unordered_map>，来实现

那么可以使用手动实现队列和哈希表来代替STL中的queue和unordered_map。

队列可以使用数组或链表来实现，这里以数组为例：

const int MAXN = 1e5; // 队列最大容量
int q[MAXN], front = 0, rear = -1;

bool empty() {
    return front > rear;
}

void push(int x) {
    q[++rear] = x;
}

void pop() {
    ++front;
}

int front() {
    return q[front];
}

哈希表可以使用数组或链表来实现，这里以数组为例：

const int MAXN = 1e6; // 哈希表最大容量
int h[MAXN], idx = 0;

void insert(int x) {
    int pos = (x % MAXN + MAXN) % MAXN; // 计算哈希值
    for (int i = h[pos]; i != -1; i = e[i].next) { // 遍历链表
        if (e[i].key == x) return; // 已经存在
    }
    e[idx].key = x; // 插入新节点
    e[idx].next = h[pos];
    h[pos] = idx++;
}

bool find(int x) {
    int pos = (x % MAXN + MAXN) % MAXN; // 计算哈希值
    for (int i = h[pos]; i != -1; i = e[i].next) { // 遍历链表
        if (e[i].key == x) return true; // 找到了
    }
    return false; // 没有找到
}

这里需要注意的是，要实现一个完整的哈希表，还需要定义一个节点结构体`struct Node { int key, next; } e[MAXN]`来存储节点信息，其中`key`表示键值，`next`表示指向下一个节点的指针。同时，初始化哈希表时需要将所有的`h[i]`初始化为-1，表示链表为空。