C++ linked list iterator implementation












5












$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);










share|improve this question









New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 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
















5












$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);










share|improve this question









New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 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














5












5








5





$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);










share|improve this question









New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$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






share|improve this question









New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 6 hours ago







user644361













New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 9 hours ago









user644361user644361

262




262




New contributor




user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






user644361 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 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














  • 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








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










1 Answer
1






active

oldest

votes


















2












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





share|improve this answer











$endgroup$














    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.










    draft saved

    draft discarded


















    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









    2












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





    share|improve this answer











    $endgroup$


















      2












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





      share|improve this answer











      $endgroup$
















        2












        2








        2





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





        share|improve this answer











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






        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited 1 hour ago

























        answered 4 hours ago









        Martin YorkMartin York

        74.1k488272




        74.1k488272






















            user644361 is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            How to make a Squid Proxy server?

            Is this a new Fibonacci Identity?

            19世紀