Using std::map should be deterministic or not?

Question

I'm facing a strange behaviour using Intel C++ compiler 2019 update 5. When I fill a std::map it seems to lead to a non deterministic (?) result. The stl is from VS2019 16.1.6 in which ICC is embedded. I am on Windows 10.0.17134.286.

My code:

#include <map>
#include <vector>
#include <iostream>

std::map<int, int> AddToMapWithDependencyBetweenElementsInLoop(const std::vector<int>& values)
{
    std::map<int, int>  myMap;
    for (int i = 0; i < values.size(); i+=3)
    {
        myMap.insert(std::make_pair(values[i], myMap.size()));
        myMap.insert(std::make_pair(values[i + 1], myMap.size()));
        myMap.insert(std::make_pair(values[i + 2], myMap.size()));
    }
    return myMap;
}

std::map<int, int> AddToMapOnePerLoop(const std::vector<int>& values)
{
    std::map<int, int>  myMap;
    for (int i = 0; i < values.size(); ++i)
    {
        myMap.insert(std::make_pair(values[i], 0));
    }
    return myMap;
}

int main()
{
    std::vector<int> values{ 6, 7,  15, 5,  4,  12, 13, 16, 11, 10, 9,  14, 0,  1,  2,  3,  8,  17 };

    {
        auto myMap = AddToMapWithDependencyBetweenElementsInLoop(values);
        for (const auto& keyValuePair : myMap)
        {
            std::cout << keyValuePair.first << ", ";
        }
        std::cout << std::endl;
    }

    {
        auto myMap = AddToMapOnePerLoop(values);
        for (const auto& keyValuePair : myMap)
        {
            std::cout << keyValuePair.first << ", ";
        }
        std::cout << std::endl;
    }

    return 0;
}

I simply wanted to perform a test so I call directly icl from the command line:

$ icl /nologo mycode.cpp
$ mycode.exe
0, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15, 16, 17,
0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 16, 17

Curious. I expected to have 18 entries and I got 15 and 14 (depending on the insertion method, see the code).

$ icl /nologo /EHsc mycode.cpp
$ mycode.exe
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17,
0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 16, 17

Still curious, now I got 17 and 14 entries rather than 18 and 18!

$ icl /nologo /Od mycode.cpp
$ mycode.exe
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,

Now, with no optimization, I got 18/18, as expected.

My question is two-fold: 1) is it normal to get such results and 2) if it's not (what I suspect) what did I do wrong? I tought a simple call to the compiler would call the std::map::insert() function correctly?

Does the problem lies in the for(){}???

Thanks for helping me understanding this problem and finding a solution!

Answer 1

只是猜测可能有与以下相关的优化for(...; i+=3)

我发现您的用例的项目数量可被 3 整除，但无论如何，我会修复您的代码中的一个错误，以适应更一般的情况：

{
  std::map<int, int>  myMap;
  for (int i = 0; (i + 2) < values.size(); i+=3)  // ignore the possibly incomplete last triplet

我知道它与您的问题没有直接关系，但也许此修复会触发编译器优化器中的某些内容来构建正确的代码。