patterncppMinor
Optimising a LinkedList data structure - Part 1
Viewed 0 times
linkedlistpartoptimisingstructuredata
Problem
I have implemented a linked list. I feel I overdid it with pointers, used old standards and C++11, and I ended with too many lines of code. I will make my quotations into two parts: one for the
For node and iterator, how can I optimize for C++11? Can you review it?
```
#include
#include
template
class LinkedList
{
private:
struct Node
{
T_ data;
Node* prev;
Node* next;
/Node(T_ D, Node p = nullptr, Node n = nullptr) : data(d), prev(p), next(n) {}/
Node( const T_ & d = Object{ }, Node p = nullptr, Node n = nullptr )
: data(d), prev(p), next(n) { }
Node( T_ && d, Node p = nullptr, Node n = nullptr )
: data( std::move(d)), prev(p), next(n) { }
Node( Node && n ) { // Rvalue move ctor
data = std::move(n.data);
prev = std::move(n.prev);
next = std::move(n.next);
}
Node& operator = ( Node && n ) { // Rvalue = operator
data = std::move(n.data);
prev = std::move(n.prev);
next = std::move(n.next);
return *this;
}
void swap(Node& rhs) throw ()
{
std::swap(prev, rhs.prev); std::swap(next, rhs.next);
}
};
public:
struct LinkedListIterator : public std::iterator
{
Node* _pNode;
LinkedListIterator(Node* p = nullptr) : _pNode(p) {}
Node* getNode() { return _pNode; }
T_ operator * () { return _pNode->data; }
LinkedListIterator & operator ++ () { _pNode = _pNode->next; return *this; } // pre
LinkedListIterator operator ++ (int) { LinkedListIterator retval = this; ++this; return retval; } // post
bool operator < ( LinkedListIterator const& rhs ) const { return _pNode < rhs._pNode; }
bool operator != ( LinkedListIterator const& rhs ) const { return _pNode != rhs._pNode; }
bool op
Node and iterator struct and the other for rest of the class.For node and iterator, how can I optimize for C++11? Can you review it?
```
#include
#include
template
class LinkedList
{
private:
struct Node
{
T_ data;
Node* prev;
Node* next;
/Node(T_ D, Node p = nullptr, Node n = nullptr) : data(d), prev(p), next(n) {}/
Node( const T_ & d = Object{ }, Node p = nullptr, Node n = nullptr )
: data(d), prev(p), next(n) { }
Node( T_ && d, Node p = nullptr, Node n = nullptr )
: data( std::move(d)), prev(p), next(n) { }
Node( Node && n ) { // Rvalue move ctor
data = std::move(n.data);
prev = std::move(n.prev);
next = std::move(n.next);
}
Node& operator = ( Node && n ) { // Rvalue = operator
data = std::move(n.data);
prev = std::move(n.prev);
next = std::move(n.next);
return *this;
}
void swap(Node& rhs) throw ()
{
std::swap(prev, rhs.prev); std::swap(next, rhs.next);
}
};
public:
struct LinkedListIterator : public std::iterator
{
Node* _pNode;
LinkedListIterator(Node* p = nullptr) : _pNode(p) {}
Node* getNode() { return _pNode; }
T_ operator * () { return _pNode->data; }
LinkedListIterator & operator ++ () { _pNode = _pNode->next; return *this; } // pre
LinkedListIterator operator ++ (int) { LinkedListIterator retval = this; ++this; return retval; } // post
bool operator < ( LinkedListIterator const& rhs ) const { return _pNode < rhs._pNode; }
bool operator != ( LinkedListIterator const& rhs ) const { return _pNode != rhs._pNode; }
bool op
Solution
There are several small things I can see in class
-
Generally speaking, with move assignment operator, you don't want to move pointers, you only want to swap them since - I believe - your nodes own the pointed values (more information here).
Node:- You have a move constructor, but no copy constructor.
- You have a move assignment operator, but no copy assignment operator.
- Since you use C++11, you should replace the exception specification
throw ()(now deprecated) bynoexcept.
- Your move assignment operator is not protected against self-assignment. You should add the condition
if (&n != this) { ... }.
- Also, if possible, your move constructor and
operator=should benoexcepttoo.
-
Generally speaking, with move assignment operator, you don't want to move pointers, you only want to swap them since - I believe - your nodes own the pointed values (more information here).
Node& operator=(Node&& n) noexcept {
if (&n != this) {
std::swap(data, n.data);
std::swap(prev, n.prev);
std::swap(next, n.next);
}
return *this;
}Code Snippets
Node& operator=(Node&& n) noexcept {
if (&n != this) {
std::swap(data, n.data);
std::swap(prev, n.prev);
std::swap(next, n.next);
}
return *this;
}Context
StackExchange Code Review Q#41388, answer score: 5
Revisions (0)
No revisions yet.