• C++STL详解（三）list的使用及其模拟实现

    文章目录

    1.简介

    官方文档

    image-20220724133139983

    1. list是可以在常数时间内去任意位置进行插入和删除的顺序容器，并且该容器可以前后双向迭代。
    2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
    3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代。
    4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
    5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。

    2.常用接口

    构造

    image-20220724135014825

    方式一： 构造一个某类型的空容器。

    list<int> lt1; //构造int类型的空容器

    • 1

    方式二： 构造一个含有n个val的某类型容器。

    list<int> lt2(10, 2); // 10个2

    • 1

    方式三： 拷贝构造某类型容器的复制品。

    list<int> lt3(lt2); 

    • 1

    方式四： 使用迭代器拷贝构造某一段内容。

    string s("hello world");
list<char> lt4(s.begin(),s.end()); //构造string对象某段区间的复制品

    • 1
    • 2

    方式五： 构造数组某段区间的复制品。

    int arr[] = { 1, 2, 3, 4, 5 };
int sz = sizeof(arr) / sizeof(int);
list<int> lt5(arr, arr + sz); //构造数组某段区间的复制品

    • 1
    • 2
    • 3

    迭代器

    void test_list1()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    
    // 正向迭代器
    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        *it += 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 反向迭代器
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        *rit -= 1;
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
	
    // 范围for
    for (auto& e : lt)
    {
        e += 1;
        cout << e << " ";
    }
    cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    image-20220724140059465

    插入删除

    头插头删尾插尾删

    void test_list2()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;

    lt.push_front(10);
    lt.push_front(20);
    lt.push_front(30);
    lt.push_front(40);

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;

    lt.pop_back();
    lt.pop_back();
    lt.pop_front();
    lt.pop_front();

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    image-20220724140038373

    insert

    image-20220809231711406

    Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence.

    #include 
#include 
#include 
#include 
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
	lt.insert(pos, 9); //在2的位置插入9
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 9 2 3
	pos = find(lt.begin(), lt.end(), 3);
	lt.insert(pos, 2, 8); //在3的位置插入2个8
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 9 2 8 8 3
	vector<int> v(2, 7);
	pos = find(lt.begin(), lt.end(), 1);
	lt.insert(pos, v.begin(), v.end()); //在1的位置插入2个7
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //7 7 1 9 2 8 8 3
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    erase

    iterator erase (iterator position);
iterator erase (iterator first, iterator last);

    • 1
    • 2
    #include 
#include 
#include 
#include 
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
	lt.erase(pos); //删除2
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 3 4 5
	pos = find(lt.begin(), lt.end(), 4);
	lt.erase(pos, lt.end()); //删除4及其之后的元素
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 3
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    front&back

    front函数用于获取list容器当中的第一个元素，back函数用于获取list容器当中的最后一个元素。

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(0);
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	cout << lt.front() << endl; //0
	cout << lt.back() << endl; //4
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    resize

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt(5, 3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //3 3 3 3 3
	lt.resize(7, 6); //将size扩大为7，扩大的值为6
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //3 3 3 3 3 6 6
	lt.resize(2); //将size缩小为2
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //3 3
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    sort

    image-20220724140419775
    注意：这里的sort排序之后是稳定的。

    algorithm中的sort是不支持对list排序的
    在这里插入图片描述

    算法中的sort()是支持随机访问的，而list不支持随机访问。
    在这里插入图片描述

    void TestOP()
{
    srand(time(0));
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);

    list<int> lt;

    for (int i = 0; i < N; ++i)
    {
        v.push_back(rand());
        lt.push_back(v[i]);
    }

    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();

    int begin2 = clock();
    //sort(lt.begin(), lt.end()); // err
    lt.sort();
    int end2 = clock();

    printf("vector Sort:%d\n", end1 - begin1);
    printf("list Sort:%d\n", end2 - begin2);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    release版本下：
    image-20220725104452896
    image-20220725104529571

    void TestOP2()
{
    srand(time(0));
    const int N = 10000000;
    vector<int> v;
    v.reserve(N);

    list<int> lt1;
    list<int> lt2;

    for (int i = 0; i < N; ++i)
    {
        auto e = rand();
        lt1.push_back(e);
        lt2.push_back(e);
    }

    // 拷贝到vector排序，排完以后再拷贝回来
    int begin1 = clock();
    for (auto e : lt1)
    {
        v.push_back(e);
    }
    sort(v.begin(), v.end());
    size_t i = 0;
    for (auto& e : lt1)
    {
        e = v[i++];
    }
    int end1 = clock();

    // 链表2单独排序，对比效率
    int begin2 = clock();
    lt2.sort();
    int end2 = clock();

    printf("vector Sort:%d\n", end1 - begin1);
    printf("list Sort:%d\n", end2 - begin2);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    image-20220725105324329
    可见，链表的排序效率非常低下，甚至都不如拷贝给别人排好序再拷贝回来。

    splice

    splice函数用于两个list容器之间的拼接，其有三种拼接方式：

    1. 将整个容器拼接到另一个容器的指定迭代器位置。
    2. 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置。
    3. 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置。

    image-20220809233239888

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt1(4, 2);
	list<int> lt2(4, 6);
	lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2 

	list<int> lt3(4, 2);
	list<int> lt4(4, 6);
	lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl; //6 2 2 2 2 

	list<int> lt5(4, 2);
	list<int> lt6(4, 6);
	lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
	for (auto e : lt5)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    注意： 容器当中被拼接到另一个容器的数据在原容器当中就不存在了。（实际上就是将链表当中的指定结点拼接到了另一个容器当中）

    remove

    remove函数用于删除容器当中特定值的元素。

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 3 2 2 3
	lt.remove(3); //删除容器当中值为3的元素
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 2 2
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    remove_if

    remove_if函数用于删除容器当中满足条件的元素。

    // list::remove_if
#include 
#include 

// a predicate implemented as a function:
bool single_digit (const int& value) { return (value<10); }

// a predicate implemented as a class:
struct is_odd {
    bool operator() (const int& value) { return (value%2)==1; }
};

int main ()
{
    int myints[]= {15,36,7,17,20,39,4,1};
    std::list<int> mylist (myints,myints+8);   // 15 36 7 17 20 39 4 1

    mylist.remove_if (single_digit);           // 15 36 17 20 39

    mylist.remove_if (is_odd());               // 36 20

    std::cout << "mylist contains:";
    for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    unique

    unique函数用于删除容器当中连续的重复元素。

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 3 2 2 3
	lt.sort(); //将容器当中的元素排为升序
	lt.unique(); //删除容器当中连续的重复元素
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 2 3 4
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    注意： 若想使用unique函数做到真正的去重，还需在去重前对容器内元素进行排序。

    merge

    merge函数用于将一个有序list容器合并到另一个有序list容器当中，使得合并后的list容器任然有序。（类似于归并排序）

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(3);
	lt1.push_back(8);
	lt1.push_back(1);
	list<int> lt2;
	lt2.push_back(6);
	lt2.push_back(2);
	lt2.push_back(9);
	lt2.push_back(5);
	lt1.sort(); //将容器lt1排为升序
	lt2.sort(); //将容器lt2排为升序
	lt1.merge(lt2); //将lt2合并到lt1当中
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //1 2 3 5 6 8 9 
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    reverse

    reverse函数用于将容器当中元素的位置进行逆置。

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.reverse(); //将容器当中元素的位置进行逆置
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //5 4 3 2 1 
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    assign

    assign函数用于将新内容分配给容器，替换其当前内容，新内容的赋予方式有两种：

    1. 将n个值为val的数据分配给容器。
    2. 将所给迭代器区间当中的内容分配给容器。

    image-20220809233858727

    注意会相应的修改size

    #include 
#include 
#include 
using namespace std;

int main()
{
	list<char> lt(3, 'a');
	lt.assign(3, 'b'); //将新内容分配给容器，替换其当前内容
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //b b b
	string s("hello world");
	lt.assign(s.begin(), s.end()); //将新内容分配给容器，替换其当前内容
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //h e l l o   w o r l d
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    swap

    swap函数用于交换两个容器的内容。

    #include 
#include 
using namespace std;

int main()
{
	list<int> lt1(4, 2);
	list<int> lt2(4, 6);
	lt1.swap(lt2); //交换两个容器的内容
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl; //2 2 2 2
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    3.模拟实现

    核心框架

    包括结点，迭代器，list。

    //模拟实现list当中的结点类
template<class T>
    struct list_node
    {
        //成员函数
        list_node(const T& val = T()); //构造函数

        //成员变量
        list_node<T>* _next;
        list_node<T>* _prev;
        T _data;
    };

//模拟实现list迭代器
template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T, Ref, Ptr> self;

        __list_iterator(Node* node);  //构造函数

        //各种运算符重载函数
        self operator++();
        self operator--();
        self operator++(int);
        self operator--(int);
        bool operator==(const self& s) const;
        bool operator!=(const self& s) const;
        Ref operator*();
        Ptr operator->();

        //成员变量
        Node* _node; //一个指向结点的指针
    };

//模拟实现list
template<class T>
    class list
    {
        public:
        typedef list_node<T> Node;
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        //反向迭代器适配list
        typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef Reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;

        //默认成员函数
        list();
        list(const list<T>& lt);
        list<T>& operator=(const list<T>& lt);
        ~list();

        //迭代器相关函数
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;
        reverse_iterator rbegin();
        reverse_iterator rend();
        const_reverse_iterator rbegin() const;
        const_reverse_iterator rend() const;

        //访问容器相关函数
        T& front();
        T& back();
        const T& front() const;
        const T& back() const;

        //插入、删除函数
        iterator insert(iterator pos, const T& x);
        iterator erase(iterator pos);
        void push_back(const T& x);
        void pop_back();
        void push_front(const T& x);
        void pop_front();

        private:
        node* _head; //指向链表头结点的指针
    };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81

    节点类

    在这里插入图片描述

    list的底层是一个带头双向循环链表。
    因此，若要实现list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）。

    // 节点
template<class T>
    struct list_node
    {
        list_node<T>* _next;
        list_node<T>* _prev;
        T _data;

        list_node(const T& val = T())
            :_next(nullptr)
                , _prev(nullptr)
                , _data(val)
            {}
    };
// 若构造结点时未传入数据，则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    迭代器

    欣赏一下源码中怎么写的：

    在这里插入图片描述

    image-20220725120414812

    之前的string、vector的迭代器就是原生指针，因为它们的底层是连续物理空间，通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作。
    但是链表不是连续的物理空间，各个结点在内存当中的位置是随机的，就不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。
    而迭代器的意义就是让使用者可以不必关心容器的底层实现，用简单统一的方式对容器内的数据进行访问。

    对于list来说，既然原生指针不好用，那我们就自己封装一个，因此就有了iterator，其实就是Node*的封装。
    因此也就需要一系列的运算符重载。

    template<class T>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T> self; // 方便后面修改T
        // self其实就是当前迭代器对象的类型

        Node* _node;

        __list_iterator(Node* node)
            :_node(node)
            {}
        // 不需要写析构，节点不属于迭代器，不需要迭代器去释放。系统自己生成的就够用了，啥也不干
        // 拷贝构造和赋值重载 默认生成的浅拷贝就可以了 it = lt.begin();

        // 先让结点指针指向后一个结点，然后再返回自增后的结点指针
        self operator++() //前置++
        {
            _node = _node->_next;
            return *this;
        }

        // 先记录当前结点指针的指向，然后让结点指针指向后一个结点，最后返回自增前的结点指针
        self operator++(int) //后置++
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        self operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        bool operator!=(const self& it) const
        {
            return _node != it._node;
        }

        bool operator==(const self& it) const
        {
            return _node == it._node;
        }
    };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    *重载

    当我们使用解引用操作符时，是想得到该位置的数据内容。因此，我们直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。

    T& operator*()
{
    return _node->_data;
}

    • 1
    • 2
    • 3
    • 4

    ->重载

    举个例子👇

    当list容器当中的结点存储的不是内置类型，而是自定义类型，例如：AA
    那么当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问AA的成员

    struct AA
{
    AA(int a1 = 0, int a2 = 0)
        :_a1(a1)
            ,_a2(a2)
        {}
    int _a1;
    int _a2;
};

void test_list2()
{
    list<AA> lt;
    lt.push_back(AA(1, 1));
    lt.push_back(AA(2, 2));
    lt.push_back(AA(3, 3));
    lt.push_back(AA(4, 4));

    list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
        // err *it返回的是节点的data，data是val，val是T()
        // 也就是这里返回的是AA 自定义类型不支持流操作的
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    在这里插入图片描述

    *it返回的是AA 是自定义类型，流操作只支持内置类型，除非我们在AA类里去重载流操作。
    如果我们不想自己写呢？因为是struct，都是公有的，因此也可以用(*it)._a1访问AA的成员

    void test_list2()
{
    list<AA> lt;
    lt.push_back(AA(1, 1));
    lt.push_back(AA(2, 2));
    lt.push_back(AA(3, 3));
    lt.push_back(AA(4, 4));

    list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout <<  (*it)._a1 << "-" << (*it)._a2 << " ";
        ++it;
    }
    cout << endl; // 1-1 2-2 3-3 4-4
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    迭代器模拟的是指针，因此要可以像指针那样去操作。
    int* it *it
    AA* it *it it->
    为了支持->，需要重载->

    T* operator->()
{
    return &(operator*());
    // 等价于
    //return &_node->_data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    在这里插入图片描述

    void test_list2()
{
    list<AA> lt;
    lt.push_back(AA(1, 1));
    lt.push_back(AA(2, 2));
    lt.push_back(AA(3, 3));
    lt.push_back(AA(4, 4));

    list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout <<  it->_a1 << "-" << it->_a2 << " ";
        ++it;
    }
    cout << endl; // 1-1 2-2 3-3 4-4
}
// it-> 返回的就是AA*，然后AA*再去调用成员变量

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    const迭代器

    const对象需要调用的是const的迭代器，而且返回的值是不能修改的，一般想法就是把__list_iterator拷贝一份，改成__list_const_iterator并修改其中的operator*()、operator->()的返回类型为const T

    const T& operator*()
{
    return _node->_data;
}

const T* operator->()
{
    return &(operator*());
}

const_iterator begin() const
{
    return const_iterator(_head->_next);
}

const_iterator end() const
{
    return const_iterator(_head);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    但是这样的话，代码太冗余了，没有很好的复用之前的代码。
    我们可以利用模板进行灵活控制：

    struct __list_iterator
{
    typedef list_node<T> Node;
    typedef __list_iterator<T, Ref, Ptr> self; // 方便后面修改T

    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &(operator*());
    }
    // 。。。
};

// list类中
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

const_iterator begin() const
{
    return const_iterator(_head->_next);
}

const_iterator end() const
{
    return const_iterator(_head);
}

void print_list(const list<int>& l)
{
    list<int>::const_iterator cit = l.begin();
    while (cit != l.end())
    {
        //*cit = 1; // const对象不允许修改，调用的也是const版本迭代器
        cout << *cit << " ";
        ++cit;
    }
    cout << endl;
}

void test_list3()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        *it += 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    print_list(lt);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    总结：
    普通对象调用的是普通迭代器，返回的是普通迭代器，普通迭代器是__list_iterator的typedef，T& T*传递给了类模板的Ref Ptr，*it访问的时候，返回值类型就是Ref也就是T&，是允许修改的。
    const对象调用的是const迭代器，返回的是const迭代器，const迭代器是__list_iterator的typedef，const T&、const T*传给了Ref Ptr，*it访问的时候，返回值类型是const T&，是不允许修改的。

    注意：如果传的是👇
    由于类型不匹配，编译都不能通过。

    typedef __list_iterator<const T, const T&, const T*> const_iterator;

    • 1

    image-20220810142242973

    list类

    构造函数

    list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。

    在这里插入图片描述

    list()
{
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    拷贝构造

    void test_list7()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int> lt1(lt); // 我们如果不写，默认生成的完成浅拷贝，指向同一个头，析构时会delete2次，崩溃。

    for (auto e : lt1)
    {
        cout << e << " ";
    }
    cout << endl; // 1 2 3 4
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    // lt2(lt1)
// 传统写法
list(const list<T>& lt)
{
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;

    for (auto e : lt)
    {
        push_back(e);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    现代写法：

    void empty_init()
{
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;
}

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
    empty_init();
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

void swap(list<T>& lt)
{
    // 只需要换头指针就行
    std::swap(_head, lt._head);
}

//现代写法 拷贝构造
list(const list<T>& lt)
{
    empty_init(); //不能用随机值和别人交换，得初始化一下自己才行
    list<T> tmp(lt.begin(), lt.end());
    swap(tmp);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    赋值重载

    //赋值重载 lt2 = lt1
list<T>& operator=(list<T> lt) // 传参时先进性一次拷贝构造
{
    swap(lt);
    return *this;
}
// lt是临时对象，换完之后，出作用域，析构的时候还得释放掉lt2

void test_list7()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int> lt1(lt); // 我们不写，默认生成的完成浅拷贝，指向同一个头，析构时会析构2次，崩溃。

    for (auto e : lt1)
    {
        cout << e << " ";
    }
    cout << endl; // 1 2 3 4

    list<int> lt2;
    lt2.push_back(10);
    lt2.push_back(20);

    lt1 = lt2;

    for (auto e : lt2)
    {
        cout << e << " ";
    }
    cout << endl; // 10 20

    for (auto e : lt1)
    {
        cout << e << " ";
    }
    cout << endl; // 10 20
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    析构函数

    ~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        // erase返回的就是删除节点的下一个
        it = erase(it);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    插入删除

    insert：Return value
    An iterator that points to the first of the newly inserted elements.

    erase：Return value
    An iterator pointing to the element that followed the last element.

    // 插在pos之前
iterator insert(iterator pos, const T& val)
{
    Node* newNode = new Node(val);
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    // prev newNode cur
    prev->_next = newNode;
    newNode->_prev = prev;
    newNode->_next = cur;
    cur->_prev = newNode;

    return iterator(newNode);
}

iterator erase(iterator pos)
{
    assert(pos != end());
    // prev cur next
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;

    delete cur;
    return iterator(next);
}

void test_list4()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_front(1);
    lt.push_front(2);
    lt.push_front(3);
    lt.push_front(4);

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 4 3 2 1 1 2 3 4

    lt.pop_back();
    lt.pop_back();
    lt.pop_front();
    lt.pop_front();

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 2 1 1 2
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    迭代器失效

    void test_list5()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(4);
    lt.push_back(5);
    lt.push_back(6);

    // 要求在偶数前面插入这个偶数*10
    auto it1 = lt.begin();
    while (it1 != lt.end())
    {
        if (*it1 % 2 == 0)
        {
            lt.insert(it1, *it1 * 10);
        }
        ++it1;
    }

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 1 20 2 20 2 3 40 4 40 4 5 60 6
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    list的insert不存在迭代器失效问题，既没有野指针问题，也没有迭代器意义改变的问题。

    void test_list6()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.push_back(6);

    // 删除所有的偶数
    auto it1 = lt.begin();
    while (it1 != lt.end())
    {
        if (*it1 % 2 == 0)
        {
            lt.erase(it1);
        }

        ++it1;
    }

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    erase妥妥的迭代器失效，野指针访问，erase把指向当前的节点都delete。

    image-20220726101421034

    解决：
    借助返回值，指向pos的下一个。

    iterator erase(iterator pos)
{
    assert(pos != end());
    // prev cur next
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;

    delete cur;
    return iterator(next);
}

void test_list6()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.push_back(6);

    // 删除所有的偶数
    auto it1 = lt.begin();
    while (it1 != lt.end())
    {
        if (*it1 % 2 == 0)
        {
            it1 = lt.erase(it1);
        }
        else
        {
            ++it1;
        }
    }

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 1 3 3 5 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    clear

    void clear()
{
    iterator it = begin();
    while (it != end())
    {
        // erase返回的就是删除节点的下一个
        it = erase(it);
    }
}

void test_list6()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.push_back(6);

    // 删除所有的偶数
    auto it1 = lt.begin();
    while (it1 != lt.end())
    {
        if (*it1 % 2 == 0)
        {
            it1 = lt.erase(it1);
        }
        else
        {
            ++it1;
        }
    }

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 1 3 3 5

    lt.clear();

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 空

    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);

    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl; // 10 20 30
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    容器访问

    //访问容器相关函数
T& front()
{
    return *begin();
}
T& back()
{
    return *(--end());
}
const T& front() const
{
    return *begin();
}
const T& back() const
{
    return *(--end());
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    源代码

    #pragma once
#include 
#include 
#include 
#include 
#include 
#include 
#include "ReverseIterator.h"
using namespace std;

namespace yzq
{
    // 节点
    template<class T>
        struct list_node
        {
            list_node<T>* _next;
            list_node<T>* _prev;
            T _data;

            list_node(const T& val = T())
                :_next(nullptr)
                    , _prev(nullptr)
                    , _data(val)
                {}
        };

    // list迭代器
    template<class T, class Ref, class Ptr>
        struct __list_iterator
        {
            typedef list_node<T> Node;
            typedef __list_iterator<T, Ref, Ptr> self; // 方便后面修改T

            Node* _node;
            __list_iterator(Node* node)
                :_node(node)
                {}

            // 不需要写析构，节点不属于迭代器，不需要迭代器去释放。系统自己生成的就够用了，啥也不干
            // 拷贝构造和赋值重载 默认生成的浅拷贝就可以了 it = lt.begin();

            Ref operator*()
            {
                return _node->_data;
            }

            Ptr operator->()
            {
                return &(operator*());
                // 等价于
                //return &_node->_data;
            }

            self operator++() //前置++
            {
                _node = _node->_next;
                return *this;
            }

            self operator++(int) //后置++
            {
                self tmp(*this);
                _node = _node->_next;
                return tmp;
            }

            self operator--()
            {
                _node = _node->_prev;
                return *this;
            }

            self operator--(int)
            {
                self tmp(*this);
                _node = _node->_prev;
                return tmp;
            }

            bool operator!=(const self& it) const
            {
                return _node != it._node;
            }

            bool operator==(const self& it) const
            {
                return _node == it._node;
            }
        };

    template<class T>
        class list
        {
            typedef list_node<T> Node;

            public:
            typedef __list_iterator<T, T&, T*> iterator;
            typedef __list_iterator<T, const T&, const T*> const_iterator;
            //反向迭代器适配list
            typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
            typedef Reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;

            // 迭代器相关函数
            const_iterator begin() const
            {
                return const_iterator(_head->_next);
            }

            const_iterator end() const
            {
                return const_iterator(_head);
            }

            iterator begin()
            {
                // 构造一个匿名对象，再传值返回
                // 构造再拷贝构造优化成直接构造
                /*等价
			iterator it(_head->_next);
			return it;*/
                return iterator(_head->_next);

                // 也可以直接这么写，单参数隐式类型转换
                //return _head->_next;
            }

            iterator end()
            {
                return iterator(_head);
            }

            reverse_iterator rbegin()
            {
                return reverse_iterator(end());
            }

            reverse_iterator rend()
            {
                return reverse_iterator(begin());
            }

            const_reverse_iterator rbegin() const
            {
                return const_reverse_iterator(end());
            }

            const_reverse_iterator rend() const
            {
                return const_reverse_iterator(begin());
            }


            // 默认成员函数
            list()
            {
                _head = new Node();
                _head->_next = _head;
                _head->_prev = _head;
            }
            /*
		// lt2(lt1)  传统写法
		list(const list& lt)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;

			for (auto e : lt)
			{
				push_back(e);
			}
		}
		*/
            void empty_init()
            {
                _head = new Node();
                _head->_next = _head;
                _head->_prev = _head;
            }

            template<class InputIterator>
                list(InputIterator first, InputIterator last)
            {
                empty_init();
                while (first != last)
                {
                    push_back(*first);
                    ++first;
                }
            }

            void swap(list<T>& lt)
            {
                // 只需要换头指针就行
                std::swap(_head, lt._head);
            }

            //现代写法 拷贝构造
            list(const list<T>& lt)
            {
                empty_init(); //不能用随机值和别人交换，得初始化一下自己才行
                list<T> tmp(lt.begin(), lt.end());
                swap(tmp);
            }

            //赋值重载 lt2 = lt1
            list<T>& operator=(list<T> lt)
            {
                swap(lt);
                return *this;
            }
            // lt是临时对象，换完之后，出作用域，析构的时候还得释放掉lt2原来的空架子

            ~list()
            {
                clear();
                delete _head;
                _head = nullptr;
            }

            void clear()
            {
                iterator it = begin();
                while (it != end())
                {
                    // erase返回的就是删除节点的下一个
                    it = erase(it);
                }
            }

            //访问容器相关函数
            T& front()
            {
                return *begin();
            }
            T& back()
            {
                return *(--end());
            }
            const T& front() const
            {
                return *begin();
            }
            const T& back() const
            {
                return *(--end());
            }


            // 插入删除函数
            void push_back(const T& x)
            {
                /*
			Node* tail = _head->_prev;
			Node* newNode = new Node(x);
			// _head tail newNode
			tail->_next = newNode;
			newNode->_prev = tail;
			newNode->_next = _head;
			_head->_prev = newNode;
			*/
                // 复用insert
                insert(end(), x);
            }
            void push_front(const T& x)
            {
                insert(begin(), x);
            }
            void pop_back()
            {
                erase(--end());
            }
            void pop_front()
            {
                erase(begin());
            }

            // 插在pos之前
            iterator insert(iterator pos, const T& val)
            {
                Node* newNode = new Node(val);
                Node* cur = pos._node;
                Node* prev = cur->_prev;
                // prev newNode cur
                prev->_next = newNode;
                newNode->_prev = prev;
                newNode->_next = cur;
                cur->_prev = newNode;

                return iterator(newNode);
            }

            iterator erase(iterator pos)
            {
                assert(pos != end());
                // prev cur next
                Node* cur = pos._node;
                Node* prev = cur->_prev;
                Node* next = cur->_next;
                prev->_next = next;
                next->_prev = prev;

                delete cur;
                return iterator(next);
            }

            private:
            Node* _head;
        };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310

    尾声

    🌹🌹🌹

    写文不易，如果有帮助烦请点个赞~ 👍👍👍

    Thanks♪(･ω･)ﾉ🌹🌹🌹

    😘😘😘

    👀👀由于笔者水平有限，在今后的博文中难免会出现错误之处，本人非常希望您如果发现错误，恳请留言批评斧正，希望和大家一起学习，一起进步ヽ(￣ω￣(￣ω￣〃)ゝ，期待您的留言评论。
    附GitHub仓库链接

  • 相关阅读:
    极线的绘制（已知相机的内外参数，极线几何）
    java计算机毕业设计医院出入院管理系统源程序+mysql+系统+lw文档+远程调试
    【C++】构造函数与析构函数概念简介 ( 构造函数和析构函数引入 | 构造函数定义与调用 | 析构函数定义与调用 | 代码示例 )
    基JavaSwing开发公司管理系统+报告 课程设计 大作业
    Laravel Valet - macOS 极简主义者的开发环境
    跨端必须要掌握的uniapp（3），前端基础
    伪原创工具-免费伪原创软件
    osg node节点生效结构图
    nginx反向代理.NetCore开发的基于WebApi创建的gRPC服务
    云计算基础技术
  • 原文地址：https://blog.csdn.net/a2076188013/article/details/126268623