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());
 }
}

• R Sahu: 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.
• jvb: size should be unsigned, or (even better) size_t. FixedSizeQueue(-1) does really bad things.
• Incomputable: @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.
• Sam: @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.
• jvb: @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...

Answer 1

Please consider using (削除) std::array (削除ここまで)std::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.

• Incomputable: std::array is unusable here due to runtime size.
• jvb: @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[].
• Incomputable: 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.
• jvb: @Incomputable I see what you mean. Let's simply use std::vector instead.

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.

• Incomputable: actually the item is still in the queue, but user will not be able to reach it
• Jerry Coffin: @Incomputable: Technically yes--but inaccessible is as good as gone.
• Sam: @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.
• Jerry Coffin: @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).