C++学习笔记——STL常用容器——list

list容器的功能：将数据进行链式存储。

链表：一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。链表由一系列结点组成，结点由存储数据元素的数据域和存储下一个结点地址的指针域组成。

STL中的链表是一个双向循环链表。

list的优点：

采用动态存储分配，不会造成内存浪费和溢出；

执行插入和删除方便，修改指针的指向即可，不需要移动大量元素。

list的缺点：

空间（指针域）和时间（遍历）耗费较大。

list插入和删除元素不会造成原有的迭代器的失效。

list构造函数：

函数原型：

//list采用采用模板类实现,对象的默认构造形式：
list<T> lst;

//构造函数将[beg, end)区间中的元素拷贝给本身。
list(beg,end);

//构造函数将n个elem拷贝给本身。
list(n,elem);

//拷贝构造函数。
list(const list &lst);

list赋值和交换：

函数原型：

//将[beg, end)区间中的数据拷贝赋值给本身。
assign(beg, end);

//将n个elem拷贝赋值给本身。
assign(n, elem);

//重载等号操作符
list& operator=(const list &lst);

//将lst与本身的元素互换。
swap(lst); 

list大小操作：

函数原型：

//返回容器中元素的个数
size();

//判断容器是否为空
empty();

//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。 
// 如果容器变短，则末尾超出容器长度的元素被删除。
resize(num);

//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
​resize(num, elem); 

list插入和删除：

函数原型：

//在容器尾部加入一个元素
push_back(elem);

//删除容器中最后一个元素
pop_back();

//在容器开头插入一个元素
push_front(elem);

//从容器开头移除第一个元素
pop_front();

//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,elem);

//在pos位置插入n个elem数据，无返回值。
insert(pos,n,elem);

//在pos位置插入[beg,end)区间的数据，无返回值。
insert(pos,beg,end);

//移除容器的所有数据
clear();

//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(beg,end);

//删除pos位置的数据，返回下一个数据的位置。
erase(pos);

//删除容器中所有与elem值匹配的元素。
remove(elem);

例子：

#include <iostream>
#include <list>
using namespace std;


void print_list(const list<int>& list1){
    for(list<int>::const_iterator it=list1.begin();it!=list1.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

void test01(){
    list<int> list1;

//    尾插
    list1.push_back(10);
    list1.push_back(30);

//    头插
    list1.push_front(15);
    list1.push_front(25);
    print_list(list1);

//    尾删
    list1.pop_back();
    print_list(list1);

//    头删
    list1.pop_front();
    print_list(list1);

//    插入
    list<int>::iterator it=list1.begin();
    list1.insert(++it,16);
    print_list(list1);

//    删除
    it=list1.end();
    list1.erase(--it);
    print_list(list1);

//    移除
    list1.push_front(20);
    list1.push_front(20);
    list1.remove(20);
    print_list(list1);

//    清空
    list1.clear();
    print_list(list1);
}

int main() {
    test01();
    return 0;
}

list数据存取：

函数原型：

//返回第一个元素。
front();

//返回最后一个元素。
back();

list反转和排序：

函数原型：

//反转链表
reverse();

//链表排序
sort(); 

例子;

#include <iostream>
#include <list>
using namespace std;


void print_list(const list<int>& list1){
    for(list<int>::const_iterator it=list1.begin();it!=list1.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

bool my_compare(int a,int b){
    return a>b;
}

void test01(){
    list<int> list1;

//    尾插
    list1.push_back(10);
    list1.push_back(30);

//    头插
    list1.push_front(15);
    list1.push_front(25);
    print_list(list1);
    
//    反转
    list1.reverse();
    print_list(list1);
    
//    排序，默认从小到大
    list1.sort();
    print_list(list1);
    
//    指定规则，从大到小
    list1.sort(my_compare);
    print_list(list1);
}

int main() {
    test01();
    return 0;
}