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

You want two containers:

• a deque<number> to store the numbers in the window in order;
• a map<number, size_t> (or unordered_map if available) to store the count of each unique number.

Then your operations are:

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();
}

Answer 2

Thanks to Mike, here is the complete class:

#include <stdio.h>
#include <assert.h>

using namespace std;
#include "map"
#include "deque"

class window{
    private:
        std::deque<int> numbers;
        std::map<int, size_t> unique;
    public:
        window(){};
        void push(int n) {
            numbers.push_back(n);
            ++unique[n];
        }

        void pop() {
            map<int, size_t>::iterator found = unique.find(numbers.front());
            assert(found != unique.end());
            assert(found->second > 0);
            if (--found->second == 0) {
                unique.erase(found);
            }
            numbers.pop_front();
        }

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

And this is the test case:

int main(){
    // example list '1 2 3 3 4 4 5 5 6 6 7 7 8'
    int list[13] = {1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8};
    window w1;
    w1.push(list[0]);w1.push(list[1]);

    int i=0;
    printf("The list is: ");
    for(i=0; i<13; i++){
        printf("%d ",list[i]);
    }
    printf("\n");

    for(i=0; i<11; i++){
        printf("[%d] Unique ones: %d\n",i+1,w1.count_unique());
        w1.push(list[i+2]);w1.pop();
    }

    return 0;
}