patterncppMinor
Template double ended queue (deque) implementation using dynamic allocation C++
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;
};
//****
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).
You can also add emplace and move methods to add an element.
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.