4
\$\begingroup\$

I'm about to post quite a bit of code. Hopefully, someone is willing to put some time into reviewing it all. I know linked lists have been done a lot on here, but I wanted to improve the basic C++ skills I learned in college by learning more about templates, inheritance, move semantics, smart pointers, SFINAE, etc. My code consists of an abstract base class, LinkedList, with two derived classes, SLinkedList and DLinkedList. Also included is a custom iterator hierarchy.

My goal in posting this is to become a better C++ programmer. Therefore, any feedback regarding a better way of doing something is welcome!

NOTE: This code does not compile using G++ due to a compiler bug. See this Stack Overflow question for more information. It compiles just fine with Clang++ 6.0.1.

LinkedList.hpp:

#ifndef LINKEDLIST_HPP
#define LINKEDLIST_HPP

#include <algorithm>
#include <memory>
#include <type_traits>
#include <utility>
#include "NodeIterator.hpp"

namespace bork_lib
{

class SingleLinkage {};
class DoubleLinkage {};

template<typename, typename = void>
struct supports_less_than : std::false_type { };

template<typename T>
struct supports_less_than<T, std::void_t<decltype(std::declval<T&>() <= std::declval<T&>())>> : std::true_type { };

template<typename LinkageType, typename ValueType>
class LinkedList {
protected:
    template<typename ShadowedLinkageType, typename = void> struct ListNode;

    template<typename ShadowedLinkageType>
    struct ListNode<ShadowedLinkageType, std::enable_if_t<std::is_same<ShadowedLinkageType, SingleLinkage>::value>>
    {
        ValueType data;
        std::unique_ptr<ListNode> next = std::unique_ptr<ListNode>(nullptr);

        template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<ValueType, Args&&...>>>
        explicit ListNode(Args&&... args) : data{std::forward<Args>(args)...} { }
        explicit ListNode(const ValueType& data) : data{data} { }
        explicit ListNode(ValueType&& data) : data{std::forward<ValueType>(data)} { }
    };

    template<typename ShadowedLinkageType>
    struct ListNode<ShadowedLinkageType, std::enable_if_t<!std::is_same<ShadowedLinkageType, SingleLinkage>::value>>
    {
        ValueType data;
        std::unique_ptr<ListNode> next = std::unique_ptr<ListNode>(nullptr);
        ListNode* prev = nullptr;

        template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<ValueType, Args&&...>>>
        explicit ListNode(Args&&... args) : data{std::forward<Args>(args)...} { }
        explicit ListNode(const ValueType& data) : data{data} { }
        explicit ListNode(ValueType&& data) : data{std::forward<ValueType>(data)} { }
    };

public:
    using value_type = ValueType;
    using reference = ValueType&;
    using const_reference = const ValueType&;
    using pointer = ValueType*;
    using const_pointer = const ValueType*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    using iterator = std::conditional_t<std::is_same<LinkageType, SingleLinkage>::value,
                     ForwardListIterator<ValueType>, ListIterator<ValueType>>;
    using const_iterator = std::conditional_t<std::is_same<LinkageType, SingleLinkage>::value,
                           ConstForwardListIterator<ValueType>, ConstListIterator<ValueType>>;

    using node_iterator = NodeIterator<ListNode<LinkageType>, value_type>;

protected:
    using node_type = ListNode<LinkageType>;
    std::unique_ptr<node_type> head = std::unique_ptr<node_type>(nullptr);
    node_type* tail = nullptr;
    bool srtd = true;         // the list is guaranteed to be sorted if true
    size_type sz = 0;         // size of the list

    void list_swap(LinkedList<LinkageType, ValueType>& other);
    void swap(value_type& a, value_type& b);

    template<typename... Args> void emplace_empty(Args&&... args);
    node_type* find_sorted_position(const value_type& val);
    virtual node_type* insert_node_before(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse) = 0;
    virtual node_type* insert_node_after(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse) = 0;

    void mergesort(std::unique_ptr<node_type>& left_owner, size_type size);
    virtual void merge(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size) = 0;

    virtual node_type* delete_node(node_type* node, bool is_reverse) = 0;
    node_type* search_front(const value_type& val) const noexcept;
    template<typename InputIterator> void construct_from_iterator_range(InputIterator begin, InputIterator end);

public:
    // construction, assignment, and destruction
    LinkedList() = default;
    LinkedList(const LinkedList<LinkageType, value_type>& other) = delete;
    LinkedList(LinkedList<LinkageType, value_type>&& other) noexcept
     : head{std::move(other.head)}, tail{other.tail}, sz{other.sz}, srtd{other.srtd} { }
    LinkedList<LinkageType, ValueType>& operator=(const LinkedList<LinkageType, ValueType>& other);
    LinkedList<LinkageType, ValueType>& operator=(LinkedList<LinkageType, ValueType>&& other) noexcept;
    virtual ~LinkedList() noexcept { clear(); };

    bool empty() const noexcept { return !head; }
    size_type size() const noexcept { return sz; }
    bool sorted() const noexcept { return srtd; }
    reference front() const noexcept { return head->data; }
    reference back() const noexcept { return tail->data; }

    node_iterator& insert_before(node_iterator& iter, const value_type& val) { return emplace_before(iter, val); }
    node_iterator& insert_before(node_iterator& iter, value_type&& val) { return emplace_before(iter, std::forward<value_type>(val)); }
    node_iterator& insert_after(node_iterator& iter, const value_type& val) { return emplace_after(iter, val); }
    node_iterator& insert_after(node_iterator& iter, value_type&& val) { return emplace_after(iter, std::forward<value_type>(val)); }
    void insert_sorted(const value_type& val) { return emplace_sorted(val); }
    void insert_sorted(value_type&& val) { return emplace_sorted(std::forward<value_type>(val)); }

    template<typename... Args> node_iterator& emplace_before(node_iterator& iter, Args&&... args);
    template<typename... Args> node_iterator& emplace_after(node_iterator& iter, Args&&... args);
    template<typename... Args> void emplace_sorted(Args&&... args);

    void push_front(const value_type& val) { emplace_front(val); }
    void push_front(value_type&& val) { emplace_front(std::forward<value_type>(val)); }
    void push_back(const value_type& val) { emplace_back(val); }
    void push_back(value_type&& val) { emplace_back(std::forward<value_type>(val)); }

    template<typename... Args> void emplace_front(Args&&... args) { iterator iter{head.get()}; emplace_before(iter, std::forward<Args>(args)...); }
    template<typename... Args> void emplace_back(Args&&... args) { iterator iter{tail}; emplace_after(iter, std::forward<Args>(args)...); }

    void pop_front() { delete_node(head.get(), false); }
    void pop_back() { delete_node(tail, false); }

    iterator find(const value_type& val) const noexcept;
    size_type count(const value_type& val) const noexcept;
    node_iterator& erase(node_iterator& iter);
    void clear() noexcept;

    template<typename T = value_type, std::enable_if_t<supports_less_than<T>::value, int> = 0>
    void sort();
    template<typename T = value_type, std::enable_if_t<!supports_less_than<T>::value, int> = 0>
    void sort() { throw std::logic_error("List cannot be sorted, as value_type does not support comparison."); }

    // iterator functions
    iterator begin() noexcept { return iterator{head.get()}; }
    const_iterator begin() const noexcept { return const_iterator{head.get()}; }
    iterator end() noexcept { return iterator{nullptr}; }
    const_iterator end() const noexcept { return const_iterator{nullptr}; };
    const_iterator cbegin() const noexcept { return const_iterator{head.get()}; }
    const_iterator cend()  const noexcept { return const_iterator{nullptr}; }

    friend class ListIterator<value_type>;
    friend class ConstListIterator<value_type>;
    friend class ReverseListIterator<value_type>;
    friend class ConstReverseListIterator<value_type>;
    friend class ForwardListIterator<value_type>;
    friend class ConstForwardListIterator<value_type>;
    friend class NodeIterator<ListNode<LinkageType>, value_type>;
};

template<typename LinkageType, typename ValueType>
LinkedList<LinkageType, ValueType>& LinkedList<LinkageType, ValueType>::operator=(const LinkedList<LinkageType, ValueType>& other)
{
    clear();
    for (const auto& x : other) {
        push_back(x);
    }

    srtd = other.srtd;
    return *this;
}

template<typename LinkageType, typename ValueType>
LinkedList<LinkageType, ValueType>& LinkedList<LinkageType, ValueType>::operator=(LinkedList<LinkageType, ValueType>&& other) noexcept
{
    list_swap(other);
    return *this;
}

template<typename LinkageType, typename ValueType>
void LinkedList<LinkageType, ValueType>::list_swap(LinkedList<LinkageType, ValueType>& other)
{
    auto temp_unique = std::move(head);
    head = std::move(other.head);
    other.head = std::move(temp_unique);

    using std::swap;
    swap(tail, other.tail);
    swap(sz, other.sz);
    swap(srtd, other.srtd);
}

template<typename LinkageType, typename ValueType>
void LinkedList<LinkageType, ValueType>::swap(value_type& a, value_type& b)
{
    value_type tmp{std::move(a)};
    a = std::move(b);
    b = std::move(tmp);
}

/* Helper function to insert an element in-place into an empty list. */
template<typename LinkageType, typename ValueType>
template<typename... Args>
void LinkedList<LinkageType, ValueType>::emplace_empty(Args&&... args)
{
    head = std::make_unique<node_type>(std::forward<Args>(args)...);
    tail = head.get();
    ++sz;
}

/* Helper function to find the correct position for inserting an element into a sorted list. */
template<typename LinkageType, typename ValueType>
typename LinkedList<LinkageType, ValueType>::node_type* LinkedList<LinkageType, ValueType>::find_sorted_position(const value_type &val)
{
    auto node = head.get();
    while (node) {
        if (node->data >= val) {
            return node;
        }
        node = node->next.get();
    }

    return nullptr;
}

/* Helper function used to recursively sort and merge sublists. */
template<typename LinkageType, typename ValueType>
void LinkedList<LinkageType, ValueType>::mergesort(std::unique_ptr<node_type>& left_owner, size_type size)
{
    if (size <= 1)  // already sorted
        return;

    size_type split = size / 2;
    mergesort(left_owner, split);                // sort left half
    auto node = left_owner.get();
    for (size_type i = 0; i < split - 1; ++i) {   // split the list
        node = node->next.get();
    }
    auto& right_owner = node->next;
    mergesort(right_owner, size - split);        // sort right half
    merge(left_owner, right_owner.get(), size - split);  // merge the two halves
}

/* Helper function that returns a pointer to the first node with the value specified. */
template<typename LinkageType, typename ValueType>
typename LinkedList<LinkageType, ValueType>::node_type* LinkedList<LinkageType, ValueType>::search_front(const value_type& val) const noexcept
{
    auto node = head.get();
    while (node) {
        if (node->data == val) {
            return node;
        }
        node = node->next.get();
    }

    return nullptr;
}


template<typename LinkageType, typename ValueType>
template<typename InputIterator>
void LinkedList<LinkageType, ValueType>::construct_from_iterator_range(InputIterator begin, InputIterator end)
{
    while (begin != end) {
        push_back(*begin++);
    }
    srtd = std::is_sorted(begin, end);
}

/* Public function that inserts a value in-place before a node in the list. */
template<typename LinkageType, typename ValueType>
template<typename... Args>
typename LinkedList<LinkageType, ValueType>::node_iterator& LinkedList<LinkageType, ValueType>::emplace_before(node_iterator& iter, Args&&... args)
{
    if (empty()) {
        emplace_empty(std::forward<Args>(args)...);
        iter.node = head.get();
    } else {
        auto new_node = std::make_unique<node_type>(std::forward<Args>(args)...);
        iter.node = insert_node_before(iter.node, new_node, iter.is_reverse());
    }

    return iter;
}

/* Public function that inserts a value in-place after a node in the list. */
template<typename LinkageType, typename ValueType>
template<typename... Args>
typename LinkedList<LinkageType, ValueType>::node_iterator& LinkedList<LinkageType, ValueType>::emplace_after(node_iterator& iter, Args&&... args)
{
    if (empty()) {
        emplace_empty(std::forward<Args>(args)...);
        iter.node = head.get();
    } else {
        auto new_node = std::make_unique<node_type>(std::forward<Args>(args)...);
        iter.node = insert_node_after(iter.node, new_node, iter.is_reverse());
    }

    return iter;
}

/* Public function that inserts a value in-place into its correct position in a sorted list. */
template<typename LinkageType, typename ValueType>
template<typename... Args>
void LinkedList<LinkageType, ValueType>::emplace_sorted(Args&&... args)
{
    if (empty()) {
        emplace_empty(std::forward<Args>(args)...);
        return;
    }

    sort();    // won't sort if already sorted
    auto new_node = std::make_unique<node_type>(std::forward<Args>(args)...);
    auto position = find_sorted_position(new_node->data);
    position ? insert_node_before(position, new_node, false) : insert_node_after(tail, new_node, false);
    srtd = true;
}

/* Public function that attempts to find a value within the list. */
template<typename LinkageType, typename ValueType>
typename LinkedList<LinkageType, ValueType>::iterator LinkedList<LinkageType, ValueType>::find(const value_type &val) const noexcept
{
    auto node = head.get();
    while (node) {
        if (node->data == val) {
            break;
        }
        node = node->next.get();
    }

    return iterator{node};
};

/* Public function that counts the occurrences of a value in the list. */
template<typename LinkageType, typename ValueType>
typename LinkedList<LinkageType, ValueType>::size_type LinkedList<LinkageType, ValueType>::count(const value_type& val) const noexcept
{
    auto node = head.get();
    size_type count = 0;
    while (node) {
        if (node->data == val) {
            ++count;
        }
        node = node->next.get();
    }

    return count;
}

/* Public sort function. Calls the mergesort helper function. */
template<typename LinkageType, typename ValueType>
template<typename T, std::enable_if_t<supports_less_than<T>::value, int>>
void LinkedList<LinkageType, ValueType>::sort()
{
    if (srtd) {
        return;
    }

    mergesort(head, sz);   // sort the entire list
    srtd = true;
}

/* Public function that erases a node pointed to by an iterator. */
template<typename LinkageType, typename ValueType>
typename LinkedList<LinkageType, ValueType>::node_iterator& LinkedList<LinkageType, ValueType>::erase(node_iterator& iter)
{
    if (empty()) {
        throw std::out_of_range{"Can't delete from empty list."};
    }

    iter.node = delete_node(iter.node, iter.is_reverse());
    return iter;
}

/* Public function that clears a list. */
template<typename LinkageType, typename ValueType>
void LinkedList<LinkageType, ValueType>::clear() noexcept
{
    while (head) {
        head = std::move(head->next);
    }

    tail = nullptr;
    sz = 0;
}

}   // end namespace

#endif


SLinkedList.hpp:

#ifndef SLINKEDLIST_HPP
#define SLINKEDLIST_HPP

#include <algorithm>
#include <initializer_list>
#include <memory>
#include <stdexcept>
#include <utility>
#include "LinkedList.hpp"
#include "NodeIterator.hpp"

namespace bork_lib
{

template<typename ValueType>
class SLinkedList : public LinkedList<SingleLinkage, ValueType>
{
public:
    using value_type = typename LinkedList<SingleLinkage, ValueType>::value_type;
    using reference = typename LinkedList<SingleLinkage, value_type>::reference;
    using const_reference = typename LinkedList<SingleLinkage, value_type>::const_reference;
    using pointer = typename LinkedList<SingleLinkage, value_type>::pointer;
    using const_pointer = typename LinkedList<SingleLinkage, value_type>::const_pointer;
    using size_type = typename LinkedList<SingleLinkage, value_type>::size_type;
    using difference_type = typename LinkedList<SingleLinkage, value_type>::difference_type;
    using iterator = typename LinkedList<SingleLinkage, value_type>::iterator;
    using const_iterator = typename LinkedList<SingleLinkage, value_type>::const_iterator;
    using LinkedList<SingleLinkage, value_type>::push_back;

private:
    using node_iterator = typename LinkedList<SingleLinkage, value_type>::node_iterator;
    using node_type = typename LinkedList<SingleLinkage, value_type>::node_type;
    using LinkedList<SingleLinkage, value_type>::head;
    using LinkedList<SingleLinkage, value_type>::tail;
    using LinkedList<SingleLinkage, value_type>::srtd;
    using LinkedList<SingleLinkage, value_type>::sz;
    using LinkedList<SingleLinkage, value_type>::LinkedList;
    using LinkedList<SingleLinkage, value_type>::construct_from_iterator_range;
    using LinkedList<SingleLinkage, value_type>::swap;

    node_type* insert_node_before(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse) override;
    node_type* insert_node_after(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse) override;

    void merge(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size) override;
    template<typename T = value_type, std::enable_if_t<supports_less_than<T>::value, int> = 0>
    void merge_helper(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size);
    template<typename T = value_type, std::enable_if_t<!supports_less_than<T>::value, int> = 0>
    void merge_helper(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size) { }

    node_type* delete_node(node_type* node, bool is_reverse) override;

public:
    SLinkedList() : LinkedList<SingleLinkage, ValueType>{} { }
    SLinkedList(const SLinkedList<value_type>& other) : SLinkedList{other.cbegin(), other.cend()} { srtd = other.srtd; }
    SLinkedList(SLinkedList<value_type>&& other) noexcept : LinkedList<SingleLinkage, value_type>{std::forward<SLinkedList<value_type>>(other)} { }
    template<typename InputIterator> SLinkedList(InputIterator begin, InputIterator end) { construct_from_iterator_range(begin, end); }
    SLinkedList(std::initializer_list<value_type> li) : SLinkedList<value_type>{li.begin(), li.end()} { }
    ~SLinkedList() = default;
    SLinkedList& operator=(const SLinkedList<value_type>& other) = default;
    SLinkedList& operator=(SLinkedList<value_type>&& other) noexcept = default;

    friend class ForwardListIterator<value_type>;
    friend class ConstForwardListIterator<value_type>;
    friend class NodeIterator<node_type, value_type>;
};

/* Helper function that takes a new node and inserts it before an existing node in the list. */
template<typename ValueType>
typename SLinkedList<ValueType>::node_type* SLinkedList<ValueType>::insert_node_before(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse)
{
    if (!node) {
        throw std::invalid_argument{"Non-empty list pointer can't be null."};
    }

    using std::swap;
    swap(node->data, new_node->data);
    return insert_node_after(node, new_node, is_reverse);
}

/* Helper function that takes a new node and inserts it before an existing node in the list. */
template<typename ValueType>
typename SLinkedList<ValueType>::node_type* SLinkedList<ValueType>::insert_node_after(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse)
{
    if (!node) {
        throw std::invalid_argument{"Non-empty list pointer can't be null."};
    }

    ++sz;
    srtd = false;
    new_node->next = std::move(node->next);
    if (node == tail) {
        tail = new_node.get();
    }
    node->next = std::move(new_node);
    return node->next.get();
}

/* Mergesort function in the base class calls this function, which calls whichever merge_helper function was
   compiled using SFINAE. */
template<typename ValueType>
void SLinkedList<ValueType>::merge(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size)
{
    merge_helper(left_owner, right_raw, right_size);
}

/* Helper function that merges two sublists (mostly) in-place. Does make a few moves because of the lack of prev pointers
   in a singly-linked list. */
template<typename ValueType>
template<typename T, std::enable_if_t<supports_less_than<T>::value, int>>
void SLinkedList<ValueType>::merge_helper(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size)
{
    auto left_raw = left_owner.get();
    using std::swap;
    /* Explanation of the following while loop conditions:
       1. right_size keeps track of the number of unmerged nodes in the right sublist. When right_size == 0,
          the last node to be merged was in the right sublist and the sublists have been merged.
       2. If left_raw == right_raw, then all the nodes in the left sublist have been merged. Since the right sublist
          is already sorted, the merging is now complete. */
    while(right_size && left_raw != right_raw)
    {
        /* When the next node to be merged is from the left sublist, simply move the left_raw pointer
        to the next node. */
        if (left_raw->data <= right_raw->data) {
            left_raw = left_raw->next.get();
        }
        /* When the next node to be merged is from the right sublist, put that node in front of the
        node pointed to by left_raw. */
        else if (right_size == 1) {  // only one element in right partition left; requires sequence of swaps
            --right_size;
            while (left_raw != right_raw) {
                swap(left_raw->data, right_raw->data);
                left_raw = left_raw->next.get();
            }
        } else {
            --right_size;
            swap(left_raw->data, right_raw->data); // put the value from the right sublist in the correct place
            swap(right_raw->data, right_raw->next->data);  // move the next value in the right sublist ahead
            auto current = std::move(right_raw->next);   // put the value that was moved back where it should be
            right_raw->next = std::move(current->next);
            current->next = std::move(left_raw->next);
            left_raw->next = std::move(current);
            left_raw = left_raw->next.get();
        }
    }
}

/* Helper function that removes a node from the list. */
template<typename ValueType>
typename SLinkedList<ValueType>::node_type* SLinkedList<ValueType>::delete_node(node_type* node, bool is_reverse)
{
    if (!node) {
        throw std::invalid_argument{"Can't delete null pointer."};
    }

    node_type* return_node = nullptr;
    if (sz == 1) {
        head.release();
        tail = nullptr;
    } else if (node == head.get()) {
        head = std::move(node->next);
        return_node = head.get();
    } else if (node == tail) {    // linear time operation
        auto search = head.get();
        while (search->next.get() != tail) {
            search = search->next.get();
        }
        tail = search;
        search->next.release();
    } else {
        node->data = std::move(node->next->data);
        node->next = std::move(node->next->next);
        return_node = node;
    }

    --sz;
    return return_node;
}

}  // end namespace

#endif


DLinkedList.hpp:

#ifndef DLINKEDLIST_HPP
#define DLINKEDLIST_HPP

#include <algorithm>
#include <initializer_list>
#include <memory>
#include <stdexcept>
#include <utility>
#include "LinkedList.hpp"
#include "NodeIterator.hpp"

namespace bork_lib
{

template<typename ValueType>
class DLinkedList : public LinkedList<DoubleLinkage, ValueType>
{
public:
    using value_type = typename LinkedList<DoubleLinkage, ValueType>::value_type;
    using reference = typename LinkedList<DoubleLinkage, value_type>::reference;
    using const_reference = typename LinkedList<DoubleLinkage, value_type>::const_reference;
    using pointer = typename LinkedList<DoubleLinkage, value_type>::pointer;
    using const_pointer = typename LinkedList<DoubleLinkage, value_type>::const_pointer;
    using size_type = typename LinkedList<DoubleLinkage, value_type>::size_type;
    using difference_type = typename LinkedList<DoubleLinkage, value_type>::difference_type;
    using iterator = typename LinkedList<DoubleLinkage, value_type>::iterator;
    using const_iterator = typename LinkedList<DoubleLinkage, value_type>::const_iterator;
    using reverse_iterator = ReverseListIterator<value_type>;
    using const_reverse_iterator = ConstReverseListIterator<value_type>;
    using LinkedList<DoubleLinkage, value_type>::push_back;

private:
    using node_iterator = typename LinkedList<DoubleLinkage, value_type>::node_iterator;
    using node_type = typename LinkedList<DoubleLinkage, value_type>::node_type;
    using LinkedList<DoubleLinkage, value_type>::head;
    using LinkedList<DoubleLinkage, value_type>::tail;
    using LinkedList<DoubleLinkage, value_type>::srtd;
    using LinkedList<DoubleLinkage, value_type>::sz;
    using LinkedList<DoubleLinkage, value_type>::LinkedList;
    using LinkedList<DoubleLinkage, value_type>::construct_from_iterator_range;

    node_type* insert_node_before(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse) override;
    node_type* insert_node_after(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse) override;

    void merge(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size) override;
    template<typename T = value_type, std::enable_if_t<supports_less_than<T>::value, int> = 0>
    void merge_helper(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size);
    template<typename T = value_type, std::enable_if_t<!supports_less_than<T>::value, int> = 0>
    void merge_helper(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size) { }

    node_type* delete_node(node_type* node, bool is_reverse) override;

public:
    DLinkedList() : LinkedList<DoubleLinkage, value_type>{} { }
    DLinkedList(const DLinkedList<value_type>& other) : DLinkedList{other.cbegin(), other.cend()} { srtd = other.srtd; }
    DLinkedList(DLinkedList<value_type>&& other) noexcept : LinkedList<DoubleLinkage, value_type>{std::forward<DLinkedList<value_type>>(other)} { }
    template<typename InputIterator> DLinkedList(InputIterator begin, InputIterator end) { construct_from_iterator_range(begin, end); }
    DLinkedList(std::initializer_list<value_type> li) : DLinkedList<value_type>{li.begin(), li.end()} { }
    ~DLinkedList() = default;
    DLinkedList& operator=(const DLinkedList<value_type>& other) = default;
    DLinkedList& operator=(DLinkedList<value_type>&& other) noexcept = default;

    reverse_iterator rbegin() noexcept { return reverse_iterator{tail}; }
    const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{tail}; };
    reverse_iterator rend() noexcept { return reverse_iterator{nullptr}; }
    const_reverse_iterator rend() const noexcept { return const_reverse_iterator{nullptr}; };
    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{tail}; }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator{nullptr}; }

    friend class ListIterator<value_type>;
    friend class ConstListIterator<value_type>;
    friend class ReverseListIterator<value_type>;
    friend class ConstReverseListIterator<value_type>;
    friend class NodeIterator<node_type, value_type>;
};

/* Helper function that takes a new node and inserts it before an existing node in the list. */
template<typename ValueType>
typename DLinkedList<ValueType>::node_type* DLinkedList<ValueType>::insert_node_before(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse)
{
    if (!node) {
        throw std::invalid_argument{"Non-empty list pointer can't be null."};
    }

    if (is_reverse) {
        return insert_node_after(node, new_node, false)->prev;
    }

    ++sz;
    srtd = false;
    new_node->prev = node->prev;
    node->prev = new_node.get();
    if (node == head.get()) {    // insert at front of list
        new_node->next = std::move(head);
        head = std::move(new_node);
    } else {
        new_node->next = std::move(new_node->prev->next);
        new_node->prev->next = std::move(new_node);
    }

    return node;
}

/* Helper function that takes a new node and inserts it after an existing node in the list. */
template<typename ValueType>
typename DLinkedList<ValueType>::node_type* DLinkedList<ValueType>::insert_node_after(node_type *node, std::unique_ptr<node_type> &new_node, bool is_reverse)
{
    if (!node) {
        throw std::invalid_argument{"Non-empty list pointer can't be null."};
    }

    if (is_reverse) {
        return insert_node_before(node, new_node, false)->prev;
    }

    ++sz;
    srtd = false;
    new_node->next = std::move(node->next);
    new_node->prev = node;
    if (node == tail) {   // insert at back of list
        tail = new_node.get();
    } else {
        new_node->next->prev = new_node.get();
    }
    node->next = std::move(new_node);
    return node->next.get();
}

/* Mergesort function in the base class calls this function, which calls whichever merge_helper function was
   compiled using SFINAE. */
template<typename ValueType>
void DLinkedList<ValueType>::merge(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size)
{
    merge_helper(left_owner, right_raw, right_size);
}

/* Helper function that merges two sublists completely in-place. */
template<typename ValueType>
template<typename T, std::enable_if_t<supports_less_than<T>::value, int>>
void DLinkedList<ValueType>::merge_helper(std::unique_ptr<node_type>& left_owner, node_type* right_raw, size_type right_size)
{
    auto left_raw = left_owner.get();

    /* Explanation of the following while loop conditions:
       1. right_size keeps track of the number of unmerged nodes in the right sublist. When right_size == 0,
          the last node to be merged was in the right sublist and the sublists have been merged.
       2. If left_raw == right_raw, then all the nodes in the left sublist have been merged. Since the right sublist
          is already sorted, the merging is now complete. */
    while(right_size && left_raw != right_raw)
    {
        /* When the next node to be merged is from the left sublist, simply move the left_raw pointer
        to the next node. */
        if (left_raw->data <= right_raw->data) {
            left_raw = left_raw->next.get();
        }
        /* When the next node to be merged is from the right sublist, put that node in front of the
        node pointed to by left_raw. */
        else {
            --right_size;
            auto current = std::move(right_raw->prev->next);          // the node currently being moved
            right_raw = right_raw->next.get();      // point to the next node to be merged

            // remove the node
            if (current->next) {
                current->next->prev = current->prev;
            } else {    // last node in list
                tail = current->prev;
            }
            current->prev->next = std::move(current->next);

            // insert the node
            current->prev = left_raw->prev;
            if (left_raw == left_owner.get()) {   // move in front of first node in left sublist
                current->next = std::move(left_owner);
                left_owner = std::move(current);
                left_raw->prev = left_owner.get();
            } else if (left_raw->prev) {
                current->next = std::move(left_raw->prev->next);
                left_raw->prev->next = std::move(current);
                left_raw->prev = left_raw->prev->next.get();
            }
        }
    }
}

/* Helper function that removes a node from the list. */
template<typename ValueType>
typename DLinkedList<ValueType>::node_type* DLinkedList<ValueType>::delete_node(node_type* node, bool is_reverse)
{
    if (!node) {
        throw std::invalid_argument{"Can't delete null pointer."};
    }

    auto return_node = is_reverse ? node->prev : node->next.get();
    if (sz == 1) {
        head.release();
        tail = nullptr;
    } else if (node == head.get()) {
        head = std::move(node->next);
    } else if (node == tail) {
        tail = node->prev;
        node->prev->next.release();
    } else {
        node->next->prev = node->prev;
        node->prev->next = std::move(node->next);
    }

    --sz;
    return return_node;
}

}  // end namespace

#endif


NodeIterator.hpp:

#ifndef NODEITERATOR_HPP
#define NODEITERATOR_HPP

#include <stdexcept>
#include <utility>

namespace bork_lib
{

class SingleLinkage;
class DoubleLinkage;
template<typename L, typename V> class LinkedList;
template<typename V> class DLinkedList;
template<typename V> class SLinkedList;

template<typename NodeType, typename ValueType>
class NodeIterator
{
protected:
    NodeType* node;
    virtual bool is_reverse() = 0;

public:
    using value_type = ValueType;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    explicit NodeIterator(NodeType* node = nullptr) : node{node} {}
    NodeIterator(const NodeIterator<NodeType, value_type>& other) : node(other.node) {}
    NodeIterator<NodeType, value_type>& operator=(const NodeIterator<NodeType, value_type>& other)
    {
        node = other.node;
        return *this;
    }
    virtual NodeIterator<NodeType, value_type>& operator++() = 0;
    virtual NodeIterator<NodeType, value_type>& operator--() = 0;
    reference operator*() { return node->data; }
    pointer operator->() { return &(node->data); }
    bool operator==(const NodeIterator<NodeType, value_type>& other) const noexcept
    {
        return node == other.node;
    }

    bool operator!=(const NodeIterator<NodeType, value_type>& other) const noexcept
    {
        return !operator==(other);
    }
    virtual ~NodeIterator() = default;

    template<typename L, typename V> friend class LinkedList;
    friend class DLinkedList<value_type>;
    friend class SLinkedList<value_type>;
};

template<typename NodeType, typename ValueType>
class ConstNodeIterator
{
protected:
    NodeType* node;
    virtual bool is_reverse() = 0;

public:
    using value_type = ValueType;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    explicit ConstNodeIterator(NodeType* node = nullptr) : node{node} {}
    ConstNodeIterator(const ConstNodeIterator<NodeType, value_type>& other) : node(other.node) {}
    ConstNodeIterator<NodeType, value_type>& operator=(const ConstNodeIterator<NodeType, value_type>& other)
    {
        node = other.node;
        return *this;
    }
    virtual ConstNodeIterator<NodeType, value_type>& operator++() = 0;
    virtual ConstNodeIterator<NodeType, value_type>& operator--() = 0;
    const_reference operator*() { return node->data; }
    const_pointer operator->() { return &(node->data); }
    bool operator==(const ConstNodeIterator<NodeType, value_type>& other) const noexcept
    {
        return node == other.node;
    }
    bool operator!=(const ConstNodeIterator<NodeType, value_type>& other) const noexcept
    {
        return !operator==(other);
    }
    virtual ~ConstNodeIterator() = default;

    template<typename L, typename V> friend class LinkedList;
    template<typename V> friend class DLinkedList;
    template<typename V> friend class SLinkedList;
};

template<typename ValueType>
class ListIterator : public NodeIterator<typename LinkedList<DoubleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return false; }
    using node_type = typename LinkedList<DoubleLinkage, ValueType>::node_type;
    using NodeIterator<node_type, ValueType>::NodeIterator;
    using NodeIterator<node_type, ValueType>::node;
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = typename NodeIterator<node_type, ValueType>::value_type;
    using reference = typename NodeIterator<node_type, value_type>::reference;
    using const_reference = typename NodeIterator<node_type, value_type>::const_reference;
    using pointer = typename NodeIterator<node_type, value_type>::pointer;
    using const_pointer = typename NodeIterator<node_type, value_type>::const_pointer;
    using size_type = typename NodeIterator<node_type, value_type>::size_type;
    using difference_type = typename NodeIterator<node_type, value_type>::difference_type;

    ListIterator<value_type>& operator=(const NodeIterator<node_type, value_type>& other)
    {
        return *this = dynamic_cast<ListIterator<value_type>&>(NodeIterator<node_type, value_type>::operator=(other));
    }
    ListIterator<value_type>& operator++() override { node = node->next.get(); return *this; }
    ListIterator<value_type>& operator--() override { node = node->prev; return *this; }
    ListIterator<value_type> operator++(int)
    {
        ListIterator<value_type> temp{*this};
        operator++();
        return temp;
    }
    ListIterator<value_type> operator--(int)
    {
        ListIterator<value_type> temp{*this};
        operator--();
        return temp;
    }
    friend class DLinkedList<value_type>;
};

template<typename ValueType>
class ConstListIterator : public ConstNodeIterator<typename LinkedList<DoubleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return false; }
    using node_type = typename LinkedList<DoubleLinkage, ValueType>::node_type;
    using ConstNodeIterator<node_type, ValueType>::ConstNodeIterator;
    using ConstNodeIterator<node_type, ValueType>::node;
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = typename ConstNodeIterator<node_type, ValueType>::value_type;
    using reference = typename ConstNodeIterator<node_type, value_type>::reference;
    using const_reference = typename ConstNodeIterator<node_type, value_type>::const_reference;
    using pointer = typename ConstNodeIterator<node_type, value_type>::pointer;
    using const_pointer = typename ConstNodeIterator<node_type, value_type>::const_pointer;
    using size_type = typename ConstNodeIterator<node_type, value_type>::size_type;
    using difference_type = typename ConstNodeIterator<node_type, value_type>::difference_type;

    ConstListIterator<value_type>& operator=(const ConstNodeIterator<node_type, value_type>& other)
    {
        return *this = dynamic_cast<ConstListIterator<value_type>&>(ConstNodeIterator<node_type, value_type>::operator=(other));
    }
    ConstListIterator<value_type>& operator++() override { node = node->next.get(); return *this; }
    ConstListIterator<value_type>& operator--() override { node = node->prev; return *this; }
    ConstListIterator<value_type> operator++(int)
    {
        ConstListIterator<value_type> temp{*this};
        operator++();
        return temp;
    }
    ConstListIterator<value_type> operator--(int)
    {
        ConstListIterator<value_type> temp{*this};
        operator--();
        return temp;
    }
    friend class DLinkedList<value_type>;
};

template<typename ValueType>
class ReverseListIterator : public NodeIterator<typename LinkedList<DoubleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return true; }
    using node_type = typename LinkedList<DoubleLinkage, ValueType>::node_type;
    using NodeIterator<node_type, ValueType>::NodeIterator;
    using NodeIterator<node_type, ValueType>::node;
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = typename NodeIterator<node_type, ValueType>::value_type;
    using reference = typename NodeIterator<node_type, value_type>::reference;
    using const_reference = typename NodeIterator<node_type, value_type>::const_reference;
    using pointer = typename NodeIterator<node_type, value_type>::pointer;
    using const_pointer = typename NodeIterator<node_type, value_type>::const_pointer;
    using size_type = typename NodeIterator<node_type, value_type>::size_type;
    using difference_type = typename NodeIterator<node_type, value_type>::difference_type;

    ReverseListIterator<value_type>& operator=(const NodeIterator<node_type, value_type>& other)
    {
        return *this = dynamic_cast<ReverseListIterator<value_type>&>(NodeIterator<node_type, value_type>::operator=(other));
    }
    ReverseListIterator<value_type>& operator++() override { node = node->prev; return *this; }
    ReverseListIterator<value_type>& operator--() override { node = node->next.get(); return *this; }
    ReverseListIterator<value_type> operator++(int)
    {
        ReverseListIterator<value_type> temp{*this};
        operator++();
        return temp;
    }
    ReverseListIterator<value_type> operator--(int)
    {
        ReverseListIterator<value_type> temp{*this};
        operator--();
        return temp;
    }
    friend class DLinkedList<value_type>;
};

template<typename ValueType>
class ConstReverseListIterator : public ConstNodeIterator<typename LinkedList<DoubleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return true; }
    using node_type = typename LinkedList<DoubleLinkage, ValueType>::node_type;
    using ConstNodeIterator<node_type, ValueType>::ConstNodeIterator;
    using ConstNodeIterator<node_type, ValueType>::node;
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = typename ConstNodeIterator<node_type, ValueType>::value_type;
    using reference = typename ConstNodeIterator<node_type, value_type>::reference;
    using const_reference = typename ConstNodeIterator<node_type, value_type>::const_reference;
    using pointer = typename ConstNodeIterator<node_type, value_type>::pointer;
    using const_pointer = typename ConstNodeIterator<node_type, value_type>::const_pointer;
    using size_type = typename ConstNodeIterator<node_type, value_type>::size_type;
    using difference_type = typename ConstNodeIterator<node_type, value_type>::difference_type;

    ConstReverseListIterator<value_type>& operator=(const ConstNodeIterator<node_type, value_type>& other)
    {
        return *this = dynamic_cast<ConstReverseListIterator<value_type>&>(ConstNodeIterator<node_type, value_type>::operator=(other));
    }
    ConstReverseListIterator<value_type>& operator++() override { node = node->prev; return *this; }
    ConstReverseListIterator<value_type>& operator--() override { node = node->next.get(); return *this; }
    ConstReverseListIterator<value_type> operator++(int)
    {
        ConstReverseListIterator<value_type> temp{*this};
        operator++();
        return temp;
    }
    ConstReverseListIterator<value_type> operator--(int)
    {
        ConstReverseListIterator<value_type> temp{*this};
        operator--();
        return temp;
    }
    friend class DLinkedList<value_type>;
};

template<typename ValueType>
class ForwardListIterator : public NodeIterator<typename LinkedList<SingleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return false; }
    using node_type = typename LinkedList<SingleLinkage, ValueType>::node_type;
    using NodeIterator<node_type, ValueType>::NodeIterator;
    using NodeIterator<node_type, ValueType>::node;
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = typename NodeIterator<node_type, ValueType>::value_type;
    using reference = typename NodeIterator<node_type, value_type>::reference;
    using const_reference = typename NodeIterator<node_type, value_type>::const_reference;
    using pointer = typename NodeIterator<node_type, value_type>::pointer;
    using const_pointer = typename NodeIterator<node_type, value_type>::const_pointer;
    using size_type = typename NodeIterator<node_type, value_type>::size_type;
    using difference_type = typename NodeIterator<node_type, value_type>::difference_type;

    ForwardListIterator<value_type>& operator=(const NodeIterator<node_type, value_type>& other)
    {
        return *this = dynamic_cast<ForwardListIterator<value_type>&>(NodeIterator<node_type, value_type>::operator=(other));
    }
    ForwardListIterator<value_type>& operator++() override { node = node->next.get(); return *this; }
    ForwardListIterator<value_type>& operator--() override { throw std::logic_error("Cannot decrement forward iterator."); }
    ForwardListIterator<value_type> operator++(int)
    { 
        ForwardListIterator<value_type> temp{*this};
        operator++();
        return temp;
    }
    ForwardListIterator<value_type> operator--(int) { throw std::logic_error("Cannot decrement forward iterator."); }
    friend class SLinkedList<value_type>;
};

template<typename ValueType>
class ConstForwardListIterator : public ConstNodeIterator<typename LinkedList<SingleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return false; }
    using node_type = typename LinkedList<SingleLinkage, ValueType>::node_type;
    using ConstNodeIterator<node_type, ValueType>::ConstNodeIterator;
    using ConstNodeIterator<node_type, ValueType>::node;
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = typename ConstNodeIterator<node_type, ValueType>::value_type;
    using reference = typename ConstNodeIterator<node_type, value_type>::reference;
    using const_reference = typename ConstNodeIterator<node_type, value_type>::const_reference;
    using pointer = typename ConstNodeIterator<node_type, value_type>::pointer;
    using const_pointer = typename ConstNodeIterator<node_type, value_type>::const_pointer;
    using size_type = typename ConstNodeIterator<node_type, value_type>::size_type;
    using difference_type = typename ConstNodeIterator<node_type, value_type>::difference_type;

    ConstForwardListIterator<value_type>& operator=(const ConstNodeIterator<node_type, value_type>& other)
    {
        return *this = dynamic_cast<ConstForwardListIterator<value_type>&>(ConstNodeIterator<node_type, value_type>::operator=(other));
    }
    ConstForwardListIterator<value_type>& operator++() override { node = node->next.get(); return *this; }
    ConstForwardListIterator<value_type>& operator--() override { throw std::logic_error("Cannot decrement forward iterator."); }
    ConstForwardListIterator<value_type> operator++(int)
    {
        ConstForwardListIterator<value_type> temp{*this};
        operator++();
        return temp;
    }
    ConstForwardListIterator<value_type> operator--(int) { throw std::logic_error("Cannot decrement forward iterator."); }
    friend class SLinkedList<value_type>;
};

}  // end namespace

#endif


For testing I used the Catch2 framework. However, attempting to post the code for my tests causes me to exceed the 65535 character limit. You can access my test code using the following links:

\$\endgroup\$
3
+50
\$\begingroup\$
template<typename, typename = void>
struct supports_less_than : std::false_type { };

template<typename T>
struct supports_less_than<T, std::void_t<decltype(std::declval<T&>() <= std::declval<T&>())>> : std::true_type { };

First, you're being a little bit more verbose than you need to. (Particularly std::void_t<decltype(...)> is a code smell IMO.) Second, has_less_than is a terrible name for a trait that detects whether the type supports the <= operator! Was this a typo? I'm going to assume it was.

template<class, class=void> struct has_less_than : std::false_type {};

template<class T> struct has_less_than<T, decltype(void(
    std::declval<T>() < std::declval<T>()
))> : std::true_type {};

template<typename LinkageType, typename ValueType>
class LinkedList {
protected:
    template<typename ShadowedLinkageType, typename = void> struct ListNode;

You probably knew, as you were writing "ShadowedLinkageType", that it felt wrong. Follow that feeling. Since ShadowedLinkageType is always equal to LinkageType, why does it need to be a parameter at all? Here's how I'd write it:

template<class LinkageType, class T>
class LinkedList {
protected:
    struct ListNode;
    // ...
};

template<class T>
struct LinkedList<SingleLinkage, T>::ListNode {
    T data;
    std::unique_ptr<ListNode> next = nullptr;

    // ...
};

template<class T>
struct LinkedList<DoubleLinkage, T>::ListNode {
    T data;
    std::unique_ptr<ListNode> next = nullptr;
    ListNode *prev = nullptr;

    // ...
};

EDITED TO ADD: If the above doesn't work (as indicated in the comments), then I'd try

template<class LinkageType, class T>
struct LinkedListNode;

template<class LinkageType, class T>
class LinkedList {
protected:
    using ListNode = LinkedListNode<LinkageType, T>;
    // ...
};

template<class T>
struct LinkedListNode<SingleLinkage, T> {
    T data;
    std::unique_ptr<LinkedListNode> next = nullptr;

    // ...
};

template<class T>
struct LinkedListNode<DoubleLinkage, T> {
    T data;
    std::unique_ptr<LinkedListNode> next = nullptr;
    LinkedListNode *prev = nullptr;

    // ...
};

which would certainly work (and be simpler, into the bargain).


Here is a super duper common newbie mistake (i.e. you are in good company):

explicit ListNode(const ValueType& data) : data{data} { }
explicit ListNode(ValueType&& data) : data{std::forward<ValueType>(data)} { }

Use std::forward for forwarding references; use std::move for rvalue references. You can tell the difference between a forwarding reference T&& and an rvalue reference T&& by looking to see whether the T is deduced or not. In this case, it's not deduced — it's pinned to be exactly ValueType — and therefore what we have is a plain old rvalue reference, and therefore you should be using std::move.

(Now, to be fair, the difference in this case is noticeable only when ValueType itself is a reference type, in which case I'm sure you have bigger problems. But it's important to build your muscle memory for good habits like "forward forwarding references and move rvalues," so that you can spend your actual brain cells on less trivial stuff.)


template<typename ValueType>
class ListIterator : public NodeIterator<typename LinkedList<DoubleLinkage, ValueType>::node_type, ValueType>
{
    bool is_reverse() override { return false; }

I believe Frank's answer touched on this point already: mixing OOP polymorphism with value semantics is generally a bad idea. And in this case, you've not only got inheritance, you've got public inheritance! Which means I can take a ListIterator and slice it:

auto it = foo.rbegin();
assert(it->is_reverse());

NodeIterator& it2 = it;
assert(it2->is_reverse());

NodeIterator it3 = it;
assert(not it3->is_reverse());

Class template argument deduction (CTAD) makes this particularly easy in C++17; but in C++14 just imagine that I wasn't so lazy and figured out what template parameters to use on NodeIterator, there.

You should eliminate the virtual bool is_reverse; it's not serving any purpose here. Make IsReverse a template parameter of the iterator type.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the review! Can you please elaborate on this: "mixing OOP polymorphism with value semantics is generally a bad idea." Does adding the IsReverse template parameter fix the "bad idea" you are referring to in that statement, or are you referring to a larger problem? \$\endgroup\$ – Mike Borkland Sep 10 '18 at 13:52
  • 1
    \$\begingroup\$ @MikeBorkland: I mean that in general, if your type has a copy constructor or assignment operator, it should not have any virtuals or inheritance relationships — and vice versa, if it is part of an inheritance hierarchy, it should generally not have any special member functions. (There may be rare exceptions, but this is generally how it works.) Eliminating virtual bool is_reverse() is part of the solution in your case, but is not the whole solution. \$\endgroup\$ – Quuxplusone Sep 11 '18 at 3:24
  • \$\begingroup\$ I liked your suggestion for resolving the ShadowedLinkageType hack. I never liked that, but I could not get it to work otherwise. Your suggestion certainly seemed like it should work, but I don't think it is possible to do it without fully specializing the outer class. Perhaps I'm missing something. See this question: stackoverflow.com/questions/33099306/… \$\endgroup\$ – Mike Borkland Sep 11 '18 at 21:10
  • 1
    \$\begingroup\$ You might be right. In that case, we increase the scope of the refactoring and make LinkedListNode into a first-class class. See "EDITED TO ADD", above. \$\endgroup\$ – Quuxplusone Sep 12 '18 at 16:16
5
\$\begingroup\$

This is indeed fairly large and will take a while to review.

Just glancing through it, two big things jumped at me immediatelly, so I'll jot them down right away, and update this answer as I make myu way further down the code.

Don't use tag types for bounded lists.

Tag types are convenient when you have have an unbounded number of alternatives. For bounded sets, you are better off with an enum:

class SingleLinkage {};
class DoubleLinkage {};

template<typename LinkageType, typename ValueType>
class LinkedList {...};

becomes:

enum class Linkage {
  single,
  double
};

template<Linkage LinkageType, typename ValueType>
class LinkedList {...};

Don't use SFINAE to validate,

SFINAE is a selection tool, not a validation tool. There are ALWAYS better ways to perform validation.

template<typename, typename = void>
struct supports_less_than : std::false_type { };

template<typename T>
struct supports_less_than<T, std::void_t<decltype(std::declval<T&>() <= std::declval<T&>())>> : std::true_type { };
template<typename T = value_type, std::enable_if_t<supports_less_than<T>::value, int> = 0>
    void sort();
template<typename T = value_type, std::enable_if_t<!supports_less_than<T>::value, int> = 0>
    void sort() { throw std::logic_error("List cannot be sorted, as value_type does not support comparison."); }

You want code that invokes sort() with supports_less_than<T>::value == false to not even compile at all, not throw an error at run time.

Normally, I would just duck-type that operator<(T,T) works fine, but there is an argument to be made that a more explicit error is desirable. I would just do this:

void sort() {
  static_assert(supports_less_than<value_type>::value);

  .. run sort...
}
\$\endgroup\$
  • \$\begingroup\$ Yeah, I don't really like what I did for the sort function either. The problem I was having though is that even a single statement like DLinkedList<UnsortableType> dlist; would not compile because of the <= used by the merge. Would the use of static_assert fix that? \$\endgroup\$ – Mike Borkland Sep 6 '18 at 11:59
  • 1
    \$\begingroup\$ Mixing type erasure and conditional features is generally a bad idea. Of two things one: Either your class only works with sortable (in which case the static_assert<> can just go in the LinkedList<> declaration). Or sorted operations are not part of the fundamental type, but external free-floating functions that are implemented in a way that uses virtualized insert() and delete() operations. \$\endgroup\$ – Frank Sep 6 '18 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.