inheriting from std::vector bad practice?

S

Steve Chow

Originally I had a bunch of related functions that all took a vector
of Point2D as their argument.
Point2D findGreatestDistance(std::vector<Point2D>& points);

However, this didn't strike me as a very C++/OO way to do things, so I
found a solution I was happy with in:
class Path : public std::vector<Point2D>
{
public:
Path();
~Path();
Point2D findGreatestDistance();
/* related functions */
};

And it works, at least as far as I can tell. Yet it's been received by
people more knowledgeable than me as disgusting and wrong, without
explaining why. Is there a better way I should be doing this?
Someone suggested moving findGreatestDistance into Point2D (struct
with x,y and overload ==) but I don't see how that's possible because
it'd only be able to look at itself.
 
A

Alf P. Steinbach

* Steve Chow:
Originally I had a bunch of related functions that all took a vector
of Point2D as their argument.
Point2D findGreatestDistance(std::vector<Point2D>& points);

However, this didn't strike me as a very C++/OO way to do things, so I
found a solution I was happy with in:
class Path : public std::vector<Point2D>
{
public:
Path();
~Path();
Point2D findGreatestDistance();
/* related functions */
};

And it works, at least as far as I can tell. Yet it's been received by
people more knowledgeable than me as disgusting and wrong, without
explaining why. Is there a better way I should be doing this?

Yes. In terms of knowledge distribution you have ensured that the knowledge
required to do something (findGreatestDistance) is there. But in doing so you
have enabled both inadvertent and intentional abuse of knowledge, like posting a
recipe for creating a simple biological weapon-of-mass-destruction on the net;
you have forgotten to /limit/ the access to those in need to know.

Someone suggested moving findGreatestDistance into Point2D (struct
with x,y and overload ==) but I don't see how that's possible because
it'd only be able to look at itself.

Yes, that sounds like a silly suggestion.

Instead, replace inheritance of std::vector<Point2D> with a private member.

Also, I'd rename 'findGreatestDistance' to just 'greatestDistance' (like,
although not in your code, I'd also rename 'calculateSin' to just 'sin', and so
on), and I'd make a type distinction between points and vectors, but as opposed
to getting rid of that inheritance this is to some degreee personal preference.



Cheers & hth.,

- Alf
 
S

Steve Chow

Instead, replace inheritance of std::vector<Point2D> with a private member.

Also, I'd rename 'findGreatestDistance' to just 'greatestDistance' (like,
although not in your code, I'd also rename 'calculateSin' to just 'sin', and so
on), and I'd make a type distinction between points and vectors, but as opposed
to getting rid of that inheritance this is to some degreee personal preference.

Cheers & hth.,

- Alf

The reason I avoided that was because I'd have to have to write a
public push_back function just to push_back to the private vector when
I wanted to add a point, no? I mean, it's trivial, but it just seemed
like a duplication. But if it's more correct I'm not really going to
argue. I tend to opt for the easy route a lot but have learned the
consequence of doing that a lot is a nightmarish maintenance
scenario.
 
A

Alf P. Steinbach

* Leigh Johnston:
The only time it is unwise to use public inheritance is if your class
invariant consists of more than just vector's invariant in which case it
might be possible to break your class's invariant by calling the
vector's member functions, but I don't believe this is the case in your
example (i.e. you are simply performing interface augmentation).

Sorry, that's bullshit. Proper design involves much more. It's possible to
disagree over what constitutes a good design and whether something constitutes
good design, but in this case it's about the opposite, a technique that's almost
universally recognized as Bad(TM), so, no discussion.


Cheers & hth.,

- Alf
 
A

Alf P. Steinbach

* Leigh Johnston:
* Alf P. Steinbach:

[don't quote signatures, please, and please /trim/ your quoting]

Sorry but that's bullshit. Interface augmentation is a perfectly valid
design practice.

The OP isn't doing interface augmentation by deriving from std::vector<Point>.

And that's not what you were talking about, your statement about "the only time
it is unwise to use public inheritance", quoted above.

I.e. you're now attacking a strawman argument or a couple of strawman arguments.

Instead of inventive strawman argumentation you might reasonably and
straigtforwardly ask why, according to me, your earlier statement is commonly
regarded as bullshit.

As opposed to strawman argumentation, which usually leads to negative outcomes,
such questioning might prove the label-affixer (i.e. here me) wrong, or you
could learn something, or whatever, but mostly positive outcomes from asking.


Cheers & hth.,

- Alf
 
A

Alf P. Steinbach

* Leigh Johnston:
Alf P. Steinbach said:
* Leigh Johnston:
* Alf P. Steinbach:
* Leigh Johnston:


The only time it is unwise to use public inheritance is if your
class invariant consists of more than just vector's invariant in
which case it might be possible to break your class's invariant by
calling the vector's member functions, but I don't believe this is
the case in your example (i.e. you are simply performing interface
augmentation).

Sorry, that's bullshit. Proper design involves much more. It's
possible to disagree over what constitutes a good design and whether
something constitutes good design, but in this case it's about the
opposite, a technique that's almost universally recognized as
Bad(TM), so, no discussion.

[don't quote signatures, please, and please /trim/ your quoting]

Sorry but that's bullshit. Interface augmentation is a perfectly
valid design practice.

The OP isn't doing interface augmentation by deriving from
std::vector<Point>.

And that's not what you were talking about, your statement about "the
only time it is unwise to use public inheritance", quoted above.

I.e. you're now attacking a strawman argument or a couple of strawman
arguments.

Instead of inventive strawman argumentation you might reasonably and
straigtforwardly ask why, according to me, your earlier statement is
commonly regarded as bullshit.

As opposed to strawman argumentation, which usually leads to negative
outcomes, such questioning might prove the label-affixer (i.e. here
me) wrong, or you could learn something, or whatever, but mostly
positive outcomes from asking.


Cheers & hth.,

- Alf

You are simply full of shit. Hope this helps.

Assume that you're right about my bodily contents. Does that help your argument?

No, it does not: it is a fallacy to attack the person.

Let's mark this up as Fallacy #1.


I repeat: interface augmentation (which is what my reply was referring
to) is quite valid

Sometimes interface augmentation is a good idea, but in this case there is no
interface augmentation. Mentioning interface agumentation is just a strawman
argument, which is a fallacy. Let's mark this up as Fallacy #2.

and Bjarne Stroustrup agrees.

This is just an appeal to authority. Which is a fallacy even when it's done
properly with references. Let's mark this as Fallacy #3.

The OP is simply
augmenting vector's interface as far as I can tell (not introducing any
new member variables that contribute to an invariant larger than vector's.)

No. std::vector is a generic type, a template type. The OP is not augmenting
std::vector.



Cheers & hth.,

- Alf
 
K

Kai-Uwe Bux

Alf said:
* Steve Chow:

Yes. In terms of knowledge distribution you have ensured that the
knowledge required to do something (findGreatestDistance) is there. But in
doing so you have enabled both inadvertent and intentional abuse of
knowledge, like posting a recipe for creating a simple biological
weapon-of-mass-destruction on the net; you have forgotten to /limit/ the
access to those in need to know.

I have difficulties in seeing what you mean; especially with the advice you
give below.
Yes, that sounds like a silly suggestion.

Instead, replace inheritance of std::vector<Point2D> with a private
member.

Ok, lets say we had:

class Path {

std::vector<Point2D>

public:

Path();
~Path();
Point2D findGreatestDistance();
/* related functions */

};

How does that limit the knowledge of findGreastedDistance to those in need
to know?


Best

Kai-Uwe Bux
 
K

Kai-Uwe Bux

Steve said:
Originally I had a bunch of related functions that all took a vector
of Point2D as their argument.
Point2D findGreatestDistance(std::vector<Point2D>& points);

However, this didn't strike me as a very C++/OO way to do things, so I
found a solution I was happy with in:
class Path : public std::vector<Point2D>
{
public:
Path();
~Path();
Point2D findGreatestDistance();
/* related functions */
};

And it works, at least as far as I can tell. Yet it's been received by
people more knowledgeable than me as disgusting and wrong, without
explaining why.

Here are some reasons _why_ inheritance from std::vector<> is often frowned
upon:

a) std::vector<> does not have a virtual destructor. Although this is (was?)
the most commonly given rationale, it is also somewhat weak: 1) usually you
will not create pointers to vectors, especially polymorphic ones; 2) the
standard library has components such as std::binary_predicate or
std::iterator, which are clearly intended to be inherited from, yet have no
virtual members. The objection from lack of virtual members derives from a
narrow view of C++ that emphasizes the object orientation paradigm of
programming.

b) Another (better) argument is that there is an implicit conversion of
Path& to std::vector<Point2D>&. This can cause trouble with signatures and
lead to unexpected behavior (i.e., code compiles that should not and then
does something unexpected, or code that is expected to compile does not). In
particular, you can have a return type mismatch: functions like

template < typename T >
std::vector<T> cycle ( std::vector<T> const & in ) {
// returns a cyclicly permuted copy of <in>.
}

will happily take a Path as an argument, but they will not return a Path.
Is there a better way I should be doing this?
[...]

Often, private inheritance is suggested. It requires some amount of
forwarding for those member functions you still want to export.

Personally, I think there are cases where inheritance from std::vector is
perfectly fine. You just need to be aware of the possible pitfalls. For
point (b) above, this usually means that you need to pay special attention
toward the signatures of free-standing functions.


Best

Kai-Uwe Bux
 
J

Jonathan Lee

And it works, at least as far as I can tell. Yet it's been received by
people more knowledgeable than me as disgusting and wrong, without
explaining why. Is there a better way I should be doing this?

I'm no expert, but my opinion is to make the std::vector a private
member, as Alf suggested.

My reasoning for this is, from my understanding, that you are simply
using vector as a convenient way to store your information. It's not
that Path "is a" vector, it's just that vector happens to be available
to you.

i.e., the vector has more to do with the internal working of your
class than what the class actually is. To me, that means private
member instead of inheritance.

Unless you really mean that Path should be like a vector, including
analogs to get_allocator(), capacity(), erase() and such. As far as
I can tell, though, you are really only using push_back() and
operator[]. So you're not really _extending_ vector, you're just
using a (small) subset of its features.

--Jonathan
 
A

Alf P. Steinbach

* Kai-Uwe Bux:
I have difficulties in seeing what you mean; especially with the advice you
give below.


Ok, lets say we had:

class Path {

std::vector<Point2D>

public:

Path();
~Path();
Point2D findGreatestDistance();
/* related functions */

};

How does that limit the knowledge of findGreastedDistance to those in need
to know?

It doesn't and what you're asking is AFAICS not meaningful. It limits knowledge
of the implementation of the sequence of points as a std::vector<Point2D>.


Cheers & hth.,

- Alf
 
K

Kai-Uwe Bux

Alf said:
* Kai-Uwe Bux:

It doesn't and what you're asking is AFAICS not meaningful.

A: "Peter was several hours under water."
B: "How did he survive?"
A: "He didn't. Therefore, what you're asking is not meaningful."
It limits
knowledge of the implementation of the sequence of points as a
std::vector<Point2D>.

I see. I was misunderstanding you because you mentioned findGreatestDistance
as the main example for distributed knowledge. I was, therefore, under the
impression, that you also suggested limiting _that_ knowledge to those in
need to know. But for the limiting, you really had _other_ knowledge in
mind.


Best

Kai-Uwe Bux
 
S

Steve Chow

In your example above, a Path might be represented by a
std::vector<Point2D>, but whether the IS-A relationship (or LSP) is
valid is questionable. By pinning down the representation of a Path so
concretely, you make it harder to change the interface later on.
The Animal: Cat, Dog example always makes the relationship between
objects seem so clear.
When ideas become more abstract I have a real difficult time
determining whether an
object should contain an object or should be an extension of an
object.
As an unrelated example I have an image class and and a class that
extracts information
from the image and translates it to data that I use for a game. That
class is completely useless
without the image class and the relationship seems murky. Another one
was "does a window have an engine? or does an
engine have a window" that arose because I was passing arguments to
Engine's constructor just so it could forward
arguments to Window's constructor. I still feel dirty. Obviously I
don't expect a solution
since I haven't provided any really useful information. I'm just
saying it's not always clear as a car
has an engine, a dog is an animal, etc. At least for me.
One might also question whether there is any logical reason why a Path
IS-A std::vector<Point2D> any more than it IS-A std::list<Point2D>, for
example.
Someone asked if all I was using was .push_back and []; the answer is
I'm not even using [].
I'm just using vector at this point because outwardly it can act like
a list and act like an array
if I decide to change it in the future.
If you're using it for a toy program,
you'll probably get away with it (but should strive to improve your
design skills nonetheless). If you're using it on a team project, expect
others to ask you to change it.
it's a toy project at the moment, but I aim to bring others on board
once I have a prototype, which is why
correctness is important to me.
Regarding findGreatestDistance(), it's somewhat hard to say where it
should go because you haven't specified precisely what it does (in
particular, the Point2D it returns doesn't seem like a distance).

p_it a,b;
p_it furthest;
float max = 0;
for(a = this->begin(); a != this->end(); a++)
{
for(b = this->begin(); b != this->end(); b++)
{
float dx = a->x - b->x;
float dy = a->y - b->y;
float distance = sqrt(pow(dx,2)+pow(dy,2));
if(distance > max)
{
max = distance;
furthest = b;
}
}
}
return *furthest;

greatestDistance is actually a misnomer. It should be furthestPoint
(the point that is furthest away from all other points in the vector)
and I'm not even sure that code is correct, but it doesn't appear to
be giving me problems.
 
A

Alf P. Steinbach

* Leigh Johnston:
I agree. I have updated my website text to the following to (hopefully)
cover all bases:

Some people eschew the derivation of the standard library containers
however there are only 3 main issues to be aware of:

1. As the container has public mutation member functions there is a need
to ensure that the derived class invariant is not broken by calling
these member functions. This is only a problem if the derived class
invariant consists of more than just the container's invariant and
consists of state which depends on the container's state. This should
not be an issue if interface augmentation only is being performed.

2. Does such an "is-a" relationship make sense? Is it important to know
that your derived class "is-a" particular container? If not consider
private inheritance and either wrap container member functions with new
member functions or use using declarations to make particular container
member functions accessible. Again this should not be an issue if
interface augmentation only is being performed.

3. A standard library container destructor is not virtual so you cannot
delete the associated object via a pointer to the container (base class).

http://www.i42.co.uk/stuff/mutable_set.htm

Well, the most important one is still missing:

0. Is the class derivation an implementation detail?

If so then exposing it as public, even as a public member instead of
as a base class,

0.A. Introduces needless ways that bugs can creep in. E.g., when deriving
from std::vector<T>, then client code may use iterators incorrectly.

0.B. Makes it (much) more costly to change implementation later, with
secondary effects that you can guess at.

0.C Adds needless complexity in client code by relying on direct use of
an implementation instead of providing the relevant abstraction(s).

Perhaps someone did tell you this earlier, but only by mentioning the very
abstract "abstraction", which can be hard to translate to actuality.

Anyway,


cheers & hth.,

- Alf

PS: The existence of a point 0 does not mean that there's not also a point 4, a
point 5 and so on, but point 0, as above, is pretty important.
 
K

Kai-Uwe Bux

Steve Chow wrote:

[...]
p_it a,b;
p_it furthest;
float max = 0;
for(a = this->begin(); a != this->end(); a++)
{
for(b = this->begin(); b != this->end(); b++)
{
float dx = a->x - b->x;
float dy = a->y - b->y;
float distance = sqrt(pow(dx,2)+pow(dy,2));
if(distance > max)
{
max = distance;
furthest = b;
}
}
}
return *furthest;

greatestDistance is actually a misnomer. It should be furthestPoint
(the point that is furthest away from all other points in the vector)
and I'm not even sure that code is correct, but it doesn't appear to
be giving me problems.

Looks like a generic algorithm to me:

template < typename PointIterator, typename DistanceFunctor >
typename DistanceFunctor::result_type
diameter ( PointIterator from, PointIterator to, DistanceFunctor dist ) {
assert( from != to );
typename DistanceFunctor::result_type result = 0;
PointIterator high = from;
while ( high != to ) {
PointIterator low = from;
while ( low != high ) {
typename DistanceFunctor::result_type distance =
dist( *low, *high );
if ( result < distance ) {
result = distance;
}
++ low;
}
++ high;
}
return ( result );
}


Best

Kai-Uwe Bux
 
K

Kai-Uwe Bux

Kai-Uwe Bux said:
Steve Chow wrote:

[...]
p_it a,b;
p_it furthest;
float max = 0;
for(a = this->begin(); a != this->end(); a++)
{
for(b = this->begin(); b != this->end(); b++)
{
float dx = a->x - b->x;
float dy = a->y - b->y;
float distance = sqrt(pow(dx,2)+pow(dy,2));
if(distance > max)
{
max = distance;
furthest = b;
}
}
}
return *furthest;

greatestDistance is actually a misnomer. It should be furthestPoint
(the point that is furthest away from all other points in the vector)
and I'm not even sure that code is correct, but it doesn't appear to
be giving me problems.

Looks like a generic algorithm to me:

template < typename PointIterator, typename DistanceFunctor >
typename DistanceFunctor::result_type
diameter ( PointIterator from, PointIterator to, DistanceFunctor dist )
{
assert( from != to );
typename DistanceFunctor::result_type result = 0;
PointIterator high = from;
while ( high != to ) {
PointIterator low = from;
while ( low != high ) {
typename DistanceFunctor::result_type distance =
dist( *low, *high );
if ( result < distance ) {
result = distance;
}
++ low;
}
++ high;
}
return ( result );
}

Oops, different problem. As for the farthest away point, maybe something
like this would work (based on the interpretation given elsethread by Stuart
Golodetz):

template < typename PointIter, typename DistanceFunctor >
PointIter
extreme_point ( PointIter from, PointIter to, DistanceFunctor dist ) {
typedef typename DistanceFunctor::result_type float_type;
PointIter candidate = from;
PointIter result = from;
float_type current_max = 0;
while ( candidate != to ) {
float_type distance = 0;
for ( PointIter iter = from; iter != to; ++ iter ) {
distance += dist( *candidate, *iter );
}
if ( distance > current_max ) {
result = candidate;
current_max = distance;
}
}
return ( result );
}

In any case, I feel that

a) you are looking for free standing functions and
b) the functions could easily be abstracting from the particular
implementation of a path. What matters is just that you have a sequence of
points. It does not matter whether that sequence is a list, a deque, or a
vector.

Wether that degree of generality is overkill, hmm ...


Best

Kai-Uwe Bux
 
S

Steve Chow

p_it i, j;
p_it furthest;
float maxDistance = 0.0f;

// For each possible furthest point...
for(p_it i=begin(); i!=end(); ++i)
{
        // ...calculate its total distance from other points...
        float distance = 0.0f;
        for(p_it j=begin(); j!=end(); ++j)
        {
                if(j == i) continue;
                float dx = j->x - i->x, dy = j->y - i->y;
                distance += sqrt(dx*dx + dy*dy);
        }

        // ...and compare this to the highest total distance so far,
        // updating the furthest distance and point if necessary.
        if(distance > maxDistance)
        {
                maxDistance = distance;
                furthest = i;
        }

}

return *furthest;

Cheers,
Stu

I'm in over my head. I have no idea what I was returning then, but it
seemingly worked. I was using it to find the endpoint of the path
(they're long & relatively straight w/ minor curves it works, at least
seemingly).
 
S

Steve Chow

I'm in over my head. I have no idea what I was returning then, but it
seemingly worked. I was using it to find the endpoint of the path
(they're long & relatively straight w/ minor curves it works, at least
seemingly).

Worked well enough to do this http://img263.imageshack.us/img263/3592/snapshot4d.png
*
Each of the those multicolored lines is a Path. I create the Path by
comparing the outlines of all these http://img406.imageshack.us/img406/2905/beforeb.png
blobs to each other. If they're touching (determined by distance <
1.5) I push_back to a vector. The order is messed up sometimes though
so I need to find an endpoint. Then I use the endpoint as the starting
position for my trace function which traces a binaryimage with
everything set to 0 except the points that correspond to the path. Out
of that I get an ordered list of points which I can feed to
GL_LINE_STRIP allowing me to draw the borders of blobs. :)
 
J

James Kanze


[...]
Regretfully, that's true in theory, but not in practice.
Sorry but that's bullshit. Interface augmentation is a
perfectly valid design practice.

From the design point of view, you're completely right.
Practically speaking, however, it doesn't work out that way.
Trying to derive from a class only works out in practice if the
class was actually designed to be a base class, with few
exceptions. And while this case *is* very close to qualifying
as an exception, there's no real reason for making it one. As
someone else pointed out, the simplest and safest solution is to
follow the model in the STL, and use a free function for the
extended interface. (But depending on the context, I generally
wouldn't refuse such code using inheritance in a code review.
IMHO, the only real risk is deleting through a pointer to the
base, and in general, you shouldn't be allocating std::vector
dynamically anyway.)
 
J

James Kanze

* Leigh Johnston:
Sometimes interface augmentation is a good idea, but in this
case there is no interface augmentation.

Strangely enough, I have to agree with Leigh here. (Doesn't
happen very often.) From what little we know of the global
context, this seems very much like what I would call "interface
augmentation". My only objection to the derivation is that in
C++ (unlike the case in e.g. Java), the idiomatic form of
interface augmentation is by using free functions: we have
std::sort, rather than std::vector<>::sort, etc.

Scott Meyers once wrote up a long discussion once about the
trade offs between free functions and members; a large part of
his point was that interface augmentation should have the same
syntax as the basic interface, *but* the types should also be
the same. IIRC, his conclusion was the best design would be to
make even the basic interface friend functions, rather than
members, and forget about the obj.func() syntax completely:).
For things that are basically containers of data, like the case
here, I think I sort of agree with him, but we're not going to
change the interface to std::vector anytime soon.

[...]
This is just an appeal to authority.

Or simply indicating that he's not the only one to think this.
(My books are still in boxes following two recent moves, so I
can't verify anything, but I do seem to recall Bjarne deriving
from std::vector in order to implement and operator[] which
guaranteed bounds checking. If this is what Leigh is thinking
of, of course, it isn't interface augmentation, but changing the
interface. And I'd study the text surrounding the example very
carefully to see whether it is just a suggestion concerning a
general direction, or whether it is presented as an example of
what should be done in production code. Code in pedagogic texts
follows radically different rules than production code.)

[...]
No. std::vector is a generic type, a template type. The OP is
not augmenting std::vector.

So Leigh didn't express himself as clearly as he should have.
What I understood him to mean (even if it wasn't his exact
words) was that the derived class augmented the interface of
class std::vector<Point2D>, and not of template<typename T,...>
std::vector.
 
J

James Kanze

Leigh Johnston wrote:

[...]
I'm wary of wading into this argument, except in so far as I
would add that in this case the other issue to consider is
whether tying yourself down to implementing Path as a
std::vector is a good idea long-term. That's not an issue to
do with inheriting from standard containers (so I guess it
doesn't augment your list above per se), but it is a general
design issue.

That's always something to consider. Of course, he could always
change the base class later, to e.g std::deque<Point2D>, for
example. In the end, the question is how much of the
std::vector interface does he want to expose. From what little
we know, I'd guess all of it. Whether this is a good idea or
not is, as you say, a design issue; if this type is fundamental
to his application, there are very strong arguments for wrapping
it. Not to provide additional functions, but to not provide
some of the existing ones, thus making a later change in the
data structure signficantly simpler, should this become
necessary. (In practice, I think that there are some cases
where it is perfectly clear that std::vector is the only
appropriate data structure. Probably less than is generally
thought, but they do exist.)
As far as inheriting from standard containers go, it's
certainly the case that designs which do so end up violating
the Liskov Substitution Principle. In particular, you can't
pass a pointer to an instance of the subclass to a function
which calls delete on a pointer to the superclass without
invoking undefined behaviour. Whether this matters to you or
not is up to you (and I won't offer an opinion here) -- but
that's at least one consideration to bear in mind when
deciding.

Never allocating a standard container dynamically seems like a
reasonable coding guideline to me, in which case, deletion
through a pointer to base becomes a non-issue.

PS: if it's not yet completely clear: I'm not really arguing
either side here. I think that there are sufficient arguments
for both sides.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top