Template double ended queue (deque) implementation using dynamic allocation C++

Question

I have written my own deque class to get a better grasp of C++ pointers and memory management. The following code is part of a larger 2D isometric game I am developing. It compiles and runs fine using MSVS express 15.

I have provided a unit test source + output. I am fairly sure there are no memory leak issues (using the global new and delete as well as placement new).

My question: Is there a computationally faster way to perform the deque copy constructor? I would also appreciate any feedback on my coding style.

#ifndef EVIL_DEQUE_H
#define EVIL_DEQUE_H
#include <new.h>
template<class type>
class eDeque;
//*************************************************
// eNode
// to be used with friend class eDeque<type>
//*************************************************
template<class type>
class eNode {
 friend class eDeque<type>;
public :
 eNode() : prev(nullptr), next(nullptr), data() {}; // default constructor
 explicit eNode(const type & data) : prev(nullptr), next(nullptr), data(data) {}; // prevent implicit conversion
 eNode(const eNode<type> & other) : prev(nullptr), next(nullptr), data(other.data) {}; // copy constructor
 // DEBUG: destructor omitted because no heap allocation occurs
 eNode<type> & operator=(const eNode<type> & other) { // copy assignment
 data.~type(); 
 new (&data) type(other.data); 
 return *this;}; 
 const type & Data() const { return data; };
 type & Data() { return data; };
 eNode<type> * Prev() const { return prev; };
 eNode<type> * Next() const { return next; };
private:
 eNode<type> * prev;
 eNode<type> * next;
 type data;
};
//*************************************************
// eDeque
// uses heap memory to manage copies of pushed data
// user code must check if deque is empty before accessing data
// TODO: replace the global new memory allocation with
// a custom heap memory block allocator (aligned) that has a templated/settable
// granularity and overridden new operator (to reduce the allocation overhead)
// DEBUG: will crash if it fails any new allocation (eg: PushFront, PushBack, operator=, cctor)
//*************************************************
template <class type>
class eDeque {
public:
 eDeque(); // default constructor
 eDeque(const eDeque<type> & other); // copy constructor
 ~eDeque(); // destructor
 eDeque<type> & operator=(const eDeque<type> & other); // copy assignment
 void PushFront(const type & data);
 void PushBack(const type & data);
 void PopFront();
 void PopBack();
 eNode<type> * Back() const;
 eNode<type> * Front() const;
 eNode<type> * FromFront(int index) const;
 eNode<type> * FromBack(int index) const;
 void Clear();
 int Size() const;
 bool IsEmpty() const;
private:
 eNode<type> * front;
 eNode<type> * back;
 int nodeCount;
};
//******************
// eDeque::eDeque
// empty eDeque
//******************
template <class type>
inline eDeque<type>::eDeque() : nodeCount(0), front(nullptr), back(nullptr) {
}
//******************
// eDeque::eDeque
//******************
template <class type>
inline eDeque<type>::eDeque(const eDeque<type> & other) {
 eNode<type> * otherIterator;
 for (otherIterator = other.back; otherIterator != nullptr; otherIterator = otherIterator->next)
 PushFront(otherIterator->data);
}
//******************
// eDeque::~eDeque
//******************
template <class type>
inline eDeque<type>::~eDeque() {
 Clear();
}
//******************
// eDeque::operator=
// deep copy back to front
//******************
template <class type>
inline eDeque<type> & eDeque<type>::operator=(const eDeque<type> & other) {
 eNode<type> * thisIterator;
 eNode<type> * otherIterator;
 eNode<type> * newFront;
/*
 // QUESTION: would this be faster than what I do in this function? Or, is heap deallocation/allocation more expensive?
 Clear();
 for (otherIterator = other.back; otherIterator != nullptr; otherIterator = otherIterator->next)
 PushFront(otherIterator->data);
*/ 
 // destroy and reconstruct pre-allocated memory if *this already has some
 for (thisIterator = back, otherIterator = other.back; 
 thisIterator != nullptr && otherIterator != nullptr;
 thisIterator = thisIterator->next, otherIterator = otherIterator->next)
 (*thisIterator) = (*otherIterator); // DEBUG: eNode copy assignemnt
 // establish a newFront if *this had more nodes than other
 newFront = nullptr;
 if (thisIterator != nullptr && otherIterator == nullptr)
 newFront = thisIterator->prev;
 // if *this had more nodes, pop all the nodes beyond other's size, down to newFront
 while (thisIterator != newFront) {
 PopFront();
 thisIterator = front;
 }
 // if *this had fewer nodes, push all the data remaining in other onto *this
 for (/*continue moving*/; otherIterator != nullptr; otherIterator = otherIterator->next)
 PushFront(otherIterator->data);
 return *this;
}
//******************
// eDeque::PushFront
// copies the data into a new node and links it to the front
//******************
template <class type>
inline void eDeque<type>::PushFront(const type & data) {
 eNode<type> * newFront;
 newFront = new eNode<type>(data);
 if (front == nullptr) {
 front = newFront;
 back = newFront;
 } else {
 newFront->prev = front;
 front->next = newFront;
 front = newFront;
 }
 nodeCount++;
}
//******************
// eDeque::PushBack
// copies the data into a new node and links it to the back
//******************
template <class type>
inline void eDeque<type>::PushBack(const type & data) {
 eNode<type> * newBack;
 newBack = new eNode<type>(data);
 if (back == nullptr) {
 back = newBack;
 front = newBack;
 } else {
 newBack->next = back;
 back->prev = newBack;
 back = newBack;
 }
 nodeCount++;
}
//******************
// eDeque::PopFront
// unlinks and deletes the front node
//******************
template <class type>
inline void eDeque<type>::PopFront() {
 eNode<type> * newFront;
 eNode<type> * oldFront;
 if (front->prev == nullptr) { // last node in the deque
 delete front;
 front = nullptr;
 back = nullptr;
 } else { // more than one node in the deque
 oldFront = front;
 newFront = front->prev;
 newFront->next = nullptr;
 front = newFront;
 delete oldFront;
 }
 nodeCount--;
}
//******************
// eDeque::PopBack
// unlinks and deletes the back node
//******************
template <class type>
inline void eDeque<type>::PopBack() {
 eNode<type> * newBack;
 eNode<type> * oldBack;
 if (back->next == nullptr) { // last node in the deque
 delete back;
 front = nullptr;
 back = nullptr;
 } else { // more than one node in the deque
 oldBack = back;
 newBack = back->next;
 newBack->prev = nullptr;
 back = newBack;
 delete oldBack;
 }
 nodeCount--;
}
//******************
// eDeque::Front
//******************
template <class type>
inline eNode<type> * eDeque<type>::Front() const {
 return front;
}
//******************
// eDeque::Back
//******************
template <class type>
inline eNode<type> * eDeque<type>::Back() const {
 return back;
}
//******************
// eDeque::FromFront
// returns the node "index" nodes behind the front
// index between [ 0, Size() - 1 ]
// returns nullptr for out-of-bounds index or empty deque
//******************
template <class type>
inline eNode<type> * eDeque<type>::FromFront(int index) const {
 eNode<type> * iterator;
 int i;
 if (index >= nodeCount || index < 0)
 return nullptr;
 if (index == nodeCount - 1)
 return back;
 i = 0;
 iterator = front;
 while (i++ < index)
 iterator = iterator->prev;
 return iterator;
}
//******************
// eDeque::FromBack
// returns the node "index" nodes ahead of the back
// index between [ 0, Size() - 1 ]
// returns nullptr for out-of-bounds index or empty deque
//******************
template <class type>
inline eNode<type> * eDeque<type>::FromBack(int index) const {
 eNode<type> * iterator;
 int i;
 if (index >= nodeCount || index < 0)
 return nullptr;
 if (index == nodeCount - 1)
 return front;
 i = 0;
 iterator = back;
 while (i++ < index)
 iterator = iterator->next;
 return iterator;
}
//******************
// eDeque::Clear
// unlinks and deletes all nodes front to back
//******************
template <class type>
inline void eDeque<type>::Clear() {
 while (!IsEmpty())
 PopFront();
}
//******************
// eDeque::Size
// current number of nodes
//******************
template <class type>
inline int eDeque<type>::Size() const {
 return nodeCount;
}
//******************
// eDeque::IsEmpty
// returns true for front == nullptr
//******************
template <class type>
inline bool eDeque<type>::IsEmpty() const {
 return front == nullptr;
}
#endif /* EVIL_DEQUE_H */

The following code is the unit test:

#include "Deque.h"
// iterate and print back to front
template<class type>
void PrintDeque(const eDeque<type> & de, const char * name) {
 eNode<int> * iterator;
 int i;
 printf("%s size == %i\n", name, de.Size());
 for (i = 0, iterator = de.Back(); iterator != nullptr; iterator = iterator->Next())
 printf("node %i == %i\n", i++, iterator->Data());
 printf("\n\n");
}
// iterate and increment by amount back to front
template<class type>
void IncrementData(const eDeque<type> & de, int amount) {
 eNode<int> * iterator;
 for (iterator = de.Back(); iterator != nullptr; iterator = iterator->Next())
 iterator->Data() += amount;
}
// unit test
int main () {
 printf("BEGIN eDeque COPY TESTS\n\n");
 eDeque<int> original;
 original.PushFront(0);
 original.PushFront(1);
 original.PushFront(2);
 original.PushFront(3);
 original.PushFront(4);
 original.PushFront(5);
 original.PushBack(6);
 original.PopBack();
 original.PopFront();
 PrintDeque(original, "original");
 eDeque<int> A(original); // copy constructor test
 printf("A(original)\n");
 PrintDeque(A, "A result");
 eDeque<int> B;
 printf("B.Size() < original.Size()\n");
 PrintDeque(B, "B_before_copyAssign");
 B = original; // copy assignment test with B.Size() < original.Size()
 printf("B = original\n");
 PrintDeque(B, "B result");
 eDeque<int> C;
 C.PushBack(10);
 C.PushFront(11);
 C.PushBack(12);
 C.PushFront(13);
 C.PushBack(14);
 C.PushFront(15);
 C.PushBack(16);
 C.PushFront(17);
 printf("C.Size() > original.Size()\n");
 PrintDeque(C, "C_before_copyAssign");
 C = original; // copy assignment test with C.Size() > original.Size()
 printf("C = original\n");
 PrintDeque(C, "C result");
 // verify the original is intact
 printf("original deque intact\n");
 PrintDeque(original, "original");
 IncrementData(C, 5);
 printf("incremented each node of C by 5\n");
 PrintDeque(C, "C result");
 printf("B.Size() == C.Size()\n");
 B = C; // copy assignment test with B.Size() == C.Size()
 printf("B = C\n");
 PrintDeque(B, "B result");
 printf("END eDeque COPY TESTS\n\n");
 printf("BEGIN eNODE COPY TESTS\n\n");
 eNode<int> * newData = new eNode<int>(999);
 eNode<int> * D = original.Front()->Prev(); // overwrite the node data just behind the front
 (*D) = (*newData); // node copy assignment test
 printf("(*D) == (*original.Font()->Prev()) = *newData\n");
 PrintDeque(original, "modified original result");
 eNode<int> E(*newData); // node cctor test
 delete newData; // E is still defined because it made a copy of the newData's data
 printf("E(*newData), delete newData, result: E.Data() == %i\n", E.Data());
 eNode<int> F(*D); // node cctor test (copies source node data, not source's next/prev)
 printf("F(*D) result: F.Data() == %i, F.Next() == %p, F.Prev() == %p\n", E.Data(), F.Next(), F.Prev());
 printf("END eNODE COPY TESTS\n\n");
 return 0;
}

The following is the unit test output:

BEGIN eDeque COPY TESTS
original size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4
A(original)
A result size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4
B.Size() < original.Size()
B_before_copyAssign size == 0
B = original
B result size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4
C.Size() > original.Size()
C_before_copyAssign size == 8
node 0 == 16
node 1 == 14
node 2 == 12
node 3 == 10
node 4 == 11
node 5 == 13
node 6 == 15
node 7 == 17
C = original
C result size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4
original deque intact
original size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4
incremented each node of C by 5
C result size == 5
node 0 == 5
node 1 == 6
node 2 == 7
node 3 == 8
node 4 == 9
B.Size() == C.Size()
B = C
B result size == 5
node 0 == 5
node 1 == 6
node 2 == 7
node 3 == 8
node 4 == 9
END eDeque COPY TESTS
BEGIN eNODE COPY TESTS
(*D) == (*original.Font()->Prev()) = *newData
modified original result size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 999
node 4 == 4
E(*newData), delete newData, result: E.Data() == 999
F(*D) result: F.Data() == 999, F.Next() == 00000000, F.Prev() == 00000000
END eNODE COPY TESTS

• Mathieu Guindon: Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers .

Answer 1

You follow the rule of 3, that's good. However you still can add the move operation (move construct and move assign).

template <class type>
inline eDeque<type>::eDeque(eDeque<type> && other): nodeCount(0), front(nullptr), back(nullptr) {
 std::swap(nodeCount, o.nodeCount);
 std::swap(front, o.front);
 std::swap(back, o.back);
}
template <class type>
inline eDeque<type> & eDeque<type>::operator=(eDeque<type> && other) {
 Clear();
 std::swap(nodeCount, o.nodeCount);
 std::swap(front, o.front);
 std::swap(back, o.back);
}

You can also add emplace and move methods to add an element.

template <class type> inline void eDeque<type>::PushBack(type && data) {
 eNode<type> * newBack;
 newBack = new eNode<type>(std::move(data)); //requires a eNode constructor taking type&&
 if (back == nullptr) {
 back = newBack;
 front = newBack;
 } else {
 newBack->next = back;
 back->prev = newBack;
 back = newBack;
 }
 nodeCount++;
}

• TOM__: The added move semantics certainly speed up construction and assignment, but my question is directly about the copy constructor and copy assignment. I've placed a comment in the original code where my question is targeted.
• TOM__: Move semantics provides enough of a speed boost for my project. I'll try finding an answer about fresh heap allocation vs. placement new speeds elsewhere.