CODEWITHSUNDEEP
c++performancedictionarymemory-leaks
Richard Dally
Richard Dally

Reputation: 1450

Fixing collision memory leak in std::map

I encountered this kind of issue: a possible memory leak.
Imagine if you store two different heap pointers for same key.

#include <map>

std::map<int, int*> myMap;

void Store(int key, int* value)
{
    myMap[key] = value;
}

int main()
{
   Store(42, new int(42));
   Store(35, new int(35));
   delete myMap[42];
   delete myMap[35];
}

I thought about fixing that way:

#include <map>

std::map<int, int*> myMap;

void Store(int key, int* value)
{
    auto it = myMap.find(key);
    if (it != myMap.end()))
    {
        delete it->second;
        it->second = value;
    }
    else
    {
        myMap[key] = value;
    }
}

int main()
{
   Store(42, new int(42));
   Store(35, new int(35));
   delete myMap[42];
   delete myMap[35];
}

But there are two logarithmic look-ups instead of one now...
Then I thought about this following code,

#include <map>

std::map<int, int*> myMap;

void Store(int key, int* value)
{
    auto& mappedValue = myMap[key];
    if (mappedValue == nullptr)
    {
        mappedValue = value;
    }
    else
    {
        delete mappedValue;
        mappedValue = value;
    }
}

int main()
{
   Store(42, new int(42));
   Store(35, new int(35));
   delete myMap[42];
   delete myMap[35];
}

but how can I be certain mappedValue will always point to nullptr if there is no associated value ? What would you suggest to tackle memory leak and stick with logarithmic complexity ?

EDIT: refactoring is very costy, I'm looking for a solution without smart pointers.

Upvotes: 0

Views: 1235

Answers (4)

Mauri
Mauri

Reputation: 1245

why not using map::insert

auto res = myMap.insert(std::make_pair(key,value));
if ( ! res.second ) {
    delete res.first->second;
    res.first->second = value;
}

Upvotes: 1

Guillaume Racicot
Guillaume Racicot

Reputation: 41750

With the new standard c++11, std::unique_ptr is your friend. It has no overhead whatsoever, and provides memory safety:

std::map<int, std::unique_ptr<int>> myMap;

void Store(int key, int* value)
{
    myMap[key] = std::unique_ptr<int>{value};
}

int main()
{
   Store(42, new int(42));
   Store(35, new int(35));
}

No memory leak with that. If you have access to c++14, you could even do this:

std::map<int, std::unique_ptr<int>> myMap;

void Store(int key, std::unique_ptr<int> value)
{
    myMap[key] = std::move(value);
}

int main()
{
   Store(42, std::make_unique<int>(42));
   Store(35, std::make_unique<int>(35));
}

No new, no delete. No memory leak and safe.

Upvotes: 1

Brandlingo
Brandlingo

Reputation: 3142

but how can I be certain mappedValue will always point to nullptr if there is no associated value ?

If operator[] adds a new element it is value-initialized. For non-class types as pointers are this is equivalent to zero-initialization which in turn is a nullptr in case of pointers. See std::map::operator[].

Upvotes: 3

Ami Tavory
Ami Tavory

Reputation: 76297

You might consider using the RAII in the form of smart pointers, and instead define your map as

#include <map>
#include <memory>

std::map<int, std::shared_ptr<int>> myMap;

(For this to work make sure to configure your compiler to c++11 mode.)

Your map becomes something like: map integers to a pointer-like object that will take care of deallocation.

Upvotes: 2

Related Questions