一看就懂！保姆级实例详解 STL list 容器【万字整理】

举报
Linux猿 发表于 2021/09/24 21:24:17 2021/09/24
【摘要】 一看就懂！保姆级实例详解 STL list 容器【万字整理】

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

list 是 STL 最长使用的容器之一，是在日常使用以及面试中经常遇到的知识点，下面来详细讲解下 list。

一、什么是 list ?
list 是一个双向链表封装起来的容器，可以实现 O(1) 的时间复杂度插入和删除元素，但是，和链表一样，不能通过下标（例如：g[i]）快速访问元素，只能通过遍历获取。

2021090510164139.png

二、List 的定义

2.1 头文件

使用 List 需要引入头文件：

#include <list>

2.2 定义

list<T>变量名称；

其中，T 是数据类型，例如：int、char、String、类等。

下面来看一下定义的例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
    cout<<"t1 size = "<<t1.size()<<endl;    // size = 0
    list<int> t2(5); // 定义一个长度为 5，初始值都为 0 的 int 类型的 list
    cout<<"t2 size = "<<t2.size()<<endl;    // size = 5
    list<int> t3(5, 10);  // 定义一个长度为 5，初始值都为 10 的 int 类型的 list
    cout<<"t3 size = "<<t3.size()<<endl;    // size = 5
 
    int idx = 0;
    list<int>::iterator iter;
    for(iter = t3.begin(); iter != t3.end(); ++iter) {
        cout<<*iter<<" ";     // *iter = 10 
    }
    cout<<endl;
    // 输出为：10 10 10 10 10
 
    list<int> t4(t3); // 使用 t3 初始化 t4，需要是一样的类型
 
    list<int> t5(t3.begin(), t3.end()); // 使用 t3 初始化 t5
}

输出为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
t1 size = 0
t2 size = 5
t3 size = 5
10 10 10 10 10 
linuxy@linuxy:~/defineDir$

还可以使用花括号的形式初始化：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1{1,2,3,4,5,6};   // 定义一个名为 t1 的 int 类型的 list
 
    list<int>::iterator iter;
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
}

输出为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 2 3 4 5 6 
linuxy@linuxy:~/defineDir$

2.3 常用方法

size() : 返回链表中的元素个数；
 
clear(): 清空所有元素；
 
empty(): 判断是否为空；
 
push_front(): 在链表开头添加元素；
 
push_back(): 在链表结尾添加元素；
 
pop_front(): 删除链表开头的元素；
 
pop_back(): 删除链表结尾元素；
 
begin(): 返回指向链表第一个元素的迭代器；
 
end(): 返回指向链表最后一个元素的迭代器；
 
rbegin(): 返回指向链表最后一个元素的迭代器；（用于逆向遍历元素）
 
rend(): 返回指向链表第一个元素的迭代器；（用于逆向遍历元素）
 
insert(position, val): 在链表 position 位置插入元素 val；
 
insert(position, n, val): 在链表 position 位置插入 n 个元素 val；
 
insert(position, first, last): 在链表 position 位置插入 [first, last) 区间的元素；
 
erase(position): 删除 position 位置的元素；
 
erase(first, last): 删除 区间[first, last) 位置的元素；

三、实例讲解

3.1 size()、clear()、empty() 方法

函数原型为：

size_type size() const // 返回链表存储的元素总数
 
void clear() // 清空链表
 
bool empty() const // 判断链表是否为空，空返回 true，否则，false

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
    cout<<"t1.size() = "<<t1.size()<<endl;    // size = 0
    cout<<"t1.empty() = "<<t1.empty()<<endl;  // 判断是否为空
    
    cout<<"--------------------------"<<endl;
    t1.push_back(1);            // 在 t1 尾部添加一个元素
    cout<<"t1 size = "<<t1.size()<<endl;    // size = 1
    cout<<"t1.empty() = "<<t1.empty()<<endl;  // 判断是否为空
 
    cout<<"--------------------------"<<endl;
    t1.clear();
    cout<<"t1 size = "<<t1.size()<<endl;    // size = 1
    cout<<"t1.empty() = "<<t1.empty()<<endl;  // 判断是否为空    
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
t1.size() = 0
t1.empty() = 1
--------------------------
t1 size = 1
t1.empty() = 0
--------------------------
t1 size = 0
t1.empty() = 1
linuxy@linuxy:~/defineDir$

3.2 push_front()、push_back() 方法

函数原型如下：

void push_front (const value_type& val); // 将元素添加到链表的开头
 
void push_back (const value_type& val); // 将元素添加到链表的结尾

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
    t1.push_front(10);
    t1.push_back(20);
 
    list<int>::iterator iter;
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<endl;
    }
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main
10
20
linuxy@linuxy:~/defineDir$

可以看到，输出的顺序为 10、20。

3.3 pop_front()、pop_back() 方法

函数原型如下：

void pop_front(); // 删除链表最前面一个（第一个）元素
 
void pop_back(); // 删除链表最后一个元素

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;                        // 定义一个名为 t1 的 int 类型的 list
    
    for(int i = 1; i <= 6; ++i) {        // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::iterator iter;            // 迭代器
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为：1 2 3 4 5 6
 
    t1.pop_front(); // 删除链表第一个元素
    t1.pop_back();  // 删除链表最后一个元素
 
    cout<<"----------------------------"<<endl;
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为：2 3 4 5
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 2 3 4 5 6 
----------------------------
2 3 4 5 
linuxy@linuxy:~/defineDir$

可以看到，链表第一个和最后一个元素被删除了。 

3.4 begin()、end() 方法

函数原型如下：

iterator begin()； // 返回指向第一个元素的迭代器
 
iterator end(); // 返回指向最后一个元素的迭代器

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;                        // 定义一个名为 t1 的 int 类型的 list
    for(int i = 1; i <= 6; ++i) {        // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::iterator iter;           // 顺序遍历链表的迭代器
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为：1 2 3 4 5 6
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 2 3 4 5 6 
linuxy@linuxy:~/defineDir$

可以看到，顺序输出了链表中的元素。

3.5 rbegin()、rend() 方法

函数原型如下：

reverse_iterator rbegin() // 返回指向最后一个元素的反向迭代器
 
reverse_iterator rend() // 返回指向第一个元素的反向迭代器

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
 
    for(int i = 1; i <= 6; ++i) {        // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::reverse_iterator iter;    // 反向迭代器
    for(iter = t1.rbegin(); iter != t1.rend(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    //输出为： 6 5 4 3 2 1
}

输出为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
6 5 4 3 2 1 
linuxy@linuxy:~/defineDir$

可以看到，逆序输出了链表元素。

注意：遍历链表的迭代器需要使用反向迭代器，例如上面的代码中 list<int>:: reverse_iterator。

3.6 insert 方法

insert 重载了多个方法，下面来看一下。

3.6.1 插入单个元素

函数原型如下：

iterator insert (const_iterator position, const value_type& val); // 在 position 的位置插入元素 val

注意：如果链表中 position 位置原先有元素，则新元素插入后，原先的元素在新元素后面。

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
 
    for(int i = 1; i <= 6; ++i) { // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::iterator iter;
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        if(*iter == 3) {       // 在元素 3 的位置插入元素 7，故元素 3 就位于了 7 后面
            t1.insert(iter, 7);
        }
    }
 
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为： 1 2 7 3 4 5 6
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 2 7 3 4 5 6 
linuxy@linuxy:~/defineDir$

可以看到，7 插入到了原先 3 的位置，插入后，3 在 7 后面。

3.6.2 插入 n 个相同的元素

iterator insert (const_iterator position, size_type n, const value_type& val); // 在 position 位置插入 n 个元素 val

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
    
    for(int i = 1; i <= 6; ++i) { // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::iterator iter;
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        if(*iter == 3) {          // 在元素 3 后面插入 5 个 7
            t1.insert(iter, 5, 7);
        }
    }
 
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为：1 2 7 7 7 7 7 3 4 5 6
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 2 7 7 7 7 7 3 4 5 6 
linuxy@linuxy:~/defineDir$

可以看到，插入了 5 个 7，插入后，3 排在了最后一个 7 后面。

3.6.3 在 postion 位置插入 [first, last) 区间的元素

iterator insert (const_iterator position, InputIterator first, InputIterator last); // 在 position 位置插入[first, last) 区间的元素

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
    
    for(int i = 1; i <= 6; ++i) { // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int> t2;
    for(int i = 7; i <= 9; ++i) { // 插入元素  7 8 9
        t2.push_back(i);
    }
 
    list<int>::iterator iter;
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        if(*iter == 3) {          // 在元素 3 的位置插入元素 7 8 9
            t1.insert(iter, t2.begin(), t2.end());
        }
    }
 
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为： 1 2 7 8 9 3 4 5 6
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 2 7 8 9 3 4 5 6 
linuxy@linuxy:~/defineDir$

可以看到 7,8,9 插入到了 t1 中原先 3 的位置。其中，迭代器 first 和 last 只要是一个区间就可以，不一定是 begin() 和 end()。

3.7 erase 方法

3.7.1 删除单个元素

函数原型如下所示：

iterator erase (const_iterator position); // 删除 position 位置的元素

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
 
    for(int i = 1; i <= 6; ++i) { // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::iterator iter = t1.begin();
    ++iter;
    t1.erase(iter);  // 删除 2 
    
    for(iter = t1.begin(); iter != t1.end(); ++iter) {
        cout<<*iter<<" ";
    }
    cout<<endl;
    // 输出为: 1 3 4 5 6
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 3 4 5 6 
linuxy@linuxy:~/defineDir$

可以看到删除了元素 2。

3.7.2 删除区间 [first, last) 的元素

函数原型如下所示：

iterator erase (const_iterator first, const_iterator last); // 删除链表中 [first, last) 区间的元素

来看一个例子：

#include <iostream>
#include <list>  // list 头文件
using namespace std; // 命名空间，如果没有，则使用 std::list
 
int main() {
    list<int> t1;   // 定义一个名为 t1 的 int 类型的 list
 
    for(int i = 1; i <= 6; ++i) { // 插入元素 1 2 3 4 5 6
        t1.push_back(i);
    }
 
    list<int>::iterator iter1, iter2; 
    iter2 = t1.begin();
    ++iter2;
    iter1 = iter2;
    ++iter2;
    ++iter2;                 // iter1 指向元素 2，iter2 指向元素 4
    t1.erase(iter1, iter2);  // 删除 [2, 4) 区间的元素，故删除链表中的 2,3 两个元素
 
    for(iter1 = t1.begin(); iter1 != t1.end(); ++iter1) {
        cout<<*iter1<<" ";
    }
    cout<<endl;
    // 输出 1 4 5 6
}

输出结果为：

linuxy@linuxy:~/defineDir$ g++ -o main main.cpp
linuxy@linuxy:~/defineDir$ ./main 
1 4 5 6 
linuxy@linuxy:~/defineDir$

可以看到删除了区间 [2, 4) 的元素，即：2 和 3。

 四、总结

以上就是 STL list 常用的方法讲解，在经常插入/删除元素操作的情况下可以考虑使用 list。

🎈 本文为博主原创，阅读更多优质好文可以关注公众号：Linux猿技术

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
容器 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入