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.

std::queue<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)) };
std::optional<Animal> adoptAny() {
   if(_animals.empty()) return std::nullopt;

   auto adoptee = std::move(_animals.front());
   _animals.pop_front();
   return adoptee; // NRVO
}


template<typename T>
auto adoptFirstOfType() -> std::optional<T> {
  // Find first animal of given type
  const auto adoptee_it = std::find_if(
      begin(_animals),
      end(_animals), 
      [](const Animal& a) { return a.holds_alternative<T>(); };

  // If not found, return empty optional.
  if(adoptee_it == end(_animals)) {
      return std::nullopt;
  }

   // If found, steal the right alternative, remove from queue and return
   auto adoptee = std::get<T>(std::move(*adoptee_it));
   _animals.remove(adoptee_it);
   return adoptee; //NRVO
}

auto adoptDog() { // type deduced consistently from returned expression
   return adoptFirstOfType<Dog>();
}
auto adoptCat() { // type deduced consistently from returned expression
   return adoptFirstOfType<Cat>();
}

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 Cat be more than a Dog because it arrived first in the shelter)

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)) };
std::optional<Animal> adoptAny() {
   if(_animals.empty()) return std::nullopt;

   auto adoptee = std::move(_animals.front());
   _animals.pop_front();
   return adoptee; // NRVO
}


template<typename T>
auto adoptFirstOfType() -> std::optional<T> {
  // Find first animal of given type
  const auto adoptee_it = std::find_if(
      begin(_animals),
      end(_animals), 
      [](const Animal& a) { return a.holds_alternative<T>(); };

  // If not found, return empty optional.
  if(adoptee_it == end(_animals)) {
      return std::nullopt;
  }

   // If found, steal the right alternative, remove from queue and return
   auto adoptee = std::get<T>(std::move(*adoptee_it));
   _animals.erase(adoptee_it);
   return adoptee; //NRVO
}

auto adoptDog() { // type deduced consistently from returned expression
   return adoptFirstOfType<Dog>();
}
auto adoptCat() { // type deduced consistently from returned expression
   return adoptFirstOfType<Cat>();
}

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)

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.

std::queue<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.push_back(a) };
std::optional<Animal> adoptAny() {
   if(_animals.empty()) return std::nullopt;

   auto adoptee = std::move(_animals.front());
   _animals.pop_front();
   return adoptee;
}


template<typename T>
auto adoptFirstOfType() -> std::optional<T> {
  // Find first animal of given type
  const auto adoptee_it = std::find_if(
      begin(_animals),
      end(_animals), 
      [](const Animal& a) { return a.holds_alternative<T>(); };

  // If not found, return empty optional.
  if(adoptee_it == end(_animals)) {
      return std::nullopt;
  }

   // If found, steal the right alternative, remove from queue and return
   auto adoptee = std::get<T>(std::move(*adoptee_it));
   _animals.remove(adoptee_it);
   return adoptee;
}

auto adoptDog() { // type deduced consistently from returned expression
   return adoptFirstOfType<Dog>();
}
auto adoptCat() { // type deduced consistently from returned expression
   return adoptFirstOfType<Cat>();
}

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 Cat be more than a Dog because it arrived first in the shelter)

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.

std::queue<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)) };
std::optional<Animal> adoptAny() {
   if(_animals.empty()) return std::nullopt;

   auto adoptee = std::move(_animals.front());
   _animals.pop_front();
   return adoptee; // NRVO
}


template<typename T>
auto adoptFirstOfType() -> std::optional<T> {
  // Find first animal of given type
  const auto adoptee_it = std::find_if(
      begin(_animals),
      end(_animals), 
      [](const Animal& a) { return a.holds_alternative<T>(); };

  // If not found, return empty optional.
  if(adoptee_it == end(_animals)) {
      return std::nullopt;
  }

   // If found, steal the right alternative, remove from queue and return
   auto adoptee = std::get<T>(std::move(*adoptee_it));
   _animals.remove(adoptee_it);
   return adoptee; //NRVO
}

auto adoptDog() { // type deduced consistently from returned expression
   return adoptFirstOfType<Dog>();
}
auto adoptCat() { // type deduced consistently from returned expression
   return adoptFirstOfType<Cat>();
}

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 Cat be more than a Dog because it arrived first in the shelter)