Animal Shelter Management C++

I am working my way through "Cracking the Coding Interview" and I came up the question(3.6) to design a data structure to manage an Animal shelter with 2 animals, Cats, and Dogs such that when we dequeue the oldest animal should be removed first (FIFO)

E.g. if the animals were taken in order C,C,D,C,C,D (C- Cat, D- Dog) and someone wants to adopt an animal there could be 3 ways either adopt D, adopt C, or adopt any(I have just implemented for any as other two are trivial). If the person chooses to adopt D the first D to come in would be chosen from the queue similarly with C. If the person has no preference either of C, D who came first can be chosen.

I implemented it as below. What all improvements can be done here? One possible way is to improve printQueue() function using 'this'.

#include <iostream>
#include <queue>

using namespace std;

class Animal {
public:
virtual string getClassName() = 0;

inline int getOrder() {
return _order;
}

void setOrder(int order) {
_order = order;
}

int setType(string type) {
_type = type;
}

inline string getType() {
return _type;
}

bool Compare(Animal* animal) {
if (this->_order > animal->_order)
return true;
return false;
}
private:
int _order;
string _type;
};

class Cat : public Animal {
public:
Cat(string name) : _name(name) {
}

inline string getClassName() {
return "Cat";
}

inline string getName() {
return _name;
}

private:
string _name;
};

class Dog : public Animal {
public:
Dog(string name) : _name(name) {
}

inline string getClassName() {
return "Dog";
}

inline string getName() {
return _name;
}

private:
string _name;
};

class AnimalQueue {
public:
void enqueue(Animal* animal) {
if (animal->getClassName() == "Cat") {
Cat* d = dynamic_cast<Cat*>(animal);
if (!d) {
cout << "\nCasting Error";
}
else {
cout << "\nEnqueued Cat";
d->setOrder(++queueOrder);
d->setType(animal->getClassName());
catQueue.push(d);
}
}
else{

Dog* d = dynamic_cast<Dog*>(animal);
if (!d) {
cout << "\nCasting Error";
}
else {
cout << "\nEnqueued Dog";
d->setOrder(++queueOrder);
d->setType(animal->getClassName());
dogQueue.push(d);
}
}
}
void dequeue() {
if (catQueue.empty()) {
dogQueue.pop();
}
if (dogQueue.empty())
{
catQueue.pop();
}
//Pop with smaller timestamp
if (catQueue.front()->Compare(dogQueue.front())) {
dogQueue.pop();
}
else {
catQueue.pop();
}
}

void printQueue() {
queue<Cat*> cQueue = this->catQueue;
queue<Dog*> dQueue = this->dogQueue;

cout << "\nCat Queue\n";
while (!cQueue.empty()) {
cout << cQueue.front()->getName() << " ";
cout << cQueue.front()->getOrder();

cout << endl;
cQueue.pop();
}

cout << "\nDog Queue\n";
while (!dQueue.empty()) {
cout << dQueue.front()->getName() << " ";
cout << dQueue.front()->getOrder();

cout << endl;
dQueue.pop();
}

}

queue<Dog*> getDogQueue() {
return dogQueue;
}

queue<Cat*> getCatQueue() {
return catQueue;
}

private:
queue<Cat*> catQueue;
queue<Dog*> dogQueue;
int queueOrder = -1;
};

int main()
{
Animal* d1 = new Dog("Max"),*d2 = new Dog ("Shaun"), *d3 = new Dog("Tiger");
Animal* c1 = new Cat("Trace"), *c2 = new Cat("Han"), *c3 = new Cat("Meow");

AnimalQueue queue;
queue.enqueue(d1);
queue.enqueue(c1);
queue.enqueue(c2);
queue.enqueue(d2);
queue.enqueue(d3);
queue.enqueue(c3);

cout << endl;
queue.printQueue();

cout << endl;

queue.dequeue();
queue.printQueue();
}

• You also need something else for this to compile ... string is an undeclared identifier ... Jul 15 '19 at 3:53
• That's why I don't use namespaces, don't know why I did it here @L.F. Jul 15 '19 at 4:05
• Just a note: you could solve this in C++ with templates and some constexpr with much less code.
– mfnx
Oct 5 '20 at 13:33

To supplement the other reviews, here are some other things you might improve.

Use override where appropriate

When a virtual function is being overridden, it should be marked override to allow catching errors at compile time. See C.128.

Make sure all paths return a value

The setType routine claims it returns an int but it does not. That's an error that should be addressed.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

The traditional role of a shelter is to take in animals and then give them to a new owner on adoption. This shelter seems to only do bookkeeping of the location of animals (by handling only pointers) rather than actually taking ownership of them. What is actually a more appropriate way to express this is by the use of a std::unique_ptr. See R.20

Think carefully about the domain and range of numbers

The _queueOrder increases without bound and is used to assign the _order of each animal. What happens when that number wraps around?

Use polymorphism effectively

Whenever you find yourself writing code like this:

if (animal->getClassName() == "Cat") {
Cat* d = dynamic_cast<Cat*>(animal);


stop and question whether this is really needed. By using animal->getClassName() as a sort of home-grown polymorphism, the code is made much more brittle and hard to maintain. Here's how I'd write that using a std::unique_ptr instead:

void enqueue(std::unique_ptr<Animal> &&animal) {
animal->setOrder(++queueOrder);
if (typeid(*animal) == typeid(Cat)) {
catQueue.push_back(std::move(animal));
} else if (typeid(*animal) == typeid(Dog)) {
dogQueue.push_back(std::move(animal));
} else {
throw std::runtime_error("This animal is not suitable for the shelter");
}
}


Note that this uses true RTTI, built into the language, instead of inventing a poor imitation. It also throws an error if the passed animal is neither a cat nor a dog. This could be handy if someone attempted to drop off a pet rhinocerous.

Don't expose class internals

It seems to me that getDogQueue and getCatQueue are both ill-advised and unneeded. I'd simply omit them both.

Base destructors should be virtual

The destructor of a base class, including a pure virtual one like Animal, should be virtual. Otherwise, deleting the object could lead to undefined behavior and probably memory leaks.

Consolidate common items into a base class

Since all of the derived classes have _name, why not move that functionality into the base class?

Use const where practical

The getName() function does not alter the underlying class because it returns a copy of the name. Similarly, the getClassName() function does not alter the class. Both should be declared const.

Use standard operators

Rather than the vaguely named Compare, better would be to simply use the standard operator<. Here's how I'd write it as a member function of Animal:

bool operator<(const Animal& b) const {
return _order < b._order;
}


Use better names

Most of the names are not bad, but rather than AnimalQueue and enqueue and dequeue, I'd suggest giving them more usage-oriented names rather than describing the internal structure. So perhaps AnimalShelter, dropoff and adopt would be more suitable.

If you use a std::deque instead of a std::queue, you gain access to iterators which are useful for printing as shown in the next suggestion.

Use an ostream &operator<< instead of display

The current code has printQueue() function but what would make more sense and be more general purpose would be to overload an ostream operator<< instead. This renders the resulting function much smaller and easier to understand:

friend std::ostream& operator<<(std::ostream& out, const AnimalShelter& as) {
out << "\nCat Queue\n";
for (const auto& critter : as.catQueue) {
out << *critter << '\n';
}
out << "\nDog Queue\n";
for (const auto& critter : as.dogQueue) {
out << *critter << '\n';
}
return out;
}


I also modified the base class to include _name as mentioned above and wrote this friend function of Animal:

friend std::ostream& operator<<(std::ostream& out, const Animal& a) {
return out << a.getClassName() << ' ' << a._name << ' ' << a._order;
}


Implement the problem specification completely

The description of the problem mentions that one might be able to adopt either a cat or a dog or the first available, but only the latter function has been implemented. Here's how I wrote all three:

std::unique_ptr<Animal> adopt() {
if (catQueue.empty() && dogQueue.empty())

if (catQueue.empty()) {
dogQueue.pop_front();
} else if (dogQueue.empty() || (catQueue.front() < dogQueue.front())) {
catQueue.pop_front();
} else {
dogQueue.pop_front();
}
}

if (!catQueue.empty()) {
catQueue.pop_front();
}
}

if (!dogQueue.empty()) {
dogQueue.pop_front();
}
}


Results

Here is the modified main to exercise the revised code:

int main()
{
AnimalShelter shelter;
shelter.dropoff(std::unique_ptr<Animal>(new Dog{"Max"}));
shelter.dropoff(std::unique_ptr<Animal>(new Cat{"Trace"}));
shelter.dropoff(std::unique_ptr<Animal>(new Cat{"Han"}));
shelter.dropoff(std::unique_ptr<Animal>(new Dog{"Shaun"}));
shelter.dropoff(std::unique_ptr<Animal>(new Dog{"Tiger"}));
shelter.dropoff(std::unique_ptr<Animal>(new Cat{"Meow"}));
try {
shelter.dropoff(std::unique_ptr<Animal>(new Rhino{"Buster"}));
} catch (std::runtime_error &err) {
std::cout << err.what() << '\n';
}
std::cout << shelter << '\n';

for (int i = 0; i < 2; ++i) {
if (pet) {
std::cout << "You have adopted " << *pet << "\n";
} else {
std::cout << "sorry, there are no more pets\n";
}
std::cout << shelter << '\n';
}

for (int i = 0; i < 6; ++i) {  // adopt any
if (pet) {
std::cout << "You have adopted " << *pet << "\n";
} else {
std::cout << "sorry, there are no more pets\n";
}
std::cout << shelter << '\n';
}

std::cout << "Final: \n" << shelter << '\n';
}

• Thankyou for briefly explaining! I didn't know much about std::endl as I have just used it in college to break lines but this explanation is really nice! Also, I did not think of the range of int, good point! Virtual destructor, how did I miss that! Jul 15 '19 at 21:36
• I would suggest to use std::make_unique instead of std::unique_ptr(new …) if you have C++14 or higher. Not 100% sure that it will work. Jul 16 '19 at 13:10
• @val: You're right about std::make_unique. An earlier iteration of my code didn't work with it but this one does. One can use std::make_unique<Cat>("Whiskers") for a bit more succinct code. Jul 16 '19 at 13:36
• Why is the exception not const. Main doesn't return a value. It's a better interface if AnimalShelter had separate dropoffDog() and dropoffCat() functions, as then you wouldn't need any RTTI nonsense and the use of unique_ptr's would be hidden from the user. This is essentially Java. Jul 16 '19 at 14:47
• @nowox I believe you are misinterpreting what it says. While they may not return the same instance, they are guaranteed to return true from their operator==(). Otherwise typeid would be rather useless. Dec 9 '20 at 11:37

In addition to the suggestions given by 1201ProgramAlarm's answer, I have the following suggestions.

First, your (over)use of RTTI seems overkill here. Even dynamic polymorphism is not necessary. A simple class is enough:

enum class Species { cat, dog };

struct Animal {
Species species;
std::string name;
};


(You are missing #include <string>)

Second, you maintain two queues. Since this is an animal shelter, why not merge them? You can use vector to accommodate for adopters that prefer a specified species.

std::vector<Animal> animals;


Third, dequeue returns void. This is abandonment, not adoption. It should return the Animal. (An animal protectionist can even go further and mark the function [[nodiscard]].)

Also, let print accept an ostream&, so you can print to any stream.

Here's the revised version:

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

enum class Species { cat, dog };

std::string to_string(Species species)
{
switch (species) {
case Species::cat:
return "cat";
case Species::dog:
return "dog";
default:
throw std::invalid_argument{"Unrecognized species"};
}
}

struct Animal {
Species species;
std::string name;
};

class Shelter {
public:
void enqueue(Animal animal)
{
animals.push_back(animal);
}
Animal dequeue(Species species)
{
auto it = std::find_if(animals.begin(), animals.end(),
[=](const Animal& animal) {
return animal.species == species;
});
if (it == animals.end())
Animal animal = std::move(*it);
animals.erase(it);
return animal;
}
Animal dequeue()
{
if (animals.empty())
Animal animal = std::move(animals.front());
animals.erase(animals.begin());
return animal;
}
void print(std::ostream& os)
{
for (const auto& animal : animals) {
os << animal.name << " (" << to_string(animal.species) << ")\n";
}
}
private:
std::vector<Animal> animals;
};

int main()
{
Shelter shelter;
shelter.enqueue({Species::dog, "Max"});
shelter.enqueue({Species::cat, "Trace"});
shelter.enqueue({Species::cat, "Han"});
shelter.enqueue({Species::dog, "Shaun"});
shelter.enqueue({Species::dog, "Tiger"});
shelter.enqueue({Species::cat, "Meow"});

shelter.print(std::cout);
std::cout << "\n";

auto new_pet = shelter.dequeue();
shelter.print(std::cout);
std::cout << "\n";

auto new_dog = shelter.dequeue(Species::dog);
shelter.print(std::cout);
}


Output:

Max (dog)
Trace (cat)
Han (cat)
Shaun (dog)
Tiger (dog)
Meow (cat)

Trace (cat)
Han (cat)
Shaun (dog)
Tiger (dog)
Meow (cat)

Trace (cat)
Han (cat)
Tiger (dog)
Meow (cat)

• I would note that algorithmic-wise, maintaining differentiating queues has a different complexity trade-off than maintaining a single queue. Popping a Cat off a single-queue is an O(number-animals) operation, while popping a Cat off differentiated queues is O(1). Jul 15 '19 at 12:12
• @MatthieuM. Good point. It seems unlikely that OP would be dealing with a lot of animals in this case, anyway :) Jul 15 '19 at 14:12
• My first thought was "oh another 'let's use inheritance for animals' type problem, let's see how unnecessary complex it can get" and I was not disappointed. Would give +2 if I could, given that other answers already started with virtual destructors and Knuth knows what. It' also easy to maintain different queues for each species with this approach as well if that's really necessary.
– Voo
Jul 16 '19 at 17:30
• @MatthieuM. If you maintain two different queues, how would you account for the case where the species doesn't matter and you just want to dequeue an animal? Jul 17 '19 at 12:07
• @AleksandrH: Similarly to what the OP is doing, you need an index (they call "queueOrder"). I would not however store it in the Animal itself, as this is metadata, and instead would store std::pair<Order, Dog> and std::pair<Order, Cat> respectively. Jul 18 '19 at 6:27

First off, you should avoid using namespace ::std.

In Animal, getOrder and getType should be const (int getOrder() const). Since they're defined within the class definition, you don't need to include the inline keyword. Similarly, getters in the derived classes should be const.

It is rarely ever necessary to use the this keyword, and the places where you use this-> to access a member variable can do without it.

Compare should also be const (and take its parameter as a const Animal *, and can be simplified to return _order > animal->_order;.

You never delete any of the memory you allocate with new.

You should declare a virtual destructor for Animal since it is used as a base class. It isn't a direct problem here, since you never delete any of the memory you allocate, but if you'd delete Animals you dequeue, you'd still leak memory as the strings in the derived classes would not be freed.

In AnimalQueue you can have separate enqueue methods that take Cat * and Dog * parameters. This would avoid needing to have all that code to check the type, and would work better if you have further derived classes (like "Tiger" derived from "Cat" or "Wolf" derived from "Dog"). The generic enqueue(Animal *) can call the proper overloaded enqueue after checking the result of the dynamic cast. Something like

if (auto cat = dynamic_cast<Cat*>(animal))
enqueue(cat);
else if (auto dog = dynamic_cast<Dog*>(animal))
enqueue(dog);
else /* error handling */;


assuming you're using a compiler that supports the variable declarations in if conditional expressions.

dequeue has several bugs. It will attempt to remove elements from empty containers, and could also try to access elements from empty containers.

printQueue should be const, and should use iterators to print the contents of the queues. Since displaying the two queues has a bunch of duplicated code, make a function that will display one queue and call that for each queue you want to display.

getDogQueue and getCatQueue should be const and return const references.

In addition to other answers: you're using inline a lot. Do not.

Modern compilers (almost all starting from year 2000) don't use it for optimization anyways: they are already clever enough to do so without hints when possible. These days inline have another meaning in some contexts (when function is defined in many translation units), but in your situation it's a simple no-op.

• Welcome to Code Review! It would be nice if you could add some external resources or a online compiler example to back your claim. Jul 15 '19 at 14:05

I'll assume in 2019 that C++17 is available.

All other answers seem to be using two queues, one for each type of animal, but I think it kinda defeats the purpose that the FIFO behaviour has to be on the whole set of animals. With two queues, the FIFO has to be implemented by an _order stored with the animal, which mixes the data with the algorithm. Once the animal is adopted, out of the shelter, the _orderhas no meaning, but is still part of the structure.

Using a queue, I would use a single queue of animals, which implements FIFO. (But the deque allows you to remove from the middle of it)

std::deque<Animal> _animals;


Now, the animal being either a cat or a dog, I would just say so

using Animal = std::variant<Dog,Cat>;


And implement each species as its own class.

class Cat { /* implementation*/ };
class Dog { /* implementation*/ };


Then, borrowing terminology from Edward's answer, I would simply implement:

void dropoff(Animal a) { _animals.emplace_back(std::move(a)) };
if(_animals.empty()) return std::nullopt;

_animals.pop_front();
}

template<typename T>
// Find first animal of given type
begin(_animals),
end(_animals),
[](const Animal& a) { return a.holds_alternative<T>(); };

return std::nullopt;
}

// If found, steal the right alternative, remove from queue and return
}

auto adoptDog() { // type deduced consistently from returned expression
}
auto adoptCat() { // type deduced consistently from returned expression
}


Edward's main function should work fine as is, because optional has the same "container access" interface as unique_ptr.

This allows to simply drop the _order and operator< hacks from his solution. (because yes, implementing operator< is a hack - it makes no sense that a Dog be more than a Cat because it arrived first in the shelter)

• Good answer! I also considered the use of std::optional for this. I also like to think of C++17 as everywhere by now but just this morning I was trying to compile a program on a Raspberry Pi and found that alas, the compiler was only up to C++14. As for operator< being a hack, I disagree. The only ordering among animals mentioned in the problem statement is time-in-shelter, so it makes sense that a standard operator would be used to express that. And by the way as I implemented it, it would be Cat < Dog if the cat had arrived first. :) Jul 16 '19 at 18:59
• @L.F.: You seem to be right. That would take a deque instead of a queue. Correcting this. Jul 17 '19 at 6:12
• @Edward: You're right, the logic is inverted in my answer. Correcting this Jul 17 '19 at 6:16
• @Edward : thinking again, I think the problem is not in the operator<, but in the fact that the _order should not belong to the Animal class, because once the animal is out of the shelter, the _order matters no more. Maybe the queue(s) should instead store a std::pair<size_t, Animal or Dog or Cat>, and then you could define a cleaner operator< like template<typename T, typename U> bool operator<(const std::pair<size_t,T>&, const std::pair<size_t,U>&) Jul 17 '19 at 6:31
• My single queue is bothering me, come to think of it. Adopting a specific animal implies a lookup, and I suppose adoptAny is not the dominating case. As such, one queue per animal type seem to be constant-time in either case, so would be the proper way to handle the problem. Jul 17 '19 at 7:01

Design

Is a single queue acceptable, or does each animal need its own?

Multiple queues need more bookkeeping, as well as slight overhead when enqueueing an animal, or dequeueing the senior resident regardless of species.
While one can put the entrance-order in the animal-class, it certainly does not belong.

A single queue potentially require looking at every single animal to find one of a specific species. On the flip-side, adding additional species comes naturally.

Implementation

1. ::std is not designed for wholesale inclusion. It contains myriad symbols, there is no comprehensive list, and it is always evolving. Your code might not "work" today, but tomorrow it might fail to compile, or worse silently change ist meaning.
Read "Why is “using namespace std” considered bad practice?" for more detail.

2. You are flat-out leaking all your animals.

As the program terminates directly afterwards, and deleteing them has no observable effect you depend on, that could be a good idea.
That is, if it was intentional, well-explained, and not demo-code, but neither is the case.

Consider an appropriate use of smart-pointers, specifically std::unique_ptr, as manual resource-management is error-prone.

3. Generally, polymorphic types should have a virtual dtor, so they can be deleted polymorphically.

4. The string type is set to the classname when enqueueing? Rip that out at the roots, you can use the source directly.

5. Unless you need a friendly name for presistence or display, consider fully relying on builtin RTTI instead of adding your own home-grown variant. Use typeid if you want exact type-matching, or dynamic_cast if subtypes are fair game.

6. All member-functions defined inline are automatically inline.

7. Avoid needlessly copying strings, that's inefficient. Prefer std::string_view where applicable.

8. Mark functions noexcept if you can.

9. Mark overrides override for documentation and to allow the compiler to catch mistakes.

10. printQueue() clears it? That violates all expectations. And anyway, it should be std::ostream& operator<<(std::ostream&, AnimalQueue const&).

You probably should move from std::queue to directly using std::deque when fixing that, even though you can safely access the underlying container.

Using a single shared queue (also live on coliru):

#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

class Animal {
public:
virtual std::string_view friendlyName() noexcept = 0;
virtual ~Animal() = default;
};

class Cat : public Animal {
std::string _name;
public:
Cat(std::string name) : _name(std::move(name)) {}

std::string_view friendlyName() noexcept override { return "Cat"; }
};

class Dog : public Animal {
std::string _name;
public:
Dog(std::string name) : _name(std::move(name)) {}

std::string_view friendlyName() noexcept override { return "Dog"; }
};

class Shelter {
std::vector<std::unique_ptr<Animal>> _queue;
public:
template <class T = Animal>
std::unique_ptr<T> get() noexcept {
auto pos = std::find_if(_queue.begin(), _queue.end(), [](auto&& x){ return dynamic_cast<T*>(x.get()); });
if (pos == _queue.end())
return {};
std::unique_ptr<T> r(dynamic_cast<T*>(pos->release()));
_queue.erase(pos);
return r;
}

void put(std::unique_ptr<Animal>&& a) {
if (a)
_queue.push_back(std::move(a));
}

friend std::ostream& operator<<(std::ostream& os, Shelter const& s) {
for (auto&& x : s._queue)
os << x->friendlyName() << ' ';
os << '\n';
return os;
}
};

int main()
{
auto d1 = std::make_unique<Dog>("Max");
auto d2 = std::make_unique<Dog>("Shaun");
auto d3 = std::make_unique<Dog>("Tiger");
auto c1 = std::make_unique<Cat>("Trace");
auto c2 = std::make_unique<Cat>("Han");
auto c3 = std::make_unique<Cat>("Meow");

Shelter shelter;
shelter.put(std::move(d1));
shelter.put(std::move(c1));
shelter.put(std::move(c2));
shelter.put(std::move(d2));
shelter.put(std::move(d3));
shelter.put(std::move(c3));

std::cout << shelter;
shelter.get();
std::cout << shelter;
}

• I also proposed a solution with a single queue, but it has the inconvenient of requiring a linear search for the common case :adopting an animal of a specific species. The OP's solution of multiple queues with an everincreasing 64-bit order of entry gives constant time search in every case. You're making good points otherwise. Jul 18 '19 at 14:28