Forward linked list implementation in C++

Question

I wrote a linked list implementation in C++ to learn the concepts about linked lists as well as C++(17). I decided to use std::unique_ptr to help me avoid leaks and also took a lot of inspiration from std::forward_list.

I am not so worried about bugs, because I wrote some tests and they seem to pass. I am interested in knowing more about what is missing from my implementation compared to a gcc implementation and what the weaknesses are of my implementation. Also, interested in suggestions for making some parts of the implementation simpler (especially thinking about the complexity of merge and sort functions).

#ifndef CUSTOM_LINKED_LIST_HPP
#define CUSTOM_LINKED_LIST_HPP
#include <cstddef>
#include <iterator>
#include <memory>
#include <sstream>
#include <type_traits>
#include <cassert>
#include <iostream>
#include <utility>
namespace custom {
struct node_base {
 node_base(): next(nullptr) {}
 node_base(std::unique_ptr<node_base>&& n): next(std::move(n)) {}
 std::unique_ptr<node_base> next;
};
template<typename T>
struct node : node_base {
 node(std::unique_ptr<node_base>&& n, T d): node_base(std::move(n)), data(std::move(d)) {}
 T data;
};
template<typename T, typename node_ptr = node_base*>
class linked_list_forward_iterator {
public:
 // https://www.internalpointers.com/post/writing-custom-iterators-modern-cpp
 using iterator_category = std::forward_iterator_tag;
 using difference_type = std::ptrdiff_t;
 using value_type = T;
 using reference = T&;
 using pointer = T*;
 linked_list_forward_iterator(node_ptr ptr): m_ptr(ptr) {};
 // copy constructor, copy assignment operator, destructor= default
 reference operator*() const {
 return data_node()->data;
 }
 pointer operator->() {
 return &data_node()->data;
 }
 bool operator==(linked_list_forward_iterator<T, node_ptr> const& other) const {
 return this->m_ptr == other.m_ptr;
 }
 bool operator!=(linked_list_forward_iterator<T, node_ptr> const& other) const {
 return !(*this == other);
 }
 // prefix increment
 node_ptr operator++() {
 assert(m_ptr);
 m_ptr = m_ptr->next.get();
 return m_ptr;
 }
 // postfix increment
 node_ptr operator++(int) {
 linked_list_forward_iterator<T, node_ptr> tmp = *this;
 ++(*this);
 return tmp.m_ptr;
 }
 node<T>* data_node() const {
 return static_cast<node<T>*>(m_ptr);
 }
 node_ptr m_ptr;
};
template<typename T>
class linked_list {
static_assert(std::is_object_v<T>, "T must be object");
public:
 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = T&;
 using const_reference = T const&;
 using pointer = T*;
 using const_pointner = T const*;
 using iterator = linked_list_forward_iterator<T>;
 using const_iterator = linked_list_forward_iterator<const T>;
 // constructors && assignments
 linked_list(): m_head(std::make_unique<node_base>(nullptr)) {}
 explicit linked_list(size_type count): linked_list(count, T{}) {}
 explicit linked_list(size_type count, const_reference value)
 : linked_list()
 {
 node_base* last_node = m_head.get();
 for (size_type i = 0; i < count; i++) {
 last_node->next = std::make_unique<node<T>>(nullptr, value);
 last_node = last_node->next.get();
 }
 }
 explicit linked_list(std::initializer_list<T> init): linked_list(init.begin(), init.end()) {}
 template<class InputIt>
 linked_list(InputIt first, InputIt last)
 : linked_list()
 {
 node_base* last_node = m_head.get();
 for (auto it = first; it != last; ++it) {
 last_node->next = std::make_unique<node<T>>(nullptr, *it);
 last_node = last_node->next.get();
 }
 }
 linked_list(const linked_list& other): linked_list(other.cbegin(), other.cend()) {}
 linked_list(linked_list&& other) = default;
 ~linked_list() = default;
 linked_list& operator=(linked_list&& other) = default;
 linked_list& operator=(const linked_list& other) {
 linked_list<T> copy {other};
 swap(copy);
 return *this;
 }
 linked_list& operator=(std::initializer_list<T> ilist) {
 *this = linked_list<T>(ilist);
 return *this;
 }
 void assign(size_type count, const T& value) {
 *this = linked_list<T>(count, value);
 }
 template<class InputIt>
 void assign(InputIt first, InputIt last) {
 *this = linked_list<T>(first, last);
 }
 void assign(std::initializer_list<T> ilist) {
 *this = linked_list<T>(ilist);
 }
 // Element access
 T& front() {
 assert(m_head);
 return *begin();
 }
 T const& front() const {
 assert(m_head);
 return *cbegin();
 }
 // capacity
 size_type size() const {
 size_type size = 0;
 for (auto it = cbegin(); it != cend(); it++) {
 size++;
 }
 return size;
 }
 bool empty() const {
 return !m_head->next;
 }
 // iterators
 iterator before_begin() {
 return iterator(m_head.get());
 }
 const_iterator before_begin() const {
 return cbefore_begin();
 }
 const_iterator cbefore_begin() const {
 return const_iterator(m_head.get());
 }
 iterator begin() {
 return iterator(m_head->next.get());
 }
 const_iterator begin() const {
 return cbegin();
 }
 const_iterator cbegin() const {
 return const_iterator(m_head->next.get());
 }
 iterator end() {
 return nullptr;
 }
 const_iterator end() const {
 return cend();
 }
 const_iterator cend() const {
 return nullptr;
 }
 // modifiers
 iterator insert_after(const_iterator pos, T value) {
 assert(pos.m_ptr);
 node_base* my_node = pos.m_ptr;
 std::unique_ptr<node_base> old_next = std::move(my_node->next);
 std::unique_ptr<node<T>> new_node = std::make_unique<node<T>>(std::move(old_next), std::move(value));
 my_node->next = std::move(new_node);
 return my_node->next.get();
 }
 iterator insert_after(const_iterator pos, size_type count, const T& value) {
 assert(pos.m_ptr);
 iterator insert_pos = pos.m_ptr;
 for (size_type i=0; i<count; i++) {
 insert_pos = insert_after(insert_pos.m_ptr, value);
 }
 return insert_pos;
 }
 template<class InputIt>
 iterator insert_after(const_iterator pos, InputIt first, InputIt last) {
 assert(pos.m_ptr);
 iterator insert_pos = pos.m_ptr;
 for (auto it = first; it != last; it++) {
 insert_pos = insert_after(insert_pos.m_ptr, *it);
 }
 return insert_pos;
 }
 iterator insert_after(const_iterator pos, std::initializer_list<T> ilist) {
 return insert_after(pos, ilist.begin(), ilist.end());
 }
 template<class... Args>
 iterator emplace_after(const_iterator pos, Args&&... args) {
 assert(pos.m_ptr);
 node_base* my_node = pos.m_ptr;
 std::unique_ptr<node_base> old_next = std::move(my_node->next);
 std::unique_ptr<node<T>> new_node = std::make_unique<node<T>>(std::move(old_next), T(std::forward<Args...>(args...)));
 my_node->next = std::move(new_node);
 return my_node->next.get();
 }
 void push_front(const T& value) {
 insert_after(cbefore_begin(), value);
 }
 void push_front(T&& value) {
 insert_after(cbefore_begin(), std::move(value));
 }
 template<class... Args>
 reference emplace_front(Args&&... args) {
 return *emplace_after(cbefore_begin(), std::forward<Args...>(args...));
 }
 void pop_front() {
 erase_after(cbefore_begin());
 }
 iterator erase_after(const_iterator pos) {
 assert(pos.m_ptr);
 node_base* my_node = pos.m_ptr;
 std::unique_ptr<node_base> old_next = std::move(my_node->next);
 std::unique_ptr<node_base> new_next = std::move(old_next->next); 
 my_node->next = std::move(new_next);
 return my_node->next.get();
 }
 iterator erase_after(const_iterator first, const_iterator last) {
 // get prev to last node
 assert(first.m_ptr);
 if (first == last) {
 return last.m_ptr;
 }
 node_base* first_node = first.m_ptr;
 node_base* prev_to_last_node = get_prev_to_last_node(first, last).m_ptr;
 std::unique_ptr<node_base> new_next = std::move(prev_to_last_node->next); 
 first_node->next = std::move(new_next);
 return first_node->next.get();
 }
 void clear() {
 erase_after(cbefore_begin(), cend());
 }
 void swap(linked_list& other) {
 using std::swap;
 swap(m_head, other.m_head);
 }
 // operations
 void merge(linked_list& other) {
 // assumes sorted list
 if (this == &other) {
 return;
 }
 auto it_1 = this->before_begin();
 auto it_2 = other.before_begin();
 while (!other.empty()) {
 if (end() == it_1.m_ptr->next.get()) {
 std::unique_ptr<node_base> node_to_move = std::move(it_2.m_ptr->next);
 it_1.m_ptr->next = std::move(node_to_move);
 continue;
 }
 T const& val1 = static_cast<node<T>*>(it_1.m_ptr->next.get())->data;
 T const& val2 = static_cast<node<T>*>(it_2.m_ptr->next.get())->data;
 if (val1 > val2) {
 std::unique_ptr<node_base> node_to_move = std::move(it_2.m_ptr->next);
 std::unique_ptr<node_base> old_next_of_node_to_move = std::move(node_to_move->next);
 std::unique_ptr<node_base> new_next_of_node_to_move = std::move(it_1.m_ptr->next);
 it_2.m_ptr->next = std::move(old_next_of_node_to_move);
 node_to_move->next = std::move(new_next_of_node_to_move);
 it_1.m_ptr->next = std::move(node_to_move);
 }
 it_1 ++;
 }
 }
 void splice_after(const_iterator pos, linked_list& other) {
 std::unique_ptr<node_base> old_next = std::move(pos.m_ptr->next);
 auto before_end_it = get_prev_to_last_node(other.cbegin(), other.cend());
 before_end_it.m_ptr->next = std::move(old_next);
 std::unique_ptr<node_base> node_to_move = std::move(other.m_head->next);
 pos.m_ptr->next = std::move(node_to_move);
 }
 void splice_after(const_iterator pos, linked_list& other, const_iterator it) {
 (void) other;
 std::unique_ptr<node_base> old_next = std::move(pos.m_ptr->next);
 std::unique_ptr<node_base> node_to_move = std::move(it.m_ptr->next);
 std::unique_ptr<node_base> others_remaining_next = std::move(node_to_move->next);
 it.m_ptr->next = std::move(others_remaining_next);
 node_to_move->next = std::move(old_next);
 pos.m_ptr->next = std::move(node_to_move);
 }
 void remove(const T& value) {
 return remove_if([&value](const T& val){ return val == value; });
 }
 template<class UnaryPredicate>
 void remove_if(UnaryPredicate p) {
 auto it = before_begin();
 while (it.m_ptr->next.get() != nullptr) {
 T const& val = static_cast<node<T>*>(it.m_ptr->next.get())->data;
 if (!p(val)) {
 it++;
 continue;
 }
 std::unique_ptr<node_base> remaining = std::move(it.m_ptr->next->next);
 it.m_ptr->next = std::move(remaining);
 }
 }
 void reverse() {
 std::unique_ptr<node_base> following = nullptr;
 std::unique_ptr<node_base> current = std::move(m_head->next);
 std::unique_ptr<node_base> previous = nullptr;
 while (current) {
 following = std::move(current->next);
 current->next = std::move(previous);
 previous = std::move(current);
 current = std::move(following);
 }
 m_head->next = std::move(previous);
 }
 void unique() {
 auto it = begin();
 while (it.m_ptr->next.get() != nullptr) {
 T const& previous_val = static_cast<node<T>*>(it.m_ptr)->data;
 T const& val = static_cast<node<T>*>(it.m_ptr->next.get())->data;
 if (previous_val == val) {
 std::unique_ptr<node_base> node_to_remove = std::move(it.m_ptr->next);
 std::unique_ptr<node_base> new_next = std::move(node_to_remove->next);
 it.m_ptr->next = std::move(new_next);
 } else {
 it ++;
 }
 }
 }
 void sort() { 
 return sort([](const T& a, const T& b){ return a < b; });
 }
 template<class Compare>
 void sort(Compare comp) {
 merge_sort(m_head->next, comp);
 }
private:
 const_iterator get_prev_to_last_node(const_iterator first, const_iterator last) {
 assert(first.m_ptr);
 assert(first != last);
 auto it = first;
 auto prev_to_last_it = first;
 while (it != last) {
 prev_to_last_it = it++;
 }
 assert(prev_to_last_it.m_ptr);
 assert(prev_to_last_it.m_ptr->next.get() == last.m_ptr);
 return prev_to_last_it;
 }
 template<class Compare>
 void merge_sort(std::unique_ptr<node_base>& node_to_sort, Compare const& comp) {
 if (!node_to_sort || !node_to_sort->next) {
 return;
 }
 std::unique_ptr<node_base> other {nullptr};
 split_list(node_to_sort, other);
 assert(node_to_sort);
 assert(other);
 assert(debug_size(node_to_sort)-debug_size(other) <= 1);
 merge_sort(node_to_sort, comp);
 merge_sort(other, comp);
 assert(node_to_sort);
 assert(other);
 merge_sorted_nodes(node_to_sort, other, comp);
 assert(node_to_sort);
 assert(!other);
 }
 void split_list(
 std::unique_ptr<node_base>& begin_a,
 std::unique_ptr<node_base>& begin_b
 ) {
 assert(begin_a);
 assert(!begin_b);
 std::unique_ptr<node_base>* ptr_1 {&begin_a->next};
 std::unique_ptr<node_base>* ptr_2 {&begin_a};
 while (*ptr_1) {
 ptr_1 = &(*ptr_1)->next;
 if (*ptr_1) {
 ptr_1 = &(*ptr_1)->next;
 ptr_2 = &(*ptr_2)->next;
 }
 }
 begin_b = std::move((*ptr_2)->next);
 (*ptr_2)->next = nullptr;
 assert(begin_b);
 }
 template<class Compare>
 void merge_sorted_nodes(
 std::unique_ptr<node_base>& a,
 std::unique_ptr<node_base>& b,
 Compare const& comp
 ) {
 // assumes sorted list
 std::unique_ptr<node_base> tmp_base = std::make_unique<node_base>(std::move(a));
 std::unique_ptr<node_base>* current_node = &tmp_base;
 while (b) {
 if (!(*current_node)->next) {
 (*current_node)->next = std::move(b);
 b = nullptr;
 continue;
 }
 T const& val1 = static_cast<node<T>*>((*current_node)->next.get())->data;
 T const& val2 = static_cast<node<T>*>(b.get())->data;
 if (comp(val2, val1)) { // val2 < val1
 std::unique_ptr<node_base> node_to_move = std::move(b);
 std::unique_ptr<node_base> old_next_of_node_to_move = std::move(node_to_move->next);
 std::unique_ptr<node_base> new_next_of_node_to_move = std::move((*current_node)->next);
 b = std::move(old_next_of_node_to_move);
 node_to_move->next = std::move(new_next_of_node_to_move);
 (*current_node)->next = std::move(node_to_move);
 }
 current_node = &(*current_node)->next;
 }
 a = std::move(tmp_base->next);
 }
 std::size_t debug_size(std::unique_ptr<node_base> const& n) {
 std::unique_ptr<node_base> const * ptr = &n;
 std::size_t i = 0;
 while(*ptr) {
 ptr = &(*ptr)->next;
 i++;
 }
 return i;
 }
 std::string debug_string(node_base const* n) {
 std::stringstream ss {};
 while (n) {
 ss << n << ", ";
 n = n->next.get();
 }
 return ss.str();
 }
 std::unique_ptr<node_base> m_head;
};
template<class T>
bool operator==(const linked_list<T>& lhs, const linked_list<T>& rhs) {
 auto it_1 = lhs.begin();
 auto it_2 = rhs.begin();
 while(it_1 != lhs.end() && it_2 != rhs.end()) {
 T const& val1 = it_1.data_node()->data;
 T const& val2 = it_2.data_node()->data;;
 if (!(val1 == val2)) {
 return false;
 }
 it_1 ++;
 it_2 ++;
 }
 return it_1 == lhs.end() && it_2 == rhs.end();
}
template<class T>
bool operator!=(const linked_list<T>& lhs, const linked_list<T>& rhs) {
 return !(lhs == rhs);
}
template<class T>
bool operator<(const linked_list<T>& lhs, const linked_list<T>& rhs) {
 auto it_1 = lhs.begin();
 auto it_2 = rhs.begin();
 while(it_1 != lhs.end() && it_2 != rhs.end()) {
 T const& val1 = it_1.data_node()->data;
 T const& val2 = it_2.data_node()->data;;
 if (!(val1 < val2)) {
 return false;
 }
 it_1 ++;
 it_2 ++;
 }
 return true;
}
template<class T>
bool operator<=(const linked_list<T>& lhs, const linked_list<T>& rhs) {
 return (lhs == rhs) || (lhs < rhs);
}
template<class T>
bool operator>(const linked_list<T>& lhs, const linked_list<T>& rhs) {
 return !(lhs <= rhs);
}
template<class T>
bool operator>=(const linked_list<T>& lhs, const linked_list<T>& rhs) {
 return (lhs == rhs) || (lhs > rhs);
}
}
namespace std {
template<class T>
void swap(custom::linked_list<T>& lhs, custom::linked_list<T>& rhs) {
 lhs.swap(rhs);
}
}
#endif

Edit:

And here are the tests I wrote:

#include <gtest/gtest.h>
#include "linked_list.hpp"
class LinkedListTestFixture : public testing::Test {
protected:
 LinkedListTestFixture() {
 }
 ~LinkedListTestFixture() = default;
};
TEST_F(LinkedListTestFixture, test_constructors_assignments_and_iterator) {
 custom::linked_list<int> my_list_1 {2, 4, 9};
 EXPECT_EQ(3, my_list_1.size());
 std::vector<int> tmp_vector {1, 5, 6};
 custom::linked_list<int> my_list_2 (tmp_vector.begin(), tmp_vector.end());
 EXPECT_EQ(3, my_list_2.size());
 my_list_2 = custom::linked_list<int>(std::size_t(5), 9);
 EXPECT_EQ(5, my_list_2.size());
 custom::linked_list<int> my_list_3 = my_list_2;
 my_list_3 = my_list_1;
 my_list_3 = my_list_2;
 EXPECT_EQ(5, my_list_3.size());
 custom::linked_list<int> my_list_4 = std::move(my_list_3);
 EXPECT_EQ(5, my_list_4.size());
 auto i = 0;
 std::vector expected_values = {2, 4, 9};
 for (int const& x : my_list_1) {
 int const& y = expected_values.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_modifier_funcs) {
 custom::linked_list<double> my_list {1, 2, 3};
 my_list.insert_after(my_list.cbefore_begin(), -2);
 my_list.insert_after(my_list.cbefore_begin(), std::size_t(2), -3);
 custom::linked_list<double> tmp_list {10, 20};
 my_list.insert_after(my_list.cbegin(), tmp_list.cbegin(), tmp_list.cend());
 my_list.insert_after(my_list.cbegin(), {309, 319});
 my_list.emplace_after(my_list.cbefore_begin(), 45);
 my_list.push_front(44);
 my_list.emplace_front(42);
 my_list.emplace_front(42);
 my_list.pop_front();
 auto i = 0;
 std::vector<double> expectation = {
 42, 44, 45, -3, 309, 319, 10, 20, -3, -2, 1, 2, 3
 };
 for (double const& x : my_list) {
 double const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
 EXPECT_EQ(expectation.size(), my_list.size());
 EXPECT_EQ(false, my_list.empty());
 my_list.clear();
 EXPECT_EQ(true, my_list.empty());
}
TEST_F(LinkedListTestFixture, test_erase_after) {
 custom::linked_list<double> my_list {1, 2, 3, 4, 5, 6};
 auto start_it = my_list.cbegin();
 auto stop_it = start_it;
 ++stop_it;
 ++stop_it;
 ++stop_it;
 my_list.erase_after(start_it, stop_it);
 auto i = 0;
 std::vector<double> expectation = {1, 4, 5, 6};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (double const& x : my_list) {
 double const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_merge) {
 custom::linked_list<int> my_list {2, 4, 6, 7};
 my_list.merge(my_list);
 EXPECT_EQ(4, my_list.size());
 custom::linked_list<int> tmp_list {1, 5, 6};
 my_list.merge(tmp_list);
 custom::linked_list<int> tmp_list_2 {9, 9};
 my_list.merge(tmp_list_2);
 EXPECT_EQ(0, tmp_list.size());
 auto i = 0;
 std::vector<int> expectation = {1, 2, 4, 5, 6, 6, 7, 9, 9};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_splice) {
 custom::linked_list<int> my_list {1, 2, 3};
 custom::linked_list<int> tmp_list {10, 12};
 my_list.splice_after(my_list.cbegin(), tmp_list);
 EXPECT_EQ(0, tmp_list.size());
 tmp_list = {21, 22, 23};
 my_list.splice_after(my_list.cbegin(), tmp_list, tmp_list.cbegin());
 EXPECT_EQ(2, tmp_list.size());
 auto i = 0;
 std::vector<int> expectation = {1, 22, 10, 12, 2, 3};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_remove) {
 custom::linked_list<int> my_list {1, 2, 3, 5, 7, 5, 3, 2, 1};
 my_list.remove(2);
 my_list.remove_if([](auto const& val) { return (val == 5) || (val == 7); });
 auto i = 0;
 std::vector<int> expectation = {1, 3, 3, 1};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_reverse) {
 custom::linked_list<int> my_list {1, 2, 3};
 my_list.reverse();
 auto i = 0;
 std::vector<int> expectation = {3, 2, 1};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_unique) {
 custom::linked_list<int> my_list {1, 2, 2, 2, 3, 2, 2, 3, 2};
 my_list.unique();
 auto i = 0;
 std::vector<int> expectation = {1, 2, 3, 2, 3, 2};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_sort) {
 custom::linked_list<int> my_list {1, 3, 2, 5, 4, 1};
 my_list.sort();
 auto i = 0;
 std::vector<int> expectation = {1, 1, 2, 3, 4, 5};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
 my_list = {1, 3, 2};
 my_list.sort();
 i = 0;
 expectation = {1, 2, 3};
 EXPECT_EQ(expectation.size(), my_list.size());
 for (auto const& x : my_list) {
 auto const& y = expectation.at(i);
 EXPECT_EQ(y, x);
 i++;
 }
}
TEST_F(LinkedListTestFixture, test_comparison_operators) {
 custom::linked_list<int> my_list_1 {1, 2};
 custom::linked_list<int> my_list_2 {7, 8, 9};
 custom::linked_list<int> my_list_3 {7, 8, 9};
 EXPECT_FALSE(my_list_1 == my_list_2);
 EXPECT_TRUE(my_list_1 != my_list_2);
 EXPECT_FALSE(my_list_1 >= my_list_2);
 EXPECT_TRUE(my_list_1 <= my_list_2);
 EXPECT_TRUE(my_list_1 < my_list_2);
 EXPECT_FALSE(my_list_1 > my_list_2);
 EXPECT_TRUE(my_list_2 == my_list_3);
 EXPECT_FALSE(my_list_2 != my_list_3);
 EXPECT_TRUE(my_list_2 >= my_list_3);
 EXPECT_TRUE(my_list_2 <= my_list_3);
 EXPECT_FALSE(my_list_2 < my_list_3);
 EXPECT_FALSE(my_list_2 > my_list_3);
}
TEST_F(LinkedListTestFixture, test_swap) {
 custom::linked_list<int> my_list_1 {1, 2};
 custom::linked_list<int> my_list_2 {7, 8, 9};
 custom::linked_list<int> my_list_3 {7, 8, 9};
 custom::linked_list<int> my_list_4 {1, 2};
 std::swap(my_list_1, my_list_2);
 EXPECT_TRUE(my_list_1 == my_list_3);
 EXPECT_TRUE(my_list_2 == my_list_4);
}

Answer 1

It appears that memory is well handled, and the API is tidy and tested. Nice code!

Performance

A number of operations do a lot more work than necessary. They're within expected algorithmic complexity (that's good), but constant multipliers do matter too.

For example, the erase_after call iterates over each erased element twice instead of once:

• Once during the call to get_prev_to_last_node.
• Once during the assignment to next, which leads to a chain of destructors being called.

Instead, it could simply pop the elements one at a time until the next element is the end.

Stack Overflow

Pertaining to the above "chain of destructors", a number of operations -- including the destructor -- are susceptible to stack overflows.

If you have a list 1 -> 2 -> 3 -> 4 then:

• Calling the destructor of 1,
• Will call the destructor of 2,
• Will call the destructor of 3,
• Will call the destructor of 4,
• The latter will complete, returning control to the destructor of 3.
• Which will complete, returning control to the destructor of 2.
• Which will complete, returning control to the destructor of 1.
• Which will complete, returning control to the caller.

This is typically of node-based structures: the depth of the call stack is proportional to the depth of the structure. For balanced binary trees, with O(log n) depth, it's typically not an issue; for linked-lists, with O(n) depth, it very much is.

There's no magic here, you cannot rely on the destructor of unique_ptr to handle the job and must manually convert the recursion to iteration every time.

Note: this typically only manifest for relatively large lists; with stacks a typical 1MB to 8MB, and a call frame taking as little as 16 - 64 bytes, it can take up to 500K elements to trigger the issue. I suggest setting up a test with a few million elements, and testing various operations.

• wakey: How would you convert the recursion of a forwards linked list to iteration? Off the cuff it would seem like you need a backwards pointer to do this effectively.
• Matthieu M.: @wakey: How insistent are you on destroying the elements backwards? If you are fine destroying them forwards, you can just go ahead and do it. If you absolutely watns backwards, then you can reverse the range to destroy and do it forwards: pop first element, pop 2nd and prepend to 1st, pop 3rd and prepend to 2nd, ... then destroy the new list "forwards".
• Toby Speight: @wakey, The key to avoiding the deep recursion is to release() each pointer before destructing it and moving along to the next element (the raw pointer release() returned).
• Matthieu M.: @TobySpeight: Rust (where such would be unsafe) taught me another method: auto next = std::move(current->next); current = std::move(next);. This way memory is still managed automatically: no manual delete or tricky stuff :)
• Sourav Ganguly: wow thats genius

Answer 2

Move all other classes into linked_list

node_base, node and linked_list_forward_iterator are all basically implementation details of linked_list. Consider moving them all into linked_list. This has several benefits, most notably you don't have to make node and linked_list_forward_iterator templates anymore, they can just use the template parameter T from linked_list itself. Furthermore, this avoids polluting the global namespace, and you can rename linked_list_forward_iterator to forward_iterator.

Merge node_base and node

I don't see any benefit of having node_base in your code. I would just make a class node that looks like this:

template<typename T>
class linked_list {
 struct node {
 T data;
 std::unique_ptr<node> next;
 ...
 };
 class forward_iterator {
 ...
 node* m_ptr;
 };
 ...
 std::unique_ptr<node> m_head;
};

This simplifies things, for example there is no longer a need for static_casts from node_base* to node*.

Increment operators of iterators should return iterators

operator++() should always return a reference to either the current or previous *this. Otherwise, code expecting the usual behavior of iterators will be broken. It might seem to work in some situations because your increment operators return a node_ptr, and linked_list_forward_iterator has a constructor that takes a node_ptr. Consider making that constructor explicit as well.

Avoid unnecessary initializations

A std::unique_ptr has a default constructor that already initializes itself to nullptr, so there is no need to do that explicitly yourself.

No need to repeat template parameters inside a template itself

Inside class linked_list, you don't need to write linked_list<T>, you can just write linked_list.

• Sourav Ganguly: Thanks. I like your suggestions. I chose to make a separate node_base because I needed a node for "before head" which does not have any value associated with it. I thought of using a std::optional<T> data in node<T> as an alternative to accomodate this "no data" node but went with the former approach just because that is what std::forward_list did.
• Sourav Ganguly: You said that a std::unique_ptr has a default constructor that already initializes itself to nullptr. But is the default constructor called automatically in this case? I know atleast for basic types like int, bool, I need to initialize myself. I always get confused with this.
• Deduplicator: Having a generic node_base is more useful for a double-linked list...
• G. Sliepen: For cursor-like things where you want to be able to point "before head", I would typically use a pointer-to-pointer, or in this case a pointer-to-std::unique_ptr<node>. You can have it point to either the linked_list's m_head or to a node's next.
• Maxim Egorushkin: From practical engineering perspective nested classes have only drawbacks. When the enclosing class is a template, nested classes end up being unique classes, even when they don't depend on template arguments. Nested classes have longer fully qualified symbol names, which results in larger debuginfo but worse readability of names in debugger and in stacktraces. Nested classed cannot be forward declared. An implementation detail namespace is a better solution.

Answer 3

The main problem in your design is using std::unique_ptr.

The default list destructor invokes ~node_base (which must be virtual, but that would double the size of node_base ), which invokes ~unique_ptr which invokes ~node_base and so on. With 10MB stack on a 64-bit Linux, destroying a list with 328k+ elements is going to crash with stack overflow.

• Toby Speight: That's pretty much what Matthieu M. said.
• Toby Speight: Eh? Can you explain what this answer adds, that wasn't already said? That comment seems detached from anything here...
• Matthieu M.: Good catch on the virtual destructor!

Answer 4

You have a good review of the linked list itself. I'll mostly focus on the tests.

Just a handful of quick observations on the list:

• We don't need to include <iostream>.
• It seems that assert() is being wrongly used as a run-time test rather than as documentation of an invariant.
• We're missing an implicit conversion from iterator to const_iterator.
• The relational operators comparing two lists can be implemented more simply using standard algorithms (std::equal() and std::lexicographical_compare() in particular).
• Although we're allowed to specialise std::swap(), the standard practice is to define custom::swap(), which can be found by ADL. We probably don't even need this, given that move-assignment (as used by unspecialised std::swap()) is cheap.

---

Anyway, let's move on to the tests. The tests seem almost complete, and exercise the class well. And they expose no memory errors when run under Valgrind. That's all good.

Some things could be made even better, though.

We have an empty fixture class. That doesn't serve any purpose - we can remove that and change our use of TEST_F() to TEST().

I'm surprised not to see the simplest test:

TEST(LinkedList, DefaultConstructor)
{
 custom::linked_list<int> list;
 EXPECT_EQ(0, list.size());
}

Small aside: I've followed the rule in the GoogleTest manual, and avoided using underscore in my test names.

The existing test_constructors_assignments_and_iterator contains several independent tests. I think it's worth separating them into individual tests. That costs pretty much nothing, and makes life easier for the reader:

TEST(LinkedList, DefaultConstructor)
{
 custom::linked_list<int> list;
 EXPECT_EQ(0, list.size());
}
TEST(LinkedList, InitializerListConstructor)
{
 custom::linked_list list{2, 4, 9};
 EXPECT_EQ(3, list.size());
}
TEST(LinkedList, IteratorPairConstructor)
{
 std::vector<int> v{1, 5, 6, 2};
 custom::linked_list<int> list(v.begin(), v.end());
 EXPECT_EQ(4, list.size());
}
TEST(LinkedList, CopyAssign)
{
 custom::linked_list list{2, 4, 9};
 EXPECT_EQ(3, list.size());
 custom::linked_list list2{1, 3};
 list = list2;
 EXPECT_EQ(2, list.size());
}
TEST(LinkedList, MoveAssign)
{
 custom::linked_list list{2, 4, 9};
 EXPECT_EQ(3, list.size());
 list = {1, 3};
 EXPECT_EQ(2, list.size());
}
TEST(LinkedList, IteratorForward)
{
 custom::linked_list list{2, 4, 9};
 auto it = list.cbegin();
 EXPECT_EQ(2, *it++);
 EXPECT_EQ(4, *it++);
 EXPECT_EQ(9, *it++);
 EXPECT_EQ(it, list.cend());
}

That's longer than what you had, but the reduced density makes comprehension easier. There's generally only one or two variables in each block now.

Most of the other tests can be split up into simpler, more targeted functions in a similar way. And we shouldn't need loops in our tests (the loops I see are all element-by-element comparison, but we can just compare entire lists once we have a proven == operator).

For example:

TEST(LinkedList, EmplaceFront)
{
 custom::linked_list<std::string> list{"one", "two", "three"};
 list.emplace_front("zero");
 const custom::linked_list<std::string> expected{"zero", "one", "two", "three"};
 EXPECT_EQ(list, expected);
}

• Deduplicator: assert() is used to test for programmer error, and AFAICS, all the constraints tested thus are bounds for UB.
• Toby Speight: I guess the appropriateness depends on where you draw the line between the "programmer" and the "user". I take the view that the public functions form the boundary, since they can be called by anyone. That means we need a reliable means to reject misuse at that point (i.e. a proper test, rather than a debug-only assert()), and limit the use of assert just to expressions that depend only on this class. Perhaps you draw the line at a different point, @Deduplicator?
• Deduplicator: The public interface is certainly the boundary, but is not a security boundary. Catching that the user broke the contract has a not insignificant cost, which quickly grows unbearably high without completely changing the design and the underlying language. Thus the asserts only catch a small (though the most common) part of it for a cost which should be acceptable when debugging, they don't change the contract nor are remotely enough to verify all preconditions. Whether you want to retain them and pay the cost in released software is your decision.