Time complexity of vector functions are actually faster than u

I can't understand logic. I have two containers with same element count: vector and unordered_map.

I'm using function that checks time complexity of some function and returns value in milliseconds

auto funcComplexity = [](auto&& func, auto&&... params)
{
    const auto& start = high_resolution_clock::now();
    for (auto i = 0; i < 100;   i) 
    {
        // function invocation using perfect forwarding
        std::forward<decltype(func)>(func)(std::forward<decltype(params)>(params)...);
    }
    const auto& stop = high_resolution_clock::now();
    
    return duration_cast<duration<double, std::milli>>(stop - start).count();
};

When I erase an element from the middle of vector, it actually gives me less time than erasing element from unordered_map

void iterateUMap(std::unordered_map<int, Test> map)
{
    map.erase(500);
}

void iterateVector(std::vector<Test> vector)
{
    std::remove_if(vector.begin(), vector.end(), [](Test& val)
        {
            return val.mId == 500;
        });
}

int main()
{
    auto funcComplexity = [](auto&& func, auto&&... params)
    {
        const auto& start = high_resolution_clock::now();
        for (auto i = 0; i < 10000;   i) 
        {
            // function invocation using perfect forwarding
            std::forward<decltype(func)>(func)(std::forward<decltype(params)>(params)...);
        }
        const auto& stop = high_resolution_clock::now();
    
        return duration_cast<duration<double, std::milli>>(stop - start).count();
    };

    std::unordered_map<int, Test> uMap;

    for(int i = 0; i < 1000; i  )
    {
        uMap.try_emplace(i, Test(i));
    }

    std::vector<Test> vector;
    vector.reserve(1000);
    for (int i = 0; i < 1000; i  )
    {
        vector.emplace_back(i);
    }

    cout << funcComplexity(iterateUMap, uMap) << endl;

    cout << endl;

    cout << funcComplexity(iterateVector, vector) << endl;
      
    return 0;
}

So the output of those two functions:

For vector is: 52.6565 milliseconds

For U_Map is : 6740.64 milliseconds

Why do erasing from u_map is actually slower than erasing from vector? The same thing happening when I just want to get element. For example:

void iterateUMap(std::unordered_map<int, Test> map)
{
    map[500].DoSomething();
}

void iterateVector(std::vector<Test> vector)
{
    for (auto& value : vector)
    {
        if(value.mId == 500)
        {
            value.DoSomething();
            break;
        }
    }
}

CodePudding user response：

You've just discovered one of the secrets about modern computer hardware.

Modern CPUs are very, very good at accessing memory linearly, you know, like how data in vectors happens get stored. Accessing X linear memory addresses is several orders of magnitude faster than access X random memory addresses; and X does not have to become very big before this is observed.

This is because, in general, memory gets retrieved from RAM in comparatively large blocks, and then stored in fast, on-CPU cache. Large blocks memory blocks get cached, accessing the next byte or word will then hit the fast on-CPU cache, and not result in a comparatively slow RAM access. And even before the next byte or word gets accessed, while the CPU is busy digesting the first couple of bytes a different part of CPU will proactively fetch the next cache line, anticipating future memory accesses.