Taking into account everything you guys told me last time I posted, I came up with this implementation of a singly-linked list, in which the first and last elements are known.
I tried to make the implementation as STL-friendly as possible, so I also implemented iterators. It's my first time with those, so there might be bugs that I have missed. Also the operator-> overload for the iterators... I have no idea if what I've done is correct.
I hope someone with experience in this can share some knowledge!!
P.S. Performance is also of great concern!
#include <stdexcept>
#include <iostream>
#include <initializer_list>
#include <cstddef>
#include <iterator>
#include <utility>
#include <type_traits>
template<class T>
class slist
{
public: //TYPE ALIASES
using value_type = T;
using size_type = std::size_t;
using reference = T&;
using const_reference = const T&;
using pointer = T*;
using const_pointer = const T*;
private: //WAY TOO LONG TO HAVE IN MULTIPLE FUNCTIONS
template<class Iterator>
using is_correct_iterator = std::enable_if_t
<
std::is_same<T, typename std::iterator_traits<Iterator>::value_type>::value &&
std::is_base_of<std::input_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category>::value
>;
private: //PRIVATE MEMBER VARIABLES
struct node
{
T key;
node* next;
} *_root, *_tail;
std::size_t _size;
public: //ITERATOR CLASSES
class iterator : public std::iterator<std::forward_iterator_tag, T>
{
protected:
node* _node;
friend class slist<T>;
//only for slist<T> to access
iterator(node* new_node) : _node(new_node) {}
public:
constexpr iterator() = default;
constexpr iterator(const iterator&) = default;
constexpr iterator(iterator&&) = default;
iterator& operator=(const iterator&) = default;
iterator& operator=(iterator&&) = default;
iterator& operator++() { _node = _node->next; return *this; }
iterator operator++(int) { iterator temp(_node); operator++(); return temp; }
bool operator!=(const iterator& rhs) const { return _node != rhs._node; }
bool operator==(const iterator& rhs) const { return _node == rhs._node; }
bool operator>(const iterator& rhs) const { return _node > rhs._node; }
bool operator<(const iterator& rhs) const { return _node < rhs._node; }
bool operator>=(const iterator& rhs) const { return _node >= rhs._node; }
bool operator<=(const iterator& rhs) const { return _node <= rhs._node; }
T& operator*() { return _node->key; }
T* operator->() { return **this; } //no idea what im doing here
};
class const_iterator : public iterator
{
private:
friend class slist<T>;
public:
using iterator::iterator; //inherit them constructors
const_iterator& operator++() { _node = _node->next; return *this; }
const_iterator operator++(int) { const_iterator temp(_node); operator++(); return temp; }
T operator*() const { return _node->key; }
T* operator->() const { return **this; } //still no idea
};
public: //ACTUAL slist<T> CLASS
//CONSTRUCTORS
slist() : _root(nullptr), _tail(nullptr), _size(0) {}
template<class Iterator, class = is_correct_iterator<Iterator>>
slist(Iterator first, Iterator last) { assign(first, last); }
slist(const std::size_t& count, const T& val) { assign(count, val); }
slist(const std::initializer_list<T>& ilist) : slist(ilist.begin(), ilist.end()) {}
slist& operator=(const std::initializer_list<T>& ilist)
{
assign(ilist.begin(), ilist.end());
return *this;
}
//COPY/MOVE CONSTRUCTORS AND ASSIGNMENT
slist(const slist& rhs)
: _root(nullptr), _tail(nullptr), _size(0)
{
for (const auto& i : rhs)
emplace_back(i);
}
slist(slist&& rhs)
: _root(nullptr), _tail(nullptr), _size(0)
{
swap(rhs);
}
slist& operator=(const slist& rhs)
{
if (this == &rhs)
return *this;
clear();
for (const auto& i : rhs)
emplace_back(i);
return *this;
}
slist& operator=(slist&& rhs)
{
if (this == &rhs)
return *this;
_root = nullptr;
_tail = nullptr;
_size = 0;
swap(rhs);
return *this;
}
//DESTRUCTOR
~slist() { clear(); }
//INSERT OPERATIONS
void push_front(T& new_key) { emplace_front(new_key); }
void push_front(T&& new_key) { emplace_front(std::move(new_key)); }
void push_back(T& new_key) { emplace_back(new_key); }
void push_back(T&& new_key) { emplace_back(std::move(new_key)); }
template<class... Args>
void emplace_front(Args&&... args)
{
_root = new node{ { std::forward<Args>(args)... }, _root };
if (!_root->next)
_tail = _root;
++_size;
}
template<class... Args>
void emplace_back(Args&&... args)
{
node* new_node = new node{ { std::forward<Args>(args)... }, nullptr };
if (!_tail)
{
_tail = new_node;
_root = new_node;
}
else
{
_tail->next = new_node;
_tail = _tail->next;
}
++_size;
}
void insert_after(const iterator& it, const T& new_key) { emplace_after(it, new_key); }
void insert_after(const iterator& it, T&& new_key) { emplace_after(it, std::move(new_key)); }
template<class... Args>
void emplace_after(const iterator& it, Args&&... args)
{
if (!it._node)
throw std::out_of_range("List is empty! Use emplace_back() or emplace_front() instead!");
it._node->next = new node{ { std::forward<Args>(args)... }, it._node->next };;
++_size;
}
//ASSIGN
void assign(const std::size_t& count, const T& val)
{
clear();
for (std::size_t i = 0; i < count; ++i)
emplace_back(val);
}
template<class Iterator, class = is_correct_iterator<Iterator>>
void assign(Iterator first, Iterator last)
{
clear();
for (; first != last; ++first)
emplace_back(*first);
}
void assign(const std::initializer_list<T>& ilist)
{
clear();
assign(ilist.begin(), ilist.end());
}
//DELETE OPERATIONS
void pop_front()
{
if (!_root)
throw std::out_of_range("Can't pop from an empty list!!");
if (_size == 1)
{
_root = nullptr;
_tail = nullptr;
}
else
{
node* temp_root = _root;
_root = _root->next;
delete temp_root;
}
--_size;
}
void pop_back() //O(n)
{
if (!_root)
throw std::out_of_range("Can't pop from an empty list!!");
if (_size == 1)
{
_root = nullptr;
_tail = nullptr;
}
else
{
node* before_tail = _root;
while (before_tail->next->next)
before_tail = before_tail->next;
before_tail->next = nullptr; //so _tail = nullptr
_tail = before_tail; //last node is equal to one before last
delete before_tail->next; //delete _tail
}
--_size;
}
void erase_after(const iterator& it)
{
if (!_root)
throw std::out_of_range("Can't erase from an empty list!!");
node* temp = it._node->next;
it._node->next = temp->next;
delete temp;
--_size;
}
void clear()
{
while (!empty())
pop_front();
}
//CAPACITY FUNCTIONS
constexpr std::size_t size() const noexcept { return _size; }
constexpr bool empty() const noexcept { return !_size; }
//ACCESS FUNCTIONS
T& front() { return _root->key; }
T& back() { return _tail->key; }
const T& front() const { return _root->key; }
const T& back() const { return _tail->key; }
//ITERATORS
iterator begin() noexcept { return iterator(_root); }
iterator end() noexcept { return iterator(nullptr); }
const_iterator begin() const noexcept { return const_iterator(const_cast<node*>(_root)); }
const_iterator end() const noexcept { return const_iterator(nullptr); }
const_iterator cbegin() const noexcept { return const_iterator(_root); }
const_iterator cend() const noexcept { return const_iterator(nullptr); }
//INDEXING
T& operator[](const std::size_t& index)
{
if (index < 0 || index >= _size)
throw std::out_of_range("Index out of bounds!");
if (index == 0)
return _root->key;
if (index == _size - 1)
return _tail->key;
iterator it(_root);
std::advance(it, index);
return *it;
}
//ALGORITHMS
void swap(slist& rhs)
{
std::swap(_root, rhs._root);
std::swap(_tail, rhs._tail);
std::swap(_size, rhs._size);
}
};
