[C++]STL-list容器

链表

链表是由一系列节点组成的，节点包含两个域，一个数据域，一个指针域。

链表内存是非连续的，所以添加删除元素，时间复杂度都是常数项，不需要移动元素，比数组添加元素效率高

链表只在需要的时候才分配内存

链表需要额外的空间保存节点的关系

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

void PrintList(list<int> mlist) {
    for (list<int>::iterator it = mlist.begin(); it != mlist.end(); it++) {
        cout << (*it) << "  ";
    }
    cout << endl;
}

//初始化
void ListTest1(){
    list<int> list1 = { 1,45,4,55,78,12 };
    list<int> list2(5, 6);  //含参构造
    list<int> list3(list2);  //拷贝构造
    list<int> list4(list1.begin(), list1.end());   //截取部分链表进行构造
    //遍历链表
    PrintList(list1);
    cout << "------------------------" << endl;
    PrintList(list2);
    cout << "------------------------" << endl;
    PrintList(list3);
    cout << "------------------------" << endl;
    PrintList(list4);

}


//list容器插入删除
void ListTest2() {
    list<int> list1;
    list1.push_back(12);  //尾部插入元素
    list1.push_back(45);
    list1.push_front(1);   //头部插入元素
    list1.push_front(52);
    list1.push_back(1);

    list1.insert(list1.begin(), 100);  //指定位置插入
    list<int>::iterator it = list1.begin();
    it++;
    it++;
    list1.insert(it, 500);


    list1.pop_back();   //尾部删除元素
    list1.pop_front();   //头部删除元素

    list1.erase(it, list1.end());  //删除指定位置或区间的元素

    list1.remove(1);  //删除匹配的所有元素


    list1.clear();  //清空所有元素

}


//list大小赋值操作
void ListTest() {
    list<int> list1 = { 1,45,4,55,78,12 };
    list<int> list2;
    //size,empty,resize等函数与之前相同
    list2.assign(10, 5);
    list2.swap(list1);
    PrintList(list1);
    cout << "------------------------" << endl;
    PrintList(list2);
}


bool MyCompare1(int v1,int v2) {
    return v1 > v2;
}
//list排序操作
void ListTest4() {
    list<int> list1 = { 1,45,4,55,78,12 };
    list1.reverse();  //容器内元素反转
    PrintList(list1);
    list1.sort();  //这里的sort不是算法，而实list类默认实现的方法，默认从小到大
    PrintList(list1);
    list1.sort(MyCompare1);  //按要求排序
    PrintList(list1);
    //算法提供的sort支持可随机访问的容器
    //list不支持随机访问，所以list只利用自身提供的sort方法


}




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