0
0

【C++驾轻就熟】list深入了解及模拟实现

一、list的介绍及使用

list介绍文档

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

二、标准库中的list类

2.1 list的常见接口说明

2.1.1 list对象的常见构造

1.无参构造函数
list();

int main()
{
    list<int> l;

    return 0;
}

2.有参构造函数(构造并初始化n个val)
list (size_type n, const value_type& val = value_type());

int main()
{
    list<int> l(5,10);

    return 0;
}

3.有参构造函数(使用迭代器进行初始化构造)
template <class InputIterator>
      list (InputIterator first, InputIterator last);

int main()
{
    string s("I LOVE YOU");
    list<char> l(s.begin(), s.end());

    return 0;
}

4.拷贝构造函数
list (const list& x);

int main()
{
    list<int> s(5,10);
    list<int> v(s);
    return 0;
}

2.1.2 list iterator的使用

1.begin() + end()

      iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iterator

       iterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator

int main()
{
    list<int> l;
    for (int i = 0; i < 10; i++)
    {
        l.push_back(i);
    }

    list<int>::iterator it = l.begin();
    while (it != l.end())
    {
        *it+=100;
        cout << *it << ' ';
        ++it;
    }

    cout << endl;

    return 0;
}

2.rbegin() + rend()

      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator 

      reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 

int main()
{
    list<int> l;
    for (int i = 0; i < 10; i++)
    {
        l.push_back(i);
    }

    list<int>::reverse_iterator it = l.rbegin();
    while (it != l.rend())
    {
        *it += 100;
        cout << *it << ' ';
        ++it;
    }

    cout << endl;

    return 0;
}

【注意】 :

  1. **begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动 **
  2. ** rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 **
2.1.3 list对象的容量操作

1.empty()函数

bool empty() const;         判断是否为空

int main()
{
    list<int> l;
    cout << l.empty() << endl;

    l.push_back(520);
    cout << l.empty() << endl;

    return 0;
}

2.size()函数

size_type size() const;      获取数据个数

int main()
{
    list<int> l;
    cout << l.size() << endl;

    for (int i = 0; i < 10; i++)
    {
        l.push_back(i);
    }

    cout << l.size() << endl;

    return 0;
}

2.1.4 list对象的增删查改及访问

1.push_front()函数

int main()
{
    list<int> l;

    l.push_front(1);
    l.push_front(2);
    l.push_front(3);
    l.push_front(4);

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    return 0;
}

void push_front (const value_type& val);  头插

2. pop_front()函数

void pop_front();  头删

int main()
{
    list<int> l;

    l.push_front(1);
    l.push_front(2);
    l.push_front(3);
    l.push_front(4);

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    l.pop_front();
    for (auto a : l)
    {
        cout << a << ' ';
    }

    return 0;
}

3. push_back()函数

void push_back (const value_type& val);   尾插

int main()
{
    list<int> l;

    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    return 0;
}

4. pop_back()函数

void pop_back();  尾删

int main()
{
    list<int> l;

    l.push_back(1);
    l.push_back(3);
    l.push_back(1);
    l.push_back(4);

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    l.pop_back();

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;
    return 0;
}

5. insert()函数

iterator insert (iterator position, const value_type& val);
insert()函数能够在position之前插入val，并返回插入数据位置的 iterator 

void insert (iterator position, size_type n, const value_type& val);
insert()函数能够在position之前插入 n 个 val             

template <class InputIterator>
        void insert (iterator position, InputIterator first, InputIterator last);
insert()函数能够在position之前插入一段迭代器区间的数据               


int main()
{
    list<char> l;
    string s("Love");

    l.push_back('y');
    l.push_back('o');
    l.push_back('u');

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    // insert()函数能够在position之前插入val，并返回插入数据位置的 iterator 
    //l.insert(v.begin() + 5, 'v');这是错误的，因为再list中没有支撑迭代器的加法
    cout << *(l.insert(l.begin(), '#')) << endl;

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    // insert()函数能够在position之前插入 n 个 val   
    list<char>::iterator it = l.begin();
    for (size_t i = 0; i < 1; i++)
    {
        ++it;
    }

    l.insert(it, 3, '@');
    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    // insert()函数能够在position之前插入一段迭代器区间的数据               
    l.insert(++l.begin(), s.begin(), s.end());
    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    return 0;
}

6. erase()函数

iterator erase (iterator position);
erase()函数能够删除在position位的的数据，并返回删除数据后面数据位置的 iterator

iterator erase (iterator first, iterator last);
erase()函数能够删除在迭代器区间 [first,last) 的的数据，并返回删除数据后面数据位置的 iterator             

int main()
{
    list<int> l;

    for (int i = 0; i < 10; i++)
    {
        l.push_back(i);
    }

    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    // erase()函数能够删除在position位的的数据
    // 并返回删除数据后面数据位置的 iterator
    cout << *(l.erase(l.begin())) << endl;
    for (auto e : l)
    {
        cout << e << ' ';
    }
    cout << endl;

    // erase()函数能够删除在迭代器区间 [first,last) 的的数据
    // 并返回删除数据后面数据位置的 iterator        
    cout << *(l.erase(++l.begin(), --l.end())) << endl;
    for (auto e : l)
    {
        cout << e << ' ';
    }

    cout << endl;

    return 0;
}

7. swap()函数

void swap (list& x);
交换两个list的数据空间

int main()
{
    list<int> l1(5, 20);
    list<int> l2(7, 5);
    //交换前
    for (auto e : l1)
    {
        cout <<  "l1 :" << e << ' ';
    }
    cout << endl;

    for (auto e : l2)
    {
        cout <<  "l2 :" << e << ' ';
    }
    cout << endl;
    //交换中
    l1.swap(l2);
    //交换后
    for (auto e : l1)
    {
        cout << "l1 :" << e << ' ';
    }
    cout << endl;

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

    return 0;
}

8. clear()函数

void clear();
清除list中的有效数据

int main()
{
    list<int> l(4, 10);
    cout << l.size() << endl;

    l.clear();
    cout << l.size() << endl;

    return 0;
}

9. front()函数 + back()函数

访问list中的第一个数据
      reference front();
const_reference front() const;

访问list中的最后一个数据
       reference back();
const_reference back() const;

int main()
{
    list<int> l;

    for (int i = 0; i < 5; i++)
    {
        l.push_back(i);
    }

    cout << "front:" << l.front() << endl;
    cout << "back:" << l.back() << endl;

    return 0;
}

三、list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

int main()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        // erase()函数执行后，it所指向的节点已被删除
        // 因此it无效，在下一次使用it时，必须先给其赋值
        l.erase(it);
        ++it;
    }

    return 0;
}

// 改正
int main()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        l.erase(it++); // it = l.erase(it);
    }
}

四、list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：

五、list的模拟实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

#include<assert.h>

using namespace std;

namespace lxp
{
    template<class T>
    struct list_node
    {
        list_node<T>* _prev;
        list_node<T>* _next;
        T _val;

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

    // typedef __list_iterator<T, T&, T*> iterator;
    // typedef __list_iterator<T, const T&, const T*> const_iterator;
    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* node)
            :_node(node)
        {}

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

        Ptr operator->()
        {
            return &_node->_val;
        }
        
        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self operator++(int)
        {
            self tmp = _node;
            _node = _node->_next;
            return tmp;
        }

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

        self operator--(int)
        {
            self tmp = _node;
            _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
    {
    public:
        typedef list_node<T> Node;
        typedef _list_iterator<T, T&, T*> iterator;
        typedef _list_iterator<T, const T&, const T*> const_iterator;

        iterator begin()
        {
            return _head->_next;
        }

        iterator end()
        {
            return _head;
        }

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

        const_iterator end() const
        {
            return _head;
        }
        
        list()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
        }

        list(const list<T>& lt)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;

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

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

        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);
            }

            _size = 0;
        }

        void push_back(const T& x)
        {
            insert(end(), x);
        }

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

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

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

        iterator insert(iterator pos, const T& x)
        {
            Node* newnode = new Node(x);
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            
            prev->_next = newnode;
            newnode->_prev = prev;

            newnode->_next = cur;
            cur->_prev = newnode;

            ++_size;
            return newnode;
        }

        iterator erase(iterator pos)
        {
            assert(pos != end());

            Node* cur = pos._node;
            Node* pre = cur->_prev;
            Node* next = cur->_next;

            pre->_next = cur->_next;
            next->_prev = pre;
            
            delete cur;
            _size--;
            
            return next;
        }

        size_t size()
        {
            return _size;
        }

    private:
        Node* _head;
        size_t _size;

    };
}

结尾

如果有什么建议和疑问，或是有什么错误，希望大家可以在评论区提一下。
希望大家以后也能和我一起进步！！
如果这篇文章对你有用的话，请大家给一个三连支持一下！！

谢谢大家收看🌹🌹

标签： c++ 开发语言 数据结构
本文转载自: https://blog.csdn.net/2201_75537851/article/details/142878753
版权归原作者 鲨鱼吃橘子 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++驾轻就熟】list深入了解及模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航