std::list的特点
1.插入和删除操作高效：在任意位置插入或删除元素的开销是 O(1)，不需要像 std::vector 那样可能需要移动大量元素。
2.不支持随机访问：访问 std::list 中的元素需要从头开始遍历到所需位置，访问特定元素的时间复杂度为O(n)
1.实例化list
实例化vector时，要指定该动态数组中存储的对象类型
std::list<int> intList;
std::list<float> floatList;
2.在开头和末尾插入元素
使用push_front()和push_back()
std::list<int> intList;
// 在尾部添加元素
intList.push_back(10);
intList.push_back(20);
// 在头部添加元素
intList.push_front(5);
3.列表初始化
std::list<int> myList = {1, 2, 4, 5};
4.使用insert()在中间插入元素
插入单个元素
void insert(const_iterator position, const value_type& value);
//第一个是插入位置的迭代器，第二个是值
#include <iostream>
#include<list>
int main() {
std::list<int> myList = {1, 2, 4, 5};
auto itBegin = myList.begin(); // 获取开始迭代器
auto itEnd=myList.end();//获取末尾迭代器
myList.insert(itBegin,0); // 在开头插入新元素0
myList.insert(itEnd,6);//在末尾插入新元素6
std::advance(itBegin,2);//将迭代器移动到第三个元素的位置
myList.insert(itBegin,55);//在第三个元素之前插入新元素55
for(int num:myList){
std::cout<<num<<std::endl;
}
system("pause");
return 0;
}
插入多个相同元素
void insert(const_iterator position, size_type count, const value_type& value);
//第一个是插入位置的迭代器，第二个是插入元素的数量，第三个是值
#include <iostream>
#include<list>
int main() {
std::list<int> myList = {1, 2, 4, 5};
auto itBegin = myList.begin(); // 获取开始迭代器
auto itEnd=myList.end();//获取末尾迭代器
myList.insert(itBegin,3,0); // 在开头插入3个0
myList.insert(itEnd,2,6);//在末尾插入2个6
std::advance(itBegin,2);//将迭代器移动到第三个元素的位置
myList.insert(itBegin,2,55);//在第三个元素之前插入2个55
for(int num:myList){
std::cout<<num<<std::endl;
}
system("pause");
return 0;
}
范围插入(例如列表或数组)
template<class InputIt>//需要使用模板函数
void insert(const_iterator position, InputIt first, InputIt last);
//第一个是插入位置的迭代器
//first和last是要插入元素范围的迭代器
#include <iostream>
#include<list>
int main() {
std::list<int> myList = {1, 2, 4, 5};
auto itBegin = myList.begin(); // 获取myList开始迭代器
auto itEnd=myList.end();//获取myList末尾迭代器
std::list<int> secList={11,22,33};//新的list
myList.insert(itEnd,secList.begin(),secList.end());
//在myList末尾插入secList
for(int num:myList){
std::cout<<num<<std::endl;
}
system("pause");
return 0;
}
5.删除list中的元素
使用erase()
删除单个元素
void erase(const_iterator position);//指向要删除元素的迭代器
删除元素范围
void erase(const_iterator first, const_iterator last);
//first指范围开始的迭代器，last指范围结束的迭代器
#include <iostream>
#include<list>
int main() {
std::list<int> myList = {1, 2, 3, 4, 5};
// 删除单个元素
auto it = myList.begin();//获取开始迭代器
std::advance(it, 2); // 移动开始迭代器到第三个元素
myList.erase(it); // 删除第三个元素
for (const auto& value : myList) {
std::cout << value << std::endl;
}
std::cout<<std::endl;//空一行方便观察
// 删除元素范围
it = myList.begin();
std::advance(it, 1);//将开始迭代器移动到第二个元素
auto itEnd = myList.end();//获取结束迭代器
std::advance(itEnd, -1); // 移动迭代器到倒数第二个元素
myList.erase(it, itEnd); // 删除从第二个元素到倒数第二个元素的范围
// 打印 list 中的所有元素
for (const auto& value : myList) {
std::cout << value << std::endl;
}
system("pause");
return 0;
}
6.对list中的元素进行反转和排序
①反转使用reverse()函数
#include <iostream>
#include <list>
int main() {
std::list<int> myList = {1, 2, 3, 4, 5};
// 反转列表
myList.reverse();
// 打印反转后的列表
std::cout << "Reversed list: ";
for (int num : myList) {
std::cout << num << " ";
}
system("pause");
return 0;
}
②排序使用sort()函数
没有参数，默认<运算
list.sort();
使用二元谓词函数作为参数，按照指定标准进行排序
list.sort(Compare);
//Compare可以是以下形式
//1.函数指针
bool Compare(const Type& a, const Type& b);
//2.Lambda表达式
[](const Type& a, const Type& b) -> bool { /* ... */ };
//3.函数对象
struct CompareFunctor {
bool operator()(const Type& a, const Type& b) const;
};
//4.std::function 对象
std::function<bool(const Type&, const Type&)> Compare;
例子
#include <iostream>
#include <list>
//自定义排序函=函数
bool customCompare(int a, int b) {
return a > b; // 降序排序
}
int main() {
std::list<int> myList = {5, 3, 6, 2, 1};
// 使用默认排序
myList.sort();
for (int num : myList) {
std::cout << num << " ";
}
std::cout<<std::endl;//空一行便于观察
// 使用函数指针进行降序排序
myList.sort(customCompare);
for (int num : myList) {
std::cout << num << " ";
}
system("pause");
return 0;
}
7.对包含对象的list进行排序以及删除其中的元素
如果list的元素类型为类，而不是int等简单内置类型，又要对其包含类的属性进行排序。
①假设我们有一个简单的 Person 类，我们想根据人的年龄进行降序排序：
#include <iostream>
#include <list>
//定义一个Person类
struct Person {
std::string name;
int age;
Person(const std::string& name, int age) : name(name), age(age) {}//初始化
};
//自定义年龄比较函数
bool compareByAge(const Person& a, const Person& b) {
return a.age > b.age; // 降序排序
}
int main() {
//创建一个人的list，包含名字和年龄
std::list<Person> peopleList = {
{"Alice", 30},
{"Bob", 25},
{"Charlie", 35}
};
// 使用函数指针按年龄降序排序
peopleList.sort(compareByAge);
// 打印排序后的列表
for (const auto& person : peopleList) {
std::cout << person.name << " - " << person.age << std::endl;
}
system("pause");
return 0;
}
②可以使用std::list::remove来删除满足条件的元素
#include <iostream>
#include <list>
//定义Person类
struct Person {
std::string name;
int age;
//初始化
Person(const std::string& name, int age) : name(name), age(age) {}
};
//自定义删除函数
bool IsOlderThan30(const Person& person) {
return person.age > 30;
}
int main() {
//创建一个人的list，包含名字和年龄
std::list<Person> peopleList = {
{"Alice", 30},
{"Bob", 25},
{"Charlie", 35},
{"Jonh", 21}
};
// 删除年龄大于30的
peopleList.remove_if(IsOlderThan30);
// 打印排序后的列表
for (const auto& person : peopleList) {
std::cout << person.name << " - " << person.age << std::endl;
}
system("pause");
return 0;
}
8.C++11引入的std::forward_list
要使用它，需要添加头文件<forward_list>，用法和list很像，但由于是一种单向链表，所以只能沿一个方向移动迭代器，所以插入只能使用push_front()，基本操作如下：
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = {1, 2, 3, 4, 5};
// 在头部插入一个新元素
flist.push_front(0);
// 删除头部元素
flist.pop_front();
// 遍历 forward_list 并打印每个元素
for (int num : flist) {
std::cout << num << " ";
}
std::cout << std::endl;
system("pause");
return 0;
}
引入std::forward_list 设计旨在解决一些 std::list（双向链表）的局限性，并提供一些特定的性能优势
- 性能优化： 在
std::list中，每个元素都需要存储两个指针（指向前一个和后一个元素），而 std::forward_list 中的每个元素只需要存储一个指向下一个元素的指针。这减少了内存的使用，并且可能提高缓存局部性，从而提升性能。 - 头部和尾部操作的效率：
std::forward_list提供了与std::list相似的高效头部和尾部插入与删除操作，但因为只维护单向链接，可能在某些实现中提供更优的性能。 - 编译器优化： 单向链表的结构可能使得编译器更容易进行某些优化，尤其是在内存对齐和迭代器实现方面。
