c++ - 用于存储数字窗口并返回唯一数字的标准容器/库？

Question

我正在寻找具有以下功能的 C++ 标准容器/库:

1. 存储数字的窗口(入队和出队就足够了)。
2. 返回窗口中唯一数字的数量。

它可以是合并 std::queue 和 std::set 功能的东西。

编辑:示例预期操作。对于此序列 '1 2 3 3 4 4 5 5 6 6 7 7 8' 和窗口大小 2，我们将执行以下步骤:

1. 窗口 = [1 2]，唯一的 = 2
2. 窗口 = [2 3]，唯一的 = 2
3. 窗口 = [3 3]，唯一的 = 1
4. 窗口 = [3 4]，唯一的 = 2
5. 等等...

Answer 1

你想要两个容器:

• 一个deque<number>按顺序存储窗口中的数字；
• 一个map<number, size_t> (或 unordered_map 如果可用)存储每个唯一号码的计数。

那么你的操作是:

void push(number n) {
    deque.push_back(n);
    ++map[n];
}

void pop() {
    auto found = map.find(deque.front());
    assert(found != map.end());
    assert(found->second > 0);
    if (--found->second == 0) {
        map.erase(found);
    }
    deque.pop_front();
}

size_t count_unique() {
    return map.size();
}