Fixing collision memory leak in std::map

Question

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.

"a possible memory leak." You can strengthen that statement. The first piece of code as a *definite* memory leak. — eerorika, Oct 26 '15 at 13:26
the non-use of smart pointers led you here, which had a time cost. Every change you make will require debugging and tests to prove correct deallocation (and non-use of deallocated objects). Refactoring to use a smart pointer will eventually prove to be an order of magnitude *less* costly. — Richard Hodges, Oct 26 '15 at 13:50

score 3 · Accepted Answer · answered Oct 26 '15 at 13:33

3

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[].

answered Oct 26 '15 at 13:33

Brandlingo

2,817
1
22
34

Wonderful, is this stated as is in Standard ? – Richard Dally Oct 26 '15 at 13:34
1

For value-initialization see §8.5 8.4, zero-initialization is §8.5 6.1 (§4.10 1 states *A null pointer constant is an integer literal (2.13.2) with value zero*) (from N4296) – Brandlingo Oct 26 '15 at 13:44
1

@LeFlou: §23.4.4.3: *`T& operator[](const key_type& x);` (...) If there is no key equivalent to `x` in the map, inserts `value_type(x, T())` into the map.* – Christian Hackl Oct 26 '15 at 13:44

score 2 · Answer 2 · edited May 23 '17 at 11:52

2

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.

edited May 23 '17 at 11:52

Community

1
1

answered Oct 26 '15 at 13:24

Ami Tavory

74,578
11
141
185

Thank you for this suggestion but I would like to know how to tackle this issue without smart pointers. – Richard Dally Oct 26 '15 at 13:26
In this case, perhaps you should explain what are the settings causing your reluctance to use shared pointers. – Ami Tavory Oct 26 '15 at 13:27
I posted a tiny part of the code, revamped for SO. Refactoring is very costy, I'm looking for another way. – Richard Dally Oct 26 '15 at 13:33

Guillaume Racicot · Answer 3 · 2015-10-26T13:48:34.230

1

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.

edited Oct 26 '15 at 13:48

answered Oct 26 '15 at 13:28

Guillaume Racicot

39,621
9
77
141

This answer is good in spirit but has a lot of errors in it. Neither the first nor the second code example compiles. First of all, even without `std::make_unique`, good practice would be instantiating the `std::unique_ptr` immediately, or just writing your own `make_unique` function. `Store` must not take `int*` but `std::unique_ptr`, and the value must then be inserted into the map using `std::move(value)`. – Christian Hackl Oct 26 '15 at 13:41

Mauri · Answer 4 · 2015-10-26T14:15:10.093

1

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;
}

edited Oct 26 '15 at 14:15

answered Oct 26 '15 at 13:54

Mauri

1,185
1
13
21

This is even shorter, I like it. – Richard Dally Oct 26 '15 at 14:30

Fixing collision memory leak in std::map

4 Answers4