现代C++链表

Question

我一直在利用这个隔离时间学习“现代C++”(构造、移动语义、智能指针等)，方法是从零开始实现基本的数据结构。作为第一步，我把一个简单的(但希望有点完整)链接列表作为基本部分之一。

linked_list.h

#pragma once

#include <utility>

namespace data_structures
{
    template<typename  T>
    class linked_list
    {
        template<typename T>
        struct list_node
        {
            friend linked_list;

            typedef list_node<T> self_type;
            typedef list_node<T>& reference;
            typedef const list_node<T>& const_reference;
            typedef list_node<T>* pointer;

            explicit list_node( const T& val )
                : data{ std::move( val ) }
            { }

            explicit list_node( const T&& val )
                : data{ std::move( val ) }
            { }

            T data;

        private:
            pointer next_ = nullptr, prev_ = nullptr;
        };

        class iterator
        {
        public:

            using node = list_node<T>;

            typedef iterator self_type;

            typedef node& reference;
            typedef node* pointer;

            explicit iterator( pointer node ) :
                ptr_( node )
            { }

            self_type operator++()
            {
                if( ptr_ )
                    ptr_ = ptr_->next_;

                return *this;
            }

            reference operator*() { return *ptr_; }
            pointer operator->() { return ptr_; }

            bool operator==( const self_type& other ) { return ptr_ == other.ptr_; }
            bool operator!=( const self_type& other ) { return ptr_ != other.ptr_; }

        private:
            pointer ptr_;
        };

        typedef linked_list<T> self_type;
        typedef linked_list<T>& reference;
        typedef const linked_list<T>& const_reference;
        typedef linked_list<T>* pointer;

        typedef size_t size_type;

        typedef list_node<T> node_type;

        using node = typename node_type::pointer;
        using node_reference = typename node_type::reference;
        using const_node_reference = typename node_type::const_reference;
        using node_pointer = std::unique_ptr<node_type>;

        node_pointer head_, tail_;
        size_t length_{};

    public:

        linked_list();

        explicit linked_list( std::initializer_list<T> init_list );
        linked_list( const self_type& other );
        linked_list( self_type&& other ) noexcept;

        ~linked_list();

        void swap( reference other ) noexcept;

        void push_back( T item ) { insert( length_, item ); }
        void push_front( T item ) { insert( 0, item ); }
        void append( const_reference other );

        T pop_front();
        T pop_back();

        const_node_reference at( size_type position );

        void remove( T value );
        void remove_at( size_type position );

        iterator begin() { return iterator( head_->next_ ); }
        iterator end() { return iterator( tail_.get() ); }

        [[nodiscard]] const_node_reference front() const { return *head_->next_; }
        [[nodiscard]] const_node_reference back() const { return *tail_->prev_; }

        [[nodiscard]] bool empty() const { return head_->next == tail_.get(); }
        [[nodiscard]] size_type size() const { return length_; }

        reference operator=( const self_type& other ); // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
        reference operator=( self_type&& other ) noexcept;  // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
        reference operator+( const self_type& other ) { append( other ); return *this; }

        void operator+=( const self_type& other ) { append( other ); }
        void operator+=( const T& value ) { push_back( value ); }

    protected:
        void insert( size_type position, T value );
        node get( size_type position );
    };

    template <typename T>
    linked_list<T>::linked_list()
    {
        head_ = std::make_unique<node_type>( T() );
        tail_ = std::make_unique<node_type>( T() );

        head_->next_ = tail_.get();
        head_->prev_ = tail_.get();

        tail_->next_ = head_.get();
        tail_->prev_ = head_.get();
    }

    template <typename T>
    linked_list<T>::linked_list( const std::initializer_list<T> init_list ) :
        linked_list()
    {
        for( auto& item : init_list )
        {
            push_back( item );
        }
    }

    template <typename T>
    linked_list<T>::linked_list( const self_type& other )
        : linked_list()
    {
        append( other );
    }

    template <typename T>
    linked_list<T>::linked_list( self_type&& other ) noexcept
        : linked_list()
    {
        swap( other );
    }

    template <typename T>
    linked_list<T>::~linked_list()
    {
        if( !head_ ) return; // destroyed from move

        for( node current = head_->next_; current != tail_.get(); )
        {
            node temp = current;

            current = current->next_;

            delete temp;
        }
    }

    template <typename T> // NOLINT(cppcoreguidelines-c-copy-assignment-signature
    typename linked_list<T>::reference linked_list<T>::operator=( const self_type& other )  // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
    {
        if( this == &other ) return *this;

        auto temp( other );

        temp.swap( *this );

        return *this;
    }

    template <typename T> // NOLINT(cppcoreguidelines-c-copy-assignment-signature
    typename linked_list<T>::reference linked_list<T>::operator=( self_type&& other ) noexcept  // NOLINT(cppcoreguidelines-c-copy-assignment-signature, misc-unconventional-assign-operator)
    {
        if( this == &other )
            return *this;

        // clean up this
        for( node current = head_->next_; current != tail_.get(); )
        {
            node temp = current;

            current = current->next_;

            delete temp;

            length_--;
        }

        // this <- other
        head_ = std::move( other.head_ );
        tail_ = std::move( other.tail_ );
        length_ = other.length_;
        other.length_ = 0;

        return *this;
    }

    template <typename T>
    void linked_list<T>::swap( reference other ) noexcept
    {
        std::swap( head_, other.head_ );
        std::swap( tail_, other.tail_ );
        std::swap( length_, other.length_ );
    }

    template <typename T>
    void linked_list<T>::append( const_reference other )
    {
        node dest = tail_->prev_;

        for( node source = other.head_->next_; 
            source != other.tail_.get();
            source = source->next_ )
        {
            node new_node{ new node_type( source->data ) };

            if( new_node == nullptr )
                throw std::bad_alloc();

            new_node->prev_ = dest;
            dest->next_ = new_node;

            dest = new_node;
            length_++;
        }

        dest->next_ = tail_.get();
        tail_->prev_ = dest;
    }

    template <typename T>
    T linked_list<T>::pop_front()
    {
        if( length_ <= 0 )
            throw std::runtime_error( "ATTEMPT_POP_EMPTY_LIST" );

        const auto value = front().data;

        remove_at( 0 );

        return value;
    }

    template <typename T>
    T linked_list<T>::pop_back()
    {
        if( length_ <= 0 )
            throw std::runtime_error( "ATTEMPT_POP_EMPTY_LIST" );

        const auto value = back().data;

        remove_at( length_ - 1 );

        return value;
    }

    template <typename T>
    typename linked_list<T>::const_node_reference linked_list<T>::at( size_type position )
    {
        if( position >= length_ )
            throw std::runtime_error( "INVALID_LIST_POSITION" );

        return *get( position );
    }

    template <typename T>
    void linked_list<T>::insert( const size_type position, T value )
    {
        if( position > length_ + 1)
            throw std::runtime_error( "INVALID_LIST_POSITION" );

        node next = get( position );

        node new_node{ new node_type( value ) };

        if( new_node == nullptr )
            throw std::bad_alloc();

        node prev = next->prev_;

        new_node->next_ = next;
        new_node->prev_ = prev;

        prev->next_ = new_node;
        next->prev_ = new_node;

        length_++;
    }

    template <typename T>
    typename linked_list<T>::node linked_list<T>::get( const size_type position )
    {
        const auto mid = ceil( length_ / 2 );

        node node;

        if( position <= mid )
        {
            node = head_->next_;

            for( size_type index = 0; index < position; index++ )
                node = node->next_;
        }
        else
        {
            node = tail_.get();

            for( size_type index = length_; index > position; index-- )
                node = node->prev_;
        }

        return node;
    }

    template <typename T>
    void linked_list<T>::remove( T value )
    {
        for( node node = head_->next_;
            node != tail_.get();
            node = node->next_ )
        {
            if( node->data == value )
            {
                node->prev_->next_ = node->next_;
                node->next_->prev_ = node->prev_;

                delete node;

                length_--;
                break;
            }
        }
    }

    template <typename T>
    void linked_list<T>::remove_at( const size_type position )
    {
        if( position >= length_ )
            throw std::runtime_error( "REMOVE_PAST_END_ATTEMPT" );

        node node = get( position );

        node->prev_->next_ = node->next_;
        node->next_->prev_ = node->prev_;

        delete node;

        length_--;
    }
}

几个注意事项：

在代码可读性和设计方面，对哨兵节点而不是实际列表内容使用智能指针似乎是最好的折衷。我对此进行了几次重构(从单独使用所有unique_ptr's，到双用unique_ptr作为头/下节点，以及对尾/prev节点的标准引用，到当前版本)。很高兴在这里听到任何建议。

这个列表本身的移动语义，我并不完全喜欢。例如，当使用std::move从现有列表初始化新列表时，旧列表将不再具有有效的哨位节点，因为它们已被新列表“回收”，因此旧的列表现在“无效”，解构函数有一个故障安全检查，如果是这样的话，不清理自己。从阅读如何实现这一点(移动‘d对象应该仍然有效的后移动，只是在’无效‘状态)，我相信我所拥有的是正确的，尽管它似乎只是次优。

我所拥有的迭代器实现不包括我所读过的const版本(或者至少我应该说)，这不再是实现迭代器的const版本& cbegin/cend的“最佳实践”，相反，使用者应该使用const正确的迭代器吗？(即，for(const auto& i : list )在C++ 17+中)。我的解释对吗？

欢迎任何其他关于改进/功能/可读性/等等的建议。

如果有人感兴趣，还有一组单元测试(GTest)。

linkedlist_test.cpp

#include "pch.h"
#include <gtest/gtest.h>

#include "../data-structures/linked_list.h"

namespace data_structure_tests::integer_linked_list_tests
{
    typedef data_structures::linked_list<int> int_list;

    /// <summary>
    /// Testing class for singly linked list.
    /// </summary>
    class linked_list_tests :
        public ::testing::Test {

    protected:
        void SetUp() override
        {
        }

        void TearDown() override
        {
        }
    };

    //
    // Linked List Tests
    //

    TEST_F( linked_list_tests, at_head )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );

        auto actual = list.at( 0 );

        EXPECT_EQ( actual.data, 1 );
    }

    TEST_F( linked_list_tests, at_tail )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );

        auto actual = list.at( 2 );

        EXPECT_EQ( actual.data, 3 );
    }

    TEST_F( linked_list_tests, get_head )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );

        auto actual = list.at( 0 );

        EXPECT_EQ( actual.data, 1 );
    }

    TEST_F( linked_list_tests, push_front_empty )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_back( 1 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );
    }

    TEST_F( linked_list_tests, push_back )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_back( 3 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 3 );

        list.push_back( 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 2 );

        list.push_back( 1 );

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 1 );
    }

    TEST_F( linked_list_tests, push_front )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_front( 3 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 3 );
        EXPECT_EQ( list.back().data, 3 );

        list.push_front( 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 3 );

        list.push_front( 1 );

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 3 );
    }

    TEST_F( linked_list_tests, init_list )
    {
        auto list = int_list{ 5, 4, 3, 2, 1 };

        EXPECT_EQ( list.size(), 5 );

        EXPECT_EQ( list.front().data, 5 );
        EXPECT_EQ( list.back().data, 1 );

        EXPECT_EQ( list.at( 4 ).data, 1 );
        EXPECT_EQ( list.at( 3 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 1 ).data, 4 );
        EXPECT_EQ( list.at( 0 ).data, 5 );
    }

    TEST_F( linked_list_tests, out_of_bounds )
    {
        auto list = int_list{ 1, 2, 3, 4 };

        try
        {
            auto no_exist = list.at( 4 );

            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "INVALID_LIST_POSITION" );
        }
    }

    TEST_F( linked_list_tests, iterator )
    {
        auto list = int_list{ 0, 1, 2, 3, 4, 5 };

        auto expected = 0;

        for( const auto& node : list )
        {
            auto actual = node.data;

            EXPECT_EQ( actual, expected );

            expected++;
        }
    }

    TEST_F( linked_list_tests, add_lists )
    {
        auto list1 = int_list{ 0, 1, 2, 3, 4 };
        const auto list2 = int_list{ 5, 6, 7, 8, 9 };

        list1 = list1 + list2;

        auto expected = 0;

        for( const auto& node : list1 )
        {
            auto actual = node.data;

            EXPECT_EQ( actual, expected );

            expected++;
        }
    }

    TEST_F( linked_list_tests, append_value )
    {
        auto list = int_list{ 0, 1, 2 };

        EXPECT_EQ( list.size(), 3 );

        list += 3;

        EXPECT_EQ( list.size(), 4 );
        EXPECT_EQ( list.back().data, 3 );

        EXPECT_EQ( list.at( 0 ).data, 0 );
        EXPECT_EQ( list.at( 1 ).data, 1 );
        EXPECT_EQ( list.at( 2 ).data, 2 );
        EXPECT_EQ( list.at( 3 ).data, 3 );
    }

    TEST_F( linked_list_tests, swap )
    {
        auto list1 = int_list{ 1, 2, 3 };
        auto list2 = int_list{ 4, 5, 6 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list2.size(), 3 );

        list1.swap( list2 );

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list2.size(), 3 );

        EXPECT_EQ( list1.at( 0 ).data, 4 );
        EXPECT_EQ( list1.at( 1 ).data, 5 );
        EXPECT_EQ( list1.at( 2 ).data, 6 );

        EXPECT_EQ( list2.at( 0 ).data, 1 );
        EXPECT_EQ( list2.at( 1 ).data, 2 );
        EXPECT_EQ( list2.at( 2 ).data, 3 );
    }

    TEST_F( linked_list_tests, copy_constructor )
    {
        auto list = int_list{ 0, 1, 2 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 0 );
        EXPECT_EQ( list.at( 1 ).data, 1 );
        EXPECT_EQ( list.at( 2 ).data, 2 );

        auto list_copy( list );

        EXPECT_EQ( list_copy.size(), 3 );
        EXPECT_EQ( list_copy.at( 0 ).data, 0 );
        EXPECT_EQ( list_copy.at( 1 ).data, 1 );
        EXPECT_EQ( list_copy.at( 2 ).data, 2 );

        list_copy.push_back( 4 );

        EXPECT_EQ( list_copy.back().data, 4 );

        EXPECT_NE( list.back().data, list_copy.back().data );
    }

    TEST_F( linked_list_tests, copy_assignment_equal )
    {
        auto list1 = int_list{ 0, 1, 2 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );

        auto list2 = int_list{ 3, 4, 5 };

        EXPECT_EQ( list2.size(), 3 );

        list2 = list1;

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );

        EXPECT_EQ( list2.size(), 3 );
        EXPECT_EQ( list2.at( 0 ).data, 0 );
        EXPECT_EQ( list2.at( 1 ).data, 1 );
        EXPECT_EQ( list2.at( 2 ).data, 2 );
    }

    TEST_F( linked_list_tests, self_copy )
    {
        auto list1 = int_list{ 0, 1, 2 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );

        list1 = list1;

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 0 );
        EXPECT_EQ( list1.at( 1 ).data, 1 );
        EXPECT_EQ( list1.at( 2 ).data, 2 );
    }

    TEST_F( linked_list_tests, move_assignment_operator )
    {
        auto list1 = int_list{ 1, 2, 3 };

        EXPECT_EQ( list1.size(), 3 );
        EXPECT_EQ( list1.at( 0 ).data, 1 );
        EXPECT_EQ( list1.at( 1 ).data, 2 );
        EXPECT_EQ( list1.at( 2 ).data, 3 );

        auto list2 = int_list{ 4, 5, 6 };

        EXPECT_EQ( list2.size(), 3 );
        EXPECT_EQ( list2.at( 0 ).data, 4 );
        EXPECT_EQ( list2.at( 1 ).data, 5 );
        EXPECT_EQ( list2.at( 2 ).data, 6 );

        list2 = std::move( list1 );

        // list1 = invalid state

        EXPECT_EQ( list1.size(), 0 ); // NOLINT(bugprone-use-after-move, hicpp-invalid-access-moved)

        EXPECT_EQ( list2.size(), 3 );
        EXPECT_EQ( list2.at( 0 ).data, 1 );
        EXPECT_EQ( list2.at( 1 ).data, 2 );
        EXPECT_EQ( list2.at( 2 ).data, 3 );
    }

    TEST_F( linked_list_tests, move_constructor )
    {
        auto list1 = int_list{ 1, 2, 3, 4, 5 };

        EXPECT_EQ( list1.size(), 5 );

        EXPECT_EQ( list1.at( 0 ).data, 1 );
        EXPECT_EQ( list1.at( 1 ).data, 2 );
        EXPECT_EQ( list1.at( 2 ).data, 3 );
        EXPECT_EQ( list1.at( 3 ).data, 4 );
        EXPECT_EQ( list1.at( 4 ).data, 5 );

        auto list2 = std::move( list1 );

        // list1 = invalid state

        EXPECT_EQ( list1.size(), 0 );  // NOLINT(bugprone-use-after-move, hicpp-invalid-access-moved)

        EXPECT_EQ( list2.size(), 5 );

        EXPECT_EQ( list2.at( 0 ).data, 1 );
        EXPECT_EQ( list2.at( 1 ).data, 2 );
        EXPECT_EQ( list2.at( 2 ).data, 3 );
        EXPECT_EQ( list2.at( 3 ).data, 4 );
        EXPECT_EQ( list2.at( 4 ).data, 5 );
    }

    TEST_F( linked_list_tests, move_constructor_copy )
    {
        auto outer = int_list();

        {
            auto inner = int_list{ 1, 2, 3, 4, 5 };

            EXPECT_EQ( inner.size(), 5 );

            EXPECT_EQ( inner.at( 0 ).data, 1 );
            EXPECT_EQ( inner.at( 1 ).data, 2 );
            EXPECT_EQ( inner.at( 2 ).data, 3 );
            EXPECT_EQ( inner.at( 3 ).data, 4 );
            EXPECT_EQ( inner.at( 4 ).data, 5 );

            outer = std::move( inner );
        }

        EXPECT_EQ( outer.size(), 5 );
        EXPECT_EQ( outer.at( 0 ).data, 1 );
        EXPECT_EQ( outer.at( 1 ).data, 2 );
        EXPECT_EQ( outer.at( 2 ).data, 3 );
        EXPECT_EQ( outer.at( 3 ).data, 4 );
        EXPECT_EQ( outer.at( 4 ).data, 5 );
    }

    TEST_F( linked_list_tests, empty_insert_delete )
    {
        auto list = int_list{ };

        EXPECT_EQ( list.size(), 0 );

        list.push_back( 1 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, remove_single )
    {
        auto list = int_list{ 1 };

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );

        list.remove( 1 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, remove_head_double )
    {
        auto list = int_list{ 1, 2 };

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 2 );

        list.remove( 1 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 2 );
    }

    TEST_F( linked_list_tests, remove_tail_double )
    {
        auto list = int_list{ 1, 2 };

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 2 );

        list.remove( 2 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 1 );
    }

    TEST_F( linked_list_tests, remove_head_triple )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.at( 0 ).data, 2 );
        EXPECT_EQ( list.at( 1 ).data, 3 );
    }

    TEST_F( linked_list_tests, remove_past_end )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );

        try
        {
            list.remove_at( 3 );
            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "REMOVE_PAST_END_ATTEMPT" );
        }

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
    }

    TEST_F( linked_list_tests, remove_tail_triple )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );

        list.remove_at( 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.back().data, 2 );
    }

    TEST_F( linked_list_tests, remove_middle )
    {
        auto list = int_list{ 1, 2, 3, 4, 5, 6 };

        EXPECT_EQ( list.size(), 6 );

        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 3 ).data, 4 );
        EXPECT_EQ( list.at( 4 ).data, 5 );
        EXPECT_EQ( list.at( 5 ).data, 6 );

        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 4 );

        EXPECT_EQ( list.size(), 5 );

        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 3 ).data, 4 );
        EXPECT_EQ( list.at( 4 ).data, 6 );

        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 3 );

        EXPECT_EQ( list.size(), 4 );

        EXPECT_EQ( list.at( 0 ).data, 1 );
        EXPECT_EQ( list.at( 1 ).data, 2 );
        EXPECT_EQ( list.at( 2 ).data, 3 );
        EXPECT_EQ( list.at( 3 ).data, 6 );

        EXPECT_EQ( list.front().data, 1 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 3 );

        EXPECT_EQ( list.at( 0 ).data, 2 );
        EXPECT_EQ( list.at( 1 ).data, 3 );
        EXPECT_EQ( list.at( 2 ).data, 6 );

        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 6 );

        list.remove_at( 2 );

        EXPECT_EQ( list.size(), 2 );

        EXPECT_EQ( list.at( 0 ).data, 2 );
        EXPECT_EQ( list.at( 1 ).data, 3 );

        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 3 );

        list.remove_at( 1 );

        EXPECT_EQ( list.size(), 1 );

        EXPECT_EQ( list.at( 0 ).data, 2 );

        EXPECT_EQ( list.front().data, 2 );
        EXPECT_EQ( list.back().data, 2 );

        list.remove_at( 0 );

        EXPECT_EQ( list.size(), 0 );

        EXPECT_EQ( list.front().data, 0 );
        EXPECT_EQ( list.back().data, 0 );
    }

    TEST_F( linked_list_tests, pop_front_empty )
    {
        auto list = int_list{};

        try
        {
            list.pop_back();
            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "ATTEMPT_POP_EMPTY_LIST" );
        }
    }

    TEST_F( linked_list_tests, pop_back_empty )
    {
        auto list = int_list{};

        try
        {
            list.pop_back();
            FAIL() << "This should throw an error.";
        }
        catch( std::runtime_error& e )
        {
            EXPECT_EQ( std::string( e.what() ), "ATTEMPT_POP_EMPTY_LIST" );
        }
    }

    TEST_F( linked_list_tests, pop_front )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.pop_front(), 1 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.pop_front(), 2 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.pop_front(), 3 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, pop_back )
    {
        auto list = int_list{ 1, 2, 3 };

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.pop_back(), 3 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.pop_back(), 2 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.pop_back(), 1 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, pop_alt )
    {
        auto list = int_list{ 1, 2, 3, 4, 5 };

        EXPECT_EQ( list.size(), 5 );
        EXPECT_EQ( list.pop_front(), 1 );

        EXPECT_EQ( list.size(), 4 );
        EXPECT_EQ( list.pop_back(), 5 );

        EXPECT_EQ( list.size(), 3 );
        EXPECT_EQ( list.pop_front(), 2 );

        EXPECT_EQ( list.size(), 2 );
        EXPECT_EQ( list.pop_back(), 4 );

        EXPECT_EQ( list.size(), 1 );
        EXPECT_EQ( list.pop_front(), 3 );

        EXPECT_EQ( list.size(), 0 );
    }

    TEST_F( linked_list_tests, find_element )
    {
        auto list = int_list{ 1, 2, 3, 4, 5 };

        const auto to_find = 3;

        auto actual = std::find_if(list.begin(), list.end(),
            [&]( const auto& node ) { return node.data == to_find; });

        EXPECT_TRUE( actual != std::end( list ) );
        EXPECT_EQ( actual->data, to_find );
    }

    TEST_F( linked_list_tests, no_find_element )
    {
        auto list = int_list{ 1, 2, 3, 4, 5 };

        const auto to_find = 6;

        auto actual = std::find_if( list.begin(), list.end(),
            [&]( const auto& node ) { return node.data == to_find; } );

        EXPECT_TRUE( actual == std::end( list ) );
    }
}

Answer 1

代码非常好，但是其中有些部分不够直观，无法巧妙地阅读。

不要误解我，你的设计是好的，但它是相当复杂的看清楚。考虑到：

我们的主要目标是最简单有意义的建筑。

把它想象成一个武术家，要有效率，动作要尽量少。强调的是，这使我们能够建立更好的系统并加以扩展。

The Good:

• 现代功能的实现增加了，这就带来了优化。
• 不使用宏(最好避免使用它们)
• 不使用using namespace
• 在需要时使用异常(在处理数据结构时必不可少)

代码审查：

• 如果您正在编写数据结构项目，您将发现动态数据结构需要公共链接组件。例如，队列或堆栈将使用单个链接节点，或者如果您希望使用双链接节点。因此，您可以在其他文件中定义list_node。通常，您会希望类和结构在不同的文件中分开。
• 默认情况下，Struct属性是公共的，您实际上不需要将linked_list作为list_node的朋友类。
• 不要那么频繁地使用typedef，这会使代码变得非常混乱。当您这样做时，您将隐藏类型，如果新的typedef没有足够的描述性，它将在代码中造成读取和调试两方面的问题。
• 与命名一致，我看到了一个名为ptr_的字段，所以您应该使用_后缀。
• 结构的最佳之处是轻松地处理其成员，因为它们是公共的，因此，实现通常会隐藏节点(应该)。
• 数据结构的实现不应返回节点对象。

一些评论：

你重新发明轮子的方式很有趣，通常有些人会说“我们不需要重新发明轮子，因为它是为什么做的……”因此，但想想看，轮胎制造商在这一时刻正在做什么。通过讨论，答案很简单，你总是需要更好的东西。

我推荐您下面的谷歌C++风格指南，这是一个很好的熟悉的东西。这是Google阐述的编码C++的标准(如果您没有已经遵循的标准)

终于来了。希望我的回答是你喜欢和帮助你。