list介绍

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

list使用

本文介绍的是list的部分常用接口，大佬们想了解更多关于list类的细节，一定要请前往官方文档（点击跳转）查阅学习！

1. 默认成员函数

1.1 构造函数

list支持三种构造方式：

默认构造：构造一个list对象，此时只有一个哨兵位节点
带参构造：构造一个list对象，初始化对象有n个val值的节点
迭代器区间构造：根据传入的迭代器区间，构造出目标区间值的list对象

int main()
{
   
   
    vector<int> arr = {
   
    1,2,3,4,5,6 };
    list<int> l1; //默认构造
    list<int> l2(8, 1); //带参构造，8个val值为1的节点
    list<int> l3(arr.begin(), arr.end()); //迭代器区间构造
    return 0;
}

1.2 拷贝构造

拷贝已有的list对象来构造出一个新的相同值对象

int main()
{
   
   
    list<int> l1(3, 6);
    list<int> l2(l1);

    cout << "l1: ";
    for (auto e : l1) cout << e << " ";
    cout << endl;

    cout << "l2: ";
    for (auto e : l2) cout << e << " ";
    return 0;
}

1.3 赋值重载

将原有list对象的值赋值给另一个已存在的对象

int main()
{
   
   
    const char* ps = "happy new year";
    list<char> l1(ps, ps + strlen(ps)); //源对象
    list<char> l2; //目标对象
    l2 = l1;
    for (auto e : l2) cout << e;
    return 0;
}

注意：即使目标对象比源对象小，也能进行赋值

1.4 析构函数

析构函数会在对象生命周期结束时自动调用，进行内存释放，调用后哨兵位也将被释放

2. 迭代器

由于list的空间不是连续的，所以它的迭代器是不同于string和vector的随机迭代器的，list类中使用的是双向迭代器，只能做单纯的双向移动

list中的迭代器

正向迭代器iterator
反向迭代器reveser_iterator
const版本正反迭代器

int main()
{
   
   
    string str = "hello world";
    list<char> l1(str.begin(), str.end()); //迭代器区间构造
    //正向遍历
    list<char>::iterator it = l1.begin();
    while (it != l1.end())
    {
   
   
        cout << *it;
        it++;
    }
    cout << endl;
    //反向遍历
    list<char>::reverse_iterator rit = l1.rbegin();
    while (rit != l1.rend())
    {
   
   
        cout << *rit;
        rit++;
    }
    return 0;
}

因为list 的空间不是连续的，所以不支持下标的随机访问，对 list 对象进行遍历时，只能使用迭代器

3. 容量操作

empty()接口：判空

size()接口：查看大小

max_size()接口：检查大小调整时的合法性

int main()
{
   
   
    list<int> l1(88, 6);
    cout << l1.size() << endl; 
    cout << l1.empty() << endl;
    cout << l1.max_size() << endl;
    return 0;
}

4. 数据访问

front()接口：访问哨兵位的下一个节点

back()接口：访问链尾数据

int main()
{
   
   
    vector<int> v = {
   
    4,1,2 };
    list<int> l1(v.begin(), v.end()); //迭代器区间构造
    cout << "front: " << l1.front() << endl;
    cout << "back: " << l1.back() << endl;
    return 0;
}

5. 数据修改

5.1 插入删除

assign()接口：赋值

push_front()接口：头插

pop_front()接口：头删

push_back()接口：尾插

pop_back()接口：尾删

int main()
{
   
   
    vector<int> vs = {
   
    4,1,2 };
    list<int> l1(vs.begin(), vs.end());
    for (auto e : l1) cout << e << " "; //4 1 2
    cout << endl;

    l1.assign(3, 6); //赋值为3个6
    for (auto e : l1) cout << e << " "; //6 6 6
    cout << endl;

    l1.push_front(12); //头插12
    for (auto e : l1) cout << e << " "; //12 6 6 6
    cout << endl;

    l1.pop_front(); //头删
    for (auto e : l1) cout << e << " "; //6 6 6
    cout << endl;

    l1.push_back(24); //尾插24
    for (auto e : l1) cout << e << " "; //6 6 6 24
    cout << endl;

    l1.pop_back(); //尾删
    for (auto e : l1) cout << e << " "; //6 6 6 
    cout << endl;
    return 0;
}

list对于首尾数据的操作效率很高

insert()接口：任意位置插入

erase()接口：任意位置删除

任意位置的操作需要配合迭代器和全局查找函数find()使用，一段数据中如果有相同值，find()会返回第一次找到的位置

int main()
{
   
   
    vector<int> vv = {
   
    4,1,2 };
    list<int> l1(vv.begin(), vv.end());
    for (auto e : l1) cout << e << " "; //4 1 2
    cout << endl;

    auto poss = find(l1.begin(), l1.end(), 2);
    l1.insert(poss, 6); //指定位置插入6
    for (auto e : l1) cout << e << " "; //4 1 6 2
    cout << endl;

    l1.insert(poss, 3, 8); //指定位置插入3个8
    for (auto e : l1) cout << e << " "; //4 1 6 8 8 8 2
    cout << endl;

    l1.insert(poss, vv.begin(), vv.end()); //指定位置插入一段数据
    for (auto e : l1) cout << e << " "; //4 1 6 8 8 8 4 1 2 2
    cout << endl;

    poss = find(l1.begin(), l1.end(), 1);
    l1.erase(poss); //删除指定位置的值
    for (auto e : l1) cout << e << " "; //4 6 8 8 8 4 1 2 2
    cout << endl;

    l1.erase(l1.begin(), l1.end()); //全删
    for (auto e : l1) cout << e << " ";
    return 0;
}

==注意：==

erase后会存在迭代器失效问题，需要及时更新迭代器位置！！！

5.2 交换调整清理

swap()接口：list对象交换

resize()接口：调整大小，若调整后的大小大于原大小，会尾插T()的值

clean()接口：清理

void Print(list<int>& l1, list<int>& l2)
{
   
   
    cout << "l1 size(): " << l1.size() << endl;
    for (auto e : l1) cout << e << " ";
    cout << endl;

    cout << "l2 size(): " << l2.size() << endl;
    for (auto e : l2) cout << e << " ";
    cout << endl;
    cout << "--------------------" << endl;
}

int main()
{
   
   
    vector<int> vc = {
   
    4,1,2 };
    list<int> l1(vc.begin(), vc.end());
    list<int> l2(vc.rbegin(), vc.rend());
    Print(l1, l2);

    l1.swap(l2); //交换l13和l14
    Print(l1, l2);

    l1.resize(1); //调整大小为1
    l2.resize(12); //调整大小为12
    Print(l1, l2);

    l2.clear(); //清理l13
    Print(l2, l2);
    return 0;
}

6. 其他操作

list类中还有诸如拼接、移除、逆置等操作，特殊场景使用起来很方便

6.1 链表拼接

splice()接口：对原链表中指定区间进行拼接，拼接后，原位置处的节点(区间)不再有，已被拼接到其他地方

void Print(list<int>& l1, list<int>& l2)
{
   
   
    cout << "l1: ";
    for (auto e : l1) cout << e << " ";
    cout << endl;

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

int main()
{
   
   
    vector<int> vx = {
   
    1, 2, 3, 4, 5, 6 };
    list<int> l1(vx.begin(), vx.begin() + 3); //123
    list<int> l2(vx.begin() + 3, vx.end()); //456
    Print(l1, l2);

    l1.splice(l1.end(), l2);    //l2拼接到l1的结尾
    Print(l1, l2);

    l1.splice(l1.end(), l1, l1.begin()); //拼接到结尾
    Print(l1, l2);

    auto first = l1.begin();
    first++;    //指向第二个节点
    auto last = l1.end();    //指向最后一个节点
    l1.splice(l1.begin(), l1, first, last);    //拼接到开头
    Print(l1, l2);
    return 0;
}

6.2 链表移除

remove()接口：这个接口就是find() + erase()的封装版，使用起来非常方便

int main()
{
   
   
    vector<int> va = {
   
    4,1,2 };
    list<int> l1(va.begin(), va.end());
    for (auto e : l1) cout << e << " ";
    cout << endl;

    l1.remove(2); //移除元素2
    for (auto e : l1) cout << e << " ";
    cout << endl;
    return 0;
}

6.3 排序

由于库中的排序std::sort使用的是快排，需要支持下标随机访问，所以list对象不能使用，list类自己也提供了排序算法，不过效率较低，还不如先将数据拷贝到vector中，排序完后再拷贝回来的效率高

下面一段代码就是测试两种排序方法的效率：

int main()
{
   
   
    srand((size_t)time(NULL)); //随机数
    int n = 10000000;
    vector<int> tmp;
    tmp.reserve(n);
    list<int> l1;
    list<int> l2;
    int val = 0;
    int i = 0;
    while (i < n)
    {
   
   
        //放入随机数
        val = rand() % 100 + 1;
        l1.push_back(val);
        l2.push_back(val);
        i++;
    }
    //使用list::sort 排序
    int begin1 = clock();
    l1.sort();
    int end1 = clock();

    int begin2 = clock();
    //先拷贝到vector中
    for (auto e : l2)
    {
   
   
        tmp.push_back(e);
    }
    //使用std::sort 排序（快排）
    std::sort(tmp.begin(), tmp.end());
    //再拷贝回去
    int pos = 0;
    for (auto& e : l2)
    {
   
   
        e = tmp[pos++];
    }
    int end2 = clock();
    cout << "list::sotr time is: " << end1 - begin1 << endl;
    cout << "std::sort time is: " << end2 - begin2 << endl;

    return 0;
}

6.4 链表逆置

reverse()接口：将list对象逆置

int main()
{
   
   
    string ss = "happy";
    list<char> l1(ss.begin(), ss.end());
    for (auto e : l1) cout << e;
    cout << endl;

    l1.reverse();
    for (auto e : l1) cout << e;
    cout << endl;
    return 0;
}

C++【STL】之list的使用，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！

文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！

C++【STL】之list的使用

list介绍

list使用

1. 默认成员函数

1.1 构造函数

1.2 拷贝构造

1.3 赋值重载

1.4 析构函数

2. 迭代器

3. 容量操作

4. 数据访问

5. 数据修改

5.1 插入删除

5.2 交换调整清理

6. 其他操作

6.1 链表拼接

6.2 链表移除

6.3 排序

6.4 链表逆置

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++【STL】之list的使用

list介绍

list使用

1. 默认成员函数

1.1 构造函数

1.2 拷贝构造

1.3 赋值重载

1.4 析构函数

2. 迭代器

3. 容量操作

4. 数据访问

5. 数据修改

5.1 插入删除

5.2 交换调整清理

6. 其他操作

6.1 链表拼接

6.2 链表移除

6.3 排序

6.4 链表逆置

热门文章

最新文章

相关课程

相关电子书

相关实验场景