Unordered_map、スライディングウインドウでスレッショルドをチェックする

Question

私はunordered_mapを持っています。キーは1時間に分（0〜60）を表し、値はその分のイベント数を表します。

私が欲しいのは、合計イベントがある閾値を上回っているかどうかをチェックすることです。例えば

、のは、私はこのunordered_mapを持っているとしましょう= [(4,3),(5,2),(7,2)] ウィンドウサイズ= 3（分） しきい値= 6

ので、この例では、私が6つの以上のイベントで3分のウィンドウを持っていませんしかし、ウィンドウのサイズが= 4だった場合は行います。

これにはどのような方法が最適ですか？私はunordered_mapを地図にコピーすることを考えました。なぜなら、それはキーがソートされているからです。

次は、新しい要素を追加して古いものを削除するたびにスライドするウィンドウがあると思っていましたが、イベントを持たない分がマップに表示されないため分かりにくい6）これをどのように克服するのですか？

があなたの問題のため、この作業を行い

Answer 1

それが最善のアプローチだ場合、私は知りませんが、私は、代わりにunordered_mapの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で試してみてください！

Answer 2

ありがとうございます（彼らはあまりにも多くの、より多くのイベント化分を超えているので、私は手動で（6,0のような空の分）を追加する必要はありませんか）？

size_t cur_idx = 0; 
array<size_t, 3> window; 
auto LoadEventsPerMinute = [&] (size_t minute) { 
    auto it = event_map.find(minute); 
    window[cur_idx] = (it == event_map.end()) ? 0 : it->second; 
    cur_idx = (cur_idx + 1) % window.size(); 
} 

for (size_t i = 0; i < window.size() - 1; i++) { 
    LoadEventsPerMinute(i); 
} 

for (size_t i = window.size() - 1; i < 60; i++) { 
    LoadEventsPerMinute(i); 
    size_t num_events = window[0] + window[1] + window[2]; 
    if (num_events > threshold) { 
    // Do your thing 
    } 
}