c++ - 带映射迭代器的 For 循环退出条件

Question

我有一个std::map<str,int> my_map

现在，键值映射如下所示 -

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

目标:

计算具有给定前缀的键值的总和。 示例:sum("ap")应该返回10 (3 + 7) .

我可以用两个循环和一个 if 条件来实现它。但是，我试图理解某人提交的以下代码来实现此功能。

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

在迭代my_map的过程中循环条件不会变成假吗？因此计算出错误的总和？

我不知道代码如何能够给出正确的结果。为什么循环在查找前缀“addition”时到达键“ap”时不会退出？

感谢任何形式的帮助。

Answer 1

循环完全正确，但乍一看不太可读。

我们有std::map它是一个关联容器，根据提供的比较函数进行排序。对于您的 map (即 std::map<std:.string, int> )，它将根据 std::string 进行排序(即 key )。

所以你的 map 已经排序如下:

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

现在让我们从 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.

循环开始时的含义:

auto it = my_map.lower_bound(prefix);

迭代器it指向 map 条目["app",7] 。在其他情况下，迭代从第一个可能的开始开始。

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

现在条件开始发挥作用:

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

第一个查看迭代器是否有效(即 it != my_map.end() )。 第二个检查前缀是否与键开始相同(即 it->first.substr(0, n) == prefix; )。由于我们从已排序的可能前缀开始开始，因此循环的结果将是正确的。