时间戳

首页 > 解决方案 > 带有映射迭代器的循环退出条件

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

问题描述

我有一个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？

任何形式的帮助表示赞赏。

标签： c++algorithmloopsstdmapc++-standard-library

解决方案

循环是完全正确的，但乍一看并不那么可读。

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

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

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

现在让我们从std::lower_bound：

返回一个迭代器，该迭代器指向范围[first, Last) 中不小于（即大于或等于）值的第一个元素，如果没有找到这样的元素，则返回 last。

循环开始时的含义：

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;）相同。由于我们从排序后的可能前缀 start 开始，因此循环的结果将是正确的。

推荐阅读