STL-list的使用及其模拟实现

news/2024/9/22 18:11:56/

      在C++标准库中，list 是一个双向链表容器，用于存储一系列元素。与 vector 和 deque 等容器不同，list 使用带头双向循环链表的数据结构来组织元素，因此list插入删除的效率非常高。

list的使用

list的构造函数

list迭代器

list的成员函数

list的模拟实现

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

    list_node(const T& x=T())
        :_next(nullptr)
        , _prev(nullptr)
        , _data(x)
    {}
};
template<class T,class Ref,class Ptr>
struct _list_iterator {
    typedef list_node<T> node;
    typedef _list_iterator<T,Ref,Ptr> self;
    node* _node;
    _list_iterator(node* n)
        :_node(n)
    {}

    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};

/*template<class T>
struct _list_const_iterator {
    typedef list_node<T> node;
    typedef _list_const_iterator<T> self;
    node* _node;
    _list_const_iterator(node* n)
        :_node(n)
    {}

    const T& operator*() {
        return _node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._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;
    //typedef _list_const_iterator<T> const_iterator;
    typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
    typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
    /*reverse_iterator rbegin()
    {
        return reverse_iterator(_head->_prev);
    }

    reverse_iterator rend()
    {
        return reverse_iterator(_head);
    }*/
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    iterator begin() {
        //iterator it(_head->next);
        //return it;
        return iterator(_head->_next);
    }
    const_iterator begin() const{
        return const_iterator(_head->_next);
    }
    iterator end() {
        //iterator it(_head);
        //return it;
        return iterator(_head);
    }
    const_iterator end() const{
        return const_iterator(_head);
    }
    void empty_init() {
        _head = new node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    list() {
        empty_init();
    }

    template <class Iterator>
    list(Iterator first, Iterator last)
    {
        empty_init();
        while (first != last) 
        {
            push_back(*first);
            ++first;
        }
    }
    // lt2(lt1)
    /*list(const list<T>& lt) {
        empty_init();
        for (auto e : lt) {
            push_back(e);
        }
    }*/
    void swap(list<T>& tmp) {
        std::swap(_head, tmp._head);
    }
    list(const list<T>& lt) {
        empty_init();

        list<T> tmp(lt.begin(), lt.end());
        swap(tmp);
    }
    //lt1=lt3
    list<T>& operator=(list<T> lt) {
        swap(lt);
        return *this;
    }
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }
    void clear() {
        iterator it = begin();
        while (it != end()) {
            //it = erase(it);
            erase(it++);
        }
    }
    void push_back(const T& x) {
        /*node* tail = _head->_prev;
        node* new_node = new node(x);

        tail->_next = new_node;
        new_node->_prev = tail;
        new_node->_next = _head;
        _head->_prev = new_node;*/
        insert(end(), x);

    }
    void push_front(const T& x) {
        insert(begin(), x);
    }
    void pop_back() {
        erase(--end());
    }
    void pop_front() {
        erase(begin());
    }
    void insert(iterator pos,const T& x) {
        node* cur = pos._node;
        node* prev = cur->_prev;

        node* new_node = new node(x);
        prev->_next = new_node;
        new_node->_prev = prev;
        new_node->_next = cur;
        cur->_prev = new_node;
    }
    //会导致迭代器失效 pos
    iterator erase(iterator pos, const T& x=0) {
        assert(pos != end());
        node* prev = pos._node->_prev;
        node* next = pos._node->_next;
        prev->_next = next;
        next->_prev = prev;
        delete pos._node;

        return iterator(next);
    }
private:
    node* _head;
};

迭代器和成员函数的模拟实现

template<class T,class Ref,class Ptr>
struct _list_iterator {
    typedef list_node<T> node;
    typedef _list_iterator<T,Ref,Ptr> self;
    node* _node;
    _list_iterator(node* n)
        :_node(n)
    {}

    Ref operator*() {
        return _node->_data;
    }
    Ptr operator->() {
        return &_node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};

/*template<class T>
struct _list_const_iterator {
    typedef list_node<T> node;
    typedef _list_const_iterator<T> self;
    node* _node;
    _list_const_iterator(node* n)
        :_node(n)
    {}

    const T& operator*() {
        return _node->_data;
    }
    self& operator++() {
        _node = _node->_next;
        return *this;
    }
    self& operator--() {
        _node = _node->_prev;
        return *this;
    }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator==(const self& s) {
        return _node == s._node;
    }
    bool operator!=(const self& s) {
        return _node != s._node;
    }

};*/

迭代器共有两种：

1.迭代器要么就是原生指针
2.迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为

迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。这样就不用专门写两种不同类型的迭代器，泛型编程减少了代码的复用，提高了效率。

list的构造函数

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

list的拷贝构造

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

void swap(list<T>& tmp) {
    std::swap(_head, tmp._head);
}
list(const list<T>& lt) {
    empty_init();

    list<T> tmp(lt.begin(), lt.end());
    swap(tmp);
}

list的析构函数

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

赋值运算符重载

//lt1=lt3
list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

list的插入和删除


void push_back(const T& x) {
    /*node* tail = _head->_prev;
    node* new_node = new node(x);

    tail->_next = new_node;
    new_node->_prev = tail;
    new_node->_next = _head;
    _head->_prev = new_node;*/
    insert(end(), x);

}
void push_front(const T& x) {
    insert(begin(), x);
}
void pop_back() {
    erase(--end());
}
void pop_front() {
    erase(begin());
}
void insert(iterator pos,const T& x) {
    node* cur = pos._node;
    node* prev = cur->_prev;

    node* new_node = new node(x);
    prev->_next = new_node;
    new_node->_prev = prev;
    new_node->_next = cur;
    cur->_prev = new_node;
}
//会导致迭代器失效 pos
iterator erase(iterator pos, const T& x=0) {
    assert(pos != end());
    node* prev = pos._node->_prev;
    node* next = pos._node->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;

    return iterator(next);
}

清空list中所有元素

void clear() {
    iterator it = begin();
    while (it != end()) {
        //it = erase(it);
        erase(it++);
    }
}

list迭代器失效

      迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

      解决方法：可以使用 erase 函数的返回值，它会返回一个指向下一个有效元素的迭代器。

list和vector区别

底层实现：

      list 通常是一个双向链表，每个节点都包含了数据和指向前一个和后一个节点的指针。这使得在任何位置进行插入和删除操作都是高效的，但随机访问和内存占用可能相对较差。
     vector 是一个动态数组，元素在内存中是连续存储的。这使得随机访问非常高效，但插入和删除操作可能需要移动大量的元素，效率较低。

插入和删除：

     在 list 中，插入和删除操作是高效的，无论是在容器的任何位置还是在开头和结尾。这使得 list 在需要频繁插入和删除操作时非常适用。
     在 vector 中，插入和删除操作可能需要移动元素，特别是在容器的中间或开头。因此，当涉及大量插入和删除操作时，vector 可能不如 list 效率高。

随机访问：

list 不支持随机访问，即不能通过索引直接访问元素，必须通过迭代器逐个遍历。
vector 支持随机访问，可以通过索引快速访问元素，具有良好的随机访问性能。

迭代器失效：

在 list 中，插入和删除操作不会导致迭代器失效，因为节点之间的关系不会改变。
在 vector 中，插入和删除操作可能导致内存重新分配，从而使原来的迭代器失效。

综上所述，如果你需要频繁进行(头部和中间)插入和删除操作，而对于随机访问性能没有特别高的要求，可以选择list；如果想要随机访问以及尾插和尾删vector是更好的选择。 


http://www.ppmy.cn/news/1428560.html

相关文章

【QT教程】QML传感器融合应用

【QT教程】QML传感器融合应用

QML传感器融合应用 使用AI技术辅助生成 QT界面美化视频课程 QT性能优化视频课程 QT原理与源码分析视频课程 QT QML C扩展开发视频课程 免费QT视频课程 您可以看免费1000个QT技术视频 免费QT视频课程 QT统计图和QT数据可视化视频免费看 免费QT视频课程 QT性能优化视频免费看 免…
阅读更多...
亚马逊测评自养号策略：手机与PC结合的重要性

亚马逊测评自养号策略：手机与PC结合的重要性

亚马逊测评的核心关键技术在于精心培养买家账号&#xff0c;之所以称之为核心关键&#xff0c;原因在于测评下单的首要条件是拥有一个活跃的买家账号。买家账号并非一次性使用&#xff0c;因此&#xff0c;养号过程显得至关重要。然而&#xff0c;在养号的过程中&#xff0c;很…
阅读更多...
【Java EE】文件内容的读写——数据流

【Java EE】文件内容的读写——数据流

目录 1.InputStream概述 1.1方法 2.FileInputStream概述 2.1构造方法 2.2代码示例 2.3.利用Scanner进行字符读取 3.OutputStream概述 3.1方法 3.2利用OutputStreamWriter进行字符写入 3.3利用PrintWriter找到我们熟悉的方法 1.InputStream概述 1.1方法 修饰符及返回…
阅读更多...
第20天：信息打点-红蓝队自动化项目资产侦察企查产权武器库部署网络空间

第20天：信息打点-红蓝队自动化项目资产侦察企查产权武器库部署网络空间

第二十天 一、工具项目-红蓝队&自动化部署 自动化-武器库部署-F8x 项目地址&#xff1a;https://github.com/ffffffff0x/f8x 介绍&#xff1a;一款红/蓝队环境自动化部署工具,支持多种场景,渗透,开发,代理环境,服务可选项等.下载&#xff1a;wget -O f8x https://f8x.io…
阅读更多...
开发语言漫谈-rust

开发语言漫谈-rust

前面介绍C语言家族时忘掉了rust&#xff0c;紧急补一篇。我们称C语言家族是指他们的语法相似&#xff0c;类似这样的&#xff1a; if(){}else{}就是C家族的。C、C的传统领域就是系统底层、硬件接口方向。C/C没有垃圾内存回收机制&#xff0c;完全靠程序员的自觉天赋&#xff0…
阅读更多...
IDEA gradle新增依赖报Could not resolve symbol “XXX“错误

IDEA gradle新增依赖报Could not resolve symbol “XXX“错误

问题 idea 新增依赖后一直报错Could not resolve symbol “XXX”&#xff0c;无法成功下载依赖 原因 未知 解决方案 暂时的解决方案是使用控制台输命令编译&#xff0c;成功编译后依赖也下载下来了&#xff0c;猜测应该是idea的问题&#xff0c;先记录下&#xff0c;后续找…
阅读更多...
【java、微服务】MQ

【java、微服务】MQ

同步通讯 优点 时效性较强&#xff0c;可以立即得到结果 问题 微服务间基于Feign的调用就属于同步方式&#xff0c;存在一些问题。 耦合度高。每次加入新的需求&#xff0c;都要修改原来的代码资源浪费。调用链中的每个服务在等待响应过程中&#xff0c;不能释放请求占用的…
阅读更多...
Spring-dataSource事务案例分析-使用事务嵌套时，一个我们容易忽略的地方

Spring-dataSource事务案例分析-使用事务嵌套时，一个我们容易忽略的地方

场景如下&#xff1a; A_Bean 中的方法a()中调用B_Bean的b();方法都开启了事务&#xff0c;使用的默认的事务传递机制&#xff08;即&#xff1a;属于同一事务&#xff09;&#xff1b; 如下两种场景会存在较大的差异&#xff1a; 在b()方法中出现了异常&#xff0c;在b()中进…
阅读更多...
最新文章

Copyright @ 2022~2023