For loop exit condition with map iterator

user_7225236 0
Viewed 124

I have a std::map<str,int> my_map

Right now, the key-value mapping looks like this -

{["apple",3],["addition",2],["app",7],["adapt",8]}

Objective:

Calculate the sum of values of keys with a given prefix. Example : sum("ap") should return 10 (3 + 7).

I could implement it with two loops and an if condition. But, I'm trying to understand the following code that's submitted by someone to implement this.

for (auto it = my_map.lower_bound(prefix); 
    it != my_map.end() && it->first.substr(0, n) == prefix;
    it++)

Won't the loop condition become false in the middle of iterating through my_map hence calculating an incorrect sum ?

I don't know how the code is able to give the right result. Why wouldn't the loop exit when it gets to key "addition" while looking for prefix "ap" ?

Any kind of help is appreciated.

stdmap c++-standard-library algorithm loops c++
1 Answers

The loop is completely correct, but not so readable at first sight.

We have std::map which is an associative container and sorted according to the compare function provided. For your map (i.e std::map<std:.string, int>), it will be sorted according to the std::string (i.e key).

So your map is already ordered like :

{["adapt",8], ["addition",2], ....., ["app",7], ["apple",3], .... }

Now let's start with the std::lower_bound:

Returns an iterator pointing to the first element in the range [first, Last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

Meaning at the loop start:

auto it = my_map.lower_bound(prefix);

iterator it is pointing to the map entry ["app",7]. In otherwards the iteration starts from the first possible start.

["app",7], ["apple",3], ....

Now the condition comes in to play:

it != my_map.end() && it->first.substr(0, n) == prefix;

The first one to see whether the iterator is valid (i.e. it != my_map.end()). The second one checks whether the prefix is the same as the key start (i.e. it->first.substr(0, n) == prefix;). Since we start from the sorted possible prefix start, the outcome of the loop will be correct.

user_96098400
Related