4
\$\begingroup\$

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());
  }
}
\$\endgroup\$
  • \$\begingroup\$ I deleted my answer since I ended up implementing a stack instead of a queue. However, my suggestion about The Rule of Three is something you should look into. \$\endgroup\$ – R Sahu Jul 16 '17 at 4:41
  • 1
    \$\begingroup\$ size should be unsigned, or (even better) size_t. FixedSizeQueue(-1) does really bad things. \$\endgroup\$ – jvb Jul 16 '17 at 6:49
  • \$\begingroup\$ @jvb, new expression will cast it anyway, so it would just overflow ram and hopefully system will kill it. Though I'm not sure if integer promotion will kick in, in which case it will just allocate huge amount of memory, but not enough to overflow. \$\endgroup\$ – Incomputable Jul 16 '17 at 6:52
  • \$\begingroup\$ @jvb I converted size_ to be of type size_t_ but I want start_index_ to remain an int so that I can assign -1 to it when the queue is empty. This causes a warning when doing start_index_ == size_ -1 comparison between signed and unsigned integer expressions. I can do start_index_ == (int)size_ -1 instead. Can you recommend a better way? of course going to a std::vector implementation as suggested below will solve this altogether. \$\endgroup\$ – Sam Jul 16 '17 at 14:32
  • 1
    \$\begingroup\$ @Sam You could maybe use a hypothetical unsigned count (current fill level) instead of end_index? Both isEmpty and isFull implementations would become easier, but you would have to replace end_index with start_index+count... \$\endgroup\$ – jvb Jul 16 '17 at 16:08
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ std::array is unusable here due to runtime size. \$\endgroup\$ – Incomputable Jul 16 '17 at 6:48
  • \$\begingroup\$ @Incomputable std::array can be used with variable size determined at runtime, but the size cannot be changed after allocation at runtime... exactly the same as with new[]. \$\endgroup\$ – jvb Jul 16 '17 at 6:55
  • \$\begingroup\$ the only place to supply the size would be constructor, but there is none that takes any integer, and default one is implicitly declared. The only option is template argument, which strictly should be supplied during compilation time. Unless one can implement type erasure and gigantic switch statement. \$\endgroup\$ – Incomputable Jul 16 '17 at 6:58
  • \$\begingroup\$ @Incomputable I see what you mean. Let's simply use std::vector instead. \$\endgroup\$ – jvb Jul 16 '17 at 7:04
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ actually the item is still in the queue, but user will not be able to reach it \$\endgroup\$ – Incomputable Jul 16 '17 at 6:44
  • \$\begingroup\$ @Incomputable: Technically yes--but inaccessible is as good as gone. \$\endgroup\$ – Jerry Coffin Jul 16 '17 at 6:50
  • \$\begingroup\$ @JerryCoffin Is it safe to generalize this and say: A member function that cannot be declared a const member function should not return a variable? Or it this statement too broad? If I understood correctly the issue is that the copy to caller might throw and exception and we end up with no return value but the function has had its effect. \$\endgroup\$ – Sam Jul 16 '17 at 15:38
  • 1
    \$\begingroup\$ @Sam: Some people take the notion of single responsibility to the point that they figure a member should either return a value, or change a value, but never both. While I respect the underlying idea, it doesn't seem (to me) that it necessarily leads to better designs (and for many compare-exchange sorts of atomic operations, it just doesn't work at all). \$\endgroup\$ – Jerry Coffin Jul 16 '17 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.