Variadic Template - find the minimum in a tuple of objects of the same type

Question

I was trying to solve the following exercise from cracking the code Cracking the Code interview (pag. 81):

An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.You may use the built-in LinkedList data structure.

With only two animals is easy and I managed to do it implementing a class Shelter that keeps two separate queues, one for cats and dogs and storing the time at which the animal is enqueued. However, I was wondering how to generalise it to a generic number of animals, without the need to actually change the interface of the class Shelter. I thought that variadic template could help, but I cannot understand how to write a the code/syntax to declare the different Queues for the different type of animals.

First is this possible? Does anyone have an idea?

Thanks to suggestions, I think I made some progress:

template <typename A>
struct Animal {
    string hello(void) {return A::hello(); }
    string name;
};


class GenericAnimal {
    public: 
        virtual string hello(void) {return "????";}
};

class Dog : public GenericAnimal {

    public:
        virtual string hello (void) {return "waf waf";}
};
class Cat : public GenericAnimal {
    public:
        virtual string hello (void) {return "miao miao";}
};


template <typename ...A>
class Shelter {
    public:
        Shelter():time(0){}
        template <typename T>
        void getQueueFor( queue< tuple<int, Animal<T>> > &q ){
            q= get< queue< tuple<int, Animal<T>> > > (shelterQueues);
        }

        template <typename T>
        void addAnimals(Animal<T> &a) {
            tuple<int, Animal<T>> aa  (time++, a);
            (get< queue< tuple<int, Animal<T>> > > (shelterQueues)).push(aa);
        } 

        GenericAnimal& getOldestAnimal (void) {
            size_t size= std::tuple_size<decltype(shelterQueues)>::value;
            for(size_t i=0; i < size; i++) {
                get<0>(shelterQueues);
                cout << i << ",";
            } 
            cout << endl;

        }

    private:
        int time;
        tuple< queue< tuple <int, Animal<A>> >... > shelterQueues;
};

I am able to enque cats and dog now. Now, I was trying to implement dequeAny(), that should return the oldest animal in the system, but I got stuck. Basically, the problem is that I have to iterate over the tuple of queues and see which head has the lowest time. Looking around I found how to iterate over a tuple iterate-over-tuple. The problem is that even if I manage to identify it, let's call it K, then I need to do get(myQueue) and this should not work because K is not known at compile time. Am I wrong? Any idea if it is possible and how to do it?

Thanks

Answer 1

Use an std::tuple. As mentioned in the comments, a tuple<queue<T>> fits your use-case. A useful thing about tuples is that it lets you query an element by type, as long as the types it is templated on are unique. Here's an example:

template <typename ... Animals>
class AnimalQueue
{
public:
template <typename T>
queue<T> GetQueueFor(){return get<queue<T>>(mQueues);}

tuple<queue<Animals>...> mQueues;
};