Fixed Size Queue

Question

I have written a simple fixed size queue and am looking to get feedback on best practices. Specifically, handling unintended behaviors e.g. construct with negative size. This is not for a specific project but more of practicing good coding skills. I tried to follow the Google Code Style.

I am also looking for feedback on code coverage and unit tests.

Note: I realize that the pop function that I implemented is different that the std::queue and I don't have front and back functions.

Full code including CMakeLists.txt is here

fixed_size_queue.h

#ifndef FIXED_SIZE_QUEUE_H
#define FIXED_SIZE_QUEUE_H
#include "iostream"

template <class T> class FixedSizeQueue {
private:
  int size_;
  int start_index_;
  int end_index_;
  T *start_p_;

public:
  // Must be constructed with an argument
  FixedSizeQueue(int size);

  ~FixedSizeQueue();

  bool isEmpty() const;

  bool isFull() const;

  // push a single element to the queue
  // returns false if queue is full
  // returns true otherwise
  bool push(const T& data); 

  // pop a single element from the queue
  // returns the element on success
  // throws a logic_error exception if attempting to pop from an empty queue (undefined behavior)
  T pop();

  void print() const;
};

#endif

fixed_size_queue.cpp

#include "fixed_size_queue.h"
#include "gmock/gmock.h"
#include "stdexcept"

template <class T>
FixedSizeQueue<T>::FixedSizeQueue(int size)
    : size_(size), start_index_(-1), end_index_(-1), start_p_(new T[size]) {}

template <class T> FixedSizeQueue<T>::~FixedSizeQueue() { delete[] start_p_; }

template <class T> bool FixedSizeQueue<T>::isEmpty() const {
  return start_index_ == -1;
}

template <class T> bool FixedSizeQueue<T>::isFull() const {
  if ((end_index_ + 1 == start_index_) ||
      (start_index_ == 0 && end_index_ == size_ - 1))
    return true;
  else
    return false;
}

template <class T> bool FixedSizeQueue<T>::push(const T &data) {
  if (isFull()) {
    return false;
  } else if (isEmpty()) {
    start_index_ = 0;
    end_index_ = 0;
    start_p_[end_index_] = data;
  } else if (end_index_ != size_ - 1) {
    start_p_[++end_index_] = data;
  } else {
    end_index_ = 0;
    start_p_[end_index_] = data;
  }
  return true;
}

template <class T> T FixedSizeQueue<T>::pop() {
  if (isEmpty()) {
    throw std::logic_error("Empty Queue");
  } else if (start_index_ == end_index_) {
    T temp = start_p_[end_index_];
    start_index_ = -1;
    end_index_ = -1;
    return temp;
  } else if (start_index_ == size_ - 1) {
    start_index_ = 0;
    return start_p_[size_ - 1];
  } else {
    return start_p_[start_index_++];
  }
}

template <class T> void FixedSizeQueue<T>::print() const {
  if (start_index_ == -1) {
    std::cout << "Empty Queue" << std::endl;
  } else {
    for (int i = start_index_; i != end_index_;) {
      std::cout << start_p_[i] << "\t";
      if (i == size_ - 1) {
        i = 0;
      } else {
        ++i;
      }
    }
    std::cout << start_p_[end_index_];
    std::cout << std::endl;
  }
}

TEST(QueueTest, PushAndPopWithoutWrapping) {
  FixedSizeQueue<int> queue(5);
  queue.push(1);
  queue.push(2);
  ASSERT_THAT(queue.pop(), testing::Eq(1));
  ASSERT_THAT(queue.pop(), testing::Eq(2));
}

TEST(QueueTest, PushAndPopWithWrapping) {
  FixedSizeQueue<int> queue(3);
  queue.push(1);
  queue.push(2);
  queue.push(3);
  queue.pop();
  queue.push(4);
  ASSERT_THAT(queue.pop(), testing::Eq(2));
  ASSERT_THAT(queue.pop(), testing::Eq(3));
  ASSERT_THAT(queue.pop(), testing::Eq(4));
}

TEST(QueueTest, PushToAFullQueue) {
  FixedSizeQueue<int> queue(3);
  ASSERT_THAT(queue.push(1), testing::Eq(true));
  ASSERT_THAT(queue.push(2), testing::Eq(true));
  ASSERT_THAT(queue.push(3), testing::Eq(true));
  ASSERT_THAT(queue.push(4), testing::Eq(false));
}

TEST(QueueTest, PopFromEmptyQueue) {
  FixedSizeQueue<int> queue(3);
  try {
    queue.pop();
  } catch (std::logic_error &e) {
    EXPECT_STREQ("Empty Queue", e.what());
  }
}

Answer 1

Please consider using std::arraystd::vector (as @Incomputable noted) for storage. If you insist on using new, you have to add an own copy constructor (or to disable the compiler-generated copy constructor).

If you copy a FixedSizeQueue, the member pointer *start_p_ will be copied, too... and both instances will operate on the same memory, which clearly is not the intended behavior. Even worse, when the destructor is called on one instance, it will render the other instance in an unpredictable state (as it will delete[] the shared memory) and its destructor call will probably crash.

Answer 2

The interface to pop()

Let's start with your definition of pop. As clumsy as it is, there is a reason that pop_back (and pop_front) don't return the popped item. As you've defined it, pop has a serious problem with exception safety. If you pop the item from the queue, then it throws an exception while you're copying it to the caller, you've lost the item you just popped--it's no longer in the queue and the caller hasn't received it either.

It is possible to define a pop that's at least somewhat less clumsy (IMO) than that used by std::deque and such.

void pop(T &dest) {
    dest = /* front of queue */;
    /* remove front item from queue */
}

This way, one of two things happens: either the pop succeeds completely, or else it has no effect.

Memory Allocation

Right now, you're using new T[size] to allocate your storage. That's fine for something like int, but it's a serious problem if you want your queue to store things that can be moved but not assigned, or items that don't support default construction.

Most containers use operator new to allocate "raw" memory, then use placement new to create items in that space.

Assymetry

Right now, push signals failure (at least part of the time) by returning false but pop signals failure by throwing an exception. It's usually cleaner to choose one or the other and stick to it throughout the design.