STL设计之链表设计,分块分组件分析,迭代器设计思路

前言.

**欢迎大家来到小杰的手写STL章节，小杰会长期根据自己所学和浅显理解，尽力以比较简单口语的方式带着大家分析STL中各种重要容器的函数接口迭代器等等组件的设计，希望大家可以支持小杰，万分感谢. **

如下附上精彩前文连接

分块刨析从函数原型到分块实现C++STL(vector)_小杰312的博客-CSDN博客分块刨析从函数原型到分块实现C++STL(vector)https://blog.csdn.net/weixin_53695360/article/details/123248476?spm=1001.2014.3001.5501

一. 思考关于list的迭代器的设计

首先关于list的迭代器设计上面，不再像vector那般的简单了，因为 List 不是连续的存储空间在存储着元素，元素的访问也就没有办法像 vector中原生指针那样直接的进行 ++ 操作去访问后序元素，但是迭代器就是可以支持做 ++ -- * 操作的一个这样一个类, 我们需要可以通过 ++ 迭代器的操作遍历访问整个容器中的元素

正因上述的需求，我们的 List 中的节点 LIstNode pnode 便是需要专门为其设计一个迭代器类进行管理的，使得 pnode 可以通过 ++ 的操作去访问下一个的元素, -- 操作可以去访问上一个元素*

所以大体上的思路出来了，一个struct iterator迭代器类封装管理一个ListNode 的指针，功能就是一个智能指针类，管理一个ListNode 指针, 对齐进行各种运算符重载：使得我们的ListNode* 指针可以通过 ++ -- 操作实现容器的遍历**

结点类

迭代器类: 此处粘贴出来的仅仅只是迭代器的重要组件，理清楚思路，其他的迭代器的运算符重载函数的书写还是蛮easy的

** 首先：我们将迭代器设置成了三个模板参数，分别是T Ref Ptr, 这样做有什么必要吗？答案肯定是肯定的， STL源码中不可能无端设计出来三个模板参数呀**

因为后序需要使用到ListIterator<T, Ref, Ptr> 还有 ListNode<T> 但是这样带着模板写有点略显麻烦了，所以起得别名, self别名代表迭代器本体类型

** 上述问题的解决其实就是在此处了，核心关键就是两种迭代器的产生, 一种是const_iterator 另外一个是 iterator ，一旦我们将其设置成三个模板参数，我们传入const 的时候他会按照模板的模子自动帮我们生成一份const类，我们就不再需要重新单独的为const 再专门设计出来一个类了, 没有必要做这个手工花销，有模板不必再自己新手写一个const 迭代器管理类了**

二. 重要函数原型分析理解,有了这些先写出来看看效果

迭代器框架必备函数刨析

operator * 重载就是取出其中的数据

opeartor-> 重载就是取出数据的地址

!= 和 == 大家都懂, 判断是否是一个迭代器

** ++ -- 操作迭代器必备的操作，代表着前进和后退一个结点**

List框架必备函数刨析

写默认构造很简单，一个没有数据的虚拟结点充当表头, 前后指针指向表头自身.

尾部插入一个结点, 三个过程

拿到尾部结点指针 pTail, 创建出新的newnode结点

pTail和newnode 相连接, newnode 成为新的tail

要构成循环，newnode 尾部结点需要和 head 相互连接

**上述简简单单的写一下for_each 使用迭代器作为模板参数，不为别的，只为了让大家感受一下为啥迭代器就能做各种容器和算法之间的粘合剂，没有迭代器就无法支持容器的遍历。。。 **

因为没有迭代器管理对象指针，智能指针类，让其支持 ++ -- * 操作来泛型的遍历整个容器，且将容器中的元素进行算法func处理， **** (STL的哪些所有的遍历算法都没法实现了，都瘫痪了)

三. 搭出大体框架

#include <iostream>
#include <list>
#include <assert.h>
using namespace std;

namespace tyj {
    //链表节点的设计, 双向循环链表
    template<class T>
    struct ListNode {
        ListNode(const T& _val = T())
            : pre(nullptr)
            , next(nullptr)
            , val(_val) {
        }
        ListNode<T>* pre;
        ListNode<T>* next;
        T val;
    };

    //分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的
    template<class T, class Ref, class Ptr>
    struct ListIterator {
        typedef ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr > self;
        Node* pnode;    //Iterator管理的指针

        ListIterator(Node* _pnode = nullptr)
            : pnode(_pnode) { 
        }
        Ref operator*() {
            return pnode->val;    //*重载访问val
        }

        Ptr operator->() {        //支持->访问
            return &pnode->val;
        }

        bool operator!=(const self& obj) const {
            return pnode != obj.pnode;
        }
        bool operator==(const self& obj) const {
            return pnode == obj.pnode;
        }

        self& operator++() {    //前置++ -- 操作返回本体
            pnode = pnode->next;
            return *this;
        }
        self operator++(int) {
            self before(*this);    //返回的是之前的
            pnode = pnode->next;
            return before;
        }

        self& operator--() {
            pnode = pnode->pre;
            return *this;
        }

        self operator--(int) {
            self before(*this);
            pnode = pnode->pre;
            return before;
        }

    };

    template<class T>
    class List {
        typedef ListNode<T> Node;//
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        //此处体现出来了  Ref  Ptr模板化的好处了    
        List() : head(new Node) {
            head->pre = head->next = head;//双向链表的最初状态
        }

        iterator begin() {//第一个结点
            return iterator(head->next);
        }

        const_iterator begin() const {
            return const_iterator(head->next);
        }

        iterator end() {
            return iterator(head);//返回虚拟头部结点
        }

        const_iterator end() const {
            return const_iterator(head);//虚拟头部结点
        }

        void push_back(const T& val) {
            Node* pTail = head->pre;
            Node* newnode = new Node(val);
            //连接到尾部
            pTail->next = newnode;
            newnode->pre = pTail;
            //成环连接到head上
            newnode->next = head;
            head->pre = newnode;
        }

    private:
        Node* head;//头部指针指向头部结点

    };

    template<class InputIterator, class Function>
    void for_each(InputIterator first, InputIterator last, Function f) {
        while (first != last) {
            f(*first++);
        }
    }
    template<class T>
    struct Print {
        void operator()(const T& val) const {
            cout << val << " ";
        }
    };
}

template<class T>
void PrintList(tyj::List<T>& lt) {
    tyj::for_each(lt.begin(), lt.end(), tyj::Print<T>());
    cout << endl;
}

int main() {

    tyj::List<int> lt;
    for (int i = 0; i < 5; ++i) {
        lt.push_back(i);
    }
    PrintList(lt);

    return 0;
}

四. 函数细节分块分析 (和vector差不大多)

区间范围range构造

vector 和 list 都是这种方式实现的, 遍历传入区间，然后调用push_back 复用代码实现传入，一种常用的套路方式.

swap为复用代码做准备
void swap(List& lt) {
    ::swap(head, lt.head);
}
swap: 非常纯粹简单的换, 将你的成员换给我, 我就成了你，你就成为了我

拷贝构造 (因为有了swap, 我自身初始化为nullptr 避免野指针, 然后将复用range构造代码构造出来的tmp对象换来构造自身)
List(const List& lt) 
    : head(nullptr) {
    List tmp(lt.begin(), lt.end());
    swap(tmp);    //换, 复用范围构造
}
赋值重载
//直接复用拷贝构造出来的lt
List& operator=(List lt) {
    head = nullptr;
    swap(lt);
    return *this;
}
**纯纯的复用拷贝构造出来的lt对象，你反正是临时对象，出来作用域就要析构，我直接换掉你底层的堆区资源构造this，复用拷贝构造 (本质还是复用range构造) **

移动构造(抢夺将亡对象的堆区资源进行构造)
List(List&& lt) {
    head = nullptr;
    swap(lt);
}
**移动构造，直接换，其他啥都不干，为啥它可以这样，拷贝构造都需要复用range范围构造构造构造出来一个tmp才能换, 但是移动构造是直接换, **

核心原因：移动构造传入的参数是一个右值，啥叫作右值，将死对象，临时对象，既然参数本来就是将亡对象，我直接就可使用它的底层堆区资源来构造自身

写完insert() + erase()接口，相当于是写好了六个接口

insert()

insert(pos, val); 在pos迭代器位置的前面插入一个值为val的结点newnode

push_back() 复用insert函数
void push_back(const T& val) {
    insert(end(), val);
    //在end()前插入一个newnode结点
}
push_front() 复用insert函数
void push_front(const T& val) {
    insert(begin(), val);
    //在begin前插入一个newnode结点    
}
erase();

erase(pos)总结就是三句话:

拿取pos前pre后next结点

delete pos

**pre 和 next结点相连 **

pop_back() 复用erase
void pop_back() {
    erase(--end());
    //删除end()前一个迭代器
    //end() == head 
    //--end() == head->pre == pTail
}
pop_front() 复用erase
void pop_front() {
    erase(begin());
    //begin() head->next;
    //head->next == firstnode
    //head是一个空头结点, firstnode才是真实的第一个元素
}

五. 总体代码 + 测试

#include <iostream>
#include <list>
#include <algorithm>
#include <assert.h>
using namespace std;

namespace tyj {
    //链表节点的设计, 双向循环链表
    template<class T>
    struct ListNode {
        ListNode(const T& _val = T())
            : pre(nullptr)
            , next(nullptr)
            , val(_val) {
        }
        ListNode<T>* pre;
        ListNode<T>* next;
        T val;
    };

    //分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的
    template<class T, class Ref, class Ptr>
    struct ListIterator {
        typedef ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr > self;
        Node* pnode;    //Iterator管理的指针

        ListIterator(Node* _pnode = nullptr)
            : pnode(_pnode) { 
        }
        Ref operator*() {
            return pnode->val;    //*重载访问val
        }

        Ptr operator->() {        //支持->访问
            return &pnode->val;
        }

        bool operator!=(const self& obj) const {
            return pnode != obj.pnode;
        }
        bool operator==(const self& obj) const {
            return pnode == obj.pnode;
        }

        self& operator++() {    //前置++ -- 操作返回本体
            pnode = pnode->next;
            return *this;
        }
        self operator++(int) {
            self before(*this);    //返回的是之前的
            pnode = pnode->next;
            return before;
        }

        self& operator--() {
            pnode = pnode->pre;
            return *this;
        }

        self operator--(int) {
            self before(*this);
            pnode = pnode->pre;
            return before;
        }

    };

    template<class T>
    class List {
        typedef ListNode<T> Node;
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        //此处体现出来了  Ref  Ptr模板化的好处了    
        List() : head(new Node) {
            head->pre = head->next = head;//双向链表的最初状态
        }

        template<class InputIterator>
        List(InputIterator first, InputIterator last)
            : head(new Node) {
            head->pre = head->next = head;
            while (first != last) {
                push_back(*first++);
            }
        }

        void swap(List& lt) {
            ::swap(head, lt.head);
        }

        List(const List& lt)
            : head(nullptr) {
            List tmp(lt.begin(), lt.end());
            swap(tmp);    //换, 复用范围构造
        }

        //直接复用拷贝构造出来的lt
        List& operator=(List lt) {
            head = nullptr;
            swap(lt);
            return *this;
        }

        List(List&& lt) {
            swap(lt);
        }

        iterator begin() {//第一个结点
            return iterator(head->next);
        }

        const_iterator begin() const {
            return const_iterator(head->next);
        }

        iterator end() {
            return iterator(head);//返回虚拟头部结点
        }

        const_iterator end() const {
            return const_iterator(head);//虚拟头部结点
        }

        //在pos位置插入一个val 
        void insert(iterator pos, const T& val) {
            assert(pos.pnode);//先断言结点位置存在, 不存在就无法插入
            Node* cur = pos.pnode;//先拿取到结点指针
            Node* pre = cur->pre;
            Node* newnode = new Node(val);//创建新的结点

            pre->next = newnode;
            newnode->pre = pre;
            //新的结点连接pre
            newnode->next = cur;
            cur->pre = newnode;
            //新的结点连接cur
        }

        void push_back(const T& val) {
            //Node* pTail = head->pre;
            //Node* newnode = new Node(val);
            连接到尾部
            //pTail->next = newnode;
            //newnode->pre = pTail;
            成环连接到head上
            //newnode->next = head;
            //head->pre = newnode;
            insert(end(), val);
        }
         
        void push_front(const T& val) {
            insert(begin(), val);
        }

        void pop_front() {
            erase(begin());
        }

        void pop_back() {
            erase(--end());
        }

        //删除pos迭代器位置元素返回下一个元素
        iterator erase(iterator pos) {
            assert(pos.pnode);//存在才可以做删除操作
            assert(pos != end());
            //拿取到前面一个结点和后一个结点
            Node* pre = pos.pnode->pre;
            Node* next = pos.pnode->next;

            //删除现在iterator
            delete pos.pnode;

            pre->next = next;
            next->pre = pre;
            return iterator(next);
        }
        void clear() {
            Node* p = head->next, *q;
            while (p != head) {
                q = p->next;
                delete p;
                p = q;
            }
            delete head;
        }

        size_t size() {
            size_t ans = 0;
            Node* p = head->next;
            while (p != head) {
                ans += 1;
                p = p->next;
            }
            return ans;
        }

        ~List() {
            if (head != nullptr)
                clear();
            head = nullptr;
        }
    private:
        Node* head;//头部指针指向头部结点
    };

    template<class InputIterator, class Function>
    void for_each(InputIterator first, InputIterator last, Function f) {
        while (first != last) {
            f(*first++);
        }
    }
    template<class T>
    struct Print {
        void operator()(const T& val) const {
            cout << val << " ";
        }
    };
}

template<class T>
void PrintList(tyj::List<T>& lt) {
    tyj::for_each(lt.begin(), lt.end(), tyj::Print<T>());
    cout << endl;
}

// 测试List的构造
void TestList1()
{
    tyj::List<int> l1;
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    tyj::List<int> l3(array, array + sizeof(array) / sizeof(array[0]));
    PrintList(l3);
    tyj::List<int> l4(l3);
    PrintList(l4);
    l1 = l4;
    PrintList(l1);
}

void TestList2()
{
    // 测试PushBack与PopBack
    tyj::List<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    PrintList(l);
    l.pop_back();
    l.pop_back();
    PrintList(l);
    l.pop_back();
    cout << l.size() << endl;
    // 测试PushFront与PopFront
    l.push_front(1);
    l.push_front(2);
    l.push_front(3);
    PrintList(l);
    l.pop_front();
    l.pop_front();
    PrintList(l);
    l.pop_front();
    cout << l.size() << endl;
}

void TestList3()
{
    int array[] = { 1, 2, 3, 4, 5 };
    tyj::List<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto pos = l.begin();
    l.insert(l.begin(), 0);
    PrintList(l);

    ++pos;
    l.insert(pos, 2);
    PrintList(l);
    l.erase(l.begin());
    l.erase(pos);
    PrintList(l);
    // pos指向的节点已经被删除，pos迭代器失效
    cout << *pos << endl;
    auto it = l.begin();
    while (it != l.end())
    {
        it = l.erase(it);
    }
    cout << l.size() << endl;
}

int main() {

    //tyj::List<int> lt;
    //for (int i = 0; i < 5; ++i) {
    //    lt.push_back(i);
    //}

    //PrintList(lt);
    //int arr[5] = { 1, 2, 3, 4, 5 };
    //tyj::List<int> lt2(arr, arr + 5);

    //PrintList(lt2);
    /*TestList1();*/

    /*TestList2();*/

    TestList3();
    return 0;
}

六. 总结

就list对比vector而言, list更能够体现出来迭代器的设计重要性

本质来说STL的list底层就是一个双向循环的链表(数据结构)而已, 其中最最有价值的部分是 iterator的设计上面. iterator是如何粘合容器 + 算法的，这一点特别的重要

**首先我们写链表需要先封装出来一个ListNode结构体: **

我们需要管理ListNode 的指针于是我们需要设计出ListIterator类来支持各种指针的运算符重载，来支持特定的容器遍历方式，粘合算法*

** 写STL 或者写一些小东西的经验之谈**

首先看是否存在一定的框架，或者官方文档，如果存在，将其总体框架分成组件，将重要组件分别设计实现，针对重要的接口进行文档阅读，分析实现.

写出框架简单测试，框架没有问题之后我们可以看见小小的效果，喜悦心理，然后再慢慢的一点一点的啃食重点接口。。写完接口要及时测试

**最终，对于整体代码进行各种特别情景下的测试。。。 **找debug

感谢你阅读完了小杰的本篇文章，小杰后序还会根据自身掌握水平持续推出一些STL的设计书写思路，如果您觉着小杰写的还不错，劳烦关注支持一下，非常感谢，最后还是祝福大家都学习的学业专业有成，工作的都升职加薪

标签：面试后端数据结构

本文转载自: https://blog.csdn.net/weixin_53695360/article/details/123647344
版权归原作者 小杰312 所有，如有侵权，请联系我们删除。

STL设计之链表设计,分块分组件分析,迭代器设计思路

前言.

一. 思考关于list的迭代器的设计

二. 重要函数原型分析理解,有了这些先写出来看看效果

迭代器框架必备函数刨析

List框架必备函数刨析

三. 搭出大体框架

四. 函数细节分块分析 (和vector差不大多)

区间范围range构造

swap: 非常纯粹简单的换, 将你的成员换给我, 我就成了你，你就成为了我

拷贝构造 (因为有了swap, 我自身初始化为nullptr 避免野指针, 然后将复用range构造代码构造出来的tmp对象换来构造自身)

赋值重载

移动构造(抢夺将亡对象的堆区资源进行构造)

写完insert() + erase()接口，相当于是写好了六个接口

insert()

push_back() 复用insert函数

push_front() 复用insert函数

erase();

pop_back() 复用erase

pop_front() 复用erase

五. 总体代码 + 测试

六. 总结

发表评论

“STL设计之链表设计,分块分组件分析,迭代器设计思路”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航