C++ linked list iterator implementation
$begingroup$
I'm a first year computer engineering student and would appreciate feedback on some code.
I've created a linked-list with an iterator to be able to range for loops like: for (int i : list) {}
where list is Linked_List<int> list;
.
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:
- Use of raw pointers
Linked_List.h
namespace Util
{
template<typename T>
class Linked_List
{
public:
struct Iterator;
private:
struct Node;
public:
Linked_List();
~Linked_List() noexcept(false);
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
// Modifiers
void push_back(T);
void push_front(T);
void pop_back();
void pop_front();
// Capacity
bool empty() const;
unsigned int size() const;
// Element access
T back() const;
T front() const;
Iterator begin() const;
Iterator end() const;
// TODO:
//Iterator insert(const Iterator, T);
//Iterator erase(const Iterator);
private:
Node* _head;
Node* _tail;
unsigned int _size;
};
};
Linked_List.cpp
#include "pch.h"
#include "Linked_List.h"
namespace Util
{
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
template<typename T>
struct Linked_List<T>::Iterator
{
Iterator() : _current(nullptr)
{
//
}
T& operator*() const
{
return _current->value;
}
Iterator& operator++()
{
_current = _current->next;
return *this;
}
bool operator!=(const Iterator& rhs)
{
return _current != rhs._current;
}
private:
friend class Linked_List<T>;
Iterator(Node* n) : _current(n) {}
Node* _current;
};
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t);
n->prev = _tail->prev;
n->next = _tail;
_tail->prev->next = n;
_tail->prev = n;
++_size;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t);
n->next = _head->next;
n->prev = _head;
_head->next->prev = n;
_head->next = n;
++_size;
}
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
template<typename T>
unsigned int Linked_List<T>::size() const
{
return _size;
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
return Iterator(_head->next);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
};
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
c++ beginner linked-list homework iterator
New contributor
$endgroup$
add a comment |
$begingroup$
I'm a first year computer engineering student and would appreciate feedback on some code.
I've created a linked-list with an iterator to be able to range for loops like: for (int i : list) {}
where list is Linked_List<int> list;
.
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:
- Use of raw pointers
Linked_List.h
namespace Util
{
template<typename T>
class Linked_List
{
public:
struct Iterator;
private:
struct Node;
public:
Linked_List();
~Linked_List() noexcept(false);
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
// Modifiers
void push_back(T);
void push_front(T);
void pop_back();
void pop_front();
// Capacity
bool empty() const;
unsigned int size() const;
// Element access
T back() const;
T front() const;
Iterator begin() const;
Iterator end() const;
// TODO:
//Iterator insert(const Iterator, T);
//Iterator erase(const Iterator);
private:
Node* _head;
Node* _tail;
unsigned int _size;
};
};
Linked_List.cpp
#include "pch.h"
#include "Linked_List.h"
namespace Util
{
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
template<typename T>
struct Linked_List<T>::Iterator
{
Iterator() : _current(nullptr)
{
//
}
T& operator*() const
{
return _current->value;
}
Iterator& operator++()
{
_current = _current->next;
return *this;
}
bool operator!=(const Iterator& rhs)
{
return _current != rhs._current;
}
private:
friend class Linked_List<T>;
Iterator(Node* n) : _current(n) {}
Node* _current;
};
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t);
n->prev = _tail->prev;
n->next = _tail;
_tail->prev->next = n;
_tail->prev = n;
++_size;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t);
n->next = _head->next;
n->prev = _head;
_head->next->prev = n;
_head->next = n;
++_size;
}
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
template<typename T>
unsigned int Linked_List<T>::size() const
{
return _size;
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
return Iterator(_head->next);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
};
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
c++ beginner linked-list homework iterator
New contributor
$endgroup$
1
$begingroup$
I'm guessing that you haven't started yourconst_iterator
yet? It can be helpful to do them together.
$endgroup$
– Toby Speight
6 hours ago
add a comment |
$begingroup$
I'm a first year computer engineering student and would appreciate feedback on some code.
I've created a linked-list with an iterator to be able to range for loops like: for (int i : list) {}
where list is Linked_List<int> list;
.
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:
- Use of raw pointers
Linked_List.h
namespace Util
{
template<typename T>
class Linked_List
{
public:
struct Iterator;
private:
struct Node;
public:
Linked_List();
~Linked_List() noexcept(false);
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
// Modifiers
void push_back(T);
void push_front(T);
void pop_back();
void pop_front();
// Capacity
bool empty() const;
unsigned int size() const;
// Element access
T back() const;
T front() const;
Iterator begin() const;
Iterator end() const;
// TODO:
//Iterator insert(const Iterator, T);
//Iterator erase(const Iterator);
private:
Node* _head;
Node* _tail;
unsigned int _size;
};
};
Linked_List.cpp
#include "pch.h"
#include "Linked_List.h"
namespace Util
{
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
template<typename T>
struct Linked_List<T>::Iterator
{
Iterator() : _current(nullptr)
{
//
}
T& operator*() const
{
return _current->value;
}
Iterator& operator++()
{
_current = _current->next;
return *this;
}
bool operator!=(const Iterator& rhs)
{
return _current != rhs._current;
}
private:
friend class Linked_List<T>;
Iterator(Node* n) : _current(n) {}
Node* _current;
};
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t);
n->prev = _tail->prev;
n->next = _tail;
_tail->prev->next = n;
_tail->prev = n;
++_size;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t);
n->next = _head->next;
n->prev = _head;
_head->next->prev = n;
_head->next = n;
++_size;
}
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
template<typename T>
unsigned int Linked_List<T>::size() const
{
return _size;
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
return Iterator(_head->next);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
};
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
c++ beginner linked-list homework iterator
New contributor
$endgroup$
I'm a first year computer engineering student and would appreciate feedback on some code.
I've created a linked-list with an iterator to be able to range for loops like: for (int i : list) {}
where list is Linked_List<int> list;
.
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:
- Use of raw pointers
Linked_List.h
namespace Util
{
template<typename T>
class Linked_List
{
public:
struct Iterator;
private:
struct Node;
public:
Linked_List();
~Linked_List() noexcept(false);
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
// Modifiers
void push_back(T);
void push_front(T);
void pop_back();
void pop_front();
// Capacity
bool empty() const;
unsigned int size() const;
// Element access
T back() const;
T front() const;
Iterator begin() const;
Iterator end() const;
// TODO:
//Iterator insert(const Iterator, T);
//Iterator erase(const Iterator);
private:
Node* _head;
Node* _tail;
unsigned int _size;
};
};
Linked_List.cpp
#include "pch.h"
#include "Linked_List.h"
namespace Util
{
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
template<typename T>
struct Linked_List<T>::Iterator
{
Iterator() : _current(nullptr)
{
//
}
T& operator*() const
{
return _current->value;
}
Iterator& operator++()
{
_current = _current->next;
return *this;
}
bool operator!=(const Iterator& rhs)
{
return _current != rhs._current;
}
private:
friend class Linked_List<T>;
Iterator(Node* n) : _current(n) {}
Node* _current;
};
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t);
n->prev = _tail->prev;
n->next = _tail;
_tail->prev->next = n;
_tail->prev = n;
++_size;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t);
n->next = _head->next;
n->prev = _head;
_head->next->prev = n;
_head->next = n;
++_size;
}
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
template<typename T>
unsigned int Linked_List<T>::size() const
{
return _size;
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
return Iterator(_head->next);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
};
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
c++ beginner linked-list homework iterator
c++ beginner linked-list homework iterator
New contributor
New contributor
edited 6 hours ago
user644361
New contributor
asked 9 hours ago
user644361user644361
262
262
New contributor
New contributor
1
$begingroup$
I'm guessing that you haven't started yourconst_iterator
yet? It can be helpful to do them together.
$endgroup$
– Toby Speight
6 hours ago
add a comment |
1
$begingroup$
I'm guessing that you haven't started yourconst_iterator
yet? It can be helpful to do them together.
$endgroup$
– Toby Speight
6 hours ago
1
1
$begingroup$
I'm guessing that you haven't started your
const_iterator
yet? It can be helpful to do them together.$endgroup$
– Toby Speight
6 hours ago
$begingroup$
I'm guessing that you haven't started your
const_iterator
yet? It can be helpful to do them together.$endgroup$
– Toby Speight
6 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Comment
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:`
- Use of raw pointers
Not sure that is a flaw. Creating a container I would expect to see RAW pointers.
Overview
There is definitely a bug in your constructor where you build two Sentinels
it should only be one. Otherwise your iterators for an empty list will iterate once.
Additionally your Node
always contains a value (even for the Sentinel
). This means your type T
(the value type) must be default constructible (not all types are so you class is limited to objects of this type).
There are some requirements for Iterators that you don't implement. The iterator type is supposed to have a couple of internal types. The standard algorithms use these internal types (or they use std::iterator_traits<Your Interator>::UsefulTypeInfo
) which default to point at your type object. Since your Iterator
does not implement these types it may not be standard compliant and fail in some algorithms.
Talking of missing type information your container is also missing some type information.
Also you provide the pre-increment on your iterator but your don't provide the post-increment function. So you are missing at least one function. There is at least one more function you are missing (but I assume this is becausew your teacher has not got that far so I will leave it up to him).
There are lots of parts to this class that look like the teacher will get you to fill in at a later date. So there is still a lot of work to do to complete this task.
Code Review
That's a bit wierd.
~Linked_List() noexcept(false);
This makes the class act like a C++03 class. Exceptions are allowed to propagate out of the destructor. Not usual but it's OK. I assume this will be modified in future class.
I assume these are deleted to make the first version easy to write.
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
Probably come back in a later class and implement these.
This is a bit strange passing by value.
void push_back(T);
void push_front(T);
I would expect you to pass by reference to avoid a copy.
Personally I hate the unsigned int as a size value. But it's very common and what was adopted by the standard container (they regretted that).
unsigned int size() const;
So I would keep it. But if you look up the history of why the standard committee choose unsigned
then regretted it its an interesting story.
But saying that. I would use std::size_t
as that conveys intentions more.
Return by value? Just like the insert by value you are potentially creating an unneeded copy.
T back() const;
T front() const;
I am now assuming this is because you have not been tought about references and thus the teacher will expand on this in later classes and show you how to provide both normal reference and const reference versions of these methods.
Sure this is fine as a starting point.
Iterator begin() const;
Iterator end() const;
But you will see that the standard containers have a lot more of these. Also since these methods are const should they not be returning a const version of the iterator. Maybe that is for a later class.
OK. A very basic Node
.
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
But the lack of interesting constructors means you will have to do some manual work setting up the chain when this could have been done in the constructor here. I'll point it out when we get to creating a node.
OK so a very basic Iterator.
template<typename T>
struct Linked_List<T>::Iterator
{
// Nothing interesting here.
};
You create a Sentinel
for both both the beginning and end. That seems a bit strange. I would expect to only see one Sentinel
value at the end.
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
I would have expected this:
template<typename T>
Linked_List<T>::Linked_List()
: _head(new Node)
, _tail(_head)
, _size(0)
{}
This way if the list is empty both head and tail point at the same node. Thus if you generate iterators for head and tail they will both generate the end
iterator (which will compare equal).
Additionally there is a bug in your version.
_head = new Node(); // Assume this works
_tail = new Node(); // Assume this fails and throws.
// Because your constructor has not finished
// when the exception is thrown this object
// will not be fully constructed and therefore
// will not have its destructor called. This
// means you will leak the value pointed at by
// _head
Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
I would simply write like this:
Linked_List<T>::~Linked_List()
{
Node* current = _head;
while(current != nullptr) {
Node* old = current;
current = current->next;
delete old;
}
}
You know I mentioned above in the Node
description that the constructor could be made more useful. This is where it would work nicely.
Node(T value, Node* nextNode)
: prev(nextNode->prev)
, next(nextNode)
, value(value)
{
if (prev) {
prev->next = this;
}
next->prev = this; // There is always a next.
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t, tail); // insert before tail.
tail = n->next;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t, head); // insert before head
head = n;
}
Personally I think that is much easier to read.
Personally I would not check if it is empty. It is the responsibility of the caller to check before calling X_pop()
. If you provide the check and it is not needed you are forcing the user to use sub-optimal code. See example below:
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
Here is a very common use case:
while(list.empty()) {
list.pop_back(); // This is guaranteed to only be called if
// if the list is not empty. So the check
// inside `pop_back()` is redudant and therefore
// a waste of cycles.
}
One of the big philosophies of C++ is to never charge people for something they don't need. Now there is also an argument to having the check. BUT this can be provided by having an explicit checked pop_back()
version: checked_pop_back()
.
list.checked_pop_back(); // Do I need to make a check before this call?
Simply go for checking the size(). If your object is in a consistent state then you can simply check the variable without having to pay the expense of the functions call.
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
I would just write:
bool Linked_List<T>::empty() const {return _size == 0;}
Again with the un-needed checks.
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
These look fine:
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
// Though with the fix I suggested above this changes.
return Iterator(_head->next);
// If you only have the tail `Sentinel` this becomes
return Iterator(_head);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
If you have to insert
before the iterator? Then you can simply implement like I did above:
Iterator insert(const Iterator iterator, T value) {
Node* n = new Node(value, iterator->_current);
return Iterator(n);
}
Lets assume erase returns the iterator to the next element.
Iterator erase(const Iterator iterator)
Node* current = iterator->_current;
if (current == _tail) // can't delete the tail
return iterator;
}
// otherwise unlink from previous item.
if (current->prev == nullptr) {
head = current->next;
}
else {
current->prev->net = current->next;
}
// Next unlink from the next item.
current->next->prev=current->prev;
// Get the next item so we can return it.
Node* result = current->next;
// Delete the old value.
delete current;
// return the new result.
return Iterator(result);
}
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
user644361 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216444%2fc-linked-list-iterator-implementation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Comment
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:`
- Use of raw pointers
Not sure that is a flaw. Creating a container I would expect to see RAW pointers.
Overview
There is definitely a bug in your constructor where you build two Sentinels
it should only be one. Otherwise your iterators for an empty list will iterate once.
Additionally your Node
always contains a value (even for the Sentinel
). This means your type T
(the value type) must be default constructible (not all types are so you class is limited to objects of this type).
There are some requirements for Iterators that you don't implement. The iterator type is supposed to have a couple of internal types. The standard algorithms use these internal types (or they use std::iterator_traits<Your Interator>::UsefulTypeInfo
) which default to point at your type object. Since your Iterator
does not implement these types it may not be standard compliant and fail in some algorithms.
Talking of missing type information your container is also missing some type information.
Also you provide the pre-increment on your iterator but your don't provide the post-increment function. So you are missing at least one function. There is at least one more function you are missing (but I assume this is becausew your teacher has not got that far so I will leave it up to him).
There are lots of parts to this class that look like the teacher will get you to fill in at a later date. So there is still a lot of work to do to complete this task.
Code Review
That's a bit wierd.
~Linked_List() noexcept(false);
This makes the class act like a C++03 class. Exceptions are allowed to propagate out of the destructor. Not usual but it's OK. I assume this will be modified in future class.
I assume these are deleted to make the first version easy to write.
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
Probably come back in a later class and implement these.
This is a bit strange passing by value.
void push_back(T);
void push_front(T);
I would expect you to pass by reference to avoid a copy.
Personally I hate the unsigned int as a size value. But it's very common and what was adopted by the standard container (they regretted that).
unsigned int size() const;
So I would keep it. But if you look up the history of why the standard committee choose unsigned
then regretted it its an interesting story.
But saying that. I would use std::size_t
as that conveys intentions more.
Return by value? Just like the insert by value you are potentially creating an unneeded copy.
T back() const;
T front() const;
I am now assuming this is because you have not been tought about references and thus the teacher will expand on this in later classes and show you how to provide both normal reference and const reference versions of these methods.
Sure this is fine as a starting point.
Iterator begin() const;
Iterator end() const;
But you will see that the standard containers have a lot more of these. Also since these methods are const should they not be returning a const version of the iterator. Maybe that is for a later class.
OK. A very basic Node
.
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
But the lack of interesting constructors means you will have to do some manual work setting up the chain when this could have been done in the constructor here. I'll point it out when we get to creating a node.
OK so a very basic Iterator.
template<typename T>
struct Linked_List<T>::Iterator
{
// Nothing interesting here.
};
You create a Sentinel
for both both the beginning and end. That seems a bit strange. I would expect to only see one Sentinel
value at the end.
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
I would have expected this:
template<typename T>
Linked_List<T>::Linked_List()
: _head(new Node)
, _tail(_head)
, _size(0)
{}
This way if the list is empty both head and tail point at the same node. Thus if you generate iterators for head and tail they will both generate the end
iterator (which will compare equal).
Additionally there is a bug in your version.
_head = new Node(); // Assume this works
_tail = new Node(); // Assume this fails and throws.
// Because your constructor has not finished
// when the exception is thrown this object
// will not be fully constructed and therefore
// will not have its destructor called. This
// means you will leak the value pointed at by
// _head
Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
I would simply write like this:
Linked_List<T>::~Linked_List()
{
Node* current = _head;
while(current != nullptr) {
Node* old = current;
current = current->next;
delete old;
}
}
You know I mentioned above in the Node
description that the constructor could be made more useful. This is where it would work nicely.
Node(T value, Node* nextNode)
: prev(nextNode->prev)
, next(nextNode)
, value(value)
{
if (prev) {
prev->next = this;
}
next->prev = this; // There is always a next.
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t, tail); // insert before tail.
tail = n->next;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t, head); // insert before head
head = n;
}
Personally I think that is much easier to read.
Personally I would not check if it is empty. It is the responsibility of the caller to check before calling X_pop()
. If you provide the check and it is not needed you are forcing the user to use sub-optimal code. See example below:
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
Here is a very common use case:
while(list.empty()) {
list.pop_back(); // This is guaranteed to only be called if
// if the list is not empty. So the check
// inside `pop_back()` is redudant and therefore
// a waste of cycles.
}
One of the big philosophies of C++ is to never charge people for something they don't need. Now there is also an argument to having the check. BUT this can be provided by having an explicit checked pop_back()
version: checked_pop_back()
.
list.checked_pop_back(); // Do I need to make a check before this call?
Simply go for checking the size(). If your object is in a consistent state then you can simply check the variable without having to pay the expense of the functions call.
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
I would just write:
bool Linked_List<T>::empty() const {return _size == 0;}
Again with the un-needed checks.
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
These look fine:
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
// Though with the fix I suggested above this changes.
return Iterator(_head->next);
// If you only have the tail `Sentinel` this becomes
return Iterator(_head);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
If you have to insert
before the iterator? Then you can simply implement like I did above:
Iterator insert(const Iterator iterator, T value) {
Node* n = new Node(value, iterator->_current);
return Iterator(n);
}
Lets assume erase returns the iterator to the next element.
Iterator erase(const Iterator iterator)
Node* current = iterator->_current;
if (current == _tail) // can't delete the tail
return iterator;
}
// otherwise unlink from previous item.
if (current->prev == nullptr) {
head = current->next;
}
else {
current->prev->net = current->next;
}
// Next unlink from the next item.
current->next->prev=current->prev;
// Get the next item so we can return it.
Node* result = current->next;
// Delete the old value.
delete current;
// return the new result.
return Iterator(result);
}
$endgroup$
add a comment |
$begingroup$
Comment
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:`
- Use of raw pointers
Not sure that is a flaw. Creating a container I would expect to see RAW pointers.
Overview
There is definitely a bug in your constructor where you build two Sentinels
it should only be one. Otherwise your iterators for an empty list will iterate once.
Additionally your Node
always contains a value (even for the Sentinel
). This means your type T
(the value type) must be default constructible (not all types are so you class is limited to objects of this type).
There are some requirements for Iterators that you don't implement. The iterator type is supposed to have a couple of internal types. The standard algorithms use these internal types (or they use std::iterator_traits<Your Interator>::UsefulTypeInfo
) which default to point at your type object. Since your Iterator
does not implement these types it may not be standard compliant and fail in some algorithms.
Talking of missing type information your container is also missing some type information.
Also you provide the pre-increment on your iterator but your don't provide the post-increment function. So you are missing at least one function. There is at least one more function you are missing (but I assume this is becausew your teacher has not got that far so I will leave it up to him).
There are lots of parts to this class that look like the teacher will get you to fill in at a later date. So there is still a lot of work to do to complete this task.
Code Review
That's a bit wierd.
~Linked_List() noexcept(false);
This makes the class act like a C++03 class. Exceptions are allowed to propagate out of the destructor. Not usual but it's OK. I assume this will be modified in future class.
I assume these are deleted to make the first version easy to write.
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
Probably come back in a later class and implement these.
This is a bit strange passing by value.
void push_back(T);
void push_front(T);
I would expect you to pass by reference to avoid a copy.
Personally I hate the unsigned int as a size value. But it's very common and what was adopted by the standard container (they regretted that).
unsigned int size() const;
So I would keep it. But if you look up the history of why the standard committee choose unsigned
then regretted it its an interesting story.
But saying that. I would use std::size_t
as that conveys intentions more.
Return by value? Just like the insert by value you are potentially creating an unneeded copy.
T back() const;
T front() const;
I am now assuming this is because you have not been tought about references and thus the teacher will expand on this in later classes and show you how to provide both normal reference and const reference versions of these methods.
Sure this is fine as a starting point.
Iterator begin() const;
Iterator end() const;
But you will see that the standard containers have a lot more of these. Also since these methods are const should they not be returning a const version of the iterator. Maybe that is for a later class.
OK. A very basic Node
.
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
But the lack of interesting constructors means you will have to do some manual work setting up the chain when this could have been done in the constructor here. I'll point it out when we get to creating a node.
OK so a very basic Iterator.
template<typename T>
struct Linked_List<T>::Iterator
{
// Nothing interesting here.
};
You create a Sentinel
for both both the beginning and end. That seems a bit strange. I would expect to only see one Sentinel
value at the end.
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
I would have expected this:
template<typename T>
Linked_List<T>::Linked_List()
: _head(new Node)
, _tail(_head)
, _size(0)
{}
This way if the list is empty both head and tail point at the same node. Thus if you generate iterators for head and tail they will both generate the end
iterator (which will compare equal).
Additionally there is a bug in your version.
_head = new Node(); // Assume this works
_tail = new Node(); // Assume this fails and throws.
// Because your constructor has not finished
// when the exception is thrown this object
// will not be fully constructed and therefore
// will not have its destructor called. This
// means you will leak the value pointed at by
// _head
Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
I would simply write like this:
Linked_List<T>::~Linked_List()
{
Node* current = _head;
while(current != nullptr) {
Node* old = current;
current = current->next;
delete old;
}
}
You know I mentioned above in the Node
description that the constructor could be made more useful. This is where it would work nicely.
Node(T value, Node* nextNode)
: prev(nextNode->prev)
, next(nextNode)
, value(value)
{
if (prev) {
prev->next = this;
}
next->prev = this; // There is always a next.
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t, tail); // insert before tail.
tail = n->next;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t, head); // insert before head
head = n;
}
Personally I think that is much easier to read.
Personally I would not check if it is empty. It is the responsibility of the caller to check before calling X_pop()
. If you provide the check and it is not needed you are forcing the user to use sub-optimal code. See example below:
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
Here is a very common use case:
while(list.empty()) {
list.pop_back(); // This is guaranteed to only be called if
// if the list is not empty. So the check
// inside `pop_back()` is redudant and therefore
// a waste of cycles.
}
One of the big philosophies of C++ is to never charge people for something they don't need. Now there is also an argument to having the check. BUT this can be provided by having an explicit checked pop_back()
version: checked_pop_back()
.
list.checked_pop_back(); // Do I need to make a check before this call?
Simply go for checking the size(). If your object is in a consistent state then you can simply check the variable without having to pay the expense of the functions call.
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
I would just write:
bool Linked_List<T>::empty() const {return _size == 0;}
Again with the un-needed checks.
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
These look fine:
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
// Though with the fix I suggested above this changes.
return Iterator(_head->next);
// If you only have the tail `Sentinel` this becomes
return Iterator(_head);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
If you have to insert
before the iterator? Then you can simply implement like I did above:
Iterator insert(const Iterator iterator, T value) {
Node* n = new Node(value, iterator->_current);
return Iterator(n);
}
Lets assume erase returns the iterator to the next element.
Iterator erase(const Iterator iterator)
Node* current = iterator->_current;
if (current == _tail) // can't delete the tail
return iterator;
}
// otherwise unlink from previous item.
if (current->prev == nullptr) {
head = current->next;
}
else {
current->prev->net = current->next;
}
// Next unlink from the next item.
current->next->prev=current->prev;
// Get the next item so we can return it.
Node* result = current->next;
// Delete the old value.
delete current;
// return the new result.
return Iterator(result);
}
$endgroup$
add a comment |
$begingroup$
Comment
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:`
- Use of raw pointers
Not sure that is a flaw. Creating a container I would expect to see RAW pointers.
Overview
There is definitely a bug in your constructor where you build two Sentinels
it should only be one. Otherwise your iterators for an empty list will iterate once.
Additionally your Node
always contains a value (even for the Sentinel
). This means your type T
(the value type) must be default constructible (not all types are so you class is limited to objects of this type).
There are some requirements for Iterators that you don't implement. The iterator type is supposed to have a couple of internal types. The standard algorithms use these internal types (or they use std::iterator_traits<Your Interator>::UsefulTypeInfo
) which default to point at your type object. Since your Iterator
does not implement these types it may not be standard compliant and fail in some algorithms.
Talking of missing type information your container is also missing some type information.
Also you provide the pre-increment on your iterator but your don't provide the post-increment function. So you are missing at least one function. There is at least one more function you are missing (but I assume this is becausew your teacher has not got that far so I will leave it up to him).
There are lots of parts to this class that look like the teacher will get you to fill in at a later date. So there is still a lot of work to do to complete this task.
Code Review
That's a bit wierd.
~Linked_List() noexcept(false);
This makes the class act like a C++03 class. Exceptions are allowed to propagate out of the destructor. Not usual but it's OK. I assume this will be modified in future class.
I assume these are deleted to make the first version easy to write.
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
Probably come back in a later class and implement these.
This is a bit strange passing by value.
void push_back(T);
void push_front(T);
I would expect you to pass by reference to avoid a copy.
Personally I hate the unsigned int as a size value. But it's very common and what was adopted by the standard container (they regretted that).
unsigned int size() const;
So I would keep it. But if you look up the history of why the standard committee choose unsigned
then regretted it its an interesting story.
But saying that. I would use std::size_t
as that conveys intentions more.
Return by value? Just like the insert by value you are potentially creating an unneeded copy.
T back() const;
T front() const;
I am now assuming this is because you have not been tought about references and thus the teacher will expand on this in later classes and show you how to provide both normal reference and const reference versions of these methods.
Sure this is fine as a starting point.
Iterator begin() const;
Iterator end() const;
But you will see that the standard containers have a lot more of these. Also since these methods are const should they not be returning a const version of the iterator. Maybe that is for a later class.
OK. A very basic Node
.
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
But the lack of interesting constructors means you will have to do some manual work setting up the chain when this could have been done in the constructor here. I'll point it out when we get to creating a node.
OK so a very basic Iterator.
template<typename T>
struct Linked_List<T>::Iterator
{
// Nothing interesting here.
};
You create a Sentinel
for both both the beginning and end. That seems a bit strange. I would expect to only see one Sentinel
value at the end.
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
I would have expected this:
template<typename T>
Linked_List<T>::Linked_List()
: _head(new Node)
, _tail(_head)
, _size(0)
{}
This way if the list is empty both head and tail point at the same node. Thus if you generate iterators for head and tail they will both generate the end
iterator (which will compare equal).
Additionally there is a bug in your version.
_head = new Node(); // Assume this works
_tail = new Node(); // Assume this fails and throws.
// Because your constructor has not finished
// when the exception is thrown this object
// will not be fully constructed and therefore
// will not have its destructor called. This
// means you will leak the value pointed at by
// _head
Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
I would simply write like this:
Linked_List<T>::~Linked_List()
{
Node* current = _head;
while(current != nullptr) {
Node* old = current;
current = current->next;
delete old;
}
}
You know I mentioned above in the Node
description that the constructor could be made more useful. This is where it would work nicely.
Node(T value, Node* nextNode)
: prev(nextNode->prev)
, next(nextNode)
, value(value)
{
if (prev) {
prev->next = this;
}
next->prev = this; // There is always a next.
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t, tail); // insert before tail.
tail = n->next;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t, head); // insert before head
head = n;
}
Personally I think that is much easier to read.
Personally I would not check if it is empty. It is the responsibility of the caller to check before calling X_pop()
. If you provide the check and it is not needed you are forcing the user to use sub-optimal code. See example below:
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
Here is a very common use case:
while(list.empty()) {
list.pop_back(); // This is guaranteed to only be called if
// if the list is not empty. So the check
// inside `pop_back()` is redudant and therefore
// a waste of cycles.
}
One of the big philosophies of C++ is to never charge people for something they don't need. Now there is also an argument to having the check. BUT this can be provided by having an explicit checked pop_back()
version: checked_pop_back()
.
list.checked_pop_back(); // Do I need to make a check before this call?
Simply go for checking the size(). If your object is in a consistent state then you can simply check the variable without having to pay the expense of the functions call.
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
I would just write:
bool Linked_List<T>::empty() const {return _size == 0;}
Again with the un-needed checks.
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
These look fine:
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
// Though with the fix I suggested above this changes.
return Iterator(_head->next);
// If you only have the tail `Sentinel` this becomes
return Iterator(_head);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
If you have to insert
before the iterator? Then you can simply implement like I did above:
Iterator insert(const Iterator iterator, T value) {
Node* n = new Node(value, iterator->_current);
return Iterator(n);
}
Lets assume erase returns the iterator to the next element.
Iterator erase(const Iterator iterator)
Node* current = iterator->_current;
if (current == _tail) // can't delete the tail
return iterator;
}
// otherwise unlink from previous item.
if (current->prev == nullptr) {
head = current->next;
}
else {
current->prev->net = current->next;
}
// Next unlink from the next item.
current->next->prev=current->prev;
// Get the next item so we can return it.
Node* result = current->next;
// Delete the old value.
delete current;
// return the new result.
return Iterator(result);
}
$endgroup$
Comment
Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:`
- Use of raw pointers
Not sure that is a flaw. Creating a container I would expect to see RAW pointers.
Overview
There is definitely a bug in your constructor where you build two Sentinels
it should only be one. Otherwise your iterators for an empty list will iterate once.
Additionally your Node
always contains a value (even for the Sentinel
). This means your type T
(the value type) must be default constructible (not all types are so you class is limited to objects of this type).
There are some requirements for Iterators that you don't implement. The iterator type is supposed to have a couple of internal types. The standard algorithms use these internal types (or they use std::iterator_traits<Your Interator>::UsefulTypeInfo
) which default to point at your type object. Since your Iterator
does not implement these types it may not be standard compliant and fail in some algorithms.
Talking of missing type information your container is also missing some type information.
Also you provide the pre-increment on your iterator but your don't provide the post-increment function. So you are missing at least one function. There is at least one more function you are missing (but I assume this is becausew your teacher has not got that far so I will leave it up to him).
There are lots of parts to this class that look like the teacher will get you to fill in at a later date. So there is still a lot of work to do to complete this task.
Code Review
That's a bit wierd.
~Linked_List() noexcept(false);
This makes the class act like a C++03 class. Exceptions are allowed to propagate out of the destructor. Not usual but it's OK. I assume this will be modified in future class.
I assume these are deleted to make the first version easy to write.
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
Probably come back in a later class and implement these.
This is a bit strange passing by value.
void push_back(T);
void push_front(T);
I would expect you to pass by reference to avoid a copy.
Personally I hate the unsigned int as a size value. But it's very common and what was adopted by the standard container (they regretted that).
unsigned int size() const;
So I would keep it. But if you look up the history of why the standard committee choose unsigned
then regretted it its an interesting story.
But saying that. I would use std::size_t
as that conveys intentions more.
Return by value? Just like the insert by value you are potentially creating an unneeded copy.
T back() const;
T front() const;
I am now assuming this is because you have not been tought about references and thus the teacher will expand on this in later classes and show you how to provide both normal reference and const reference versions of these methods.
Sure this is fine as a starting point.
Iterator begin() const;
Iterator end() const;
But you will see that the standard containers have a lot more of these. Also since these methods are const should they not be returning a const version of the iterator. Maybe that is for a later class.
OK. A very basic Node
.
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
But the lack of interesting constructors means you will have to do some manual work setting up the chain when this could have been done in the constructor here. I'll point it out when we get to creating a node.
OK so a very basic Iterator.
template<typename T>
struct Linked_List<T>::Iterator
{
// Nothing interesting here.
};
You create a Sentinel
for both both the beginning and end. That seems a bit strange. I would expect to only see one Sentinel
value at the end.
template<typename T>
Linked_List<T>::Linked_List() : _size(0)
{
_head = new Node();
_tail = new Node();
_head->next = _tail;
_tail->prev = _head;
}
I would have expected this:
template<typename T>
Linked_List<T>::Linked_List()
: _head(new Node)
, _tail(_head)
, _size(0)
{}
This way if the list is empty both head and tail point at the same node. Thus if you generate iterators for head and tail they will both generate the end
iterator (which will compare equal).
Additionally there is a bug in your version.
_head = new Node(); // Assume this works
_tail = new Node(); // Assume this fails and throws.
// Because your constructor has not finished
// when the exception is thrown this object
// will not be fully constructed and therefore
// will not have its destructor called. This
// means you will leak the value pointed at by
// _head
Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).
template<typename T>
Linked_List<T>::~Linked_List() noexcept(false)
{
while (!empty())
{
pop_back();
}
delete head;
delete tail;
}
I would simply write like this:
Linked_List<T>::~Linked_List()
{
Node* current = _head;
while(current != nullptr) {
Node* old = current;
current = current->next;
delete old;
}
}
You know I mentioned above in the Node
description that the constructor could be made more useful. This is where it would work nicely.
Node(T value, Node* nextNode)
: prev(nextNode->prev)
, next(nextNode)
, value(value)
{
if (prev) {
prev->next = this;
}
next->prev = this; // There is always a next.
}
template<typename T>
void Linked_List<T>::push_back(T t)
{
Node* n = new Node(t, tail); // insert before tail.
tail = n->next;
}
template<typename T>
void Linked_List<T>::push_front(T t)
{
Node* n = new Node(t, head); // insert before head
head = n;
}
Personally I think that is much easier to read.
Personally I would not check if it is empty. It is the responsibility of the caller to check before calling X_pop()
. If you provide the check and it is not needed you are forcing the user to use sub-optimal code. See example below:
template<typename T>
void Linked_List<T>::pop_back()
{
if (empty()) throw Error("pop_back(): on empty list");
Node* n = _tail->prev;
_tail->prev->prev->next = _tail;
_tail->prev = _tail->prev->prev;
--_size;
delete n;
}
template<typename T>
void Linked_List<T>::pop_front()
{
if (empty()) throw Error("pop_front(): on empty list");
Node* n = _head->next;
_head->next->next->prev = _head;
_head->next = _head->next->next;
--_size;
delete n;
}
Here is a very common use case:
while(list.empty()) {
list.pop_back(); // This is guaranteed to only be called if
// if the list is not empty. So the check
// inside `pop_back()` is redudant and therefore
// a waste of cycles.
}
One of the big philosophies of C++ is to never charge people for something they don't need. Now there is also an argument to having the check. BUT this can be provided by having an explicit checked pop_back()
version: checked_pop_back()
.
list.checked_pop_back(); // Do I need to make a check before this call?
Simply go for checking the size(). If your object is in a consistent state then you can simply check the variable without having to pay the expense of the functions call.
template<typename T>
bool Linked_List<T>::empty() const
{
//return (_head->next == _tail) && (_tail->prev == _head);
return size() == 0;
}
I would just write:
bool Linked_List<T>::empty() const {return _size == 0;}
Again with the un-needed checks.
template<typename T>
T Linked_List<T>::back() const
{
if (empty()) throw Error("back(): on empty list");
return _tail->prev->value;
}
template<typename T>
T Linked_List<T>::front() const
{
if (empty()) throw Error("front(): on empty list");
return _head->next->value;
}
These look fine:
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::begin() const
{
// Though with the fix I suggested above this changes.
return Iterator(_head->next);
// If you only have the tail `Sentinel` this becomes
return Iterator(_head);
}
template<typename T>
typename Linked_List<T>::Iterator Linked_List<T>::end() const
{
return Iterator(_tail);
}
I haven't yet figured out how to implement:
Iterator insert(const Iterator, T);
Iterator erase(const Iterator);
If you have to insert
before the iterator? Then you can simply implement like I did above:
Iterator insert(const Iterator iterator, T value) {
Node* n = new Node(value, iterator->_current);
return Iterator(n);
}
Lets assume erase returns the iterator to the next element.
Iterator erase(const Iterator iterator)
Node* current = iterator->_current;
if (current == _tail) // can't delete the tail
return iterator;
}
// otherwise unlink from previous item.
if (current->prev == nullptr) {
head = current->next;
}
else {
current->prev->net = current->next;
}
// Next unlink from the next item.
current->next->prev=current->prev;
// Get the next item so we can return it.
Node* result = current->next;
// Delete the old value.
delete current;
// return the new result.
return Iterator(result);
}
edited 1 hour ago
answered 4 hours ago
Martin YorkMartin York
74.1k488272
74.1k488272
add a comment |
add a comment |
user644361 is a new contributor. Be nice, and check out our Code of Conduct.
user644361 is a new contributor. Be nice, and check out our Code of Conduct.
user644361 is a new contributor. Be nice, and check out our Code of Conduct.
user644361 is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216444%2fc-linked-list-iterator-implementation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I'm guessing that you haven't started your
const_iterator
yet? It can be helpful to do them together.$endgroup$
– Toby Speight
6 hours ago