Counting number of occurrences in a range within an unordered_map

Question

I have my unordered_map set up as:

unordered_map<int, deque<my_struct>> table;

When I read values to my program, I usually do:

 table[int].push_back(obj);

What I want to be able to do is if I'm given 2 integer variables, I want to be able to find the number of keys that occur between the two.

So if in my table I have code like

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

If I execute my search function(which I'm currently trying to write) to look between the key values of 45 and 65, I should have 3 results.

I'm not exactly sure how to go about it in an efficient manner. Any ideas would be helpful. Than you.

It's an unordered_map -- the notion of "things between" is inherently nonsense (it implies there's an order we can use to count between other things!). Any value you obtain may vary between compilers, and can change as you insert items into the unordered_map. If you use a map it's at least a sensible question. — druckermanly
– druckermanly, Commented Nov 6, 2016 at 4:59
Okay, thank you for clearing that up for me! I will look into figuring out how to do this using map instead — MMM
– MMM, Commented Nov 6, 2016 at 5:04

Chris Drew · Accepted Answer · 2016-11-06 22:02:07Z

If you are using a std::unordered_map I don't think you have a choice but to loop over all integers 45 to 65 and use find to check if the key exists in the 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;
}

But this may not be very efficient. If you use a std::map instead the elements are ordered so this can be achieved more efficiently:

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

I've used the std::map::lower_bound function.

Depending on how sparse your map is you might even consider using something like std::vector<std::deque<my_struct>> as a flat map.

Live demo.

Collectives™ on Stack Overflow

Counting number of occurrences in a range within an unordered_map

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related