I'm learning C++, data structures and algorithms and I have implemented a (Doubly) Linked List class for practice. Some STL functionalities are deliberately missing for now (e.g. some functions overloads, rbegin/rend/crbegin/crend, relational operators and many others). I would like to know if my approach is correct before implementing other functionalities. For example, I never implemented an iterator class before, so I opted to get a review on this first version before implementing a reverse iterator. Also, I learned from a standard book how to sort an array using merge sort, but not a linked list, so I'm curious to know if my approach to List::sort (based on this pseudocode) is clear and efficient, and how I could improve it.
I'm learning C++ through a C++11 book and trying to learn C++14 and C++17 best practices on the fly. I appreciate any advice on how make it more compatible with modern best practices. I'm using g++ compiler with -std=c++17 flag.
List.h
#ifndef LIST_H
#define LIST_H
#include <initializer_list>
#include <memory>
namespace algorithms
{
template<typename T>
class List
{
private:
struct Node
{
Node() = default;
Node(Node* right, Node* left, const T& value): next(right), prev(left), value(value)
{}
Node(Node* right, Node* left, T&& value): next(right), prev(left), value(std::move(value))
{}
Node(Node* right, Node* left): next(right), prev(left)
{}
template<typename... Args>
Node(Node* right, Node* left, Args&&... args): next(right), prev(left), value(std::forward<Args>(args)...)
{}
Node* next { nullptr };
Node* prev { nullptr };
T value {};
};
public:
using size_type = std::size_t;
using reference = T&;
using const_reference = const T&;
class const_iterator
{
public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = List::size_type;
using pointer = const value_type*;
using reference = const value_type&;
const_iterator() = default;
void swap(const_iterator& iterator) noexcept
{
using std::swap;
swap(node, iterator.node);
}
bool operator==(const const_iterator& iterator) const noexcept
{
return node == iterator.node;
}
bool operator!=(const const_iterator& iterator) const noexcept
{
return node != iterator.node;
}
reference operator*() const
{
return node->value;
}
reference operator->() const
{
return node->value;
}
// Prefix operators
const_iterator& operator++()
{
node = node->next;
return *this;
}
const_iterator& operator--()
{
node = node->prev;
return *this;
}
// Postfix operators
const_iterator operator++(int)
{
const_iterator old(*this);
node = node->next;
return old;
}
const_iterator operator--(int)
{
const_iterator old(*this);
node = node->prev;
return old;
}
protected:
Node* node { nullptr };
explicit const_iterator(Node* ptr): node(ptr)
{}
friend class List;
};
class iterator: public const_iterator
{
public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = List::size_type;
using pointer = value_type*;
using reference = value_type&;
iterator() = default;
reference operator*()
{
return this->node->value;
}
const reference operator*() const
{
return const_iterator::operator*();
}
reference operator->()
{
return this->node->value;
}
const reference operator->() const
{
return const_iterator::operator->();
}
// Prefix operators
iterator& operator++()
{
this->node = this->node->next;
return *this;
}
iterator& operator--()
{
this->node = this->node->prev;
return *this;
}
// Postfix operators
iterator operator++(int)
{
iterator old(*this);
++(*this);
return old;
}
iterator operator--(int)
{
iterator old = *this;
++(*this);
return old;
}
protected:
explicit iterator(Node* ptr): const_iterator(ptr)
{}
friend class List;
};
// Constructors and Destructor
List() = default;
List(size_type initial_size, const T& value);
explicit List(size_type inital_size);
template<typename InputIt>
List(InputIt first, InputIt last);
List(std::initializer_list<T> initializer);
List(const List& list);
List(List&& list) noexcept;
List& operator=(const List& list);
List& operator=(List&& list) noexcept;
~List();
// Iterators
iterator begin() noexcept;
const_iterator begin() const noexcept;
const_iterator cbegin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cend() const noexcept;
// Capacity
size_type size() const noexcept;
bool empty() const noexcept;
// Modifiers
template<typename InputIt>
void assign(InputIt first, InputIt last);
void assign(std::initializer_list<T> initializer);
iterator insert(const_iterator position, const T& value);
iterator insert(const_iterator position, T&& value);
template<typename InputIt>
iterator insert(const_iterator position, InputIt first, InputIt last);
template<typename... Args>
iterator emplace(const_iterator position, Args&&... args);
template<typename... Args>
reference emplace_back(Args&&... args);
void push_back(const T& value);
void push_back(T&& value);
void pop_back();
template<typename... Args>
reference emplace_front(Args&&... args);
void push_front(const T& value);
void push_front(T&& value);
void pop_front();
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void clear() noexcept;
void resize(size_type new_size, const T& value);
void resize(size_type new_size);
void swap(List& list) noexcept;
// Accessors
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// Operations
// Merge two sorted lists; no copies are made
template<typename Compare = std::less<>>
void merge(List& list, Compare compare = Compare());
template<typename Compare = std::less<>>
void sort(Compare compare = Compare());
template<typename Function>
size_type remove_if(Function function);
size_type remove(const T& value);
void splice(const_iterator position, List& list, const_iterator first, const_iterator last);
void splice(const_iterator position, List& list, const_iterator iterator);
void splice(const_iterator position, List& list);
void reverse() noexcept;
size_type unique();
template<typename BinaryFunction>
size_type unique(BinaryFunction binary_function);
private:
using Alloc = std::allocator<T>;
using NodeAlloc = typename std::allocator_traits<Alloc>::template rebind_alloc<Node>;
NodeAlloc node_allocator;
Node* head { create_head() };
size_type current_size { 0 };
Node* create_head();
template<typename... Args>
Node* create_node(Node* next, Node* prev, Args&&... args);
void destroy_node(Node* node);
template<typename... Args>
iterator insert_internal(const_iterator position, Args&&... args);
template<typename... Args>
void resize_internal(size_type new_size, Args&&... args);
template<typename Function>
size_type remove_if_internal(Function function);
template<typename BinaryFunction>
size_type unique_internal(BinaryFunction binary_function);
// Sorting utility functions
template<typename Compare>
const_iterator merge_sort(const_iterator first, size_type size, Compare compare);
template<typename Compare>
const_iterator merge(const_iterator first1, const_iterator first2, Compare compare);
};
// Non-member swap function
template<typename T>
void swap(List<T>& left, List<T>& right) noexcept;
}
#include "List.inl"
#endif // LIST_H
List.inl
#include <iterator>
namespace algorithms
{
// Constructors and Destructor
template<typename T>
List<T>::List(size_type initial_size, const T& value)
{
resize(initial_size, value);
}
template<typename T>
List<T>::List(size_type inital_size)
{
resize(inital_size);
}
template<typename T>
template<typename InputIt>
List<T>::List(InputIt first, InputIt last)
{
insert(begin(), first, last);
}
template<typename T>
List<T>::List(std::initializer_list<T> initializer): List(initializer.begin(), initializer.end())
{}
template<typename T>
List<T>::List(const List& list): List(list.begin(), list.end())
{}
template<typename T>
List<T>::List(List&& list) noexcept
{
list.swap(*this);
}
template<typename T>
List<T>& List<T>::operator=(const List& list)
{
List temp(list);
temp.swap(*this);
return *this;
}
template<typename T>
List<T>& List<T>::operator=(List&& list) noexcept
{
list.swap(*this);
return *this;
}
template<typename T>
List<T>::~List()
{
clear();
destroy_node(head);
}
// Iterators
template<typename T>
typename List<T>::iterator List<T>::begin() noexcept
{
return iterator(head->next);
}
template<typename T>
typename List<T>::const_iterator List<T>::begin() const noexcept
{
return const_iterator(head->next);
}
template<typename T>
typename List<T>::const_iterator List<T>::cbegin() const noexcept
{
return const_iterator(head->next);
}
template<typename T>
typename List<T>::iterator List<T>::end() noexcept
{
return iterator(head);
}
template<typename T>
typename List<T>::const_iterator List<T>::end() const noexcept
{
return const_iterator(head);
}
template<typename T>
typename List<T>::const_iterator List<T>::cend() const noexcept
{
return const_iterator(head);
}
// Capacity
template<typename T>
typename List<T>::size_type List<T>::size() const noexcept
{
return current_size;
}
template<typename T>
bool List<T>::empty() const noexcept
{
return current_size == 0;
}
// Modifiers
template<typename T>
template<typename InputIt>
void List<T>::assign(InputIt first, InputIt last)
{
clear();
insert(begin(), first, last);
}
template<typename T>
void List<T>::assign(std::initializer_list<T> initializer)
{
clear();
insert(begin(), initializer.begin(), initializer.end());
}
template<typename T>
typename List<T>::iterator List<T>::insert(const_iterator position, const T& value)
{
return emplace(position, value);
}
template<typename T>
typename List<T>::iterator List<T>::insert(const_iterator position, T&& value)
{
return emplace(position, value);
}
template<typename T>
template<typename InputIt>
typename List<T>::iterator List<T>::insert(const_iterator position, InputIt first, InputIt last)
{
iterator iterator;
while (first != last)
{
iterator = insert(position, *first++);
}
return iterator;
}
template<typename T>
template<typename... Args>
typename List<T>::iterator List<T>::emplace(const_iterator position, Args&&... args)
{
return insert_internal(position, std::forward<Args>(args)...);
}
template<typename T>
template<typename... Args>
typename List<T>::reference List<T>::emplace_back(Args&&... args)
{
auto iterator = insert_internal(end(), std::forward<Args>(args)...);
return *iterator;
}
template<typename T>
void List<T>::push_back(const T& value)
{
insert_internal(end(), value);
}
template<typename T>
void List<T>::push_back(T&& value)
{
insert_internal(end(), value);
}
template<typename T>
void List<T>::pop_back()
{
erase(const_iterator(head->prev));
}
template<typename T>
template<typename... Args>
typename List<T>::reference List<T>::emplace_front(Args&&... args)
{
auto iterator = insert_internal(begin(), std::forward<Args>(args)...);
return *iterator;
}
template<typename T>
void List<T>::push_front(const T& value)
{
insert_internal(begin(), value);
}
template<typename T>
void List<T>::push_front(T&& value)
{
insert_internal(begin(), value);
}
template<typename T>
void List<T>::pop_front()
{
erase(const_iterator(head->next));
}
template<typename T>
typename List<T>::iterator List<T>::erase(const_iterator position)
{
auto node_to_destroy = position.node;
auto next_node = node_to_destroy->next;
auto prev_node = node_to_destroy->prev;
// Link the node before position.node to the node after position.node
prev_node->next = next_node;
next_node->prev = prev_node;
// Unlink the node to be destroyed from the list and destroy it
node_to_destroy->next = node_to_destroy;
node_to_destroy->prev = node_to_destroy;
destroy_node(node_to_destroy);
--current_size;
return iterator(next_node);
}
template<typename T>
typename List<T>::iterator List<T>::erase(const_iterator first, const_iterator last)
{
if (first == begin() && last == end())
{
clear();
}
else
{
while (first != last)
{
first = erase(first);
}
}
return iterator(last.node);
}
template<typename T>
void List<T>::clear() noexcept
{
Node* node = head->next;
head->next = head;
head->prev = head;
for (Node* next_node; node != head; node = next_node)
{
next_node = node->next;
destroy_node(node);
}
current_size = 0;
}
template<typename T>
void List<T>::resize(size_type new_size, const T& value)
{
resize_internal(new_size, value);
}
template<typename T>
void List<T>::resize(size_type new_size)
{
resize_internal(new_size);
}
template<typename T>
void List<T>::swap(List& list) noexcept
{
using std::swap;
swap(this->head, list.head);
swap(this->current_size, list.current_size);
}
// Accessors
template<typename T>
typename List<T>::reference List<T>::front()
{
return head->next->value;
}
template<typename T>
typename List<T>::const_reference List<T>::front() const
{
return head->next->value;
}
template<typename T>
typename List<T>::reference List<T>::back()
{
return head->prev->value;
}
template<typename T>
typename List<T>::const_reference List<T>::back() const
{
return head->prev->value;
}
// Operations
template<typename T>
template<typename Compare>
void List<T>::merge(List& list, Compare compare)
{
if (this == &list)
{
return;
}
iterator this_it { begin() };
iterator other_it { list.begin() };
while (this_it != end() && other_it != list.end())
{
// return true if other < this using the custom comparison function
if (compare(*other_it, *this_it))
{
auto node_to_merge = other_it;
++other_it;
splice(this_it, list, node_to_merge, other_it);
}
else
{
++this_it;
}
}
// If other_it did not exhaust the list, splice it to the end of the list
if (other_it != list.end())
{
splice(end(), list, other_it, list.end());
}
}
template<typename T>
template<typename Compare>
void List<T>::sort(Compare compare)
{
merge_sort(begin(), size(), compare);
}
template<typename T>
template<typename Function>
typename List<T>::size_type List<T>::remove_if(Function function)
{
return remove_if_internal(function);
}
template<typename T>
typename List<T>::size_type List<T>::remove(const T& value)
{
return remove_if_internal([&value = value](const T& node_value) { return value == node_value; });
}
template<typename T>
void List<T>::splice(const_iterator position, List& list, const_iterator first, const_iterator last)
{
if (this == &list)
{
return;
}
auto size_change = std::distance(first, last);
auto position_node = position.node;
auto prev_node = position_node->prev;
auto first_node = first.node;
auto last_node = last.node->prev;
// Link the node before first.node to the node at last.node in the list passed as argument
auto new_first = first_node->prev;
new_first->next = last.node;
last.node->prev = new_first;
// Insert the nodes in range [first; last[ between position and it's previous node
first_node->prev = prev_node;
last_node->next = position_node;
prev_node->next = first_node;
position_node->prev = last_node;
current_size += size_change;
list.current_size -= size_change;
}
template<typename T>
void List<T>::splice(const_iterator position, List& list, const_iterator iterator)
{
if (this == &list)
{
return;
}
splice(position, list, iterator, const_iterator(iterator.node->next));
}
template<typename T>
void List<T>::splice(const_iterator position, List& list)
{
if (this == &list)
{
return;
}
splice(position, list, list.begin(), list.end());
}
template<typename T>
void List<T>::reverse() noexcept
{
using std::swap;
for (auto iterator = begin(); iterator != end(); )
{
auto current_node = iterator.node;
++iterator;
swap(current_node->next, current_node->prev);
}
auto new_first = head->prev;
auto new_last = head->next;
head->next = new_first;
head->prev = new_last;
}
template<typename T>
typename List<T>::size_type List<T>::unique()
{
return unique_internal([](const T& lhs, const T& rhs) { return lhs == rhs; });
}
template<typename T>
template<typename BinaryFunction>
typename List<T>::size_type List<T>::unique(BinaryFunction binary_function)
{
return unique_internal(binary_function);
}
// Private
template<typename T>
typename List<T>::Node* List<T>::create_head()
{
Node* node = node_allocator.allocate(1);
// Construct Node in storage pointed by node; node->next and node->prev points to node itself
node_allocator.construct(node, node, node);
return node;
}
template<typename T>
template<typename... Args>
typename List<T>::Node* List<T>::create_node(Node* next, Node* prev, Args&&... args)
{
Node* new_node = node_allocator.allocate(1);
node_allocator.construct(new_node, next, prev, std::forward<Args>(args)...);
return new_node;
}
template<typename T>
void List<T>::destroy_node(Node* node)
{
node_allocator.destroy(node);
node_allocator.deallocate(node, 1);
}
template<typename T>
template<typename... Args>
typename List<T>::iterator List<T>::insert_internal(const_iterator position, Args&&... args)
{
Node* next_node = position.node;
Node* previous_node = next_node->prev;
Node* new_node = create_node(next_node, previous_node, std::forward<Args>(args)...);
previous_node->next = new_node;
next_node->prev = new_node;
++current_size;
return iterator(new_node);
}
template<typename T>
template<typename... Args>
void List<T>::resize_internal(size_type new_size, Args&&... args)
{
if (size() < new_size)
{
auto to_add = new_size - size();
for (size_type i = 0; i < to_add; ++i)
{
insert_internal(end(), std::forward<Args>(args)...);
}
}
else
{
auto to_destroy = size() - new_size;
for (size_type i = 0; i < to_destroy; ++i)
{
pop_back();
}
}
}
template<typename T>
template<typename Function>
typename List<T>::size_type List<T>::remove_if_internal(Function function)
{
auto previous_size = size();
for (auto iterator = begin(); iterator != end(); )
{
if (function(*iterator))
{
auto to_erase = iterator;
iterator = erase(to_erase);
}
else
{
++iterator;
}
}
return previous_size - size();
}
template<typename T>
template<typename BinaryFunction>
typename List<T>::size_type List<T>::unique_internal(BinaryFunction binary_function)
{
auto previous_size = size();
auto iterator = begin();
auto back_iterator = iterator;
++iterator;
while (iterator != end())
{
if (binary_function(*back_iterator, *iterator))
{
auto to_erase = iterator;
iterator = erase(to_erase);
}
else
{
back_iterator = iterator;
++iterator;
}
}
return previous_size - size();
}
template<typename T>
template<typename Compare>
typename List<T>::const_iterator List<T>::merge_sort(const_iterator first, size_type size, Compare compare)
{
// Base case
if (size <= 1)
{
// Temporarily unlink the node from the list
first.node->next = head;
first.node->prev = head;
return first;
}
auto half_size = size / 2;
auto mid = std::next(first, half_size);
first = merge_sort(first, half_size, compare);
mid = merge_sort(mid, size - half_size, compare);
return merge(first, mid, compare);
}
template<typename T>
template<typename Compare>
typename List<T>::const_iterator List<T>::merge(const_iterator first1, const_iterator first2, Compare compare)
{
Node* lesser_node;
Node* greater_node;
// first1 and first2 each points to the start of two sublists, both ending at head.
// The merge operation reorder the nodes without creating any new node; only the links
// of the nodes are changed. At the end, the resulting list is sorted and head->next
// points to the start of the list and head->prev points to the end of the list.
while (first1.node != head || first2.node != head)
{
if (first1.node == head)
{
while (first2.node->next != head)
{
++first2;
}
head->prev = first2.node;
break;
}
else if (first2.node == head)
{
while (first1.node->next != head)
{
++first1;
}
head->prev = first1.node;
break;
}
else if (compare(*first1, *first2)) // first1 < first2 using the custom comparison function
{
lesser_node = first1.node;
greater_node = first2.node;
++first1;
}
else
{
lesser_node = first2.node;
greater_node = first1.node;
++first2;
}
greater_node->prev->next = lesser_node;
lesser_node->prev = greater_node->prev;
lesser_node->next = greater_node;
greater_node->prev = lesser_node;
}
// Returns iterator to the first node at the merged list
return const_iterator(head->next);
}
// Non-member swap function
template<typename T>
void swap(List<T>& left, List<T>& right) noexcept
{
left.swap(right);
}
}
EDIT:
As asked in the comments, the code bellow shows one example of how to use the class. It compiles and runs using g++ -std=c++17 -g -Wall main.cpp -o main. (I'm assuming that the List.h and List.inl files are in the same folder as main.cpp)
Running it with valgrind gave me no memory leaks and running it with GDB gave no errors. I've written more test cases, however I feel that the code in this post is already very long so I will post a not too large test.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include "List.h"
void test_sort()
{
namespace algs = algorithms;
algs::List<int> ascending { 3, 9, 1, 2, 4, 6, 5, 8, 7 };
ascending.sort();
assert(std::is_sorted(ascending.begin(), ascending.end()));
assert(ascending.size() == 9); // Assertion: no element was lost during the sort
assert(ascending.back() == 9);
algs::List<int> descending { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9 };
descending.sort(std::greater<>());
assert(std::is_sorted(descending.begin(), descending.end(), std::greater<>()));
assert(descending.size() == 10);
assert(descending.back() == -9);
auto string_comparison =
[](const std::string& lhs, const std::string& rhs)
{
return lhs.size() == rhs.size() ? (lhs < rhs) : lhs.size() < rhs.size();
};
algs::List<std::string> strings { "deque", "list", "vector", "stack", "graph", "set", "queue", "map" };
strings.sort(string_comparison);
assert(std::is_sorted(strings.begin(), strings.end(), string_comparison));
assert(strings.size() == 8);
assert(strings.back() == "vector");
}
void test_remove()
{
namespace algs = algorithms;
algs::List<std::string> list { "Alpha", "Beta", "Alpha", "Gamma", "Alpha", "Delta", "Alpha" };
auto old_size = list.size();
auto removed = list.remove("Alpha");
assert(list.size() + removed == old_size);
old_size = list.size();
removed = list.remove_if([](const auto& string) { return string.size() == 5; });
assert(list.size() + removed == old_size);
assert(list.size() == 1);
}
int main()
{
test_sort();
test_remove();
std::cout << "End of Test" << std::endl;
return 0;
}
Node
constructor already covers the others besides the default one and you can fix that by defaultingright
andleft
tonullptr
. \$\endgroup\$ – nwp Nov 11 at 12:33