##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
{
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);
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);
}