Operations on objects in a container of heterogenous templated class

[daviddoria]

There are two classes, ImageBase, and template <T> Image in a library I'm using. I want to store many of these images in a container, and then pass them to a function templates that expect an Image<T>. The only thing I knew to do was store ImageBase* in the container:

#include <iostream>
#include <vector>

class ImageBase { };

template <typename TPixel>
class Image : public ImageBase
{
public:
  TPixel GetPixel() const 
  {
    TPixel a = 3; return a;
  }
};

template<typename TImage>
void DoSomething(const TImage* image)
{
  TPixel pixel = image->GetPixel(); // Dummy call to an Image function 
}

int main(int, char *[])
{
  std::vector<ImageBase*> images;
  ImageBase* image = new Image<float>;
  images.push_back(image);
  ImageBase* image2 = new Image<int>;
  images.push_back(image2);

  //DoSomething(images[0]); // no member named GetPixel

  return 0;
}

but of course passing an ImageBase to a function that calls a function expecting a type Image (using functions defined in Image and not in ImageBase) doesn't make sense. Of course I could add pure virtual functions in ImageBase and implement them in Image, but then I will be using a modified version of the library, which is huge headaches for users. Is there a way to do this without touching ImageBase?

Thanks,

David

[mike_2000_17]

You're trying to mix a compile-time mechanism (overloading) and a run-time mechanism (dynamic dispatching). They can't mix (at least, not that way). You have to choose.

You can achieve run-time dispatching based on the type, that is dynamic dispatching. The native mechanism for doing that is the use of virtual functions. If you can't use that, you can do it externally with a dispatching function that uses the RTTI (Run-time Type Identification) via either uses of dynamic_cast or with the typeid() operator. Generally, you only need to do this if you are implementing a double dispatching mechanism. Double dispatching is notoriously difficult to implement in a scalable way, I think the quote of Alexandrescu says a lot: (talking about double dispatching) "I am convinced there is a solution to the inheritance problem. But, alas, writers of books have deadlines, too.".

However, at compile-time, double dispatching is a piece of cake, overloading rules and Koenig-lookup solves the problem for you, all you have to do is provide the required overloads (and/or template specializations).

Of course, if you have overloads that take a pointer to derived classes and another version that takes a base-class pointer, then the most derived class version will be selected if the function is called with a pointer to an object of the actual type of the object it points to (.. you know what I mean..). So, the problem becomes to store an "array" of objects of heterogeneous types.

First thing to realize here is that the only way that you can benefit from overloading (i.e. static dispatching) is if the type is known at compile time (otherwise, you would need reflection to do this at run-time).

If you need to know the type at compile time, you need to know about all the elements of the "array" at compile-time too (or at least, you need to know which type of heterogeneous elements you want and how many).

Since each element of the "array" could potentially dispatch to a different function call (overload), then you need a separate piece of compiled code to do each call.

If you need a separate piece of code to do each call (i.e. a function template is what you need), you need compile-time loop that generates those function templates, which is not possible per se, you have to resort to recursion. In other words, to iterate through the elements of the "array" you have to use a compile-time recursion of function templates, this is a template meta-programming technique.

If any of the above is not acceptable to you, or if TMP scares you, then use the ad hoc solution mentioned earlier, that is, implement your dispatching with a bunch of dynamic_cast tests and calls to the appropriate function version for the different run-time types. Another possible solution is the use of Boost.Variant which is a kind of "union on steroids" because it allows non-POD types in the union and it discriminates the current type that it holds, however, the syntax is generally a bit bloated and you have to live with the fact that, like unions, the resulting object is as large as the largest type that it must be able to hold.

If you want to go the compile-time way, one possible solution is the concept of "tuples" (literally, static arrays of objects of heterogeneous types), either the standard tuple (just added to C++11) or the Boost.Tuple library. Tuples will be much more efficient than Boost.Variant or any other dynamic dispatching method, however, you pay a price in the restrictions you have to live with (which aren't that bad if you do a lot of compile-time designs). To traverse the tuple to do some iteration on its elements, you have to use a recursive template call, which is scary at first but it's fine once you get a hang for it. An example of that is my arithmetic_tuple implementation.

[vijayan121]

> Of course I could add pure virtual functions in ImageBase and implement them in Image,
> but then I will be using a modified version of the library, which is huge headaches for users.
> Is there a way to do this without touching ImageBase?

If the only issue is with not modifying image_base , add an interface class between image_base and image<>

struct image_base { virtual ~image_base() {} /* ... */ } ;

struct basic_image : image_base { virtual int get_it() = 0 ; } ;

template< typename T > struct image :  basic_image { virtual int get_it() override { return sizeof(T) ; } } ;

int main()
{
    std::vector< basic_image* > seq = { new image<int>(), new image<double>(), new image<int>() } ;
    for( auto& p : seq ) std::cout << p->get_it() << '\n' ;
}

Or if the std::vector< image_base* > must itself be exposed to the users,

int main()
{
    std::vector< image_base* > seq = { new image<int>(), new image<double>(), new image<int>() } ;
    for( auto& p : seq ) std::cout << dynamic_cast<basic_image*>(p)->get_it() << '\n' ;
}

If modification to image<T> is also taboo, you have to simulate dynamic dispatch programmatically.

struct image_base { virtual ~image_base() {} /* ... */ } ;

template< typename T > struct image :  image_base { int get_it() { return sizeof(T) ; } } ;

template< typename T > int get_it( image_base* p ) { return dynamic_cast< image<T>* >(p)->get_it() ; }

std::unordered_map< std::type_index, std::function< int(image_base*) > > lookup =
{
    { typeid( image<int> ), get_it<int> },
    { typeid( image<double> ), get_it<double> }
    // etc
};

int main()
{
    std::vector< image_base* > seq = { new image<int>(), new image<double>(), new image<int>() } ;
    for( auto& p : seq ) std::cout << lookup[ typeid(*p) ](p) << '\n' ;
}

[daviddoria]

@vijayan121 - your last suggestions is close to what I'm talking about. However, it seems you'd have to make a 'lookup' map for every function you want to call? yuck! Also, since the template parameter of image (e.g. image<int>) matches exactly the template parameter of the function (e.g. get_it<int>), is there not a way to make that map automatically without explicitly listing the types?

@mike_2000_17 - I'm still reading your post and looking into tuples. I'll get back to you.

[daviddoria]

@mike_2000_17 - I looked at boost::variant. It lets me add the items to the container (as long as I explicitly list all of the types I'm expecting in the variant template parameters), but then when I try to call the function template it tries to pass a boost::variant:

#include <iostream>
#include <vector>
#include <boost/variant.hpp>

class ImageBase { };

template <typename TPixel>
class Image : public ImageBase
{
public:
  TPixel GetPixel() const 
  {
    TPixel a = 3; return a;
  }
};

template<typename TImage>
void Output(const TImage* image)
{
  std::cout << image->GetPixel();
}

int main()
{
  std::vector<boost::variant< Image<int>*, Image<float>* > > images;

  images.push_back(new Image<float>);
  images.push_back(new Image<int>);
  Output(images[0]);
}

To pass an element as the correct type would require already knowing the type:

Output(boost::get<Image<int>*>(images[0]);

right?

[daviddoria]

Ok, none of these methods seem to make it "easy". I guess what I really want is to use the normal polymorphic style operations:

images[0]->DoSomething();
images[1]->DoSomething();

I'm happy to introduce new classes into the hierarchy, but that also doesn't seem possible without touching ImageBase/Image? Something like:

class CustomImageBase : public ImageBase
{
 virtual void DoSomething() = 0;
};

template<typename TPixel>
class CustomImage : public Image<TPixel>, public CustomImageBase
{
 void DoSomething();
}

main()
{
 std::vector<CustomImageBase*> images;
 images.push_back( new CustomImage<int> );
 images.push_back( new CustomImage<float> );
 images[0]->DoSomething();
 images[1]->DoSomething();
}

The problem with this is that Image inherits ImageBase, so then CustomImage inherits ImageBase twice :(

I tried to make CustomImageBase not derive from anything, but then it complains that there is no valid conversion when I try to add the objects to the vector. Are there any other tricks to try down this road?

[daviddoria]

By the way, the reason for this is that the user loads a bunch of images through a GUI and then I want to carry them all through a big process. I can't know the types of these images before hand, as they are read from the files the users selects. This seems like a pretty common case to want to handle, no?

[mike_2000_17]

The preferred mechanism to use boost.variant are visitors. Your example would translate to:

#include <iostream>
#include <vector>
#include <boost/variant.hpp>

class ImageBase { };

template <typename TPixel>
class Image : public ImageBase
{
public:
  TPixel GetPixel() const 
  {
    TPixel a = 3; return a;
  }
};

struct OutputVisitor : public boost::static_visitor<> {
  template<typename TImage>
  void operator()(const TImage* image)
  {
    std::cout << image->GetPixel();
  };
};

int main()
{
  std::vector<boost::variant< Image<int>*, Image<float>* > > images;

  images.push_back(new Image<float>);
  images.push_back(new Image<int>);

  boost::apply_visitor( OutputVisitor, images[0]);
}

[daviddoria]

@mike_2000_17 - that does work, great. However it requires converting a hundred function templates into functors (yuck!).

I'm still curious about the inheritance method I suggested (CustomImage). If I'm going to have to change all of my functions, associating them with a class rather than leaving them as free functions seems like a better way to go.

[mike_2000_17]

>>Are there any other tricks to try down this road?

Yes.

First, to avoid the multiple presence of the base-class ImageBase, you must use virtual inheritance. Your problem here is actually called the "dreaded diamond" and is easily solved with virtual inheritance. Ideally, however, the CustomImageBase should not inherit from ImageBase because it is just an additional interface for your classes.

Second, to solve the casting problem: if CustomImageBase doesn't have ImageBase as a base-class how do you store it in the container and how to you retrieve it from the container? The answer: cast it. You will need to use dynamic_cast to cast from CustomImageBase to ImageBase or vice versa. Ideally, of course, you should just store pointers to CustomImageBase in your container instead and avoid all the stupid casting back-and-forth. If you use shared-pointers (as you should), then it is even easier to have two containers, one with shared-pointers to ImageBase (for use in the rest of the library) and one with shared-pointers to CustomImageBase (for use in your special part of the library), or as weak-pointers.

>>I can't know the types of these images before hand, as they are read from the files the users selects. This seems like a pretty common case to want to handle, no?

Sure it's very common, but you can generate all the code for each image type before-hand, can't you? Here is the typical way I would handle this problem (say I wanted to have a "DoSomething" algorithm for all my image types):

template <typename T>
class Image; //forward-decl

template <typename T>
void DoSomething_impl( Image<T>& image) {
  /* ... write the generic implementation here ... */
};

void DoSomething_impl( Image<bool>& image) {
  /* ... write a specific implementation for bool-images here ... */
};


template <typename T>
class Image : public ImageBase {
  //...
  public:
    virtual void DoSomething() {
      DoSomething_impl(*this);
    };
};

The point is that not knowing the type before-hand means that you have to dispatch dynamically at some point in the execution. But you generally don't need that many dynamic dispatching, usually just one time. As in the example above, I implement the algorithm (both generic and specializations) via static dispatching (function overloading or template specializations), but then I wrap this up, at the top level, with a dynamic dispatching (the virtual DoSomething member function). The point is, I do one dynamic dispatch (only if necessary) at the top-level, and implement the rest using static dispatching methods which are much more flexible (and I can also benefit from not having to use any dynamic dispatching at all if that is not necessary (e.g. the type is known at compile-time)).

This is the way I handle the situation you described, of course, some people use only the dynamic dispatching mechanism (e.g. implement the algorihms directly in virtual functions) (more pure OOP), but I prefer to get the best of both worlds, and generally, I find that using static dispatching under-the-hood tends to minimize actual code duplication (it is called "generic programming" after all).

[daviddoria]

First, to avoid the multiple presence of the base-class ImageBase, you must use virtual inheritance. Your problem here is actually called the "dreaded diamond" and is easily solved with virtual inheritance. Ideally, however, the CustomImageBase should not inherit from ImageBase because it is just an additional interface for your classes.

Ah, I did forget about virtual inheritance. However, it doesn't seem to work in my real case. In a simple example, it works:

#include <vector>

class ImageBase {};

template <typename TPixel>
class Image : public ImageBase {};

struct CustomImageBase : public virtual ImageBase
{
  virtual void DoSomething() = 0;
};

template <typename TPixel>
struct CustomImage : public Image<TPixel>, public CustomImageBase
{
  void DoSomething(){}
};

int main(int, char *[])
{
  CustomImage<float>* floatImage = new CustomImage<float>;
  floatImage->DoSomething();
  CustomImage<int>* intImage = new CustomImage<int>;
  intImage->DoSomething();

  std::vector<CustomImageBase*> images;
  images.push_back(floatImage);
  images.push_back(intImage);
  for(unsigned int i = 0; i < images.size(); ++i)
  {
    images[i]->DoSomething();
  }
  return 0;
}

However in the real case:

#include "itkImage.h"
#include "itkImageRegionIterator.h"

struct CustomImageBase : public virtual itk::ImageBase<2>
{
  virtual void DoSomething() = 0;
};

template <typename TPixel>
struct CustomImage : public itk::Image<TPixel, 2>, public CustomImageBase
{
  void DoSomething()
  {
    itk::Index<2> index;
    index.Fill(0);
    std::cout << this->GetPixel(index);
  }
};

int main(int, char *[])
{
  std::vector<CustomImageBase*> images;

  CustomImage<float>* floatImage = CustomImage<float>::New();
  CustomImage<int>* intImage = CustomImage<int>::New();

  return EXIT_SUCCESS;
}

(I can't inherit ImageBase from Image virtually as the FAQ suggests, though that doesn't seem to be necessary for it to work in my trivial example).

I get on this line (CustomImage<float>* floatImage = CustomImage<float>::New();) "error reference to 'New' is ambiguous". (You have to use the New() function to create ITK objects, they have make the constructors private so 'new' doesn't work.) Anything that can be done about this?

Second, to solve the casting problem: if CustomImageBase doesn't have ImageBase as a base-class how do you store it in the container and how to you retrieve it from the container? The answer: cast it. You will need to use dynamic_cast to cast from CustomImageBase to ImageBase or vice versa. Ideally, of course, you should just store pointers to CustomImageBase in your container instead and avoid all the stupid casting back-and-forth. If you use shared-pointers (as you should), then it is even easier to have two containers, one with shared-pointers to ImageBase (for use in the rest of the library) and one with shared-pointers to CustomImageBase (for use in your special part of the library), or as weak-pointers.

Sure, I'm happy to store CustomImageBase pointers. If we fix the above problem I think we're in business.

Sure it's very common, but you can generate all the code for each image type before-hand, can't you? Here is the typical way I would handle this problem (say I wanted to have a "DoSomething" algorithm for all my image types):

I don't need special versions for each type, my functions can all handle any type (I've just been writing free function templates for everything). This is why it is so frustrating to have to do all of this monkey business - my functions can already handle any type, but I can't pass them the objects that I have, even though they were created as one of the types my function templates can handle!

[vijayan121]

> However, it seems you'd have to make a 'lookup' map for every function you want to call?

Yes.

> Also, since the template parameter of image (e.g. image<int>) matches exactly the
> template parameter of the function (e.g. get_it<int>), is there not a way
> to make that map automatically without explicitly listing the types?

There is a way to make that map automatically with the help of the preprocessor; but you have to at least specify the types involved.

The Boost Preprocessor library would be handy. Create a list of the types involved.
For example, ( int, ( double, ( short, BOOST_PP_NIL ) ) ) and then use a repetition construct like BOOST_PP_LIST_FOR_EACH