For循环退出条件与地图迭代器

Question

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

现在，键值映射看起来像这样 -

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

Objective:

计算具有给定前缀的键值的总和。示例：sum("ap") 应该 return 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 的过程中变为假，从而计算出不正确的总和？

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

感谢任何形式的帮助。

Answer 1

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

我们有 std::map 这是一个关联容器，并根据提供的比较功能进行排序。对于您的地图（即 std::map<std:.string, int>），它将根据 std::string（即键）进行排序。

所以你的地图已经订购了：

{["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 指向映射条目 ["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;）。由于我们从排序的可能前缀开始，循环的结果将是正确的。

For循环退出条件与地图迭代器

For loop exit condition with map iterator

c++

algorithm

loops

stdmap

c++-standard-library