[snipped previous discussion about dynamic_cast]
Andreas said:
In
something like a drawing program you have objects and their position
on the drawing stack. Type has nothing to do with position, hence any
operation which has to honour stack position (like drawing or finding
the topmost object via graphical positions) has to process N lists
interleaved rather than just one (in which you'd get the stack position
entirely for free). Stack positions have to be unique, so you'll have to
guarantee that over N lists.
Maybe I should elaborate my point of view a little bit: When I said
that I wanted to store the objects in multiple lists, I did not mean
that the original list should be discarded:
class CGeometricObject
{
public:
virtual void Draw (/*SomeDeviceContextType& dc*/) const = 0;
};
class CCircle
{
public:
virtual void Draw (/*SomeDeviceContextType& dc*/) const
{
// Draw a circle
}
private:
// Whatever is needed.
};
class CRectangle
{
public:
virtual void Draw (/*SomeDeviceContextType& dc*/) const
{
// Draw a circle
}
private:
// Whatever is needed.
};
class CDrawingApplication
{
private:
// The stack that contains all objects in the order
// in which they should appear on the screen from top
// to bottom.
std::list<CGeometricObject*> GeometricObjects;
// The list of geometric objects that must be handled in a
// special way by the application.
std::list<CCircle> Circles;
std::list<CRectangle> Rectangles;
public:
void AddCircle (const CCircle& Circle)
{
Circles.push_back (Circle);
GeometricObjects.push_back (&Circle);
}
void AddRectangle (const CRectangle& Rectangle)
{
Rectangles.push_back (Rectangle);
GeometricObjects.push_back (&Rectangle);
}
void Draw (/*SomeDeviceContextType dc*/)
{
for (std::list<CGeometricObject*>::iterator it =
GeometricObjects.begin (); it != GeometricObjects.end (); +
+it)
{
it->Draw ();
}
}
};
For many other operations, all types will
behave the same, so you'll need N identical implementations (which may
be addressed via templates, but that still results in N implementations
on object code level). Keeping one object in multiple lists depending on
the view is also a bad idea because redundancy always implies a high risk
of inconsistency. If new types appear, you'll need new lists and all code
processing the objects will have to take the new lists into account;
Nope. All code that uses only the base interface CGeometricObject can
stay as it is (see above example of CDrawingApplication:
raw).
However, if the application needs to do something special to a new
class (let's say CTriangle), the newly added method for triangle-
specific handling can simply just the newly added list of triangles.
besides, what makes you think you'd actually know all types at the time
of writing, e.g. in a library context?
Right. Now we are getting to some constraints that have not been
mentioned yet. Libraries that must facilitate for extensions may be a
reason why one should have to use dynamic_casts, although I am not
sure why the drawing program should be such a candidate. Consider
this: If the user wants to add a geometric object of unknown type, the
application can do nothing with it except things that are provided by
the base interface CGeometricObject. So there is no need to keep a
special list for the new type.
[snip]
It gets really great for something
like "Does A intersect B" (and I don't mean bounding boxes but the
real deal which needs to know the exact properties of both shapes,
e.g. circle and bezier curve). Trying to do this with N containers
and without dynamic casts would mean N^2 implementations of the entire
code sequence from retrieving the objects from their respective
containers based on some criteria (usually not type-related) to the
actual evaluation of the intersection function (N functions, actually,
one for each type).
I don't think that this is true. I would just add the following method
to the base interface:
bool Intersects (const CGeometricObject* Other) const = 0;
Now I can add a method to CPaintApplication that computes all
intersections:
std::list<std:
air<CGeometricObject*,CGeometricObject*> >
ComputeIntersections ()
{
std::list<std:
air<CGeometricObject*,CGeometricObject*> > RetVal;
for (std::list<CGeometricObject*>::iterator first =
GeometricObjects.begin ();
first != GeometricObjects.end (); ++first)
{
std::list<std:
air<CGeometricObject*,CGeometricObject*> > RetVal;
for (std::list<CGeometricObject*>::iterator first =
GeometricObjects.begin ();
first != GeometricObjects.end (); ++first)
{
std::list<CGeometricObject*>::iterator second = first;
++second;
for (; second != GeometricObjects.end (); ++second)
{
if ((*first)->Intersects (*second))
RetVal.push_back (
std:
air<CGeometricObject*,CGeometricObject*>
(*first, *second));
}
}
return RetVal;
}
}
No. Why would keeping N objects in M containers need considerably more
memory than keeping them in one container?
I would need additional space because I reference the same object from
two containers: One that is specific to the runtime type and one that
uses the base type of the object.
The whole code would look like this (including the Double Dispatch
meachanism, as Joshua proposed in his posting down this sub-thread):
#include <list>
#include <iostream>
class CCircle;
class CRectangle;
class CGeometricObject
{
public:
virtual void Draw (/*SomeDeviceContextType& dc*/) const = 0;
virtual bool Intersects (const CGeometricObject* Other) const = 0;
virtual bool _Intersects (const CCircle* OtherCircle) const = 0;
virtual bool _Intersects (const CRectangle* OtherRectangle) const =
0;
};
class CCircle : public CGeometricObject
{
public:
virtual void Draw (/*SomeDeviceContextType& dc*/) const
{
// Draw a circle
}
virtual bool Intersects (const CGeometricObject* Other) const
{
// Perform double Dispatch: Forward the call to the other object.
return Other->_Intersects (this);
}
// Those methods are necessary to provide for Double Dispatch.
virtual bool _Intersects (const CCircle* OtherCircle) const
{
std::cout << "Computing Intersection between two circles.";
return true;
}
virtual bool _Intersects (const CRectangle* OtherRectangle) const
{
std::cout << "Computing Intersection between circle and
rectangle.";
return true;
}
private:
// Whatever is needed.
};
class CRectangle : public CGeometricObject
{
public:
virtual void Draw (/*SomeDeviceContextType& dc*/) const
{
// Draw a circle
}
virtual bool Intersects (const CGeometricObject* Other) const
{
// Perform double Dispatch: Forward the call to the other object.
return Other->_Intersects (this);
}
virtual bool _Intersects (const CCircle* OtherCircle) const
{
std::cout << "Computing Intersection between circle and
rectangle.";
return true;
}
virtual bool _Intersects (const CRectangle* OtherRectangle) const
{
std::cout << "Computing Intersection between two rectangles.";
return true;
}
private:
// Whatever is needed.
};
class CDrawingApplication
{
private:
// The stack that contains all objects in the order
// in which they should appear on the screen from top
// to bottom.
std::list<CGeometricObject*> GeometricObjects;
// The list of geometric objects that must be handled in a
// special way by the application.
std::list<CCircle*> Circles;
std::list<CRectangle*> Rectangles;
public:
void AddCircle (CCircle* Circle)
{
Circles.push_back (Circle);
GeometricObjects.push_back (Circle);
}
void AddRectangle (CRectangle* Rectangle)
{
Rectangles.push_back (Rectangle);
GeometricObjects.push_back (Rectangle);
}
void Draw (/*SomeDeviceContextType dc*/)
{
for (std::list<CGeometricObject*>::iterator it =
GeometricObjects.begin (); it != GeometricObjects.end (); +
+it)
{
(*it)->Draw ();
}
}
std::list<std:
air<CGeometricObject*,CGeometricObject*> >
ComputeIntersections ()
{
std::list<std:
air<CGeometricObject*,CGeometricObject*> > RetVal;
for (std::list<CGeometricObject*>::iterator first =
GeometricObjects.begin ();
first != GeometricObjects.end (); ++first)
{
std::list<CGeometricObject*>::iterator second = first;
++second;
for (; second != GeometricObjects.end (); ++second)
{
if ((*first)->Intersects (*second))
RetVal.push_back
(std:
air<CGeometricObject*,CGeometricObject*> (*first, *second));
}
}
return RetVal;
}
};
int main()
{
CDrawingApplication app;
CCircle Circle;
CRectangle Rectangle;
app.AddCircle (&Circle);
app.AddRectangle (&Rectangle);
app.ComputeIntersections ();
return 0;
}
What do you think?
Stuart
