STL\_list

编程与经验 c++

list容器
list使用

list容器

list 是顺序容器的一种。list是一个双向链表。使用list需要包含头文件list。双向链表的每个元素中都有一个指针指向后一个元素，也有一个指针指向前一个元素。

双向链表

在list容器中，在已经定位到要增删元素的位置的情况下，增删元素能在常数时间内完成。在$a_i$和$a_i$+1之间插入一个元素，只需要修改$a_i$和$a_i$+1中的指针即可。

链表插入

list的构造函数和许多成员函数的用法都与vector类似。除了顺序容器都有的成员函数外，list容器还独有如下表所示的成员函数（此表不包含全部成员函数，且有些函数的参数较为复杂，表中只列出函数名）

成员函数	作用
void push_front(const T& x)	将x插入链表最前面
void pop_front()	删除链表最前面的元素
void sort(…)	将链表从小到大排序
void remove(const T &val)	删除和val相等的元素
bool remove_if(…)	删除符合某种条件的元素
void unique()	删除所有和前一个元素相等的元素
void merge(list &x)	将链表x合并进来并清空x。要求链表自身和x都是有序的
void splice(iterator i, list &x, iterator first, iterator last)	在位置 i 前面插入链表x中的区间[first, last)，并在链表x中删除该区间。链表自身和链表x可以是同一个链表，只要i不在[first, last)中即可

STL中的算法sort可以用来对vector和deque排序，它需要随机访问迭代器的支持。因为list不支持随机访问迭代器，所以不能用算法sort对list容器排序。因此，list容器引入了sort成员函数以完成排序。

list使用

#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
class A {
private: int n;
public:
    A(int n_) { n = n_; }
    friend bool operator < (const A & a1, const A & a2);
    friend bool operator == (const A & a1, const A & a2);
    friend ostream & operator << (ostream & o, const A & a);
};
bool operator < (const A & a1, const A & a2) {
    return a1.n < a2.n;
}
bool operator == (const A & a1, const A & a2) {
    return a1.n == a2.n;
}
ostream & operator << (ostream & o, const A & a) {
    o << a.n;
    return o;
}
template <class T>
void Print(T first, T last)
{
    for (; first != last; ++first)
        cout << *first << " ";
    cout << endl;
}
int main()
{
    A a[5] = { 1, 3, 2, 4, 2 };
    A b[7] = { 10, 30, 20, 30, 30, 40, 40 };
    list<A> lst1(a, a + 5), lst2(b, b + 7);
    lst1.sort();
    cout << "1)"; Print(lst1.begin(), lst1.end());
    lst1.remove(2);
    cout << "2)"; Print(lst1.begin(), lst1.end());
    lst2.pop_front();
    cout << "3)"; Print(lst2.begin(), lst2.end());40
    lst2.unique();
    cout << "4)"; Print(lst2.begin(), lst2.end());
    lst2.sort();
    lst1.merge(lst2);
    cout << "5)"; Print(lst1.begin(), lst1.end());
    cout << "6)"; Print(lst2.begin(), lst2.end());
    lst1.reverse();
    cout << "7)"; Print(lst1.begin(), lst1.end()); 1
    lst2.insert(lst2.begin(), a + 1, a + 4);
    list <A>::iterator p1, p2, p3;
    p1 = find(lst1.begin(), lst1.end(), 30);
    p2 = find(lst2.begin(), lst2.end(), 2);
    p3 = find(lst2.begin(), lst2.end(), 4);
    lst1.splice(p1, lst2, p2, p3);
    cout << "8)"; Print(lst1.begin(), lst1.end());
    cout << "9)"; Print(lst2.begin(), lst2.end());
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com