«

Alf P. Steinbach wrote:

> * Kai-Uwe Bux:
>> Alf P. Steinbach wrote:
>>
>>> * 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.
>>
>> I have difficulties in seeing what you mean; especially with the advice
>> you give below.
>>
>>>> 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.
>>
>> 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.

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

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

* Leigh Johnston:
>
>
> "Stuart Golodetz" <> wrote in
> message news:...
>> Leigh Johnston wrote:
>>> To accommodate my obvious failure to convey what I actually mean to
>>> some people perhaps the following makes things clearer:
>>>
>>> Some people eschew the derivation of the standard library containers
>>> however the only issues to be aware of are 1) that their destructors
>>> are not virtual and 2) the need to ensure that the derived class's
>>> invariant is not broken by calling the container's member functions
>>> which is only a problem if the derived class's invariant consists of
>>> more than just the container's invariant (i.e. contains additional
>>> state which depends on the container's state) which should not be the
>>> case if interface augmentation only is being performed.
>>>
>>> I apologize for my language but people calling common sense bullshit
>>> winds me up no end.
>>>
>>> /Leigh
>>
>> 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.
>>
>> 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.
>>
>> Cheers,
>> Stu
>
> 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.

Steve Chow wrote:

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

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

Kai-Uwe Bux wrote:

> Steve Chow wrote:
>
> [...]
>>> 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.
>
> 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

> 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).

On Apr 3, 1:32*pm, Steve Chow <robertogobe...@gmail.com> wrote:
> > 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).

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.

On Apr 3, 4:52 pm, "Leigh Johnston" <le...@i42.co.uk> wrote:
> "Alf P. Steinbach" <al...@start.no> wrote in
> messagenews:hp7o1h$uun$...

[...]
> >>> Seehttp://www.i42.co.uk/stuff/mutable_set.htmalso (something I wrote
> >>> but deriving from map/multimap instead of vector).

> >> 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).

Regretfully, that's true in theory, but not in practice.

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

> 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.)

--
James Kanze

On Apr 3, 5:16 pm, "Alf P. Steinbach" <al...@start.no> wrote:
> * Leigh Johnston:
> > "Alf P. Steinbach" <al...@start.no> wrote in message
> >news:hp7p5m$6rb$...
> > 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.

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.

[...]
> > and Bjarne Stroustrup agrees.

> 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.)

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

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.

--
James Kanze

On Apr 3, 6:18 pm, Stuart Golodetz
<sgolod...@NdOiSaPlA.pMiPpLeExA.ScEom> wrote:
> Leigh Johnston wrote:

[...]
> > Some people eschew the derivation of the standard library
> > containers however the only issues to be aware of are 1)
> > that their destructors are not virtual and 2) the need to
> > ensure that the derived class's invariant is not broken by
> > calling the container's member functions which is only a
> > problem if the derived class's invariant consists of more
> > than just the container's invariant (i.e. contains
> > additional state which depends on the container's state)
> > which should not be the case if interface augmentation only
> > is being performed.

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

--
James Kanze