Flaw in g++ implementation of stl vector

[christophe (dot) poucet (at) gmail (dot) com]

Hello,

I noticed there is a flaw in the vector implementation of g++ (3.4).
Basically when you erase an element from a vector, it calls the wrong
destructor. In most cases this is not such a big issue, but if one
were to store a class holding a resource, then the wrong resource would
be freed. Here is a test case to show what I mean: (Disregard the
destructors called for the temporaries).


#include <vector>
#include <iostream>

class A {
public:
A(int i) : i_(i) {
std::cout << "Making " << i_ << std::endl;
}
A(const A& other) : i_(other.i_) {
std::cout << "Making " << i_ << std::endl;
}
~A() {
std::cout << "Killing " << i_ << std::endl;
}
private:
int i_;
};

int main() {
std::vector<A> v;
v.push_back(A(1));
v.push_back(A(2));
v.push_back(A(3));
v.push_back(A(4));
std::cout << "Removing" << std::endl;
v.erase(v.begin()); // Should print "Killing 1"
std::cout << "Done Removing" << std::endl;
return 0;
}

The result is this:
---------------------------------------------------------
Making 1
Making 1
Killing 1
Making 2
Making 1
Making 2
Killing 1
Killing 2
Making 3
Making 1
Making 2
Making 3
Killing 1
Killing 2
Killing 3
Making 4
Making 4
Killing 4
Removing
Killing 4 <- FLAW, should be "Killing 1"
Done Removing
Killing 2
Killing 3
Killing 4
---------------------------------------------------------
Now of course, in this case it's rather pointless.. But in the case of
shared resources or smart pointers, this would lead to a crash (due to
wrong deallocation of 4 twice) and a memory leak (due to lack of
deallocation of 1, where there is a missing "Killing 1")

With regards,
Christophe

 

[Jay Nabonne]

Hello,

I noticed there is a flaw in the vector implementation of g++ (3.4).
Basically when you erase an element from a vector, it calls the wrong
destructor. In most cases this is not such a big issue, but if one
were to store a class holding a resource, then the wrong resource would
be freed. Here is a test case to show what I mean: (Disregard the
destructors called for the temporaries).

Removing
Killing 4 <- FLAW, should be "Killing 1"
Done Removing
Killing 2
Killing 3
Killing 4
---------------------------------------------------------
Now of course, in this case it's rather pointless.. But in the case of
shared resources or smart pointers, this would lead to a crash (due to
wrong deallocation of 4 twice) and a memory leak (due to lack of
deallocation of 1, where there is a missing "Killing 1")

Put some prints in your assignment operator. I would bet you'll see for
the removal of 1:

1 gets assigned the value of 2
2 gets assigned the value of 3
3 gets assigned the value of 4
4 gets destructed.

Of course "3" now has the contents of "4", so it appears to be destructed
twice. But it's not. Print out the "this" values to see what's going
on.

- Jay

 

[Bob Hairgrove]

Hello,

I noticed there is a flaw in the vector implementation of g++ (3.4).
Basically when you erase an element from a vector, it calls the wrong
destructor. In most cases this is not such a big issue, but if one
were to store a class holding a resource, then the wrong resource would
be freed. Here is a test case to show what I mean: (Disregard the
destructors called for the temporaries).


#include <vector>
#include <iostream>

class A {
public:
A(int i) : i_(i) {
std::cout << "Making " << i_ << std::endl;
}
A(const A& other) : i_(other.i_) {
std::cout << "Making " << i_ << std::endl;
}
~A() {
std::cout << "Killing " << i_ << std::endl;
}
private:
int i_;
};

int main() {
std::vector<A> v;
v.push_back(A(1));
v.push_back(A(2));
v.push_back(A(3));
v.push_back(A(4));
std::cout << "Removing" << std::endl;
v.erase(v.begin()); // Should print "Killing 1"
std::cout << "Done Removing" << std::endl;
return 0;
}

The result is this:
---------------------------------------------------------
Making 1
Making 1
Killing 1
Making 2
Making 1
Making 2
Killing 1
Killing 2
Making 3
Making 1
Making 2
Making 3
Killing 1
Killing 2
Killing 3
Making 4
Making 4
Killing 4
Removing
Killing 4 <- FLAW, should be "Killing 1"
Done Removing
Killing 2
Killing 3
Killing 4
---------------------------------------------------------
Now of course, in this case it's rather pointless.. But in the case of
shared resources or smart pointers, this would lead to a crash (due to
wrong deallocation of 4 twice) and a memory leak (due to lack of
deallocation of 1, where there is a missing "Killing 1")

With regards,
Christophe

I'm notsure that this is a bug ... I got the same "Killing 4" with two
other compilers I tested this with (Borland C++ 5.5.1 and Microsoft
Visual C++ Toolkit 2003). Here's the output from both -- what I don't
understand is the wasteful (IMHO) construction and destruction of so
may temporaries, except for Borland which doesn't really shine in
terms of C++ standards compliance in other areas:

Borland:

Making 1
Making 1
Killing 1
Making 2
Making 2
Killing 2
Making 3
Making 3
Killing 3
Making 4
Making 4
Killing 4
Removing
Killing 4 // <--- same as above
Done Removing
Killing 2
Killing 3
Killing 4

VC++ 2003 toolkit:

Making 1
Making 1
Making 1
Killing 1
Killing 1
Making 2
Making 2
Making 1
Making 2
Killing 1
Killing 2
Killing 2
Making 3
Making 3
Making 1
Making 2
Making 3
Killing 1
Killing 2
Killing 3
Killing 3
Making 4
Making 4
Making 1
Making 2
Making 3
Making 4
Killing 1
Killing 2
Killing 3
Killing 4
Killing 4
Removing
Killing 4 // <--- same as above
Done Removing
Killing 2
Killing 3
Killing 4

 

[Victor Bazarov]

I noticed there is a flaw in the vector implementation of g++ (3.4).
Basically when you erase an element from a vector, it calls the wrong
destructor. In most cases this is not such a big issue, but if one
were to store a class holding a resource, then the wrong resource would
be freed. Here is a test case to show what I mean: (Disregard the
destructors called for the temporaries).


#include <vector>
#include <iostream>

class A {
public:
A(int i) : i_(i) {
std::cout << "Making " << i_ << std::endl;
}
A(const A& other) : i_(other.i_) {
std::cout << "Making " << i_ << std::endl;
}
~A() {
std::cout << "Killing " << i_ << std::endl;
}
private:
int i_;
};

int main() {
std::vector<A> v;
v.push_back(A(1));
v.push_back(A(2));
v.push_back(A(3));
v.push_back(A(4));
std::cout << "Removing" << std::endl;
v.erase(v.begin()); // Should print "Killing 1"
std::cout << "Done Removing" << std::endl;
return 0;
}

The result is this:
---------------------------------------------------------
Making 1
Making 1
Killing 1
Making 2
Making 1
Making 2
Killing 1
Killing 2
Making 3
Making 1
Making 2
Making 3
Killing 1
Killing 2
Killing 3
Making 4
Making 4
Killing 4
Removing
Killing 4 <- FLAW, should be "Killing 1"
Done Removing
Killing 2
Killing 3
Killing 4
---------------------------------------------------------
Now of course, in this case it's rather pointless.. But in the case of
shared resources or smart pointers, this would lead to a crash (due to
wrong deallocation of 4 twice) and a memory leak (due to lack of
deallocation of 1, where there is a missing "Killing 1")

You're missing the fact that internally, a bunch of assignments is
performed. Try defining the assignment op and watch what happens when
you 'erase'. In the case of shared resources or smart pointers, you will
_need_ to define the assignment and everything should be fine.

In fact, you will have
....
Removing
Assigning 1 to be as 2
Assigning 2 to be as 3
Assigning 3 to be as 4
Killing 4
Done Removing
....

The contents of the vector shift up and the tail is destroyed.

V

 

[red floyd]

You're missing the fact that internally, a bunch of assignments is
performed. Try defining the assignment op and watch what happens when
you 'erase'. In the case of shared resources or smart pointers, you will
_need_ to define the assignment and everything should be fine.

This is an excellent example of why you should follow the Rule of 3.

If you provide copy constructor and destructor, you should also provide
assignment.

Then when you have all the internal assignment when you call
erase(v.begin()), all the smart pointers will be reassigned by your
operator=(), and the correct thing will be deleted somewhere down the
line. Of course, if you use naked pointers, you had better be d@mn sure
that you don't have duplicate deletion (which is why Victor said *smart
pointers* earlier).

 

[Richard Herring]

In message <[email protected]>,
"christophe (dot) poucet (at) gmail (dot) com"

Hello,

I noticed there is a flaw in the vector implementation of g++ (3.4).
Basically when you erase an element from a vector, it calls the wrong
destructor. In most cases this is not such a big issue, but if one
were to store a class holding a resource, then the wrong resource would
be freed. Here is a test case to show what I mean: (Disregard the
destructors called for the temporaries).


#include <vector>
#include <iostream>

class A {
public:
A(int i) : i_(i) {
std::cout << "Making " << i_ << std::endl;
}
A(const A& other) : i_(other.i_) {
std::cout << "Making " << i_ << std::endl;
}
~A() {
std::cout << "Killing " << i_ << std::endl;
}
private:
int i_;
};

int main() {
std::vector<A> v;
v.push_back(A(1));
v.push_back(A(2));
v.push_back(A(3));
v.push_back(A(4));
std::cout << "Removing" << std::endl;
v.erase(v.begin()); // Should print "Killing 1"
std::cout << "Done Removing" << std::endl;
return 0;
}

The result is this:
---------------------------------------------------------
Making 1
Making 1
Killing 1
Making 2
Making 1
Making 2
Killing 1
Killing 2
Making 3
Making 1
Making 2
Making 3
Killing 1
Killing 2
Killing 3
Making 4
Making 4
Killing 4
Removing
Killing 4 <- FLAW, should be "Killing 1"
Done Removing
Killing 2
Killing 3
Killing 4
---------------------------------------------------------
Now of course, in this case it's rather pointless.. But in the case of
shared resources or smart pointers, this would lead to a crash (due to
wrong deallocation of 4 twice) and a memory leak (due to lack of
deallocation of 1, where there is a missing "Killing 1")

It's doing what I'd expect. The usual way to erase an element from a
vector is to *copy* the later elements back down the vector, then to
delete the last element. Add an operator=() to your class which also
writes a message, and see what output you get.

Vector elements have to be copyable, so if your A manages resources, it
also has to provide an operator= that behaves consistently when a new
value is assigned. Yet another example of the rule of 3.