c++ - Unordered_map，检查滑动窗口中的阈值

Question

我有一个 unordered_map，键代表一小时中的分钟数(从 0 到 60)，值代表那一分钟的事件数。

我想要的是在给定的窗口大小下检查总事件是否高于某个阈值。

例如，假设我有这个 unordered_map=[(4,3),(5,2),(7,2)] 窗口大小 = 3(分钟) 阈值 = 6

所以在这个例子中，我没有一个 3 分钟的窗口包含超过 6 个事件，但是如果窗口大小 = 4 那么就可以。

解决这个问题的最佳方法是什么？我想将 unordered_map 复制到 map ，因为它是键排序的。

接下来我想有一个滑动窗口，每次添加新元素并删除最旧的元素，但我很难做到这一点，因为没有事件的分钟不会显示在 map 中(比如第 6 分钟) )m 我该如何克服这个问题？ (我不想手动添加像 (6,0) 这样的空分钟，因为它们太多了，超过了事件分钟数)

谢谢

Answer 1

我不知道这是否是最佳方法，但我会使用 map 而不是 unordered_map，使用迭代器来连续加载将元素添加到临时 list 中，只要它们在窗口内并从那里检查它们的总事件

std::map<int, int> map{ {4,3},{5,2},{7,2} };
std::list<std::pair<int, int>> list;
const int threshold = 6, window = 4;
for (auto it = map.begin(); it != map.end(); ++it)
{
    while (list.size() > 0 && it->first - list.front().first >= window)
        list.pop_front();
    list.push_back(*it);

    int count = 0;
    for (auto e : list)
        count += e.second;
    if (count > threshold)
        std::cout << "over threshold" << std::endl;
}
std::cout << "end" << std::endl;

试试cloliru !