不会飞的纸飞机
  1. 当前位置：
  2. 首页
  3. C++
  4. STL学习笔记（1）- list的简易仿真

STL学习笔记（1）- list的简易仿真

原创
2022-11-24
4698
0

ist的实际上是一个双向链表，本篇文章简单的实现一个list

首先创建一个节点模板类：

template <typename T>
class MListNode
{
public:
    MListNode<T> *next = nullptr;
    MListNode<T> *prev = nullptr;
    T data;
};

接下来创建迭代器类，迭代器中包含一个节点的指针，并通过该指针来完成自增自减、比较、和获取值等效果。

template <typename T>
class MList;

template <typename T>
class MListIterator
{
public:
    MListIterator(MListNode<T> *p) : node(p){}
    MListIterator() {}
    ~MListIterator() {}

    // 重载前++
    MListIterator& operator++ () {
        node = node->next;
        return *this;
    }

    // 重载后++
    MListIterator operator++ (int) {
        MListIterator temp = *this;
        node = node->next;
        return temp;
    }

    // 重载前--
    MListIterator& operator-- () {
        node = node->prev;
        return *this;
    }

    // 重载后--
    MListIterator operator-- (int) {
        MListIterator temp;
        --*this;
        return temp;
    }

    // 重载*
    T& operator* () {
        return node->data;
    }

    // 重载->
    T* operator-> () {
        return &(node->data);
    }

    // 重载 ==
    bool operator== (const MListIterator &itor) {
        return (node == itor.node);
    }

    // 重载 !=
    bool operator!= (const MListIterator& itor) {
        return (node != itor.node);
    }

    friend class MList<T>;
private:
    MListNode<T> *node = nullptr;
};

最后实现自己的list列表类，列表初始化时，创建一个头节点（尾节点）并且头尾指针指向自己

template <typename T>
class MList
{
public:
    typedef  MListIterator<T> iterator;
public:
    MList() {
        m_Node = new MListNode<T>;
        m_Node->next = m_Node;
        m_Node->prev = m_Node;
    }
    ~MList() {
        while (m_Length)
            pop_back();
    }

    iterator begin(void) {
        return m_Node->next;
    }

    iterator end(void) {
        return m_Node;
    }

    // 尾部插入数据
    void push_back(const T& d) {
        insert(end(), d);
    }
    // 尾部删除
    void pop_back(void) {
        if (m_Length <= 0)
            return;

        erase(--end());
    }

    // 顶部插入数据
    void push_front(const T& d) {
        insert(begin(), d);
    }
    // 顶部删除
    void pop_front(void) {
        if (m_Length <= 0)
            return;

        erase(begin());
    }

    // 任意位置插入
    void insert(iterator& itor, const T& d) {
        MListNode<T> *node = new MListNode<T>;
        node->prev = itor.node->prev;
        node->next = itor.node;
        node->data = d;

        itor.node->prev->next = node;
        itor.node->prev = node;
        m_Length++;
    }

    // 删除元素
    void erase(iterator& itor) {
        itor.node->prev->next = itor.node->next;
        itor.node->next->prev = itor.node->prev;
        delete itor.node;

        m_Length--;
    }

    // 获取大小
    int size(void) {
        return m_Length;
    }

    // 查找
    iterator find(T d) {
        for (MList<int>::iterator itor = begin(); itor != end(); ++itor)
            if (d == *itor)
                return itor;

        return end();
    }

private:
    MListNode<T> *m_Node = nullptr;
    int m_Length = 0;
};

这里 typedef MListIterator iterator; 定义了list的迭代器。并简单实现了 begin() 、end() 、 push_back() 、push_front() 、pop_back() 、pop_front() 等插入删除节点的函数，包括获取容器存储数据大小的函数 size() 和查找函数 find()

测试代码如下：

MList<int> nList;
nList.push_back(10);
nList.push_back(20);
nList.push_back(30);
nList.push_front(0);

for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
    std::cout << *itor << std::endl;
std::cout << "List Size is " << nList.size() << std::endl;
std::cout << "----------------------------------------------------" << std::endl;

nList.pop_back();
nList.pop_front();

for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
    std::cout << *itor << std::endl;
std::cout << "List Size is " << nList.size() << std::endl;
std::cout << "----------------------------------------------------" << std::endl;

if (nList.find(10) != nList.end())
    std::cout << "Finded Number 10" << std::endl;
else
    std::cout << "Can't Find Number 10" << std::endl;

if (nList.find(0) != nList.end())
    std::cout << "Finded Number 0" << std::endl;
else
    std::cout << "Can't Find Number 0" << std::endl;

运行结果：
0
10
20
30
List Size is 4
----------------------------------------------------
10
20
List Size is 2
----------------------------------------------------
Finded Number 10
Can’t Find Number 0

程序的完整代码如下：

#include <iostream>
#include <stdlib.h>
#include <list>

template <typename T>
class MListNode
{
public:
    MListNode<T> *next = nullptr;
    MListNode<T> *prev = nullptr;
    T data;
};

template <typename T>
class MList;

template <typename T>
class MListIterator
{
public:
    MListIterator(MListNode<T> *p) : node(p){}
    MListIterator() {}
    ~MListIterator() {}

    // 重载前++
    MListIterator& operator++ () {
        node = node->next;
        return *this;
    }

    // 重载后++
    MListIterator operator++ (int) {
        MListIterator temp = *this;
        node = node->next;
        return temp;
    }

    // 重载前--
    MListIterator& operator-- () {
        node = node->prev;
        return *this;
    }

    // 重载后--
    MListIterator operator-- (int) {
        MListIterator temp;
        --*this;
        return temp;
    }

    // 重载*
    T& operator* () {
        return node->data;
    }

    // 重载->
    T* operator-> () {
        return &(node->data);
    }

    // 重载 ==
    bool operator== (const MListIterator &itor) {
        return (node == itor.node);
    }

    // 重载 !=
    bool operator!= (const MListIterator& itor) {
        return (node != itor.node);
    }

    friend class MList<T>;
private:
    MListNode<T> *node = nullptr;
};

template <typename T>
class MList
{
public:
    typedef  MListIterator<T> iterator;
public:
    MList() {
        m_Node = new MListNode<T>;
        m_Node->next = m_Node;
        m_Node->prev = m_Node;
    }
    ~MList() {
        while (m_Length)
            pop_back();
    }

    iterator begin(void) {
        return m_Node->next;
    }

    iterator end(void) {
        return m_Node;
    }

    // 尾部插入数据
    void push_back(const T& d) {
        insert(end(), d);
    }
    // 尾部删除
    void pop_back(void) {
        if (m_Length <= 0)
            return;

        erase(--end());
    }

    // 顶部插入数据
    void push_front(const T& d) {
        insert(begin(), d);
    }
    // 顶部删除
    void pop_front(void) {
        if (m_Length <= 0)
            return;

        erase(begin());
    }

    // 任意位置插入
    void insert(iterator& itor, const T& d) {
        MListNode<T> *node = new MListNode<T>;
        node->prev = itor.node->prev;
        node->next = itor.node;
        node->data = d;

        itor.node->prev->next = node;
        itor.node->prev = node;
        m_Length++;
    }

    // 删除元素
    void erase(iterator& itor) {
        itor.node->prev->next = itor.node->next;
        itor.node->next->prev = itor.node->prev;
        delete itor.node;

        m_Length--;
    }

    // 获取大小
    int size(void) {
        return m_Length;
    }

    // 查找
    iterator find(T d) {
        for (MList<int>::iterator itor = begin(); itor != end(); ++itor)
            if (d == *itor)
                return itor;

        return end();
    }

private:
    MListNode<T> *m_Node = nullptr;
    int m_Length = 0;
};

int main(int argc, char** argv)
{
    MList<int> nList;
    nList.push_back(10);
    nList.push_back(20);
    nList.push_back(30);
    nList.push_front(0);

    for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
        std::cout << *itor << std::endl;
    std::cout << "List Size is " << nList.size() << std::endl;
    std::cout << "----------------------------------------------------" << std::endl;

    nList.pop_back();
    nList.pop_front();

    for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
        std::cout << *itor << std::endl;
    std::cout << "List Size is " << nList.size() << std::endl;
    std::cout << "----------------------------------------------------" << std::endl;

    if (nList.find(10) != nList.end())
        std::cout << "Finded Number 10" << std::endl;
    else
        std::cout << "Can't Find Number 10" << std::endl;

    if (nList.find(0) != nList.end())
        std::cout << "Finded Number 0" << std::endl;
    else
        std::cout << "Can't Find Number 0" << std::endl;

    system("pause");
    return 0;
}
不会飞的纸飞机
扫一扫二维码，了解我的更多动态。
上一篇文章：c++11学习笔记（8）- 可变参数宏、函数、模板
下一篇文章：STL学习笔记（2）- vector和deque

不会飞的纸飞机

不积跬步，无以至千里；
不积小流，无以成江海。
职业：
C++/Qt软件工程师
居住地：
北京市
联系方式：
qq514200399
文章分类
Qt53篇
C++17篇
数据库10篇
多线程16篇
杂七杂八11篇
关注我
微信公众号
最新博客
1
异地过年，我要用它看春晚！- Qt趣味开发之基于QtAV的电视播放器
2
Qt趣味开发之打造一个3D名字渲染小工具
3
圣诞节到了！！你的桌面下雪了吗？？ - Qt趣味开发之让你的桌面下雪
4
基于QGraphicsView的简易画板EasyCanvas -- 第二版
5
Qt与OpenGL趣味开发 - 绘制炫酷倒影
6
蒙皮骨骼动画
文章精选
1
自定义QGraphicsItem实现平移、改变尺寸和旋转
2
Qt 图片预览（等比例显示、放大、缩小、平移图像）显示
3
使用Qt播放音频
4
7.QML中的信号和信号处理
5
8.QML中的组件Component
6
Qt中的线程池QThreadPool
打赏
您的支持就是我最大的动力
微信扫一扫
支付宝扫一扫