【C++】一篇文章带你深入了解list

目录

• 一、list的介绍
• 二、 标准库中的list类
• • 2.1 list的常见接口说明
  • • 2.1.1 list对象的常见构造
    • • 2.1.1.1 无参构造函数
      • 2.1.1.2 有参构造函数(构造并初始化n个val)
      • 2.1.1.3 有参构造函数(使用迭代器进行初始化构造)
      • 2.1.1.4 拷贝构造函数
      • 2.1.2 list iterator的使用
      • • 2.1.2.1 begin() + end()
        • 2.1.2.2 rbegin() + rend()
        • 2.1.3 list对象的容量操作
        • • 2.1.3.1 empty()函数
          • 2.1.3.2 size()函数
          • 2.1.4 list对象的增删查改及访问
          • • 2.1.4.1 push_front()函数
            • 2.1.4.2 pop_front()函数
            • 2.1.4.3 push_back()函数
            • 2.1.4.4 pop_back()函数
            • 2.1.4.5 insert()函数
            • 2.1.4.6 erase()函数
            • 2.1.4.7 swap()函数
            • 2.1.4.8 clear()函数
            • 2.1.4.9 front()函数 + back()函数
            • 2.1.5 list的迭代器失效
            • 三、list的模拟实现
            • • 3.1 list 节点类的实现
              • 3.2 list 中默认成员函数的实现
              • 3.3 list 中 size、empty 和 swap 函数的实现
              • 3.4 list 中 迭代器类 的实现
              • 3.5 list 中 迭代器 、 范围构造函数 和 clear 函数 的实现
              • 3.6 list 中 insert 和 erase 的实现
              • 3.7 list 中 push_back、pop_back、push_front 和 pop_front 函数的实现
              • 3.8 list 中 反向迭代器类 和 反向迭代器 的实现
              • 3.9 list 实现汇总及函数测试
              • 四、 list 与 vector 的对比
              • 结尾

                一、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对象的常见构造

                2.1.1.1 无参构造函数

                list();

                int main(){list l;return 0;}

                ---

                2.1.1.2 有参构造函数(构造并初始化n个val)

                list (size_type n, const value_type& val = value_type());

                int main(){list l(5, 4);return 0;}

                ---

                2.1.1.3 有参构造函数(使用迭代器进行初始化构造)

                template   list (InputIterator first, InputIterator last);

                int main(){string s("Love");list l(s.begin(), s.end());return 0;}

                ---

                2.1.1.4 拷贝构造函数

                list (const list& x);

                int main(){list l1(5,6);list l2(l1);return 0;}

                ---

                2.1.2 list iterator的使用

                2.1.2.1 begin() + end()

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

                int main(){list l;for (int i = 0; i _prev = prev;            prev->_next = next;            // 删除节点            delete cur;            cur = nullptr;            // 减少节点数目            --_size;            // 返回删除节点的下一个位置            // return iterator(next);            return next;        }        void clear()        {            list::iterator lit = begin();            while (lit != end())            {                lit = erase(lit);            }        }        void swap(list& l)        {            std::swap(_head, l._head);            std::swap(_size, l._size);        }    private:        void CreateHead()        {            _head = new Node();            _head->_next = _head;             _head->_prev = _head;            _size = 0;        }        PNode _head;    // 头结点        int _size;      // 记录链表中节点的个数    };    struct AA    {        AA(int a1 = 0 , int a2 = 0)            :_a1(a1)            ,_a2(a2)        {}        int _a1;        int _a2;    };    //template    //void print_list(const list& l)    //{    //    // list未实例化的类模板，编译器不能去他里面去找    //    // 那么编译器就无法确定这里的    //    // const_iterator是静态变量还是内嵌类型    //    // 加上typename就相当于告诉编译器这里是内嵌类型    //    // 等list初始化后再到类中去取    //    typename list::const_iterator it = l.begin();    //    while (it != l.end())    //    {    //        cout         typename Container::const_iterator it = l.begin();        while (it != l.end())        {            cout         list            cout             cout             cout         list            cout             e += 10;            cout         list            cout             cout             cout         list        list        list            cout             cout             cout         list            cout         list            cout             cout             e *= 10;            cout             cout             cout         list        list            cout