4
\$\begingroup\$

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
Improve this question
\$\endgroup\$
1

1 Answer 1

Reset to default
3
\$\begingroup\$

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++;
}
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – TOM__
    Nov 17, 2016 at 18:40
  • \$\begingroup\$ 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. \$\endgroup\$
    – TOM__
    Nov 22, 2016 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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