CODEWITHSUNDEEP
c++dictionarystl
ComicSansMS
ComicSansMS

Reputation: 54589

Searching in a map: Member vs. non-member lower_bound

I need to look up two elements in a std::map. Since my map is sparse, I might not have an entry for every key, so I use lower_bound for lookup. For sake of simplicity, let's assume that I can always find two elements like this and that they are always distinct.

The quickest solution would of course be:

auto it1 = my_map.lower_bound(k1);
auto it2 = my_map.lower_bound(k2);

However, I know that the element at index k2 is located between begin and the element at index k1. Therefore, I was thinking of using std::lower_bound for the second lookup to avoid having to search the full range again:

auto it1 = my_map.lower_bound(k1);
auto it2 = std::lower_bound(begin(my_map), it1, k2);

Any opinions on the second solution? Complexity-wise it should be better, but it's a lot less pleasant to look at than the original code and I'm wondering whether it is worth bothering at all. Also, should I expect any drawbacks due to the fact that I'm using the non-member lower_bound for the second call?

Upvotes: 1

Views: 68

Answers (1)

Dave S
Dave S

Reputation: 21058

The primary drawback is that the non-member std::lower_bound has to rely on the bidirectional iterators that map provides. So while it's able to perform O(log(n)) comparisons, it still has to perform O(n) iterations.

On the other hand, the member lower_bound() is aware of the internal structure of the map, which is typically some sort of binary tree. This means that's capable of traversing in ways the standard algorithm cannot.

Upvotes: 3

Related Questions