5

std::multimap::equal_range()と を使用して次の問題に遭遇しました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") を持つ multimap 内のすべての既存のアイテムを取得し、それらを 2 番目のキー ("b") の下に複製することです。実際には、最初のループが決して終了しないため、最初のループは決してit終了しませんrange.second。マップの 3 番目の要素が処理された後++it、新しく挿入された項目の最初の項目を指すイテレータを残します。

VS2012、Clang、および GCC でこれを試してみましたが、すべてのコンパイラで同じことが起こるように見えるので、「正しい」と思います。「No iterators or references are invalidated.」という文を読みすぎていませんか? end()この場合、イテレータとしてカウントされませんか?

4

3 に答える 3

5

multimap::equal_rangepairこの場合、2 番目の要素が終端要素へのイテレータ (「これはコンテナの終端値です」[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 に答える
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 に答える