Is valgrind crazy or is this is a genuine std map iterator memory leak?

Question

Well, I'm very new to Valgrind and memory leak profilers in general. And I must say it is a bit scary when you start using them cause you can't stop wondering how many leaks you might have left unsolved before!

To the point, as I'm not an experienced in c++ programmer, I would like to check if this is certainly a memory leak or is it that Valgrind is doing a false positive?

typedef std::vector<int> Vector;
typedef std::vector<Vector> VectorVector;
typedef std::map<std::string, Vector*> MapVector;
typedef std::pair<std::string, Vector*> PairVector;
typedef std::map<std::string, Vector*>::iterator IteratorVector;

VectorVector vv;
MapVector m1;
MapVector m2;

vv.push_back(Vector());
m1.insert(PairVector("one", &vv.back()));

vv.push_back(Vector());
m2.insert(PairVector("two", &vv.back()));

IteratorVector i = m1.find("one");
i->second->push_back(10);
m2.insert(PairVector("one", i->second));

m2.clear();
m1.clear();
vv.clear();

Why is that? Shouldn't the clear command call the destructor of every object and every vector?

Now after doing some tests I found different solutions to the leak:

1) Deleting:

i->second->push_back(10);

2) Adding:

delete i->second;

3) Deleting the second

vv.push_back(Vector());
m2.insert(PairVector("two", &vv.back()));

Using solution 2) makes Valgring print: 10 allocs, 11 frees Is that OK?

As I'm not using new why should I delete?

Thanks, for any help!

Answer 1

You have undefined behaviour here:

m1.insert(PairVector("one", &vv.back()));

vv.push_back(Vector());

Insert invalidates iterators and references pointing into the vector, which means also the pointer you stored in the map is basically pointing to some black hole after the insert.

makes Valgring print: 10 allocs, 11 frees Is that OK?

It's strange, doesn't it also print something about double-frees?

For the solution, I would suggest using a different container than vector (eg. list, or deque, whose mutating functions invalidate iterators, but not references). Or you could store pointers (preferably smart, but could be ordinary) to data in the vector so the adress of actual data is stable.

Answer 2

You are doing some dangerous things with vectors here. You are keeping pointers to vectors that may become invalid during program execution.

std::vector<>::push_back() may invalidate any iterators or references to the std::vector<> if it was already full. Since std::vector<> guarantees that its contents will be stored contiguously (so you can use it in place of an array), when it needs more memory it has to copy itself to a different memory block and the original becomes invalid.

This means that all calls to push_back() in your code (excepting for the first one) lead to undefined behaviour, so anything can be happening here.

Answer 3

Basically this line is causing the problem:

i->second->push_back(10);

This is because i->second may have become invalid when you did:

vv.push_back(Vector());

The second time.

There is no need to call clear. When the vv object goes out of scope it will correctly destroy all the objects. Also all the maps don't own any vectors so their destructors do not affect the vectors they point at. Thus your use of clear is not required.

If you want to keep the same overall solution create a list of vectors for your vv object. Then insertion into the list will not affect already existing members and you r maps will work correctly.

std::list<Vector> vv;  // insertion into this will not invalidate any other members.
                       // Thus any pointers to members you have will not become invalidated.

Personally I think you are over complicating things.
I think you can achieve the same results by vastly simplifying this.
If the vectors are not referenced by multiple map elements then just put the vector into the map.

std::map<std::string, std::vector<int> >    m1;

m1["one"].push_back(10);
m1["two"].push_back(20);