文章目录
- 一、 list简介
- 二、 构造函数
- 1. 默认构造函数
- 2. 拷贝构造
- 3. 迭代器区间初始化
- 4. 插入n个值为x的数据
- 5. 代码示例
- 三、 容量和元素访问
- 1. empty()
- 2. size()
- 3. max_size()
- 3. back()
- 4. front()
- 5. 代码示例
- 四、 增删查改
- 1. push_back()
- 2. push_front()
- 3. emplace_back()
- 4. emplace_front()
- 5. pop_back()
- 6. pop_front()
- 7. insert()
- 8. erase()
- 9. clear()
- 10. swap
- 五、迭代器
- 1. begin()
- 2. end()
- 3. rbegin()
- 4. rend()
- 5. cbegin()、cend()、crbegin()、crend()
- 六、 操作函数
- 1. splice()
- 2. unique()
- 3. remove()
- 4. remove_if()
- 5. merge()
- 6. sort()
- 7 . reserve()
- 七、 sort排序效率测评
- 八、 list迭代器失效问题
list_4">一、 list简介
C++ STL(Standard Template Library)中的list
是一个双向链表容器,它允许在序列中的任何位置进行快速插入和删除操作。list
容器中的元素不是连续存储的,而是由节点(通常包含数据和指向下一个及前一个元素的指针)组成,因此它不需要在插入或删除元素时移动其他元素。
以下是list
的一些基本特点和用法:
特点
- 双向链表:每个元素都包含指向其前一个和后一个元素的指针,这使得在任何位置进行插入和删除操作都非常高效。
- 动态大小:
list
的大小可以动态变化,可以根据需要添加或删除元素。 - 非连续存储:与数组或向量不同,
list
的元素不是连续存储在内存中的。
基本用法
包含头文件
#include <list>
创建list
可以创建一个空的list
,也可以在创建时初始化它。
std::list<int> myList; // 创建一个空的int类型的list
std::list<int> myList = {1, 2, 3, 4, 5}; // 创建一个包含5个元素的list
添加元素
可以使用push_back
、push_front
、insert
等方法向list
中添加元素。
myList.push_back(6); // 在list的末尾添加元素6
myList.push_front(0); // 在list的开头添加元素0
myList.insert(myList.begin(), 7); // 在list的开头插入元素7
删除元素
可以使用pop_back
、pop_front
、erase
等方法从list
中删除元素。
myList.pop_back(); // 删除list的最后一个元素
myList.pop_front(); // 删除list的第一个元素
myList.erase(myList.begin()); // 删除list的第一个元素(使用迭代器)
遍历元素
可以使用迭代器或范围基于的for循环来遍历list
中的元素。
// 使用迭代器遍历
for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " ";
}// 使用范围基于的for循环遍历
for (const auto& elem : myList) {std::cout << elem << " ";
}
查找元素
可以使用find
方法来查找list
中的元素。
auto it = std::find(myList.begin(), myList.end(), 3); // 查找值为3的元素
if (it != myList.end()) {std::cout << "Found element: " << *it << std::endl;
} else {std::cout << "Element not found" << std::endl;
}
这只是list
容器的一些基本用法,它还提供了许多其他功能和方法,如排序、合并、分割等,可以通过查阅C++ STL文档来了解更多详情。
二、 构造函数
构造函数( (constructor)) | 接口说明 |
---|---|
list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
list() | 构造空的list |
list (const list& x) | 拷贝构造函数 |
list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
1. 默认构造函数
这个构造函数用于创建一个空的 std::list 容器。它可以接受一个可选的分配器参数,用于指定内存分配策略。
list() //默认构造函数
std::list<int> ls; //建立一个空的list容器
2. 拷贝构造
拷贝构造用于创建一个与已存在的std::list
容器x相同的副本,它会将 x中的所有元素拷贝到新的容器中。
list (const list& x) //拷贝构造
std::list<int> A={1,2,3,4};
std::list<int> copy(A);
3. 迭代器区间初始化
这个构造函数使用迭代器范围 [first, last) 中的元素创建一个 std::list
容器。这使你可以通过一个迭代器范围来初始化容器。同样,它也接受一个可选的分配器参数。
list (InputIterator first, InputIterator last) //用[first, last)区间中的元素构造list
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> List(vec.begin(), vec.end());// 从迭代器范围内的元素创建 std::list 容器
4. 插入n个值为x的数据
这个构造函数用于创建一个包含 n 个元素的 std::list
容器,并将这些元素初始化为 val。你可以通过传递不同的 val 值来创建一个包含相同值的容器。同样,也可以传递一个可选的分配器参数。
list (size_type n, const value_type& val = value_type()) //构造的list中包含n个值为val的元素
std::list<int> A(5,10); //构建一个有五个元素,每个元素都是10的容器
5. 代码示例
#include <iostream>
#include <list>int main()
{std::list<int> first; // 默认构造函数std::list<int> second(4, 100); // 四个元素都是100std::list<int> third(second.begin(), second.end()); // 迭代器区间构造std::list<int> fourth(third); //拷贝构造//迭代器构造函数也可以用于从数组构造:int myints[] = { 16,2,77,29 };std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are: ";for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)std::cout << *it << ' ';std::cout << '\n';return 0;
}
三、 容量和元素访问
1. empty()
判断容器中元素是否为空,为空返回true否则false。
2. size()
返回容器中元素个数。
3. max_size()
返回列表容器可以容纳的最大元素数。
3. back()
返回对列表容器中最后一个元素的引用。
与成员list::end不同,该函数返回的迭代器刚好经过该元素,它返回的是直接引用。
在空容器上调用此函数会导致未定义的行为。
4. front()
返回对列表容器中第一个元素的引用。
与向同一元素返回迭代器的成员list::begin不同,此函数返回一个直接引用。
在空容器上调用此函数会导致未定义的行为。
5. 代码示例
#include <iostream>
#include <list>int main()
{std::list<int> Mylist;Mylist.push_back(1);//在最后插入一个元素,后面会详细说明Mylist.push_back(2);Mylist.push_back(3);Mylist.push_back(4);std::cout << "Mylist中元素个数为:" << Mylist.size() << std::endl;std::cout << "Mylist是否为空:" << Mylist.empty() << std::endl;std::cout << "Mylist首元素为:" << Mylist.front() << std::endl;std::cout << "Mylist最后一个元素为:" << Mylist.back() << std::endl;return 0;
}
四、 增删查改
1. push_back()
在列表容器的末尾,在其当前最后一个元素之后添加一个新元素。
#include <iostream>
#include <list>int main()
{std::list<int> Mylist;Mylist.push_back(1);Mylist.push_back(2);//输出list中的元素for (const auto e : Mylist)std::cout << e << " ";return 0;
}
2. push_front()
在列表的开头,即当前第一个元素之前插入一个新元素。
#include <iostream>
#include <list>int main()
{std::list<int> Mylist;Mylist.push_back(1);Mylist.push_back(2);//输出list中的元素for (const auto e : Mylist)std::cout << e << " ";std::cout << std::endl;Mylist.push_front(3);Mylist.push_front(4);for (const auto e : Mylist)std::cout << e << " ";std::cout << std::endl;return 0;
}
3. emplace_back()
用法和push_back一样,作用也一样,就是在特定情况下效率比push_back高
这里不详细介绍他的原理了,后面会专门写一篇有关右值引用的博客,在内篇文章中我们会探讨这个问题。
- 在列表末尾的当前最后一个元素的正后方插入一个新元素。这个新元素是使用args作为其构造参数就地构造的。
- 该元素是通过调用allocator_traits::construct和转发的args就地构造的。
- 存在一个类似的成员函数push_back,它可以将现有对象复制或移动到容器中
4. emplace_front()
用法和push_front一样,作用也一样,就是在特定情况下效率比push_front高
这里不详细介绍他的原理了,后面会专门写一篇有关右值引用的博客,在内篇文章中我们会探讨这个问题。
- 在列表的开头,即当前第一个元素之前插入一个新元素。这个新元素是使用args作为其构造参数就地构造的。
- 该元素是通过调用allocator_traits::construct和转发的args就地构造的。
- 存在一个类似的成员函数push_front,它将现有对象复制或移动到容器中。
5. pop_back()
删除list容器中的最后一个元素。
#include <iostream>
#include <list>int main()
{std::list<int> Mylist;Mylist.push_back(1);Mylist.push_back(2);Mylist.push_back(3);Mylist.push_back(4);Mylist.pop_back();//输出list中的元素for (const auto e : Mylist)std::cout << e << " ";std::cout << std::endl;return 0;
}
6. pop_front()
删除list容器中的第一个元素
#include <iostream>
#include <list>
int main()
{std::list<int> Mylist;Mylist.push_back(1);Mylist.push_back(2);Mylist.push_back(3);Mylist.push_back(4);Mylist.pop_front();Mylist.pop_front();//输出list中的元素for (const auto e : Mylist)std::cout << e << " ";std::cout << std::endl;return 0;
}
7. insert()
- 通过在指定位置的元素之前插入新元素来扩展容器。这有效地将list大小增加了插入的元素数量。
- 与其他标准序列容器不同,list和forward_list对象经过专门设计,可以有效地在任何位置插入和删除元素,即使是在序列的中间。
- 参数确定插入了多少个元素以及将它们初始化为哪些值:
#include <iostream>
#include <list>
#include <vector>int main()
{std::list<int> mylist;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5it = mylist.begin();++it; // it points now to number 2 ^mylist.insert(it, 10); // 1 10 2 3 4 5// "it" still points to number 2 ^mylist.insert(it, 2, 20); // 1 10 20 20 2 3 4 5--it; // it points now to the second 20 ^std::vector<int> myvector(2, 30);mylist.insert(it, myvector.begin(), myvector.end());// 1 10 20 30 30 20 2 3 4 5// ^std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
8. erase()
- 从列表容器中删除单个元素(位置)或一系列元素([第一个,最后一个))。这有效地减少了容器的大小,减少了被销毁的元素的数量。
- 与其他标准序列容器不同,list和forward_list对象经过专门设计,可以有效地在任何位置插入和删除元素,即使是在序列的中间。
#include <iostream>
#include <list>int main()
{std::list<int> mylist;std::list<int>::iterator it1, it2;// set some values:for (int i = 1; i < 10; ++i) mylist.push_back(i * 10);// 10 20 30 40 50 60 70 80 90it1 = it2 = mylist.begin(); // ^^advance(it2, 6); // ^ ^++it1; // ^ ^it1 = mylist.erase(it1); // 10 30 40 50 60 70 80 90// ^ ^it2 = mylist.erase(it2); // 10 30 40 50 60 80 90// ^ ^++it1; // ^ ^--it2; // ^ ^mylist.erase(it1, it2); // 10 30 60 80 90// ^std::cout << "mylist contains:";for (it1 = mylist.begin(); it1 != mylist.end(); ++it1)std::cout << ' ' << *it1;std::cout << '\n';return 0;
}
9. clear()
从列表容器中删除所有元素(已销毁),并使容器的大小为0。
#include <iostream>
#include <list>int main()
{std::list<int> mylist;// set some values:for (int i = 1; i < 10; ++i) mylist.push_back(i * 10);// 10 20 30 40 50 60 70 80 90std::cout << mylist.size() << std::endl;mylist.clear();std::cout << mylist.size() << std::endl;return 0;
}
10. swap
- 用x的内容交换容器的内容,x是另一个相同类型的列表。尺寸可能不同。
- 在调用该成员函数之后,该容器中的元素是调用之前在x中的元素,而x的元素是在此中的元素。所有迭代器、引用和指针对于交换的对象仍然有效。
- 请注意,存在一个具有相同名称的非成员函数swap,该函数使用与该成员函数类似的优化重载该算法。
- 容器分配器是否也被交换没有定义,除非在这种情况下,适当的分配器特性明确指示它们应该传播。
#include <iostream>
#include <list>int main()
{std::list<int> mylist1,mylist2;// set some values:for (int i = 1; i < 10; ++i){mylist1.push_back(i * 10);// 10 20 30 40 50 60 70 80 90mylist2.push_back(i);//1 2 3 4 5 6 7 8 9 }for (auto e : mylist1)std::cout << e << " ";std::cout << std::endl;for (auto e : mylist2)std::cout << e << " ";std::cout << std::endl;mylist1.swap(mylist2);//交换元素for (auto e : mylist1)std::cout << e << " ";std::cout << std::endl;for (auto e : mylist2)std::cout << e << " ";std::cout << std::endl;return 0;
}
五、迭代器
1. begin()
返回一个迭代器,该迭代器指向list容器中的第一个元素。
请注意,与返回对第一个元素的引用的member-list::front不同,此函数返回指向它的双向迭代器。
如果容器为空,则不应该解引用返回的迭代器值。
#include <iostream>
#include <list>int main()
{std::list<int> mylist1;// 1 2 3 4 5for (int i = 1; i <= 5; i++) mylist1.push_back(i);std::list<int>::iterator it = mylist1.begin();std::cout << *it << std::endl;return 0;
}
2. end()
返回一个迭代器,该迭代器指向list容器中最后一个元素的下一个元素。
因此它不指向任何元素,不能执行解引用操作。
由于标准库的函数所使用的范围不包括其end迭代器所指向的元素,因此此函数经常与list::begin结合使用,以指定一个包括容器中所有元素的范围。
如果容器为空,此函数将返回与list::begin相同的值。
因为end返回的迭代器指向最后一个元素的下一个元素,所以不能解引用,那只需要让这个迭代器先--再解引用,那得到的就是最后一个元素
#include <list>int main()
{std::list<int> mylist1;// 1 2 3 4 5for (int i = 1; i <= 5; i++) mylist1.push_back(i);std::list<int>::iterator it = mylist1.end();std::cout << *(--it) << std::endl;return 0;
}
3. rbegin()
返回一个反向迭代器,指向容器中的最后一个元素(即其反向开头)。
反向迭代器向后迭代:增加它们会将它们移向容器的开头。
rbegin指向成员端将指向的元素之前的元素。
请注意,与返回对同一元素的引用的member-list::back不同,此函数返回一个反向双向迭代器。
#include <iostream>
#include <list>int main()
{std::list<int> mylist1;// 1 2 3 4 5for (int i = 1; i <= 5; i++) mylist1.push_back(i);std::list<int>::reverse_iterator it = mylist1.rbegin();std::cout << *(it) << std::endl;return 0;
}
4. rend()
返回一个反向迭代器,该迭代器指向列表容器中第一个元素之前的理论元素(被视为其反向端)。
list::rbegin和list::rend之间的范围包含容器的所有元素(按相反顺序)。
因为rend返回的迭代器指向第一个元素的前一个元素,所以不能解引用,那只需要让这个迭代器先--再解引用,那得到的就是第一个元素
#include <iostream>
#include <list>int main()
{std::list<int> mylist1;// 1 2 3 4 5for (int i = 1; i <= 5; i++) mylist1.push_back(i);std::list<int>::reverse_iterator it = mylist1.rend();std::cout << *(--it) << std::endl;return 0;
}
5. cbegin()、cend()、crbegin()、crend()
cbegin()、cend()、crbegin()、crend()所代表的含义分别和begin()、end()、rbegin()、rend()一样,唯一的区别是前者是const版本的,只能读,不能修改,而后面的读写都可以。
以begin()和cbegin()为例:
可以看到begin是可以修改的,(it)++之后再输出it就从1变成2了。
cbegin直接报错了。
六、 操作函数
1. splice()
splice函数用于两个list容器之间的拼接,其有三种拼接方式:
- 将整个容器拼接到另一个容器的指定迭代器位置。
- 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置。
- 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置。
#include <iostream>
#include <list>
using namespace std;int main()
{list<int> lt1(4, 2);list<int> lt2(4, 6);lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头for (auto e : lt1){cout << e << " ";}cout << endl; //6 6 6 6 2 2 2 2 list<int> lt3(4, 2);list<int> lt4(4, 6);lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头for (auto e : lt3){cout << e << " ";}cout << endl; //6 2 2 2 2 list<int> lt5(4, 2);list<int> lt6(4, 6);lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头for (auto e : lt5){cout << e << " ";}cout << endl; //6 6 6 6 2 2 2 2return 0;
}
2. unique()
不带参数的版本(1)从容器中每个连续的相等元素组中删除除第一个元素外的所有元素。
请注意,只有当一个元素与紧挨在它前面的元素进行比较时,它才会从列表容器中删除。因此,此函数对排序列表特别有用。
#include <iostream>
#include <list>int main()
{std::list<int> mylist1;mylist1.push_back(4);for (int i = 1; i <= 5; i++) mylist1.push_back(5);mylist1.push_back(4);for (int i = 1; i <= 5; i++) mylist1.push_back(5);mylist1.unique();for (auto e : mylist1)std::cout << e << " ";return 0;
}
3. remove()
从容器中删除所有与值相等的元素。这将调用这些对象的析构函数,并按删除的元素数量减少容器大小。
与成员函数list::erase(使用迭代器)按位置擦除元素不同,此函数(list::remove)按元素的值删除元素。
#include <iostream>
#include <list>int main() {std::list<int> myList1 = { 1,2,3,4,5,3 };myList1.remove(3);for (int num : myList1) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
4. remove_if()
这个成员函数用于根据给定的谓词函数 pred 移除满足特定条件的元素。
谓词函数 pred 接受一个参数(参数类型同*迭代器返回的类型相同)并返回一个布尔值,用于判断是否需要移除该元素。如果谓词返回 true,则该元素将被移除。
从容器中删除Predicate pred返回true的所有元素。这将调用这些对象的析构函数,并通过移除的元素数量来减少容器大小。
函数为每个元素调用pred(*i)(其中i是该元素的迭代器)。列表中返回true的任何元素都将从容器中删除。
#include <iostream>
#include <list>bool judge(int num)
{return num % 2 == 0;
}
int main() {std::list<int> myList1 = { 1,2,3,4,5,6,7,8,9 };myList1.remove_if(judge);for (int num : myList1) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
5. merge()
C++标准库中的std::list的merge函数要求两个列表在合并前都已经是排序的。如果两个列表不是有序的,那么merge函数的结果将是不确定的,因为它会按照元素的大小顺序来合并两个列表。
- 第一个成员函数用于将另一个列表 x 合并到当前列表中,合并后的列表会按照升序排列。
#include <iostream>
#include <list>int main() {std::list<int> myList1 = { 1, 3, 5 };std::list<int> myList2 = { 2, 4, 6 };myList1.merge(myList2); // 将 myList2 合并到 myList1 中std::cout << "myList1 after merge: ";for (int num : myList1) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
2. 第二个成员函数不仅可以将两个list合并,还能指明排序方法。上面是升序,我们可以弄成降序
6. sort()
对列表中的元素进行排序,改变它们在容器中的位置。
- 默认升序
int main() {std::list<int> myList1 = { 3,1,5,4,2,3 };myList1.sort();for (int num : myList1) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
- 可以指定如何排序,比如这里我们让它降序
7 . reserve()
颠倒列表容器中元素的顺序
#include <iostream>
#include <list>int main() {std::list<int> myList1 = { 1,2,3,4,5 };myList1.reverse();for (int num : myList1) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
七、 sort排序效率测评
list容器虽然有一个排序的sort函数,但我们一般是不会使用的,因为效率太低了。
现在我们使用下面的代码来测试vector和list排序的性能,看一下结果。
现在产生1000000个随机数,分别放到vector和list中,然后list调自己提供的sort,vector调库里面的sort,我们来对比一下它们的运行时间:
多运行几次,可以发现虽然每次时间都不太一样,但是vector的排序总是比list快很多。
void test_op1()
{srand(time(0));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;for (int i = 0; i < N; ++i){auto e = rand();v.push_back(e);lt1.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());// vector排序int end1 = clock();int begin2 = clock();lt1.sort();//list排序int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
既然如此,那我们就比点有可比性的。我们先分别向两个list中都插入1000000个随机数。然后一个是先把list的数据拷贝到vector中,利用vector排序完之后再拷贝回list中,另一个是直接调用list的成员函数sort进行排序,比比谁快。
可以看到还是前者快,所以一般不用list的sort因为效率太低了。
void test_op1()
{srand(time(0));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt2.push_back(e);lt1.push_back(e);}// 拷贝到vector排序,排完以后再拷贝回来int begin1 = clock();// 先拷贝到vectorfor (auto e : lt1){v.push_back(e);}// 排序sort(v.begin(), v.end());// 拷贝回去size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
list_907">八、 list迭代器失效问题
迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
当使用 std::list 进行删除操作时,可能会导致迭代器失效。如下:
int main() {std::list<int> myList = { 1, 2, 3, 4, 5 };auto it = myList.begin();++it; // Move the iterator to the second elementmyList.erase(it); // Erase the second elementfor (auto num : myList) {std::cout << num << " ";}return 0;
}
但如果此时再次*it就会出问题,这就是迭代器失效导致的。
在上面的示例中,当我们在第二个元素位置处使用 erase 函数删除元素后,迭代器 it 就会失效,因为它指向的元素已经被删除。如果我们尝试使用失效的迭代器,可能会导致未定义的行为。
要修正这个问题,可以使用 erase 函数的返回值,它会返回一个指向下一个有效元素的迭代器:
#include <iostream>
#include <list>int main() {std::list<int> myList = { 1, 2, 3, 4, 5 };auto it = myList.begin();++it; // Move the iterator to the second elementit = myList.erase(it); // Erase the second element and update the iteratorfor (auto num : myList) {std::cout << num << " ";}return 0;
}