双端队列设计路由器

题目描述

请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：

• source：生成该数据包的机器的唯一标识符。
• destination：目标机器的唯一标识符。
• timestamp：该数据包到达路由器的时间戳。

类实现接口

实现 Router 类：

• Router(int memoryLimit) 初始化路由器对象，并设置固定的内存限制。memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。

  注意：如果添加一个新数据包会超过这个限制，则必须移除 最旧的（即最早到达的）数据包以腾出空间。

• bool addPacket(int source, int destination, int timestamp) 将具有给定属性的数据包添加到路由器。

• 如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为 重复数据包，返回 false。
• 如果数据包成功添加（即不是重复数据包），返回 true。

• int[] forwardPacket() 以 FIFO（先进先出） 顺序转发下一个数据包。

• 从存储中移除该数据包。
• 以数组 [source, destination, timestamp] 的形式返回该数据包。
• 如果没有数据包可以转发，则返回空数组 []。

• int getCount(int destination, int startTime, int endTime) 返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。

约束条件

1. 对于 addPacket 的调用，其 timestamp 是按 非递减 顺序给出的。
2. memoryLimit 是一个正整数。
3. 必须保证所有操作的效率，尤其是范围查询 getCount。

---

示例运行逻辑

输入：

addPacket(1, 10, 100) -> true
addPacket(2, 10, 105) -> true
addPacket(1, 10, 100) -> false (重复)
getCount(10, 100, 103) -> 1 (只有第一个包在范围内)
forwardPacket() -> [1, 10, 100]
getCount(10, 100, 103) -> 0 (包已转发)

---

思路

• 去重：使用 HashSet<Tuple> 存储当前在内存中的包属性。
• 内存淘汰与转发：使用 Deque（双端队列）维持插入顺序。由于时间戳是非递减的，队首永远是最旧的包。
• 范围查询：为每个 destination 维护一个升序的 List<timestamp>。利用时间戳递增的特性，结合 二分查找 (Binary Search) 即可在 $O(\log N)$ 时间内完成计数。

代码

struct TupleHash{
    template<typename T>
    static void hash_combine(size_t& seed, const T& v){
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    size_t operator()(const tuple<int,int,int>& t) const {
        auto& [a,b,c] = t;
        size_t seed = 0;
        hash_combine(seed,a);
        hash_combine(seed,b);
        hash_combine(seed,c);
        return seed;
    }
};

class Router {
    int memory_limit;
    queue<tuple<int,int,int>> packet_q;
    unordered_set<tuple<int,int,int>, TupleHash> packet_set;
    unordered_map<int,deque<int>> dest_to_timestamps;
public:
    Router(int memoryLimit) {
        memory_limit = memoryLimit;
    }

    bool addPacket(int source, int destination, int timestamp) {
        auto packet = tuple(source,destination,timestamp);
        if (!packet_set.insert(packet).second){
            return false;
        }
        if (packet_q.size() == memory_limit){
            forwardPacket();
        }
        packet_q.push(packet);
        dest_to_timestamps[destination].push_back(timestamp);
        return true;
    }

    vector<int> forwardPacket() {
        if (packet_q.empty()){
            return {};
        }
        auto packet = packet_q.front();
        packet_q.pop();
        packet_set .erase(packet);
        auto [source, destination, timestamp] = packet;
        dest_to_timestamps[destination].pop_front();
        return {source,destination,timestamp};
    }

    int getCount(int destination, int startTime, int endTime) {
        auto& timestamps = dest_to_timestamps[destination];
        auto left = ranges::lower_bound(timestamps,startTime);
        auto right = ranges:: upper_bound(timestamps,endTime);
        return right - left;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */