計數數量內的unordered_map

Question

我有我unordered_map設置爲：

unordered_map<int, deque<my_struct>> table; 

當我讀值，我的計劃，我通常會做：

table[int].push_back(obj); 

我希望能夠做到的是，如果我給了2個整數變量，我希望能夠找到兩個之間發生的鍵的數量。

所以，如果在我的表我有一個像

table[49].push_back(obj); 
    table[59].push_back(obj); 
    table[60].push_back(obj); 

代碼如果我執行我的搜索功能（這我目前正在寫的）的45和65的關鍵值之間的樣子，我應該有3個結果。

我不太確定如何以有效的方式去解決這個問題。任何想法都會有所幫助。比你。

Answer 1

如果您使用的是std::unordered_map我不認爲你有一個選擇，但遍歷所有整數45至65，並使用find檢查的關鍵在unordered_map存在：

using my_table = std::unordered_map<int, std::deque<my_struct>>; 

int count(const my_table& table, int begin, int end) { 
    int sum = 0; 
    for (int i = begin; i != end; ++i) { 
    auto find_result = table.find(i); 
    if (find_result != table.end()) 
     sum++; 
    } 
    return sum; 
} 

但這可能效率不高。如果使用std::map代替元素被排序使得這可以更有效地實現：

using my_table = std::map<int, std::deque<my_struct>>; 

int count(const my_table& table, int begin, int end) { 
    auto begin_itr = table.lower_bound(begin); 
    if (begin_itr == table.end()) 
     return 0; 
    auto end_itr = table.lower_bound(end); 
    return std::distance(begin_itr, end_itr); 
} 

我用過的std::map::lower_bound功能。

根據地圖的稀疏程度，你甚至可以考慮使用類似std::vector<std::deque<my_struct>>這樣的平面地圖。

Live demo。