C++_list

2019-09-26 0 条评论 37 次阅读 0 人点赞

list

1.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来说这可能是一个重要的因素)

2. list使用

2.1 list的构造

构造函数 接口说明
list() 构造空的list
list(size_t type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list

2.2 list迭代器

函数声明 接口说明
begin + end 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend 返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的 reverse_iterator,即begin位置

【注意】

  1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  2. rbegin和rend为反向迭代器,对迭代器执行++操作,迭代器向前移动

2.3 list capacity

函数声明 接口说明
empty 检测list是否为空,是返回true,否则返回false
size 返回list中有效节点个数

2.4 list element access

函数声明 接口说明
front 返回list的第一个节点中 值的引用
back 返回list的最后一个节点中 值的引用

2.5 list modifiers

函数声明 接口说明
push_front 在list首元素前插入值为val的元素
pop_front 删除list中第一个元素
push_back 在list尾部插入值为val的元素
pop_back 删除list中最后一个元素
insert 在list position位置中插入值为val的元素
erase 删除list position位置的元素
swap 交换两个list中的元素
clear 清空list中的有效元素

2.6 list迭代器失效

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

3. 模拟实现list

namespace km{
    template <class T>
    class ListNode{
    public:
        T m_val;
        ListNode *m_prev;
        ListNode *m_next;

        ListNode(const T &val = T()):
        m_prev(nullptr),
        m_next(nullptr),
        m_val(val){

        }
    };

    /*
List 的迭代器
迭代器有两种实现方式,具体应根据容器底层数据结构实现:
    1. 原生态指针,比如:vector
    2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:
        1. 指针可以解引用,迭代器的类中必须重载operator*()
        2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
        3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前移动,所以需要重载,如果是forward_list就不需要重载--
        4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
*/

    template <class T>
    class list{
        ListNode<T> *m_head;

        void creatHead(){
            m_head = new ListNode<T>;
            m_head->m_next = m_head->m_prev = m_head;
        }

    public:
        class iterator{//构建迭代器类, 重载必要的操作符
        public:
            ListNode<T> *m_pos;

            iterator(ListNode<T> *val = nullptr):
            m_pos(val){
            }

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

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

            iterator operator++(){
                m_pos = m_pos->m_next;
                return *this;
            }

            iterator operator++(int){
                iterator tmp = *this;
                m_pos = m_pos->m_next;
                return tmp;
            }

            iterator operator--(){
                m_pos = m_pos->m_prev;
                return *this;
            }

            iterator operator--(int){
                iterator tmp = *this;
                m_pos = m_pos->m_prev;
                return tmp;
            }

            bool operator==(const iterator& ci) const {
                return m_pos == ci.m_pos;
            }

            bool operator!=(const iterator& ci) const {
                return m_pos != ci.m_pos;
            }
        };

        list(){
            creatHead();
        }

        list(int n, const T &val = T()){
            creatHead();

            int i;
            for(i = 0; i < n; i++){
                Bush_back(val);
            }
        }

        list(iterator start, iterator finish){
            creatHead();

            Inser(End(), start, finish);
        }

        list(T *start, T *finish){
            creatHead();
            Insert(End(), start, finish);
        }

        list(list<T> &l){
            creatHead();
            Insert(End(), l.Begin(), l.End());
        }

        list<T>& operator=(const list<T> l){
            this->swap(l);
            return *this;
        }

        ~list(){
            Erase(Begin(), End());
            delete m_head;
        }

        void Clear(){
            Erase(Begin(), End());
        }

        void push_back(const T &val){
            Insert(End(), val);
        }

        void Push_pront(const T &val){
            Insert(Begin(), val);
        }

        void Pop_back(const T &val){
            Erase(--End());
        }

        void Pop_front(){
            Erase(Begin());
        }

        iterator Insert(iterator pos, const T &val) {
            ListNode<T> *cur = new ListNode<T>;
            ListNode<T> *npos = pos.m_pos;

            cur->m_val = val;

            cur->m_prev = npos->m_prev;
            cur->m_prev->m_next = cur;

            cur->m_next = npos;
            npos->m_prev = cur;

            return cur;
        }

        iterator Insert(iterator pos, T* start, T *finish){
            T *tmp;
            iterator tmpit = --pos;//pos放到插入前的前一个元素
            pos++;

            for(tmp = start; tmp != finish; tmp++){
                Insert(pos, *tmp);
            }

            return ++tmpit;//插入后恢复
        }

        iterator Insert(iterator pos, iterator start, iterator end){
            iterator tmp;
            iterator tmpit = --pos;
            pos++;

            for(tmp = start; tmp != end; tmp++){
                Insert(pos, *tmp);
            }

            return ++tmpit;
        }

        iterator Erase(iterator pos){
            ListNode<T> *cur = pos.m_pos;
            ListNode<T> *nextpos = cur->m_next;

            cur->m_next->m_prev = cur->m_prev;
            cur->m_prev->m_next = cur->m_next;
            delete cur;

            return nextpos;
        }

        iterator Begin(){
            return m_head->m_next;
        }

        iterator End(){
            return m_head;
        }

    };
};

4. list与vector进行比较

list vector
底层结构 带头节点的双向循环链表 动态顺序表,一段连续空间
随机访问 不支持随机访问,访问某个元素效率O(N) 支持随机访问,访问某个元素效率O(1)
插入和删除 任意位置插入和删除效率高,不需要搬移元素,时间复杂度O(1) 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N), 插入时有可能需要增容(增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低)
空间利用率 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低 底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高
迭代器 对原生态指针(节点指针)进行封装 原生态指针
迭代器失效 插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响 在插入元素时,要给所有的迭代器重新赋值,因为插入元素可能重新扩容,导致原来的迭代器失效,删除时,当前迭代器需要重新加载赋值否则会失效
使用场景 大量插入和删除操作,不关心随机访问 需要高效存储,支持随机访问,不关心插入删除效率

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)