C++ STL——list 容器详解
目录
（4）双向迭代器 Bidirectional Iterator
（5）随机访问迭代器 Random Access Iterator
1. 什么是 list
在 C++ STL 中，list 是一个非常重要的序列式容器，它的底层结构是 带头结点的双向循环链表。
与 vector 不同，list 中的元素在内存中不是连续存储的，而是通过节点之间的指针连接起来，因此它更擅长进行频繁的插入和删除操作。
2. list 的特点
list 的优点
-
任意位置插入、删除效率高
-
插入删除不会大量搬移数据
-
不会像
vector一样频繁扩容 -
插入时不会导致其它迭代器失效
list 的缺点
-
不支持随机访问
-
访问元素效率低
-
节点额外存储指针，空间利用率低
-
缓存命中率较低
3. list 的常见构造函数
（1）构造空 list
list<int> l1;
创建一个空链表。
（2）构造 n 个 val
list<int> l2(5, 10);
创建 5 个值为 10 的节点。
结果：
10 10 10 10 10
（3）拷贝构造
list<int> l3(l2);
使用已有 list 构造新 list。
（4）迭代器区间构造
int array[] = {1,2,3,4,5};
list<int> l4(array, array + 5);
使用区间 [first, last) 中的数据构造 list。
4. list 的迭代器
由于 list 底层是链表，因此不能使用下标访问。
STL 使用 迭代器 iterator 来访问元素。
正向迭代器
begin()
end()
-
begin()指向第一个元素 -
end()指向最后一个元素的下一个位置
示例：
list<int> l = {1,2,3,4,5};
list<int>::iterator it = l.begin();
while(it != l.end())
{
cout << *it << " ";
++it;
}
输出：
1 2 3 4 5
5. 迭代器的类型
STL 根据迭代器能力的不同，将迭代器分为五类。
（1）输入迭代器 Input Iterator
特点
- 只能读
- 只能单向移动
- 不能修改数据
支持操作
++
*
==
!=应用场景
用于：
读取数据例如：
- 输入流
- 文件读取
（2）输出迭代器 Output Iterator
特点
- 只能写
- 只能向前移动
示例
ostream_iterator<int> out(cout, " ");应用
copy(v.begin(), v.end(), out);（3）单向迭代器 Forward Iterator
特点
- 可读可写
- 只能向前移动
支持
++
*
->典型容器
forward_list单向链表。
（4）双向迭代器 Bidirectional Iterator
特点
在前向迭代器基础上：
新增：
--支持向前和向后移动。
典型容器
list
set
map
multimap示例
list<int> lt = {1,2,3};
auto it = lt.end();
--it;
cout << *it;（5）随机访问迭代器 Random Access Iterator
功能最强
支持：
+
-
[]
<
>
<=
>=可以像数组一样随机访问。
典型容器
vector
deque
string示例
vector<int> v = {1,2,3,4,5};
cout << v.begin()[2];输出：
36. 五种迭代器关系
能力是逐渐增强的。
输入/输出迭代器
↓
前向迭代器
↓
双向迭代器
↓
随机访问迭代器6. list 的容量相关接口
empty()
判断是否为空。
if(l.empty())
{
cout << "为空";
}
size()
获取有效节点个数。
cout << l.size() << endl;
7. list 的元素访问
front()
获取头元素。
cout << l.front();
back()
获取尾元素。
cout << l.back();
8. list 的修改操作
push_back()
尾插。
l.push_back(10);
push_front()
头插。
l.push_front(20);
pop_back()
尾删。
l.pop_back();
pop_front()
头删。
l.pop_front();
insert()
任意位置插入。
这里list迭代器是双向迭代器，不支持+ - 操作，因此不能像vector一样来直接begin+数字来访问迭代器
void test_list3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
auto it = lt.begin();
int k = 3;
while (k--)
{
++it;
}
lt.insert(it, 30);
}第三个位置插入
erase()
删除指定位置。
跟插入操作访问迭代器是一样的
l.erase(pos);
clear()
清空所有元素。
l.clear();
splice()
转移链表节点
剪切链表的一段数据到另一个链表的某个位置
void test_list()
{
// 一个链表节点转移给另一个链表
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
}/调整当前链表节点的顺序
// 调整当前链表节点的顺序
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
int x = 0;
cin >> x;
it = find(lt.begin(), lt.end(), x);
if (it != lt.end())
{
//lt.splice(lt.begin(), lt, it);
lt.splice(lt.begin(), lt, it, lt.end());
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;假设输入3
输出
1 2 3 4 5 6
3 4 5 6 1 29. list的排序
algorithm算法库有一个排序接口，底层用的快排逻辑，这样就涉及到了+ -操作，像vector这样的容器是随机迭代器，我们可以直接使用
sort(vector.begin(),vector.end());但是像list这样的双向迭代器，我们就没法用算法库的排序接口，但是list类里面自己实现了排序接口
list<int> lt;
lt.sort()排序默认是升序，如果我们要进行降序，就要传一个仿函数
lt.sort(greater<int>());更多推荐
11
0- 0
已为社区贡献10条内容
所有评论(0)