STL list容器的简单认识
- list容器基本概念
- list容器构造函数
- list容器赋值和交换
- list容器大小操作
- list容器插入和删除
- list容器数据存取
- list容器反转和排序
- list排序案例
list容器基本概念
list容器是将数据进行链式存储的容器，链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
链表的组成：链表由一系列节点组成
节点的组成：一个是存放数据元素的数据域，另一个是存储下一个结点地址的指针域
链表的优点：可以对任意位置进行快速的插入或删除元素
缺点：容器的遍历速度没有数组快，占用的空间比数组大
STL中的链表是一个双向循环链表
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器
list的优点：
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list的缺点： - 链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大
list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的
list容器构造函数
list<T> lit;默认构造函数
list<int> lst;
list(beg, end);构造函数将[beg, end)中的元素拷贝给本身
list<int> lst;
list<int> lst_2(lst.begin(), lst.end());
list(n, elem);构造函数将n个elem拷贝给本身
list<int> lst(3, 12);
list(const list* list);拷贝构造函数
list<int> lst;
list<int> lst_2(lst);
list容器赋值和交换
assign(beg, end);将[beg, end)区间中的数据拷贝赋值给本身
list<int> lst;
list<int> lst2;
lst2.assign(lst.begin(), lst.end());
assign(n, elem);将n个elem拷贝赋值给本身
list<int> lst2;
lst2.assign(3, 12);
list& operator=(const list& lst);重载等号运算符
list<int> lst;
list<int> lst2;
lst2 = lst;
swap(lst);将lst与本身的元素互换
list<int> lst;
lst.push_back(12);
lst.push_back(13);
list<int> lst2;
lst2.push_back(14);
lst2.push_back(15);
lst2.swap(lst);
for (list<int>::iterator it = lst.begin(); it != lst.end(); it++)
{
std::cout << *it << " ";
}
std::cout << std::endl;
for (list<int>::iterator it = lst2.begin(); it != lst2.end(); it++)
{
std::cout << *it << " ";
}
list容器大小操作
size();返回容器中元素的个数
lis.size();
empty();判断容器是否为空
lis.empty();
resize(num);重新指定容器长度为num,容器变长，默认值填充之，容器变短，元素删除之
lis.resize(20);
resize(num, elem);重新指定容器长度为num,容器变长，elem填充之，容器变短，元素删除之
lis.resize(20, 10);
list容器插入和删除
push_back(elem);在容器尾部加入一个元素
list lst;
lst.push_back(12);
pop_back();删除容器尾部的一个元素
list lst;
lst.pop_back();
push_front(elem);在容器头部插入一个元素
list lst;
lst.push_front(12);
pop_front();删除容器头部的一个元素
list lst;
lst.pop_front();
insert(pos, elem);在pos位置插入elem元素的拷贝，返回新数据的位置
list lst;
lst.insert(lst.begin(), 100);
insert(pos, n, elem);在pos位置插入n个elem元素的拷贝，无返回值
list lst;
lst.insert(lst.begin(), 10, 100);
insert(pos, beg, end);在pos位置插入[beg, end)区间的数据，无返回值
list li;
list l2;
l2.insert(li.begin(), li.end());
clear();清空列表的数据
list ls;
ls.clear();
erase(beg, end);删除[beg, end)区间的数据，返回下一个数据的位置
list ls;
ls.earse(ls.begin(), ls.end());
earse(pos);删除pos位置的元素，返回下一个元素的位置
list ls;
ls.earse(ls.begin());
remove(elem);删除容器中所有与elem元素匹配的元素
list ls;
ls.remove(12);
list容器数据存取
front();返回第一个元素
list<int> lst;
lst.push_back(10);
lst.push_back(20);
//返回第一个元素
std::cout << lst.front() << std::endl;
back();返回最后一个元素
list<int> lst;
lst.push_back(10);
lst.push_back(20);
std::cout << lst.back() << std::endl;
list容器反转和排序
reverse();反转链表
#include <iostream>
#include <list>
using namespace std;
void printf(const list<int>& lst)
{
for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
std::cout << *it << " ";
}
std::cout << std::endl;
}
int main()
{
list<int> lst;
lst.push_back(10);
lst.push_back(20);
std::cout << "调用反转链表前：" << std::endl;
printf(lst);
lst.reverse();
std::cout << "调用反转链表后：" << std::endl;
printf(lst);
}
sort();链表排序
#include <iostream>
#include <list>
using namespace std;
void printf(const list<int>& lst)
{
for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
std::cout << *it << " ";
}
std::cout << std::endl;
}
bool compare(int a, int b)
{
//降序，第一个数大于第一个数
return a > b;
}
int main()
{
list<int> lst;
lst.push_back(10);
lst.push_back(30);
lst.push_back(20);
std::cout << "调用排序链表前：" << std::endl;
printf(lst);
lst.sort();
std::cout << "调用排序链表后：" << std::endl;
printf(lst);
//使用自定义比较方法
lst.sort(compare);
std::cout << "调用自定义排序链表后：" << std::endl;
printf(lst);
}
所有不支持随机访问迭代器的容器不能使用标准排序算法，这些容器会内置排序算法
list排序案例
定义一个Person类，包含姓名、年龄、身高三个属性，最终打印结果按照年龄进行升序，年龄一致则按照身高降序排列
#include <iostream>
#include <string>
#include <list>
#include <ctime>
using namespace std;
class Person
{
private:
string m_Name;
int m_Age;
float m_Height;
public:
Person(string name, int age, float height)
{
this->m_Age = age;
this->m_Height = height;
this->m_Name = name;
}
int getAge()
{
return this->m_Age;
}
float getHeight()
{
return this->m_Height;
}
//常函数内部不能修改属性值，除非属性添加关键字mutable
void printf() const
{
std::cout << this->m_Name << " 的年龄：" << this->m_Age << " 身高：" << this->m_Height << std::endl;
}
static bool compare(Person& front, Person& next)
{
if (front.getAge() < next.getAge())
{
return true;
}
if (front.getAge() == next.getAge()) {
return front.getHeight() >= next.getHeight();
}
return false;
}
};
void printfAll(const list<Person>& lst)
{
for (list<Person>::const_iterator it = lst.begin(); it != lst.end(); it++)
{
//常对象只能调用常函数
it->printf();
}
}
int main()
{
//随机数种子
srand((unsigned int)time(NULL));
string name_Str[] = { "张三","李四","王二","麻子" };
list<Person> person_list;
for (int i = 0; i < sizeof(name_Str) / sizeof(name_Str[0]); i++)
{
Person person(name_Str[i], rand() % 60 + 40, rand() % 150 + 40);
person_list.push_back(person);
}
std::cout << "调用排序前，初始化的信息为：" << std::endl;
printfAll(person_list);
std::cout << "调用排序后，排序后的信息为：" << std::endl;
person_list.sort(Person::compare);
printfAll(person_list);
}
