Function for manipulating container of Base/Derived objects

Question

consider the following algorithm with arrays:

class MyType;
{
    // some stuff
}

class MySubType:MyType
{
    // some stuff
}

void foo(MyType** arr, int len)
{
    for (int i = 0;i<len;i++)
        // do something on arr[i]->
}

void bar()
{
    MySubType* arr[10];
    // initialize all MySubType*'s in arr
    foo(&arr, 10);
}

Nothing too fancy here. My question is - how do I do this with templates?

void foo(std::vector<MyType>& s)
{
    std::vector<MyType>::iterator i;
    for (i = s.begin(); i != s.end(); i++)
        // do stuff on *i
}

so, in bar, I can't do this:

void bar()
{
    std::vector<MySubType> s;
    foo(s);  // compiler error
}

error: invalid initialization of reference of type std::vector<MyType, std::allocator<MyType> >& from expression of type std::vector<MySubType, std::allocator<MySubType> >

Is there some way to do something like this?

Basically, if there's a way to do this:

std::vector<MySubType> s;
std::vector<MyType>& t = s;

I'd be happy...

Answer 1

Here's the problem with this - if s and t point to the same object, what's to stop you putting MyOtherSubType (not related to MySubType) into into t? That would make s contain objects that are not MySubType. I don't know of any type-safe programming language that lets you do this. If it were allowed, imagine the problems we'd have:

//MySubType inherits from MyType
//MyOtherSubType also inherits from MyType

std::vector<MySubType> s;
std::vector<MyType>& t = s;

MyOtherSubType o;
t.push_back(o);

Since t and s are exactly the same object under different names, the element at s[0] is something that is not MySubType. Huge problem - we could never be sure that our vectors contained the types they are supposed to! Thus, the compiled disallows it.

Answer 2

C++ does not support covariance on template types, any more than C# currently does, much for the same reasons. If you want to do this, it is best to make your vector be templatised on a common interface type (of pointers to that type), and make the function foo accept a vector of that type.

Answer 3

Unfortunately, there isn't. Different template specialisations are considered different classes; you can't convert between std::vector<MyType> and std::vector<MySubType>.

You could split the "do stuff" common bit of foo() into a separate function and have a separate loop over each vector (or possibly use std::foreach).

Answer 4

This might fix your problem

template <typename T>
void foo(std::vector<T>& s)
{
    typename std::vector<T>::iterator i;
    for (i = s.begin(); i != s.end(); i++)
        // do stuff on *i
}

Answer 5

Since you say, "Nothing too fancy here", I'm not sure you realize this:

Your original code is broken; or if you're lucky it might not be broken right now, but it's quite fragile and will break as soon as someone does something more than look at the MySubType class.

The problem is that you're passing a MyType* to foo() but it really points to an array of MySubType. If a MySubType object happens to be larger than a MyType object (which is pretty likely if you've added anything to the derived class), then the pointer arithmetic done in the foo() function will be incorrect.

This is one of the serious and classic pitfalls of arrays of derived class objects.

Answer 6

Using boost (for smart pointer):

foo( std::vector<boost::shared_ptr<MyType> >& v )
{
   std::for_each( v.begin(),
                  v.end(),
                  do_something );
}

bar()
{
    std::vector<boost::shared_ptr<MyType> > s;
    // s.push_back( boost::shared_ptr<MyType> ( new MySubType() ) );
    foo( s ); 
}

Answer 7

To expand on kuoson's answer, the idiomatic C++ style is to pass iterators to a function rather than containers.

template<typename Iterator>
void foo(const Iterator & begin, const Iterator & end)
{
    Iterator i;
    for (i = begin;  i != end;  ++i)
        // do stuff on *i
}

Answer 8

If I'd know what's the real code behind those foobars then maybe I'd know better, but isn't there already a solution for your problem in the STL?

for_each(s.begin(), s.end(), DoStuffOnI());

Just put your "do stuff on *i" code in a function or a functor:

struct DoStuffOnI : public std::unary_function<MyType&,void> {
    void operator()(MyType& obj) {
        // do stuff on *i
    }
};

If you're bothered about sending away two parameters instead of one, then ok, maybe you can do something like:

template<typename In>
struct input_sequence_range : public std::pair<In,In> {
    input_sequence_range(In first, In last) : std::pair<In,In>(first, last)
    {
    }
};

template<typename C>
input_sequence_range<typename C::iterator> iseq(C& c)
{
    return input_sequence_range<typename C::iterator>(c.begin(), c.end());
}

template<typename In, typename Pred>
void for_each(input_sequence_range<In> r, Pred p) {
    std::for_each(r.first, r.second, p);
}

Then call for_each like so:

for_each(iseq(s), DoStuffOnI());

Answer 9

If you want to store objects of multiple different MyType-derived types inside a single vector (as I suspect you do, although that's not necessary for this particular example), you'll need to use a std::vector<MyType*> instead of std::vector<MyType>. This suggestion is analogous to that proposed by Michael Burr for your original pointer code.

This does have the unfortunate side-effect that you cannot implicitly convert a std::vector<MySubType*> to a std::vector<MyType*> to call foo() with. But the conversion code is not too onerous:

void foo(std::vector<MyType*>& s)
{
    ...
}

void bar()
{
    std::vector<MySubType*> s;

    // Populate s
    ...

    std::vector<MyType*> u(s.begin(), s.end());    // Convert
    foo(u);
}

Or, just have bar() use a std::vector<MyType*> from the beginning.