CODEWITHSUNDEEP
c++maps
user1106831
user1106831

Reputation:

std::map, std::equal_range, and comparison function

If I have a map/multimap with keys inserted using a comparison function (functor), is it possible to use map::equal_range with a comparison function as well? For instance, if I have a std::map m, and keys:

sometype a.getVal == 101
sometype b.getVal == 112 <-first pair (using equal_range)
sometype c.getVal == 113
sometype d.getVal == 121 <-second pair (using equal_range)

and I wanted to get a range/set of keys 11* is that possible?

Upvotes: 2

Views: 2494

Answers (2)

Gorpik
Gorpik

Reputation: 11028

There is a good reason why you cannot use map::equal_range() with a custom comparer: it would defeat the asociativity of the container. It can be done, but the algorithm would be O(n) instead of O(log(n)), since it would have to compare all map elements regardless of their position.

I think the best solution for your problem would be a custom function that uses map::lower_bound() and map::upper_bound() to find your interval limits. Something like:

typedef std::map<int>::iterator Iter;
std::pair<Iter, Iter> CustomEqualRange (const std::map<int>& theMap, int lowerBound, int range)
{
  Iter lower = theMap.lower_bound(lowerBound);
  Iter upper = theMap.upper_bound(lowerBound + range);
  return std::make_pair(lower, upper);
}

Upvotes: 1

Rob Kennedy
Rob Kennedy

Reputation: 163287

The equal_range function doesn't offer that, but you could call lower_bound passing a value with getVal == 110, and upper_bound passing a value with getVal == 120. That pair of iterators should represent all values in the half-open range [110, 120).

Upvotes: 0

Related Questions