Transform a list of pointers to base class

Question

I have a design where I have a std::list of base pointers that I'd like to transform into a parallel list that adds behavior. The problem I'm having is that the object that I'm trying to use to do the transform doesnt know what the actual types are when it is invoked.

It's quite possible that I'm missing something subtle and that there is an easy fix. However, if this is a design flaw (I've seen this suggested in other posts) what is the appropriate way to approach this?

Suppose the following:

class Sprite { /* ... */ };
class Character : public Sprite {};
class Markup : public Sprite {};

These are constructed (based on some input) into a std::list< Sprite * >. What I'd like to do is eventually take the list and transform it into a parallel structure suitable for output operations. For instance, given:

class HTMLSprite { /* ... */ };
class HTMLCharacter : public HTMLSprite {};
class HTMLMarkup : public HTMLSprite {};

I'd ideally like to do something like

std::transform(sprites.begin (), sprites.end (), html.begin (), HTMLConvert);

with something like

struct HTMLConvert_ {
  HTMLSprite * operator () (const Character * c) { return new HTMLCharacter (); }
  HTMLSprite * operator () (const Markup * c) { return new HTMLMarkup (); }
} HTMLConvert;

Now, I get the error

call of `(HTMLConvert) (const Sprite* const&)' is ambiguous
HTMLSprite* HTMLConvert::operator()(const Character*) const <near match>

Which leads me to my question. What is the best solution to this problem - redesign or otherwise?

Thanks.

Answer 1

I'd suggest adding the function to convert to HTML type to each class. So you'd have a virtual Convert function as a member of Sprite and each derived class can override it. Then when you call the Convert function on your list of Sprite *s, it will call the appropriate converter. You'll need to forward declare the return type (HTMLSprite).

There are probably more elegant ways, but this idea allows you to use virtual functions.

The problem with your suggestion is that the pointers in the array are all type Sprite * regardless of what they actually point to, so a Sprite * is what will be passed to your function. Instead, use something like mem_fun to make a struct that will call the member; this will call the appropriate function through a virtual call:

std::transform(sprites.begin (), sprites.end (), html.begin (), mem_fun(&Sprite::Convert));

Comment if you need me to clarify anything.

Answer 2

As your convert will need to know about all the types to convert from and too it is performing a mapping function.

Here is my quick hack

struct HTMLConvert_ {
  HTMLSprite * operator () (const Sprite* const& sp ) { 
    Character const * c = dynamic_cast<Character const *>(sp);
    if( c )
      return new HTMLCharacter (c);

    Markup const * m = dynamic_cast<Markup const *>(sp);
    if( c )
      return new HTMLMarkup (m);
  }
} HTMLConvert;

Answer 3

How about an abstract factory?

       +-----------------+                            +--------+         
       |  RenderFactory  |                            | Sprite |
       |=================|                            +--------+
       | CreateSprite()  |                                 /\
       | CreateMarkup()  |                         +------------------+
       +-----------------+                         |                  |
               /\                            +------------+    +-------------+
       +-----------------+              ....>| HTMLSprite |    | PlainSprite |
       |                 |              :    +------------+    +-------------+
+----------------+   +----------------+ :
| PlainFactory   |   |  HTMLFactory   | :
|================|   |================| :                 +--------+
| CreateSprite() |   | CreateSprite() |.:...              | Markup |
| CreateMarkup() |   | CreateMarkup() |..  :              +--------+
+----------------+   +----------------+    :                  /\
                                           :          +----------------+
                                           :          |                |
                                           :    +------------+   +-------------+
                                            ..> | HTMLMarkup |   | PlainMarkup |
                                                +------------+   +-------------+

Answer 4

In addition to JoshD's suggestion, you can keep the door open for other transformations by using the visitor pattern.

Add a method dispatch_visit to the Sprite hierarchy, using covariant return types:

class Sprite{
    virtual HTMLSprite * dispatch_visit( HTMLConvert_ const &c ) const = 0;
};
class Character : public Sprite {
    virtual HTMLCharacter * dispatch_visit( HTMLConvert_ const &c ) const
        { return c( this ); }
};
class Markup : public Sprite {
    virtual HTMLMarkup * dispatch_visit( HTMLConvert_ const &c ) const
        { return c( this ); }
};

This allows each object to notify the converter of its dynamic type — essentially, a dynamic dispatch into the parallel type, or even a parallel type hierarchy. Everything else pretty much works as your code is written… the best candidate is chosen among the operator()() functions of the converter, based on the static parameter type.

Oh, you'll need to add the "missing function" to the converter:

struct HTMLConvert_ {
  HTMLSprite * operator () (const Sprite * c) { return c->dispatch_visit( *this ); }
  HTMLCharacter * operator () (const Character * c) { return new HTMLCharacter (); }
  HTMLMarkup * operator () (const Markup * c) { return new HTMLMarkup (); }
} HTMLConvert;

Hmm, that repetitive function could be encapsulated by a template… this only seems to work in C++0x if you want the visitable template to automatically determine the return type of dispatch_visit. If you don't like principal_base you can factor it out.

#include <functional>

template< class T >
struct principal_base
    { typedef void type; };

template< class Client, class Visitor,
    class Base = typename principal_base< Client >::type >
struct visitable :
    virtual visitable< typename principal_base< Client >::type, Visitor > {
    virtual typename std::result_of< Visitor( Client * ) >::type
    dispatch_visit( Visitor const &v ) const
        { return v( static_cast< Client const * >( this ) ); }
};

template< class Client, class Visitor >
struct visitable< Client, Visitor, void > {
    virtual typename std::result_of< Visitor( Client * ) >::type
    dispatch_visit( Visitor const &v ) const = 0;
};

class HTMLSprite { /* ... */ };
class HTMLCharacter : public HTMLSprite {};
class HTMLMarkup : public HTMLSprite {};

class Sprite;
class Character;
class Markup;

struct HTMLConvert_ {
  HTMLSprite * operator () (const Sprite * c);
  HTMLCharacter * operator () (const Character * c);
  HTMLMarkup * operator () (const Markup * c);
} HTMLConvert;

class Sprite : public visitable< Sprite, HTMLConvert_ > {};
template<> struct principal_base< Character >
    { typedef Sprite type; };
class Character : public Sprite, visitable< Character, HTMLConvert_ > {};
template<> struct principal_base< Markup >
    { typedef Sprite type; };
class Markup : public Sprite, visitable< Markup, HTMLConvert_ > {};

//class Invalid : Character, Markup {};

HTMLSprite * HTMLConvert_::operator () (const Sprite * c)
    { return c->dispatch_visit( *this ); }
HTMLCharacter * HTMLConvert_::operator () (const Character * c)
    { return new HTMLCharacter (); }
HTMLMarkup * HTMLConvert_::operator () (const Markup * c)
    { return new HTMLMarkup (); }