计数数量内的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。