容器本质"/>
＜C++＞ list容器本质
✅作者简介：热爱后端语言的大学生，CSDN内容合伙人
✨精品专栏：C++面向对象
🔥系列专栏：C++泛型编程
文章目录
- 1、list 容器本质与特点
- 2、list 基本操作与常用接口
- 2.1、list 构造函数
- 2.2、list 赋值和交换
- 2.3、list 大小操作
- 2.4、 list 插入和删除
- 2.5、list 数据存取
- 2.6、list 反转和排序
- 3、排序案例
- 3.1、生肖类
- 3.2、排序规则
- 3.3、具体实现与效果
🔥前言
今天把 list容器的基本操作、常用接口做一个系统的整理，结合具体案例熟悉自定义内部排序方法的使用。
list与vector是STL中最常用的两个容器，如果对vector 容器不熟悉的朋友可以在系列专栏里翻阅复习或者学习。
1、list 容器本质与特点
本质：
list 容器可以看做一个双向循环链表，用于存储的每个结点包含数据域和指针域
示意图：
名词解释：
begin和end都是迭代器，可以看成指针来操作- begin 对应的是容器首个元素，而end 对应容器最后一个元素的下一个位置
prev和next代表前驱指针和后继指针，并不是 list容器的接口- 指针域用来存储下一个结点的地址
front和back分别是第一个和最后一个结点的数据域push_back、push_front、pop_back、pop_front代表尾插、头插、尾删、头删
通过前驱后继指针可以将每个结点连接起来，头结点的前驱与尾结点后继指针都指向
null
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器
list 特点：
- 优点：可以对任意位置快速插入删除，动态分配存储，不会造成内存浪费和溢出
- 缺点：遍历速度比数组慢，占用空间比数组大
list有一个重要的性质，插入和删除操作都不会造成原有 list迭代器的失效
2、list 基本操作与常用接口
包含 list容器的构造、赋值交换、插入删除、数据存取、空间大小、反转、排序。
2.1、list 构造函数
- 用于创建list容器
函数原型：
list<T> lst;- 采用模板类实现,对象的默认构造形式
list(beg,end);- 构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);- 构造函数将n个elem拷贝给本身。
list(const list &lst);- 拷贝构造函数
示例：
#include<iostream>
#include <list>
using namespace std;void printList(const list<int>& L) {for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}void test()
{//默认构造list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);printList(L1);//区间构造list<int>L2(L1.begin(),L1.end());printList(L2);//拷贝构造list<int>L3(L2);printList(L3);//相同值构造list<int>L4(10, 1000);printList(L4);
}
2.2、list 赋值和交换
- 用于给
list容器进行赋值，以及交换list容器
函数原型：
assign(beg, end);- 将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem);- 将n个elem拷贝赋值给本身
list& operator=(const list &lst);- 重载等号操作符
swap(lst);- 将lst与本身的元素互换
示例：
//赋值和交换
void test01()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);//赋值list<int>L2;L2 = L1;list<int>L3;L3.assign(L2.begin(), L2.end());list<int>L4;L4.assign(10, 100);
}//交换
void test02()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);list<int>L2;L2.assign(10, 100);cout << "交换前： " << endl;printList(L1);printList(L2);L1.swap(L2);cout << "交换后： " << endl;printList(L1);printList(L2);
}
2.3、list 大小操作
- 用于对
list容器的大小进行操作
函数原型：
size();- 返回容器中元素的个数
empty();- 判断容器是否为空
resize(num);- 重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
- 如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);- 与
resize(num)的区别是默认值变为elem
- 与
示例：
void testr()
{list<int>L6;L6.push_back(10);L6.push_back(30);L6.push_back(40);//判断容器是否为空if (L6.empty()){cout << "list 为空" << endl;}else {cout << "lsit 不为空，元素个数为：" << L6.size() << endl;}//重新指定大小L6.resize(6, 100);printInfo(L6);L6.resize(3);printInfo(L6);
}
2.4、 list 插入和删除
- 用于对
list容器进行数据的插入和删除
函数原型：
push_back(elem);- 在容器尾部加入一个元素
pop_back();- 删除容器中最后一个元素
push_front(elem);- 在容器开头插入一个元素
pop_front();- 从容器开头移除第一个元素
insert(pos,elem);- 在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);- 在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);- 在pos位置插入[beg,end)区间的数据，无返回值。
clear();- 移除容器的所有数据
erase(beg,end);- 删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);- 删除pos位置的数据，返回下一个数据的位置。
remove(elem);- 删除容器中所有与elem值匹配的元素
示例：
void testt()
{list<int>L7;//尾插L7.push_back(1);L7.push_back(2);L7.push_back(3);//头插L7.push_front(30);L7.push_front(20);L7.push_front(10);printInfo(L7);//插入 insertlist<int>::iterator t = L7.begin();L7.insert(++t, 6);//删除 eraset = L7.end();//end迭代器指向最后一个有效元素的下一个位置L7.erase(--t);printInfo(L7);//移除L7.push_back(10000);L7.push_back(10000);printInfo(L7);L7.remove(10000);printInfo(L7);//清空L7.clear();if (L7.empty()){cout << "list 已经清空" << endl;}
}
2.5、list 数据存取
- 用于对
list容器中数据进行存取
函数原型：
front();- 返回第一个元素。
back();- 返回最后一个元素。
示例：
void testy()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(50);//访问首尾元素cout << "第一个元素值为：" << L1.front() << endl;cout << "最后一个元素值为：" << L1.back() << endl;//不支持下标访问，也不支持随机访问，底层是链表list<int>::iterator it = L1.begin();it++;//正确//it + 1;//错误，不存在与"+"匹配的运算符
}
2.6、list 反转和排序
- 将容器中的元素反转，以及将容器中的数据进行排序
函数原型：
reverse();- 反转链表
sort();- 链表排序
反转示例：
void testu()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);cout << "反转前：" << endl;printInfo(L1);cout << "反转后：" << endl;L1.reverse();printInfo(L1);
}
排序示例：
//用于降序排序
bool myCompare(int v1, int v2)
{//降序：让第一个数 > 第二个数return v1 > v2;
}
void testi()
{list<int>L;L.push_back(2);L.push_back(1);L.push_back(6);L.push_back(4);L.push_back(5);L.push_back(3);cout << "排序前：" << endl;printInfo(L);cout << "升序排序后：" << endl;L.sort();printInfo(L);cout << "降序排序后：" << endl;L.sort(myCompare);printInfo(L);
}
- 所有不支持随机访问迭代器的容器，不可以使用标准算法
- 这些容器内部会提供排序的成员方法
sort是list容器内部的排序方法，默认为升序排列，可以通过自己编写函数来决定排序的规则。
3、排序案例
3.1、生肖类
class Person
{
public:Person(string name, int age, int height){this->name = name;this->age = age;this->height = height;}//属性string name;int age;int height;
};
3.2、排序规则
//自定义排序规则 compare
bool compare(Person& p1, Person& p2)
{//按照身高降序if (p1.height == p2.height){//如果身高相同，按照年龄升序排序return p1.age < p2.age;}else {return p1.height > p2.height;}}
3.3、具体实现与效果
//打印list容器
void printList(list<Person>&L)
{for (list<Person>::iterator it = L.begin(); it != L.end(); it++){cout << "姓名：" << it->name << "\t年龄："<< it->age << "\t身高：" << it->height << endl;}
}
//函数主体
void test_Person()
{list<Person>L;//准备数据Person p1("辰龙", 29, 188);Person p2("寅虎", 27, 186);Person p3("子鼠", 25, 168);Person p4("丑牛", 26, 189);Person p5("卯兔", 28, 168);Person p6("亥猪", 36, 186);//尾插L.push_back(p1);L.push_back(p2);L.push_back(p3);L.push_back(p4);L.push_back(p5);L.push_back(p6);cout << "排序前：" << endl;printList(L);cout << "---------------------------------------" << endl;cout << "排序后：" << endl;L.sort(compare);printList(L);
}
list容器在泛型编程里还是比较重要的，希望我的分享可以给大家带来帮助，最后要个赞不过分吧
更多推荐
＜C++＞ list容器本质
发布评论