CODEWITHSUNDEEP
c++queue
Salem
Salem

Reputation: 11

C++ Queue Implementation using the Default Move Assignment Operator

My group and I attempted to implement a queue in C++ based on the following example for the code of a stack.

template<typename T>
class Stack {

private:
 struct Node {
   T data;
   Node* next;
   Node(T data, Node* next): data(data), next(next) {}
   // No destructor here; it is a private inner class and would be slow
   // to delete a chain of nodes this way!
 };
 private:
 Node* head;
 public:
 Stack(): head(nullptr) {}
 ~Stack() {
   while (head != nullptr) {
     Node* old_head = head;
     head = head->next;   // update
     delete old_head;
   }
 }

 // Prohibit copy construction and copy assignment
 Stack(Stack&) = delete;
 Stack& operator=(Stack&) = delete;

 // Wait wait I want to be able to move
 Stack(Stack&&) = default;
 Stack& operator=(Stack&&) = default;

public:
 int getSize() {
   int count = 0;
   for (Node* n = head; n != nullptr; n = n->next) count++;
   return count;
 }
  bool isEmpty() {
   return head == nullptr;
 }
  void push(T x) {
   head = new Node(x, head);
 }
  T pop() {
   if (isEmpty()) {
     throw underflow_error("Cannot pop from empty stack");
   }
   Node* nodeToDelete = head;
   T poppedValue = head->data;
   head = head->next;
   delete nodeToDelete;
   return poppedValue;
 }
  T peek() {
   if (isEmpty()) {
     throw underflow_error("Cannot peek into empty stack");
   }
   return head->data;
 }
};

Just like the stack example, we attempted to implement move for the queue using the same ideas, including the default move assignment operator. Doing this, we came across problems such as invalid operands errors, collapsed stack frames and more when running our code.

template < typename T >
class Queue {
  private:
    struct Node {
      T data;
      Node * next;
      Node(T data, Node * next): data(data), next(next) {}
    };
  private: Node * head;
  private: Node * tail;
  public:
    Queue(): head(nullptr), tail(nullptr) {}~Queue() {
      while (head != nullptr) {
        Node * old = head;
        head = head -> next;
        delete old;
      }
    }
  Queue(Queue & ) = delete;
  Queue & operator = (Queue & ) = delete;
  Queue(Queue && ) = default;
  Queue & operator = (Queue && ) = default;
  public:
    int get_size() {
      int count = 0;
      for (Node * n = head; n != nullptr; n = n -> next)
        count++;
      return count;
    }
  bool isEmpty() {
    return head == nullptr;
  }
  void enqueue(T x) {
    Node * temp = new Node {x, nullptr};
    if (head == nullptr) {
      head = temp;
      tail = temp;
    } else {
      tail -> next = temp;
      tail = temp;
    }
  }
  T dequeue() {
    if (isEmpty()) {
      throw underflow_error("Cannot dequeue from empty queue");
    }
    Node * nodeToDelete = head;
    T poppedValue = head -> data;
    head = head -> next;
    delete nodeToDelete;
    return poppedValue;
  }
};

We ended up making our own move assignment operator which the queue worked as expected. The following code is what we ended up with.

Template <typename T>
class Queue {
private:
  struct Node {
    T data;
    Node *next;
    Node(T data, Node *next) : data(data), next(next) {}
  };
private:
  Node *head;
private:
  Node *tail;
public:
  Queue() : head(nullptr), tail(nullptr) {}
  ~Queue() {
    while (head != nullptr) {
      Node *old = head;
      head = head->next;
      delete old;
    }
  }
  Queue(Queue &) = delete;
  Queue &operator=(Queue &) = delete;
  Queue(Queue &&) = default;
  Queue &operator=(Queue &&other) {
    if (&other == this) {
      return *this;
    }
    delete head;
    head = other.head;
    tail = other.tail;
    other.head = nullptr;
    other.tail = nullptr;
    return *this;
  }
public:
  int get_size() {
    int count = 0;
    for (Node *n = head; n != nullptr; n = n->next) {
      count++;
    }
    return count;
  }
  bool is_empty() {
    return head == nullptr;
  }
  void enqueue(T x) {
    Node *temp = new Node{x, nullptr};
    if (head == nullptr) {
      head = temp;
      tail = temp;
    } else {
      tail->next = temp;
      tail = temp;
    }
  }
  T dequeue() {
    if (is_empty()) {
      throw underflow_error("Cannot dequeue from empty queue");
    }
    Node *nodeToDelete = head;
    T poppedValue = head->data;
    head = head->next;
    delete nodeToDelete;
    return poppedValue;
  }

Although we ultimately went with the latter implementation, we were really curious as to why the default move assignment operator worked for the stack and not the queue. We were wondering if it was because we created our own destructor for the class and disabled the copy operator, but we are unsure. Perhaps we were going about the implementation wrong? Any help/ feedback would be much appreciated!

Upvotes: 1

Views: 201

Answers (1)

RabidBear
RabidBear

Reputation: 182

Generally, you should always consider implement your own move assignment operator and move constructor when it comes to dynamic memory allocation.

Your stack one just appeared to work, but actually it is not correct.

Try to add these to your stack, and you will see the problem:

Stack <int> func() {
    Stack <int> s;
    s.push(3);
    return s;
}

int main()
{
    Stack <int> b;
    b = func();     // assignment move
    return 0;
}
  • func() is returning a Stack with non-null head member variable (this is critical)
  • When leaving func(), local variable s is destructed
  • When leaving main(), local variable b is destructed (problem here)

That's why this code causes a double-free problem in your Stack.

(BTW, your Queue assignment move operator may cause memory leak, since delete head; may not be what you want to do.)

Upvotes: 1

Related Questions