list容器基本概念
功能：将数据进行链式储存
链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
链表的组成：
结点的组成：
STL中链表是一个双向循环列表
list的优点：
- 采用动态存储分配，不会造成内存浪费或溢出
- 可以对任意位置进行快速插入或删除元素
缺点：
list的重要性质：
- 插入和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的
STL中list和vector是最常被使用的容器，各有优缺点
list构造函数
-
list<T>lst;//采用模板类实现，默认构造函数
-
list(beg, end);//构造函数将[beg,end)区间中的元素拷贝给自身
-
list(n, elem);//将n个elem拷贝给自身
-
list(const list& list);//拷贝构造函数
#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
list<int>L1;//默认构造
for (int i = 0; i < 10; i++)
{
L1.push_back(i);
}
PrintList(L1);
list<int>L2(L1.begin(), L1.end());//区间方式构造
PrintList(L2);
list<int>L3(L2);//拷贝构造
PrintList(L3);
list<int>L4(10, 2);//n个elem
PrintList(L4);
return 0;
}
list赋值和交换
-
.assign(beg, end);//将[beg,end)区间中的数据拷贝赋值给自身
-
.assign(n, elem);//将n个elem拷贝赋值给本身
-
list& operator=(const list& lst);//重载等号运算符
-
.swap(lst);//将lst与本身元素互换
#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
list<int>L1;//默认构造
for (int i = 0; i < 10; i++)
{
L1.push_back(i);
}
list<int>L2;
L2.assign(L1.begin(), L1.end());//区间赋值
PrintList(L2);
L2.assign(10, 1);//n个elem赋值
PrintList(L2);
L2 = L1;//等号赋值
PrintList(L2);
return 0;
}
list容器大小操作
-
.empty();//判断容器是否为空
-
.size();//返回容器中元素的个数
-
.resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值0填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
-
.resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
list插入和删除
两端插入操作：
-
.push_back(elem);//尾插
-
.push_front(elem);//头插
-
.pop_back();//尾删
-
.pop_front();//头删
指定位置操作：
-
.insert(pos, elem);//在pos位置插入elem元素的拷贝，返回新数据的位置
-
.insert(pos, n, elem);//在pos位置插入n个elem元素数据，无返回值
-
.insert(pos, beg, end);//在pos位置插入[beg,end)区间的数据，无返回值
-
.clear();//清空容器内所有数据
-
.eraser(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置
-
.erase(pos);//删除pos位置的数据，返回下一个数据的位置
以上操作与deque容器相同，不同的是，list支持remove操作：
-
.remove(elem);//删除容器中所有与elem值匹配的元素
#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
list<int>L1(10, 1);
PrintList(L1);
L1.remove(1);
PrintList(L1);
return 0;
}
list数据存取
只支持存取首位：
-
.front();//返回第一个元素
-
.back();//返回最后一个元素
list本质是链表，不是用连续性空间存储数据
-
不能直接利用中括号和at的方式进行访问，而且它的迭代器不支持随机访问，只能前移和后移
//验证迭代器是不支持随机访问的
list<int>L1(10, 1);
list<int>::iterator it = L1.begin();
it++;//可以运行
//it += 1;//会报错
如何验证容器支持的迭代器：
-
it++;//支持向前
-
it--;//双向迭代器
-
it += 1;//支持随机访问
list反转和排序
-
.reverse();//反转链表
-
.sort();//链表排序
不能使用sort(L1.begin(), L1.end());
- 所有不支持随机访问迭代器的容器，不可以用标准算法
- 不支持随机访问迭代器的容器，内部会提供一些对应的算法
sort默认升序排列，如果要降序，要写仿函数，sort参数为函数名
#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
bool myCompare(int v1,int v2)
{
//降序，就让第一个数大于第二个数
return v1 > v2;
}
int main()
{
//验证迭代器是不支持随机访问的
list<int>L1;
for (int i = 0; i < 10; i++)
{
L1.push_back(i);
}
PrintList(L1);
L1.reverse();
PrintList(L1);
L1.sort();//默认从小到大
PrintList(L1);
L1.sort(myCompare);
PrintList(L1);
return 0;
}
自定义数据类型排序
以Person为例，有姓名、年龄、身高等属性
排序规则：按照年龄进行升序，如果年龄相同，按照身高进行降序
高级排序方法：
- 制定排序规则，年龄相同和不同时分别如何排序
- 注意返回值表达式中的
>和<，分别为降序和升序
#include <iostream>
#include<list>
#include<string>
using namespace std;
class Person
{
public:
Person(string name, int age, int height)
{
this->m_name = name;
this->m_age = age;
this->m_height = height;
}
string m_name;
int m_age;
int m_height;
};
//制定排序规则
bool myCompare(Person& p1, Person& p2)
{
//按照年龄升序
if (p1.m_age == p2.m_age)
//年龄相同，按照身高降序
return p1.m_height > p2.m_height;
else
return p1.m_age < p2.m_age;
}
int main()
{
list<Person>l;
//准备数据
Person p1("A", 10, 100);
Person p2("B", 17, 90);
Person p3("C", 15, 190);
Person p4("D", 15, 150);
Person p5("E", 15, 90);
//插入数据
l.push_back(p1);
l.push_back(p2);
l.push_back(p3);
l.push_back(p4);
l.push_back(p5);
for (list<Person>::iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it).m_name << " " << (*it).m_age << " " << (*it).m_height << endl;
}
l.sort(myCompare);
for (list<Person>::iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it).m_name << " " << (*it).m_age << " " << (*it).m_height << endl;
}
return 0;
}
