STL中list的使用

list的底层结构

list底层是一个带头节点的双向循环链表，任意位置插入和删除时间复杂度0(1)

list迭代器
由于list底层是带头节点的双向循环链表，因此list的迭代器需要list的实现者自己提供

迭代器怎么实现呢？

迭代器的本质是指针，将指针封装出新的类型，指针有的操作，迭代器也视情况支持这些操作，比如：指针++，–，*，-> 等操作。迭代器在类中将这些操作重载出来即可，然后将list迭代器看作list的一种内部类型使用。

list的操作

Iterators: 迭代器

begin()
end()
rbegin() //重置后的开始
rend()   //重置后的结尾

Capacity:

empty（）   
size（）  //有效元素个数
resize（） //重置有效元素个数

Element access:

front  //返回第一个引用
back   //返回最后一个引用

Modifiers:

push_front
pop_front
push_back
pop_back
insert  //任意位置插入
erase    //任意位置删除
swap      //交换两个list
clear         //情空

Operations:

remove    //按条件删除元素
remove_if  
unique      //去重
merge      //合并两个有序链表
sort       //单链表排序
reversr    //单链表的逆置

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


void TestList1()
{
    //构造空的list
    list<int>L1;

    //构造10个值为1的list
    list<int>L2(10, 1);

    //构造用一段区间中的元素构造list
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> L3(arr, arr + sizeof(arr) / sizeof(arr[0]));

    //用L3取构造L4
    list<int>L4(L3);

    cout << "L1元素个数:" << L1.size() << endl;
    cout << "L2元素个数:" << L2.size() << endl;
    cout << "L3元素个数:" << L3.size() << endl;
    cout << "L4元素个数:" << L4.size() << endl;

    //遍历list1
    list<int>::iterator it1 = L1.begin();
    while (it1 != L1.end())
    {
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;

    //遍历list2
    list<int>::iterator it2 = L2.begin();
    while (it2 != L2.end())
    {
        cout << *it2 << " ";
        ++it2;
    }
    cout << endl;

    //遍历list3
    list<int>::iterator it3 = L3.begin();
    while (it3 != L3.end())
    {
        cout << *it3 << " ";
        ++it3;
    }
    cout << endl;

    //遍历list4
    list<int>::iterator it4 = L4.begin();
    while (it4 != L4.end())
    {
        cout << *it4 << " ";
        ++it4;
    }
    cout << endl;

    //逆向遍历list4
    list<int>::reverse_iterator it5 = L4.rbegin();
    while (it5 != L4.rend())
    {
        cout << *it5 << " ";
        ++it5;
    }
    cout << endl;
}
void TestList2()
{
    list<int>L;

    //尾插
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4);
    L.push_back(5);
    L.push_back(6);

    list<int>::iterator it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //尾删
    L.pop_back();
    L.pop_back();
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //头插
    L.push_front(0);
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    L.pop_front();
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    任意位置的插入
    //list<int>::iterator pos = find(L.begin(), L.end(), 2);
    //if (pos != L.end())
    //  pos = L.insert(pos, 9);
    //it = L.begin();
    //while (it != L.end());
    //{
  
    //  cout << *it << " ";
    //  ++it;
    //}
    //cout << endl;

    任意位置删除、
    //L.erase(pos);
    //it = L.begin();
    //while (it != L.end())
    //{
  
    //  cout << *it << " ";
    //  ++it;
    //}
    //cout << endl;

    //给list重新赋值
    int arr[] = { 1,2,3, 4, 5, 6, 7, 8, 9 };
    L.assign(arr, arr + sizeof(arr) / sizeof(arr[0]));
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    cout << "第一个元素" << L.front() << endl;
    cout << "第一个元素" << L.back() << endl;


}

void TestList3()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    list<int>L(arr, arr + sizeof(arr) / sizeof(arr[0]));
    list<int>::iterator it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    L.remove(3); //按值删除
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    class Odd
    {
    public:
        bool operator()(int value)
        {
            return value & 0x01;
        };
    };

    L.remove_if(Odd());
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

}

void TestList4()
{
    int arr[] = { 1, 2,  5, 3,1, 2, 3, 4, 5,7,6, 8, 9 };
    list<int>L(arr, arr + sizeof(arr) / sizeof(arr[0]));
    L.unique();

    list<int>::iterator it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl; 

    L.sort();
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    L.unique();
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //class Three
    //{
  
    //public:
    //  bool operator()(int left, int right)
    //  {
  
    //      return 0 == (left + right) % 3;
    //  }
    //};
    //L.unique(Three());
    //it = L.begin();
    //while (it != L.end());
    //{
  
    //  cout << *it << " ";
    //  ++it;
    //}
    //cout << endl;
}

void TestList5()
{
    list<int>L;
    L.push_back(1);
    L.push_back(4);
    L.push_back(6);

    list<int>L2;
    L2.push_back(2);
    L2.push_back(3);
    L2.push_back(8);

    //将两个已序链表合并成为一个链表，合并后依然有序
    L.merge(L2);
    list<int>::iterator it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //反转链表
    L.reverse();
    it = L.begin();
    while (it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
int main()
{

    //TestList1(); 构造及其遍历
    //TestList2();
    //TestList3();
    //TestList4();
    //TestList5();
    return 0;
}