list<T, Alloc>


类别: 容器	组件类型: 类型

描述

一个list是一个双向链表。也就是说，它是一个支持正向和反向遍历的序列，并且可以在开头、结尾或中间进行（均摊）常数时间的元素插入和删除。List具有以下重要特性：插入和拼接不会使指向列表元素的迭代器失效，并且即使删除也只会使指向被删除元素的迭代器失效。迭代器的顺序可能会发生改变（也就是说，list<T>::iterator在列表操作之后可能会有不同的前驱或后继，而不是之前），但迭代器本身不会失效，也不会指向不同的元素，除非该失效或变异是显式的。[1]

请注意，只支持正向遍历的单向链表有时也很有用。如果您不需要反向遍历，那么slist可能比list.

定义

在标准头文件list和非标准向后兼容头文件list.h中定义。

示例

list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 1 2 0

模板参数

参数	描述	默认值
`T`	的`list`值类型：存储在列表中的对象类型。
`Alloc`	的`list`的分配器，用于所有内部内存管理。	`alloc`

模型

可逆容器、前向插入序列、后向插入序列。

类型要求

无，除了可逆容器、前向插入序列和后向插入序列的要求所强加的那些要求。

公共基类

无。

成员

成员	定义位置	描述
`value_type`	容器	对象类型，`T`存储在列表中。
`pointer`	容器	指向`T`.
`reference`	容器	指向`T`
`const_reference`	容器	指向`T`
`size_type`	容器	无符号整型。
`difference_type`	容器	有符号整型。
`iterator`	容器	迭代器，用于遍历`list`.
`const_iterator`	容器	常量迭代器，用于遍历`list`.
`reverse_iterator`	可逆容器	迭代器，用于反向遍历`list`.
`const_reverse_iterator`	可逆容器	常量迭代器，用于反向遍历`list`.
`iterator begin()`	容器	返回一个`iterator`指向`list`.
`iterator end()`	容器	返回一个`iterator`指向`list`.
`const_iterator begin() const`	容器	返回一个`const_iterator`指向`list`.
`const_iterator end() const`	容器	返回一个`const_iterator`指向`list`.
`reverse_iterator rbegin()`	可逆容器	返回一个`reverse_iterator`指向反向列表的开头。
`reverse_iterator rend()`	可逆容器	返回一个`reverse_iterator`指向反向列表的结尾。
`const_reverse_iterator rbegin() const`	可逆容器	返回一个`const_reverse_iterator`指向反向列表的开头。
`const_reverse_iterator rend() const`	可逆容器	返回一个`const_reverse_iterator`指向反向列表的结尾。
`size_type size() const`	容器	返回`list`的大小。注意：你不应该假设这个函数是常数时间。它允许为O(N)，其中N是`list`中的元素数量。如果你想测试`list`是否为空，你应该写`L.empty()`而不是`L.size() == 0`.
`size_type max_size() const`	容器	返回`list`.
`bool empty() const`	容器	`true`如果`list`的大小为`0`.
`list()`	容器	创建一个空列表。
`list(size_type n)`	序列	创建一个包含`n`个元素的列表，每个元素都是`T()`.
`list(size_type n, const T& t)`	序列	创建一个包含`n`的副本`t`.
`list(const list&)`	容器	复制构造函数。
template <class InputIterator> list(InputIterator f, InputIterator l) [2]	序列	创建一个包含一个范围副本的列表。
`~list()`	容器	析构函数。
`list& operator=(const list&)`	容器	赋值运算符
`reference front()`	前向插入序列	返回第一个元素。
`const_reference front() const`	前向插入序列	返回第一个元素。
`reference back()`	序列	返回最后一个元素。
`const_reference back() const`	后向插入序列	返回最后一个元素。
`void push_front(const T&)`	前向插入序列	在开头插入一个新元素。
`void push_back(const T&)`	后向插入序列	在结尾插入一个新元素。
`void pop_front()`	前向插入序列	删除第一个元素。
`void pop_back()`	后向插入序列	删除最后一个元素。
`void swap(list&)`	容器	交换两个列表的内容。
`iterator insert(iterator pos, const T& x)`	序列	在`x`之前插入`pos`.
template <class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l) [2]	序列	插入范围`[f, l)`之前插入`pos`.
void insert(iterator pos, size_type n, const T& x)	序列	在`n`的副本`x`之前插入`pos`.
`iterator erase(iterator pos)`	序列	删除位置为`pos`.
`iterator erase(iterator first, iterator last)`	序列	删除范围`[first, last)`
`void clear()`	序列	删除所有元素。
`void resize(n, t = T())`	序列	在结尾插入或删除元素，使大小变为`n`.
`void splice(iterator pos, list& L)`	`list`	参见下文。
void splice(iterator pos, list& L, iterator i)	`list`	参见下文。
void splice(iterator pos, list& L, iterator f, iterator l)	`list`	参见下文。
`void remove(const T& value)`	`list`	参见下文。
`void unique()`	`list`	参见下文。
`void merge(list& L)`	`list`	参见下文。
`void sort()`	`list`	参见下文。
bool operator==(const list&, const list&)	前向容器	测试两个列表是否相等。这是一个全局函数，而不是成员函数。
bool operator<(const list&, const list&)	前向容器	字典序比较。这是一个全局函数，而不是成员函数。

新成员

这些成员在可逆容器、前向插入序列和后向插入序列要求中没有定义，而是特定于list.

函数	描述
void splice(iterator position, list<T, Alloc>& x);	`位置`必须是`this`中的有效迭代器，并且`x`必须是一个与`this`不同的列表。（也就是说，要求`&x != this`。）`x`的所有元素都插入到`位置`之前，并从`x`中删除。所有迭代器都保持有效，包括指向`x`中元素的迭代器。[3] 此函数为常数时间。
void splice(iterator position, list<T, Alloc>& x, iterator i);	`位置`必须是`this`中的有效迭代器，并且`i`必须是`x`. `Splice`将`i`指向的元素从`x`移动到`this`，在`位置`中删除。所有迭代器都保持有效，包括指向`x`之前插入它。[3] 如果`position == i`或`position == ++i`，则此函数为空操作。此函数为常数时间。
void splice(iterator position, list<T, Alloc>& x, iterator f, iterator l);	`位置`必须是`this`中的有效迭代器，并且`[first, last)`必须是`x`. `位置`中的有效范围，`[first, last)`. `Splice`不能是范围`[first, last)`指向的元素从`x`移动到`this`中的迭代器。将`位置`中删除。所有迭代器都保持有效，包括指向`x`中元素的迭代器。[3] 此函数为常数时间。
`中的元素移动到`	中，在`void remove(const T& val);`删除所有与`val`相等的元素。未删除元素的相对顺序保持不变，指向未删除元素的迭代器仍然有效。此函数为线性时间：它执行恰好
template<class Predicate> void remove_if(Predicate p); [4]	size()`个相等比较。`删除所有元素`i`，使得`val`p(i)`为真。未删除元素的相对顺序保持不变，指向未删除元素的迭代器仍然有效。此函数为线性时间：它执行恰好`.
`次`	p`void unique();`相等的元素。未删除元素的相对顺序保持不变，指向未删除元素的迭代器仍然有效。此函数为线性时间：它执行恰好
template<class BinaryPredicate> void unique(BinaryPredicate p); [4]	删除每个连续的相等元素组中除第一个元素以外的所有元素。未删除元素的相对顺序保持不变，指向未删除元素的迭代器仍然有效。此函数为线性时间：它执行恰好`个相等比较。`size() - 1`次比较。`删除每个连续的等效元素组中除第一个元素以外的所有元素，其中两个元素`*i`，使得`void unique();`相等的元素。未删除元素的相对顺序保持不变，指向未删除元素的迭代器仍然有效。此函数为线性时间：它执行恰好
`和`	j`this`size() - 1`x`如果`p(i, j)`为真，则被认为是等效的。`&x != this`void merge(list<T, Alloc>& x);`x`两者都`this`必须根据`this`operator<`x`排序，并且它们必须是不同的。（也就是说，要求`this`。）此函数删除所有`x`的元素，并将它们按顺序插入到`this`size() - 1`x`中。合并是稳定的；也就是说，如果`中的一个元素与`中的一个元素等效，那么来自
template<class BinaryPredicate> void merge(list<T, Alloc>& x, BinaryPredicate Comp); [4]	`的元素将排在来自`的元素之前。指向`T`中元素的所有迭代器都保持有效。此函数为线性时间：它最多执行`this`size() - 1`x`size() + x.size() - 1`x`size() - 1`this`次比较。`&x != this`void merge(list<T, Alloc>& x);`x`两者都`this`必须根据`this`operator<`x`排序，并且它们必须是不同的。（也就是说，要求`this`。）此函数删除所有`x`的元素，并将它们按顺序插入到`this`size() - 1`x`中。合并是稳定的；也就是说，如果`中的一个元素与`p(*i)`的元素将排在来自`.
`Comp`	必须是一个比较函数，它对类型为
`的对象产生一个严格的弱排序（如小于可比较要求中定义），并且两者都`	必须根据该排序进行排序。列表`this`必须是不同的。（也就是说，要求`p(i, *j)`void reverse();`反转列表中元素的顺序。所有迭代器都保持有效，并且继续指向相同的元素。[5] 此函数为线性时间。`void sort();`根据`对`list`进行排序。排序是稳定的，也就是说，等效元素的相对顺序得以保留。所有迭代器都保持有效，并且继续指向相同的元素。[6] 比较次数大约为
template<class BinaryPredicate> void sort(BinaryPredicate comp); [4]	`的元素将排在来自`N log N`T`，其中`*this`必须是不同的。（也就是说，要求`的元素将排在来自`void reverse();`反转列表中元素的顺序。所有迭代器都保持有效，并且继续指向相同的元素。[5] 此函数为线性时间。`void sort();`根据`对`list`进行排序。排序是稳定的，也就是说，等效元素的相对顺序得以保留。所有迭代器都保持有效，并且继续指向相同的元素。[6] 比较次数大约为

N

是的大小。必须是一个比较函数，它对类型为i的对象产生一个严格的弱排序（如小于可比较要求中定义）。此函数对列表进行排序。注释i[1] 与ivectori进行比较很有指导意义。假设进行排序。是一个有效的isize() - 1vector<T>::iterator。如果在n删除所有元素之前的位置插入或删除元素，那么此操作要么导致指向与之前不同的元素，要么使isize() - 1vector<T>::iterator完全失效。（例如，如果插入需要重新分配，则list将失效。）但是，假设listj

都是指向vector的迭代器，并且存在某个整数i == j + n。在这种情况下，即使在向量中插入元素，并且指向不同的元素，两个迭代器之间的关系仍然成立。一个.

正好相反：迭代器不会失效，也不会指向不同的元素，但是，对于迭代器，前驱/后继关系不是不变的。size() - 1[2] 此成员函数依赖于成员模板函数，这些函数目前（1998 年初）尚未得到所有编译器的支持。如果你的编译器支持成员模板，你可以使用任何类型的输入迭代器调用此函数。但是，如果你的编译器尚不支持成员模板，那么参数必须是. const value_type*类型或list::const_iterator类型。

[3] 类似的属性适用于所有版本的

insert()erase()List<T, Alloc>::insert()从不使任何迭代器失效，并且size() - 1list<T, Alloc>::erase()仅使指向实际被删除元素的迭代器失效。从不使任何迭代器失效，并且[4] 此成员函数依赖于成员模板函数，这些函数目前（1998 年初）尚未得到所有编译器的支持。只有当你的编译器支持成员模板时，你才能使用此成员函数。erase()[5] 如果list<T, Alloc>::erase()Llist<T, Alloc>::erase()是一个列表，请注意T的赋值运算符，而成员函数从不使任何迭代器失效，并且不会。

[6] 的排序算法仅适用于随机访问迭代器。然而，原则上，编写一个也接受双向迭代器的排序算法是可能的。即使存在这样的版本，排序，它仍然对list具有一个排序成员函数仍然有用。也就是说，排序提供为成员函数不仅是为了效率，也是因为它的属性，即它保留列表迭代器指向的值。

另请参阅

双向迭代器、可逆容器、序列，slist 的大小。.