当前位置 博文首页 > Jude_Zhang:C++ STL list

    Jude_Zhang:C++ STL list

    作者:Jude_Zhang 时间:2021-01-30 18:51

    list即双向链表,是C++ STL中的一种容器

    std::list

    <list>

    列表性质

    ??1、双向链表

    ??2、只支持双向顺序访问,不支持下标访问(随机访问迭代器)(元素随机访问)

    ??3、因为不支持随机访问迭代器,所以不能使用std::sort进行排序,需要调用成员函数list::sort

    ??4、在list中任何位置进行插入/删除操作速度都很快

    容器操作

    1、类型别名

    类型 解释
    iterator 此容器类型的迭代器类型
    const_iterator 可以读取元素,但不能修改元素的迭代器类型
    size_type 无符号整数类型,足够保存此种容器类型最大可能容器的大小
    difference_type 带符号整数类型,足够保存两个迭代器之间的距离
    value_type 元素类型
    reference 元素的左值类型;与value_type&含义相同
    const_reference 元素的左值类型,(即const value_type&)

    2、构造list

    ?1)、默认构造

    构造一个没有任何元素的空容器

        list<int> mylist;
    
    ?2)、填充构造

    构造一个含有 n 个元素的容器, 每一个元素被赋值为 val(如果存在 val)

    list<type> mylist( size_type n, const value_type &val );

        list<int> mylist (5); // 含有 5 个元素,每个元素都被执行了默认初始化 (0)
    
        list<int> mylist ( 5, 1314 ); // 含有 5 个元素,每个元素的值都是 1314
    
    ?3)、范围构造

    构造一个容器,具有和范围 [ first, last ) 一样多数量的元素,并且容器内元素顺序与范围内元素顺序对应

    list<type> mylist( Iterator first, Iterator last );

        int myints[5] = { 75, 23, 65, 42, 13 };
    
        list<int> mylist ( myints, myints + 5 ); // 构造一个 list 容器,元素为 myints 内的元素的副本
    
    ?4)、拷贝构造

    构造一个与mylist中的元素与元素顺序相同的容器

    list<type> yourlist( const list &mylist );

        list<int> mylist (5, 1314);
    
        list<int> yourlist ( mylist ); // 将 mylist 的元素拷贝给 yourlist
    
    ?5)、列表构造(列表元素初始化)

    构造一个与il中的元素与元素顺序相同的容器,initializer_list{ }

    list<type> mylist( initializer_list<value_type> il );

        /* 三种写法相同 */
    
        list<int> mylist ( {1, 3, 5} );  //mylist 内的元素为1, 3, 5
    
        list<int> mylist {1, 3, 5};
        
        list<int> mylist = {1, 3, 5}; // 下文 `赋值`中会说明‘=’的作用
    

    3、赋值?(=)

    ?1)拷贝

    将 列表x 拷贝给 列表mylist

    mylist = const list &x;

        list<int> mylist ( {1, 3, 5} );
        // 不需要提前给 x 分配大小 因为 ‘=’ 会把 mylist 中的元素信息全部拷贝过去
        list<int> x;
    
        x = mylist;
    
    ?2)列表拷贝

    通过列表拷贝 initializer_list{ }

    mylist = initializer_list<value_type> il;

        list<int> mylist(3);
        // 注意要为 mylist 分配大小
        mylist = {1, 2, 3};
    

    4、迭代器

    ?1)begin

    返回指向容器第一个元素的迭代器

    ?2)end

    返回一个尾后迭代器,指向尾元素的下一个位置

    用法举例:

    #include <iostream>
    #include <list>
    
    using namespace std;
    
    int main ( void )
    {
        list<int> lk;
    
        for ( int i = 1; i <= 5; i++ ) // 1, 2, 3, 4, 5
            lk.push_back(i);
        
        for ( auto i = lk.begin(); i != lk.end(); i++ )
            cout << *i << " ";
    
        cout << endl;
        
        return 0;
    }
    

    ?4)cbegin

    返回的迭代器类型为const_iterator 所以不可以对迭代器解引用修改

    ?5)cend

    返回的迭代器类型为const_iterator 所以不可以对迭代器解引用修改

    ?5)rbegin

    返回指向容器的尾元素之前位置的迭代器

    ?6)rend

    返回指向容器首元素之前位置的迭代器

    ?7)crbegin

    返回const_iterator

    ?8)crend

    返回const_iterator

    5、空间

    ?1)empty

    返回当前容器是否为空

    ?2)size

    容器中元素的数目

    ?3)max_size

    容器可保存的最大元素数目

    6、访问元素

    ?1)front

    返回对list容器的第一个元素的引用

    ?2)back

    返回对list容器的最后一个元素的引用

    7、修改

    ?1)assign

    assign也是一种赋值方式,和初始化赋值不同的是:assign允许我们从一个不同但相容类型赋值,或者从容器的一个子序列赋值。

    assign操作用参数所指定的元素(的拷贝)替换左边容器中的所有元素。

    例如,我们可以用assign实现将一个vector中的一段char*值赋予一个list中的string

    #include <iostream>
    #include <list>
    #include <vector>
    
    using namespace std;
    
    int main ( void )
    {
        list<string> myString;
    
        vector<char*> myChar;
    
        myChar.push_back ( "1 2 3 4 5 6" );
        myChar.push_back ( "7 8 9 10" );
        myChar.push_back ( "11 12 13 14" );
    
        myString.assign ( myChar.begin(), myChar.end() );         //可以将 char* 转换为 string
    
        for ( auto i = myString.begin(); i != myString.end(); i++ )
        {
            cout << *i << ' ';
        }
    
        cout << endl;
        
        return 0;
    }
    

    这段代码中对assign的调用将names中的元素替换为迭代器指定的范围中的元素的拷贝。
    assign的参数决定了容器中将有多少个元素以及它们的值都是什么。
    输出

    类型 解释
    val 待插入元素的值
    n 新的容器尺寸
    first, last 指定元素范围的迭代器,将 [first,last)范围内的所有元素拷贝到list容器中
    il 一个列表元素,相当于列表初始化
    (1)范围赋予

    void assign ( InputIterator first, InputIterator last );

    (2)填充赋予

    接受一个整数值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素

    void assign ( size_type n, const value_type &val );

    (3)列表元素赋予

    接受一段元素列表,将list容器中的元素和大小按序替换为该元素列表内的值和个数

    void assign ( initializer_list<value_type> il );

    ?2)emplace
    ?3)emplace_front

    void emplace_front ( Args&&... args );

    ?4)emplace_back

    void emplace_back ( Args&&... args );

    来救救蒟蒻吧,emplace没学懂,欢迎留言补充交流

    ?5)push_front

    list容器的头部创建一个值为val的元素,相应地使size增大了1

    void push_front ( const value_type &val );

    ?6)pop_front

    删除list容器的的首元素

    void pop_front ( void );

    ?7)push_back

    list容器的尾部创建一个值为val的元素,相应地使size增大了1

    void push_back ( const value_type &val );

    ?8)pop_back

    删除list容器的的尾元素

    void pop_back ( void );

    ?9)insert
    类型 解释
    position 在容器中插入新元素的位置,新元素将插入在position的前面
    val 待插入元素的值
    n 要插入的元素个数,每个数的值都是val
    first, last 指定元素范围的迭代器,将 [first,last)范围内的所有元素副本插入到position的前面
    il 将列表{ }内的值插入到position的前面
    (1)插入单个元素

    在迭代器position指向的元素之前创建一个值为val的元素,返回指向新添加的元素的迭代器

    iterator insert ( const_iterator position, const value_type& val );

    (2)插入 n 个相同元素

    在迭代器position指向的元素之前插入n个值为val的元素,返回指向新添加的一个元素的迭代器;若n0,则返回p

    iterator insert ( const_iterator position, size_type n, const value_type& val );

    (3)插入元素值列表 { a, b, c, ... }

    il是一个花括号包围的元素值列表。将这些给定值插入到迭代器position指向的元素之前。返回指向新添加的第一个元素的迭代器;若列表为空,则返回p

    iterator insert (const_iterator position, initializer_list<value_type> il);

    ?10)erase
    ?a.删除单个元素

    删除由一个迭代器指定的单个元素

    返回指向删除的元素之后位置的迭代器

    iterator erase ( const_iterator position );

    ?b.删除多个元素

    接受一对迭代器,允许我们删除一个范围内的元素
    迭代器first指向要删除的第一个元素,last指向我们要删除的最后一个元素之后的位置

    iterator erase ( const_iterator first, const_iterator last );

    ?11)swap

    用于交换容器内容,swap交换两个list容器内部的数据结构(元素本身并未交换),所以非常快,可以保证在常数时间内完成。

    void swap ( list &x );

    ?12)resize

    将容器的大小变为n

    1、如果n小于当前容器的大小,则将元素个数减少到前n个元素,并删除超出范围的元素。

    2、如果n大于当前容器的大小,则通过在末尾插入任意数量的元素以达到n个元素。

    如果指定了val,则将新元素初始化为val的副本,否则,将对它们进行值的默认初始化。

    void resize ( size_type n, value_type val = value_type() );

    ?13)clear

    删除list容器中所有元素
    void clear ( void )

    8、操作

    ?1)splice

    例如有lista,listb
    splice的作用是将b中的某些元素移动a当中的某个位置去

    ?a.移动所有元素

    x容器中的所有元素移动到指定容器的迭代器position所指向的位置。

    插入的第一个元素置于迭代器position所指向的位置

    原先位置的元素置于被插入的最后一个元素的后面。(两容器的大小均已改变)

    注意和insert的区别,splice相当是把元素插入在了position的前面

    void splice ( iterator position, list &x );

    ?c.单一元素移动

    x容器中,迭代器i所指向的元素移动到list容器中,迭代器position所指向的位置之前.

    void splice (iterator position, list& x, iterator i);

    ?c.范围元素移动

    将范围[first,last)内的元素从x移动到list容器中position所指向的位置之前。

    void splice (iterator position, list& x, iterator first, iterator last);

    关于splice的具体操作请见代码:

    // splicing lists
    #include <iostream>
    #include <list>
    
    int main ()
    {
      std::list<int> mylist1, mylist2;
      std::list<int>::iterator it;
    
      // set some initial values:
      for (int i=1; i<=4; ++i)
         mylist1.push_back(i);      // mylist1: 1 2 3 4
    
      for (int i=1; i<=3; ++i)
         mylist2.push_back(i*10);   // mylist2: 10 20 30
    
      it = mylist1.begin();
      ++it;                         // points to 2
    
      mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                    // mylist2 (empty)
                                    // "it" still points to 2 (the 5th element)
                                              
      mylist2.splice (mylist2.begin(),mylist1, it);
                                    // mylist1: 1 10 20 30 3 4
                                    // mylist2: 2
                                    // "it" is now invalid.
      it = mylist1.begin();
      std::advance(it,3);           // "it" points now to 30
    
      mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                    // mylist1: 30 3 4 1 10 20
    
      std::cout << "mylist1 contains:";
      for (it=mylist1.begin(); it!=mylist1.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      std::cout << "mylist2 contains:";
      for (it=mylist2.begin(); it!=mylist2.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      return 0;
    }
    

    OutPut:

    mylist1 contains: 30 3 4 1 10 20
    mylist2 contains: 2
    

    以上代码源于http://www.cplusplus.com/reference/list/list/splice/

    ?2)remove

    删除具有val的元素

    void remove ( const value_type &val );

    ?3)remove_if

    删除满足条件的元素

    void remove_if ( Predicate pred );

    代码说明一切

    // list::remove_if
    #include <iostream>
    #include <list>
    
    // a predicate implemented as a function:
    bool single_digit (const int& value) { return (value<10); }
    
    // a predicate implemented as a class:
    struct is_odd {
      bool operator() (const int& value) { return (value%2)==1; }
    };
    
    int main ()
    {
      int myints[]= {15,36,7,17,20,39,4,1};
      std::list<int> mylist (myints,myints+8);   // 15 36 7 17 20 39 4 1
    
      mylist.remove_if (single_digit);           // 15 36 17 20 39
    
      mylist.remove_if (is_odd());               // 36 20
    
      std::cout << "mylist contains:";
      for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      return 0;
    }
    

    OutPut:

    mylist contains: 36 20
    

    以上代码源于http://www.cplusplus.com/reference/list/list/remove_if/

    ?4)unique

    删除相邻重重元素,是真的销毁掉.

    void unique ( void );

    ?5)merge

    拼接list容器

    ?a.拼接

    void merge ( list &x );

    ?b.带有比较模板的拼接

    void merge ( list& x, Compare comp );

    ?6)sort

    list容器进行排序

    ?a.升序排序 // 0, 1, 2, 3, 4

    void sort ( void );

    ?b.cmp模板排序

    void sort ( Compare comp );

    ?7)reverse

    反转list容器中元素的顺序

    void reverse ( void );

    bk