HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
templatedequedoubleusingdynamicimplementationallocationqueueended

Problem

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

template
class eDeque;
//*****
// eNode
// to be used with friend class eDeque
//*****
template
class eNode {

friend class eDeque;

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 & other) : prev(nullptr), next(nullptr), data(other.data) {}; // copy constructor
// DEBUG: destructor omitted because no heap allocation occurs

eNode & operator=(const eNode & other) { // copy assignment
data.~type();
new (&data) type(other.data);
return *this;};

const type & Data() const { return data; };
type & Data() { return data; };
eNode * Prev() const { return prev; };
eNode * Next() const { return next; };

private:

eNode * prev;
eNode * next;
type data;
};

//****

Solution

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

template 
inline eDeque::eDeque(eDeque && other): nodeCount(0), front(nullptr), back(nullptr) {
    std::swap(nodeCount, o.nodeCount);
    std::swap(front, o.front);
    std::swap(back, o.back);
}

template 
inline eDeque & eDeque::operator=(eDeque && 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  inline void eDeque::PushBack(type && data) {
    eNode * newBack;

    newBack = new eNode(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++;
}

Code Snippets

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

Context

StackExchange Code Review Q#147302, answer score: 3

Revisions (0)

No revisions yet.