5

std::multimap::equal_range()我使用and遇到了以下问题insert()。

根据cplusplus.com和cppreference.com，std::multimap::insert不会使任何迭代器无效，但以下代码会导致无限循环：

#include <iostream>
#include <map>
#include <string>

int main(int argc, char* argv[])
{
    std::multimap<std::string,int> testMap;
    testMap.insert(std::pair<std::string,int>("a", 1));
    testMap.insert(std::pair<std::string,int>("a", 2));
    testMap.insert(std::pair<std::string,int>("a", 3));

    auto range = testMap.equal_range(std::string("a"));
    for (auto it = range.first; it != range.second; ++it)
    {
        testMap.insert(std::pair<std::string,int>("b", it->second));
        // this loop becomes infinite
    }

    // never gets here
    for (auto it = testMap.begin(); it != testMap.end(); ++it)
    {
        std::cout << it->first << " - " << it->second << std::endl;
    }
    return 0;
}

目的是使用特定键（在本例中为“a”）获取多图中的所有现有项目，并将它们复制到第二个键（“b”）下。在实践中，第一个循环永远不会退出，因为it永远不会匹配range.second。处理完映射中的第三个元素后，++it让迭代器指向新插入的第一个元素。

我已经用 VS2012、Clang 和 GCC 尝试过这个，所有编译器似乎都发生了同样的事情，所以我认为它是“正确的”。我是否对“没有迭代器或引用无效。”这句话读得太多了？end()在这种情况下不算作迭代器？

4

3 回答 3

5

multimap::equal_range返回 a pair，在这种情况下，它的第二个元素是指向过去元素的迭代器（“这是容器的过去结束值”[container.requirements.general]/6）。

我将稍微重写代码以指出一些事情：

auto iBeg = testMap.begin();
auto iEnd = testMap.end();

for(auto i = iBeg; i != iEnd; ++i)
{
    testMap.insert( std::make_pair("b", i->second) );
}

在这里，iEnd包含一个过去的迭代器。调用multimap::insert不会使这个迭代器失效；它仍然是一个有效的结束迭代器。因此循环等效于：

for(auto i = iBeg; i != testMap.end(); ++i)

如果您继续添加元素，这当然是一个无限循环。

于 2013-10-16T00:51:20.487 回答
2

结束迭代器range.second不会失效。

循环无限的原因是循环体的每次重复：

  • 在 map 的末尾插入一个新元素，从而将it与 end 之间的距离增加一（因此，在此插入之后，range不再代表equal_rangefor 键"a"，因为您在它所代表的范围内插入了一个新键，从第一个"a"到容器的末尾）。
  • increments ，将与 endit之间的距离减一。it

因此，it永远不会到达终点。

以下是我可能编写您想要的循环的方式：

for (auto it = testMap.lower_bound("a"); it != testMap.end() && it->first == "a"; ++it)
{
     testMap.insert(std::pair<std::string,int>("b", it->second));
}
于 2013-10-16T00:51:59.733 回答
0

使其按预期工作的解决方案（随时改进，这是一个社区 wiki）

auto range = testMap.equal_range(std::string("a"));
if(range.first != range.second)
{
    --range.second;
    for (auto it = range.first; it != std::next(range.second); ++it)
    {
        testMap.insert(std::pair<std::string,int>("b", it->second));
    }
}
于 2013-10-16T01:01:38.020 回答