2018年深圳建设网站公司,wordpress用户的区别,中企高呈建设网站,discuz 旅游网站模版STL常用容器—list容器#xff08;链表#xff09; 一、list容器基本概念二、list容器基本操作与常用方法1. list构造函数2. ☆list 插入和删除3. list 获取头尾数据4. list 大小操作5. list赋值和交换6. list 反转和排序 三、排序案例 参考博文1: #xff1c;C#xff1e;… STL常用容器—list容器链表 一、list容器基本概念二、list容器基本操作与常用方法1. list构造函数2. ☆list 插入和删除3. list 获取头尾数据4. list 大小操作5. list赋值和交换6. list 反转和排序 三、排序案例 参考博文1: C list容器本质|常用接口|自定义排序规则 参考博文2STL常用容器—— list 容器的使用 本文主要整理总结C STL中list链表常用容器的常用方法的操作关于链表的底层设计与C语言实现请参考博文【数据结构与算法】——单链表的原理及C语言实现
一、list容器基本概念 list 容器 的本质是一个双向循环链表用于存储的每个结点包含数据域和指针域
示意图 名词解释
begin 和 end 都是迭代器可以看成指针来操作 begin 对应的是容器首个元素而end 对应容器最后一个元素的下一个位置prev 和 next 代表前驱指针和后继指针并不是 list 容器的接口指针域用来存储下一个结点的地址front 和 back 分别是第一个和最后一个结点的数据域push_back、push_front、pop_back、pop_front 代表尾插、头插、尾删、头删 通过前驱后继指针可以将每个结点连接起来头结点的前驱与尾结点后继指针都指向null 由于链表的存储方式并不是连续的内存空间因此链表list中的迭代器只支持前移和后移属于双向迭代器 list的优点
采用动态存储分配不会造成内存浪费和溢出可以对任意位置进行快速插入或删除元素修改指针即可不需要移动大量元素
list的缺点
链表灵活但是空间指针域和 时间遍历额外耗费较大
STL中List和vector是两个最常被使用的容器各有优缺点
二、list容器基本操作与常用方法
1. list构造函数
函数原型功能listT lst;采用模板类实现对象的默认构造形式listT lst {x1,x2...};构造并出初始化list(n,elem);n个elemlist(const list lst);拷贝构造函数list(beg,end);构造函数将[beg, end)区间中的元素拷贝给本身
示例
listint list1;
list1.push_back(10);
list1.push_back(20);
list1.push_back(30);listint list2{2,4,6,8};//构造并初始化
listint list3(5,100); //5个100
listint list4(list1); //拷贝list1//list2的部分区间
listint list5(list2.begin(), --list2.end()); cout list1: ; showList(list1);
cout list2: ; showList(list2);
cout list3: ; showList(list3);
cout list4: ; showList(list4);
cout list5: ; showList(list5);其中showList
void showList(listint list)
{for(int item:list)cout item ;cout endl;
}2. ☆list 插入和删除
方法原型功能-----------常用-----------push_back(elem);在容器尾部插入一个元素push_front(elem);在容器开头插入一个元素pop_back();删除容器中最后一个元素pop_front();删除容器中第一个元素clear();清空容器所有数据-----------不常用-----------insert(pos,elem);在pos位置插elem元素的拷贝返回新数据的位置。insert(pos,n,elem);在pos位置插入n个elem数据无返回值。insert(pos,beg,end);在pos位置插入[beg,end)区间的数据无返回值erase(beg,end);删除[beg,end)区间的数据返回下一个数据的位置erase(pos);删除pos位置的数据返回下一个数据的位置remove(elem);删除容器中所有与elem值匹配的元素。
示例
void test()
{listint list1;//尾插list1.push_back(2); list1.push_back(4);//头插list1.push_front(10);list1.push_front(30);cout list1 push back front: ;showList(list1); //30 10 2 4//尾删list1.pop_back();cout pop back: ; showList(list1); //30 10 2//头删list1.pop_front();cout pop front: ; showList(list1); //10 2//头1插list1.insert(list1.begin(), 666);cout front insert: ; showList(list1); //10 666 2//头1删list1.erase(list1.begin());cout front1 erase: ; showList(list1); //10 2
}3. list 获取头尾数据 list 容器不支持随机访问不提供下标操作符 [] 和 at() 成员函数也没有提供 data() 成员函数。 只能使用 front() 和 back() 成员函数或者使用 list 容器迭代器访问或修改元素的值。 使用 front() 和 back() 成员函数 方法原型功能front();返回第一个元素back();返回最后一个元素
int main()
{listint list1 {2,4,6,8,10};//获取元素引用int first list1.front();int last list1.back();cout first last endl;//修改元素first 100;last 200;cout list1.front() list1.back() endl;return 0;
}注意
list容器中不可以通过[]或者at方式访问数据返回第一个元素 — front返回最后一个元素 — back 使用 list 容器迭代器 int main()
{listint list1 {2,4,6,8,10};auto it list1.begin(); //迭代器指向头while(it ! list1.end()) //迭代遍历{cout *it ;it; //迭代器自增}return 0;
}注意 list容器的迭代器类型为双向迭代器而不是和之前的array、vector容器一样是随机访问迭代器。
双向迭代器特性假如it1it2都是双向迭代器那么 支持it1、 it1、 it1- -、 it1、 *it1、 it1 it2 以及 it1 ! it2 不支持it1[i]、it1-i、 it1i、 it1i 、it1-i、it1 it2、it1 it2、 it1 it2、 it1 it2 4. list 大小操作
方法原型功能size(); 返回容器中元素的个数empty(); 判断容器是否为空resize(num);重新指定容器的长度为num若容器变长则以默认值0填充若变短则删除末尾多余元素resize(num, elem); 重新指定容器的长度为num若容器变长则以 elem 填充若变短则删除末尾多余元素
示例程序
void test()
{listint list1 {10,20,30};listint list2 {2,4,6,8,10};if(!list1.empty()){cout size: list1.size() endl;list1.resize(5); //重置大小为5个以默认值填充cout resize: list1.size() endl;showList(list1);}elsecout 容器为空 endl;
}5. list赋值和交换
方法原型功能assign(beg, end);将[beg, end)区间中的数据拷贝赋值给本身assign(n, elem);将n个elem拷贝赋值给本身list operator(const list lst);已重载 操作符swap(lst);将list与本身的元素互换
示例
listint list1 {10,20,30};
listint list2 {2,4,6,8,10};list1 list2;
showList(list1); //2,4,6,8,10list1.assign(5,100);
showList(list1); //5个100list1.assign(list2.begin(),--list2.end());
showList(list1); //4,6,8list1.swap(list2);
showList(list1); //2,4,6,8,10
showList(list2); //4,6,86. list 反转和排序
方法原型功能reverse();反转链表sort();链表排序
示例
//用于降序排序
bool myCompare(int v1, int v2)
{//降序让第一个数 第二个数return v1 v2;
}void test03()
{listint list1 {6,4,2,10,3};cout src data: ; showList(list1);//降序排序list1.sort(myCompare);cout sort: ; showList(list1);//反转list1.reverse();cout reverse: ; showList(list1);
}sort 是 list 容器内部的排序方法默认为升序排列需要通过自己编写函数仿函数来决定排序的规则。 三、排序案例
案例描述 将Person自定义数据类型进行排序Person中属性有姓名、年龄、身高 排序规则 按照年龄进行升序如果年龄相同按照身高进行降序
示例程序
/******************自定义Person类****************/
class Person {
public:Person(string name, int age , int height){this-name name;this-age age;this-height height;}public:string name; //姓名int age; //年龄int height; //身高
};
/*****************定义仿排序顺序 仿函数**************/
bool PersonCompare(Person p1, Person p2)
{if(p1.age p2.age) //年龄相同 按身高降序{if(p1.height p2.height)return true;elsereturn false;}else //按年龄升序{if(p1.age p2.age)return true;elsereturn false;}
}
/****************遍历容器函数**************/
void showPersonList(listPerson list)
{auto it list.begin();for( ; it ! list.end(); it){cout name: it-name \tage: it-age;cout \t\theight: it-height endl;}
}
/*****************主程序 测试程序*************/
void test04()
{Person p1(张三, 22, 170);Person p2(李四, 21, 173);Person p3(王五, 20, 168);Person p4(陈六, 25, 177);Person p5(赵七, 22, 180);listPerson list1 {p1,p2,p3,p4,p5};//排序前cout before sort: endl; showPersonList(list1);//自定义排序list1.sort(PersonCompare);//显示排序后结果cout after sort: endl; showPersonList(list1);
}程序输出
总结
对于自定义数据类型必须要指定排序规则否则编译器不知道如何进行排序高级排序只是在排序规则上再进行一次逻辑规则制定并不复杂
