Why is this code flagged as having performance issue by static analysis tool?

Question

I'm running cppcheck tool on some code and it reports me a performance issue in some code verifying a map does not have a value before inserting a new one.

I isolated the code in a MCVE snippet (that makes no sense...but illustrates the issue):

std::map<int, float*> myMap;
myMap[1] = new float(3.0f);

for ( size_t pos = 0; pos != 10; ++pos )
{
    if ( myMap.find( pos ) == myMap.end() )
    {
        myMap[pos] = new float(4.0f);
    }
}

CppCheck reports (performance,ID=stlFindInsert) Searching before insertion is not necessary.

Actuaually, it is necessary to prevent leak by replacing the old value by a new one...and by the way you may not want to replace the old value if any....

How am I supposed to write the code better to prevent this performance issue?

Answer 1

You actually do 2 look-ups whereas only 1 is needed.

You can use insert/emplace instead (and to avoid memory leak, insert nullptr instead and overwrite it):

std::map<int, float*> myMap;
myMap[1] = new float(3.0f);

for ( size_t pos = 0; pos != 10; ++pos )
{
    if (auto [it, inserted] = myMap.emplace(pos, nullptr); inserted)
    {
        it->second = new float(4.0f);
    }
}

Another way, if you didn't insert default value in the map before might be

std::map<int, float*> myMap;
myMap[1] = new float(3.0f);

for ( size_t pos = 0; pos != 10; ++pos )
{
    auto& pointer = myMap[pos]; // operator [] does the default instertion,
                                // if not already present
    if (pointer == nullptr)
    {
        pointer = new float(4.0f);
    }
}

Answer 2

To avoid a double map lookup you can search for the item using equal_range, then using insert with passing the result the iterator hint.

https://en.cppreference.com/w/cpp/container/map/equal_range

https://en.cppreference.com/w/cpp/container/map/insert

The result is that you only pay the logarithmic time to insert the item for the equal_range call, while insert should happen in amortized constant time