C++: Returning abstract type as an interface

I'm trying to achieve something illustrated with this piece of code, but I can't get it to work. I can't return an Animal, and I really don't think returning an Animal* would be a good solution, because I'd have to new and delete manually.

EDIT: I updated the question with a more specific code snippet, demonstrating why returning Animal* isn't a really good idea.

As you can see from the snippet, I basically want to use an Animal as an interface for a bunch of data, and that data may be part of an array or it may be a more conventional object.

EDIT 2: Working example: http://ideone.com/4qp3qT

Remaining problems:

duplicate code (FeedAnimals())
performance?
having to delete manually (for the cats)

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <stdlib.h>
using namespace std;


class Animal {
    virtual void eat() = 0;
};

// Dog is more high-level
class Dog: public Animal {
    char attr1;
    char attr2;

    Dog(_attr1, _attr2):
        attr1(_attr1),
        attr2(_attr2)
        {}

    Dog():
        attr1('d'),
        attr2('g')
        {}

    void eat() {
        cout << "Dog ate food (" << attr1 << attr2 << ").\n";
    }

    void barf() {
        cout << "Whaf";
    }
};

// Cat is more low-level
class Cat: public Animal {
    // A cat can basically only exist in a cage
    // and it's attributes are defined by it's location
    // in the Cage's underlying array. A Cat should also
    // have to 2 attributes (both char), so this would
    // be kind of true:
    //   sizeof(Cat) == 2

    char* ptr;

    // I will only use a Cat in a context of arrays, so
    // no need to care about memory management here.
    Cat(char* _ptr):
        ptr(_ptr)
        {}

    void eat() {
        cout << "Cat ate food (" << *ptr << *(ptr+1) << ").\n";
    }

    void meow() {
        cout << "Meow.";
    }
};


class Cage {
    virtual Animal GetRandomAnimal() = 0;
};

// DogCage uses a nice (more high level) vector
class DogCage {
    vector<Dog> dogs;

    DogCage():
        dogs(5)
        {}

    Animal GetRandomAnimal() {
        // ?
    }
}

// CatCage uses a more low level pointer together with
// malloc etc.
class CatCage {
    char* cats;

    CatCage():
        cats((char*) malloc(4*2)) // room for 4 cats
        {}

    ~CatCage() {
        free(cats);
    }

    Animal GetRandomAnimal() {
        // ...

        // This is why it's difficult to return a pointer
        // to an Animal. I basically want to use a Cat as
        // a simple interface to a part of an array.
        // If I use pointers etc, that seems like it would
        // hit performance.
        return Cat(cats+(random*2))
    }
}

void FeedAnimals(Animal& a) {
    a.eat();
}

int main() {
    Cage cage; // ?
    string s;

    cout << "Cats or dogs?";
    cin >> s;
    if (s=="Cats") {
        cage = CatCage(); // ?
    } else {
        cage = DogCage(); // ?
    }

    // fill cage with animals (either cats or dogs)

    FeedAnimals(cage.GetRandomAnimal());
}

Solution

Your real problem is that you're arbitrarily trying to avoid using the tools (pointer, reference, or smart pointer) available for the job.

I'm guessing, this is because you are familiar with some other language that seems to permit this. The thing is, languages which do such things do it by blending concepts of object, reference, and pointer in ways that C++ does not.

It is not possible in C++ to return an abstract class by value. Period. Returning a class by value means it is necessary to instantiate it and an abstract class is one that cannot be instantiated.

If your function returns a raw reference or pointer, it is necessary that the objects exist when the caller uses them, and that the objects are released (cease to exist) when no longer needed. Either that means your function accepts responsibility for managing object lifetime (e.g. the object is an element of an array) or that the caller is (e.g. function dynamically creates object, caller releases it when done).

Returning a smart pointer means returning an object that manages lifetime of the contained object. The function creates the object, hands it to a smart pointer, and the smart pointer is returned to the caller. When the smart pointer no longer exists (e.g. caller returns so it passes out of scope), the object is released.