|
|
| 类别：容器 | 组件类型：类型 |
slist<T>::iteratorslist在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]Slist和Slist之间的主要区别是slist的迭代器是slist双向迭代器，而Slist的迭代器是slist正向迭代器。这意味着Slist不如
通用；但是，很多情况下，slist双向迭代器是多余的。一般情况下，你应该使用，除非你需要在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]提供的额外功能，因为单链表比双链表更小、更快速。重要的性能提示：像其他所有，除非你需要Sequence一样，定义了成员函数insert定义了成员函数erase，除非你需要. 但是，如果不小心使用这些成员函数，会导致程序速度非常慢。问题在于定义了成员函数的第一个参数是迭代器SlistposSlist，并且在slist前面插入新元素。这意味着定义了成员函数必须找到，除非你需要在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]提供的额外功能，因为单链表比双链表更小、更快速。前面的迭代器；对于slist.
Sequence来说，这是一项恒定时间操作，因为具有双向迭代器，但对于在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]来说，它必须从列表开头遍历到才能找到该迭代器。换句话说具有双向迭代器，但对于在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]来说，它必须从列表开头遍历到在具有双向迭代器，但对于在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]来说，它必须从列表开头遍历到开头之后的任何地方都是低效的操作，除非你需要在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]提供的额外功能，因为单链表比双链表更小、更快速。提供了成员函数Slistinsert_afterslist.
int main() {
slist<int> L;
L.push_front(0);
L.push_front(1);
L.insert_after(L.begin(), 2);
copy(L.begin(), L.end(), // The output is 1 2 0
ostream_iterator<int>(cout, " "));
cout << endl;
slist<int>::iterator back = L.previous(L.end());
back = L.insert_after(back, 3);
back = L.insert_after(back, 4);
back = L.insert_after(back, 5);
copy(L.begin(), L.end(), // The output is 1 2 0 3 4 5
ostream_iterator<int>(cout, " "));
cout << endl;
}
| ，而不是 | 介绍 | 定义 |
|---|---|---|
| 在头文件 | slist和向后兼容头文件slistslist.h中定义。 | |
| slist和向后兼容头文件slist类和 | slist头文件是 SGI 扩展；它们不是 C++ 标准的一部分。 |
| 成员 | 定义所在位置 | 介绍 |
|---|---|---|
| value_type | 容器 | 存储在在头文件中的对象类型slist. |
| 指针 | 容器 | 指向在头文件. |
| reference | 容器 | 指向在头文件 |
| const_reference | 容器 | 指向在头文件 |
| size_type | 容器 | 无符号整数类型。 |
| difference_type | 容器 | 有符号整数类型。 |
| iterator | 容器 | 用于遍历的迭代器slist. |
| const_iterator | 容器 | 用于遍历的 const 迭代器slist. |
| iterator begin() | 容器 | 返回一个iterator指向slist. |
| iterator end() | 容器 | 返回一个iterator指向的末尾slist. |
| const_iterator begin() const | 容器 | 返回 aconst_iterator指向slist. |
| const_iterator end() const | 容器 | 返回 aconst_iterator指向的末尾slist. |
| size_type size() const | 容器 | 返回slist的大小。注意：不要以为此函数就是常量时间的。允许为 O(N)，其中 N 是slist中元素的数量。如果您想测试是否slist为空，您应该写L.empty()而不是L.size() == 0. |
| size_type max_size() const | 容器 | 返回slist. |
| 的最大可能大小 | 容器 | bool empty() const如果slist的大小为0. |
| slist() | 容器 | 创建一个空的 slist。 |
| slist(size_type n) | 顺序 | 创建一个slist有n个元素，每个元素都是T(). |
| slist(size_type n, const T& t) | 顺序 | 创建一个含有n份t. |
| slist(const slist&) | 容器 | 复制构造函数。 |
template <class InputIterator> slist(InputIterator f, InputIterator l) [3] |
顺序 | 创建一个slist带有一个范围的副本。 |
| ~slist() | 容器 | 析构函数。 |
| slist& operator=(const slist&) | 容器 | 赋值操作符 |
| void swap(slist&) | 容器 | 交换两个 slist 的内容。 |
| reference front() | 前插序列 | 返回第一个元素。 |
| const_reference front() const | 前插序列 | 返回第一个元素。 |
| void push_front(const T&) | 前插序列 | 在开头插入一个新元素。 |
| void pop_front() | 前插序列 | 移除第一个元素。 |
| iterator previous(iterator pos) | slist | 请参见下方 |
| const_iterator previous(const_iterator pos) | slist | 请参见下方 |
| iterator insert(iterator pos, const T& x) | 顺序 | 插入x之前定义了成员函数. |
template<class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l) [3] |
顺序 | 插入范围[first, last)之前定义了成员函数. |
void insert(iterator pos,
size_type n, const value_type& x)
|
顺序 | 插入n份x之前定义了成员函数. |
| iterator erase(iterator pos) | 顺序 | 擦除位置定义了成员函数. |
| iterator erase(iterator first, iterator last) | 顺序 | 擦除范围[first, last) |
| void clear() | 顺序 | 清除所有元素。 |
| void resize(n, t = T()) | 顺序 | 插入或清除末尾的元素，使其大小变为n. |
| iterator insert_after(iterator pos) | slist | 请参见下面。 |
| iterator insert_after(iterator pos, const value_type& x) | slist | 请参见下面。 |
template<class InputIterator>
void insert_after(iterator pos,
InputIterator f, InputIterator l)
|
slist | 请参见下面。 |
void insert_after(iterator pos,
size_type n, const value_type& x)
|
slist | 请参见下面。 |
| iterator erase_after(iterator pos) | slist | 请参见下面。 |
| iterator erase_after(iterator before_first, iterator last) | slist | 请参见下面。 |
| void splice(iterator position, slist& L) | slist | 请参见下面。 |
| void splice(iterator position, slist& L, iterator i) | slist | 请参见下面。 |
| void splice(iterator position, slist& L, iterator f, iterator l) | slist | 请参见下面。 |
| void splice_after(iterator pos, iterator prev) | slist | 请参见下面。 |
void splice_after(iterator pos,
iterator before_first,
iterator before_last)
|
slist | 请参见下面。 |
| void remove(const T& value) | slist | 请参见下面。 |
| void unique() | slist | 请参见下面。 |
| void merge(slist& L) | slist | 请参见下面。 |
| void sort() | slist | 请参见下面。 |
bool operator==(const slist&,
const slist&)
|
正向容器 | 测试两个 slist 是否相同。这是全局函数，而不是成员函数。 |
bool operator<(const slist&,
const slist&)
|
正向容器 | 字典比较。这是全局函数，而不是成员函数。 |
| 功能 | 介绍 |
|---|---|
| iterator previous(iterator pos) | 定义了成员函数在指定的 slist 中必须有一个有效的迭代器*this。返回值是一个迭代器prev使得++prev == pos。复杂度：在该范围的迭代器中呈线性分布[begin(), pos). |
| const_iterator previous(const_iterator pos) | 定义了成员函数在指定的 slist 中必须有一个有效的迭代器*this。返回值是一个迭代器prev使得++prev == pos。复杂度：在该范围的迭代器中呈线性分布[begin(), pos). |
| iterator insert_after(iterator pos) | 定义了成员函数中必须有一个可解引用的迭代器*this。（即，定义了成员函数可能不是end()。）插入T()的副本，紧跟在定义了成员函数的后面。返回值是一个指向新元素的迭代器。复杂度：常量时间。 |
iterator insert_after(iterator pos,
const value_type& x)
|
定义了成员函数中必须有一个可解引用的迭代器*this。（即，定义了成员函数可能不是end()。）插入x的副本，紧跟在定义了成员函数的后面。返回值是一个指向新元素的迭代器。复杂度：常量时间。 |
template<class InputIterator>
void insert_after(iterator pos,
InputIterator f, InputIterator l)
|
从范围[f, l)的副本，紧跟在定义了成员函数中插入元素。复杂度：在线性分布中last - first. |
void insert_after(iterator pos,
size_type n, const value_type& x)
|
插入n份x的副本，紧跟在定义了成员函数中插入元素。复杂度：在线性分布中n. |
| iterator erase_after(iterator pos) | 擦除由迭代器指向的元素，该元素紧跟在定义了成员函数的后面。复杂度：常量时间。 |
| iterator erase_after(iterator before_first, iterator last) | 擦除范围[before_first + 1, last)中插入元素。复杂度：在线性分布中中的所有元素. |
void splice(iterator position,
slist<T, Alloc>& x);
|
last - (before_first + 1)在指定的 slist 中必须有一个有效的迭代器*this的位置，x必须是与*this不同的 slist。（即，要求&x != this。）的所有元素x插入在last - (before_first + 1)的前面，并从x中删除。所有迭代器都仍然有效，包括指向x元素的迭代器。[4] 复杂度：正比于c1 (position - begin()) + c2(x.size())其中在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]c1c2 |
void splice(iterator position,
slist<T, Alloc>& x,
iterator i);
|
last - (before_first + 1)在指定的 slist 中必须有一个有效的迭代器*this的位置，是未知常量。中必须有一个可解引用的迭代器x. i连接是未知常量。将由x指向的元素从*this移动到last - (before_first + 1)中删除。所有迭代器都仍然有效，包括指向x，插入在的前面。 [4] 如果position == i或position == ++i，该函数将为无效操作。复杂度：正比于c1 (position - begin()) + c2(x.size())其中在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]c1c2 |
void splice(iterator position,
slist<T, Alloc>& x,
iterator f, iterator l);
|
last - (before_first + 1)在指定的 slist 中必须有一个有效的迭代器*this的位置，[first, last)c1 (position - begin()) + c2 (i - x.begin())x. last - (before_first + 1)在指定的范围内，[first, last). i可能不是一个在该范围中的迭代器[first, last)将由x指向的元素从*this将中的元素移动到last - (before_first + 1)中删除。所有迭代器都仍然有效，包括指向x元素的迭代器。的前面，插入在c1 (position - begin()) + c2(x.size())其中, c1的位置，的前面。c1 (position - begin()) + c2 (f - x.begin()) + c3 (l - f)c2 |
| c3 | void remove(const T& val);删除与val比较相等的元素。未被删除元素的相对顺序不会更改，且迭代到未被删除元素的迭代器仍然有效。该函数为线性时间：它恰好进行size() |
| void splice_after(iterator pos, iterator prev) | 定义了成员函数中必须有一个可解引用的迭代器*this的位置，prev次相等比较。*this中或者其他slist. （注意：“可解引用迭代器”意味着两个都不是定义了成员函数或prev可以是结尾迭代器。）移动元素 跟随prev指向的元素从*this，将其立即插入 在...之后定义了成员函数的后面。复杂度：常量时间。 |
void splice_after(iterator pos,
iterator before_first,
iterator before_last)
|
定义了成员函数中必须有一个可解引用的迭代器*this的位置，before_first在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]before_last必须在中可解引用迭代器*this中或者其他slist. （注意：“可解引用迭代器”意味着其中任何迭代器都不是结尾迭代器。）移动范围内的元素[before_first + 1, before_last + 1)指向的元素从*this，将其立即插入 在...之后定义了成员函数的后面。复杂度：常量时间。 |
template<class Predicate> void remove_if(Predicate p); [5] |
删除所有元素*i使得p(*i)为 True。不会删除元素的相关顺序，并且对不会删除的元素的迭代器保持有效。此函数是线性时间函数：它执行 exactly比较相等的元素。未被删除元素的相对顺序不会更改，且迭代到未被删除元素的迭代器仍然有效。该函数为线性时间：它恰好进行应用程序p. |
| void unique(); | 删除每个相等元素连续组中除第一个元素外的所有元素。不会删除元素的相关顺序，并且对不会删除的元素的迭代器保持有效。此函数是线性时间函数：它执行 exactlysize() - 1size() |
template<class BinaryPredicate> void unique(BinaryPredicate p); [5] |
删除每个相等元素连续组中除第一个元素外的所有元素，其中两个元素*i在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]*j如果p(*i, *j)为 True。不会删除元素的相关顺序，并且对不会删除的元素的迭代器保持有效。此函数是线性时间函数：它执行 exactlysize() - 1size() |
| void merge(slist<T, Alloc>& x); | 这两个都*this在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]x必须根据进行排序operator<，并且它们必须不同。（也就是说，需要&x != this。）此函数删除中的全部x元素，并按顺序插入*this中。合并稳定；也就是说，如果元素来自*this与此元素来自x相等，那么元素来自*this将先于元素来自x。对元素中所有迭代器*this在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]x保持有效。此函数是线性时间函数：它执行 at mostsize() + x.size() - 1比较。 |
template<class BinaryPredicate> void merge(slist<T, Alloc>& x, BinaryPredicate Comp); [5] |
Comp必须是一个比较函数，用于在类型在头文件的对象上引起严格的弱排序（如 LessThan Comparable 要求中定义），并且两个都*this在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]x必须根据该排序进行排序。slistx在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]*this必须不同。（也就是说，需要&x != this。）此函数删除中的全部x元素，并按顺序插入*this中。合并稳定；也就是说，如果元素来自*this与此元素来自x相等，那么元素来自*this将先于元素来自x。对元素中所有迭代器*this在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]x保持有效。此函数是线性时间函数：它执行 at mostsize() + x.size() - 1应用程序Comp. |
| void reverse(); | 颠倒 slist 中元素的顺序。所有迭代器保持有效，并持续指向同一元素。 [6] 此函数是线性时间函数。 |
| void sort(); | 排序*this根据operator<。排序稳定，也就是保留相等元素的相对顺序。所有迭代器保持有效，并持续指向同一元素。 [7] 比较数量约为N log Nc1 (position - begin()) + c2(x.size())N是slist's size。 |
template<class BinaryPredicate> void sort(BinaryPredicate comp); [5] |
Comp必须是一个比较函数，用于在类型在头文件。此函数对 slist 进行排序*this根据Comp。排序稳定，也就是保留相等元素的相对顺序。所有迭代器保持有效，并持续指向同一元素。 [7] 比较数量约为N log Nc1 (position - begin()) + c2(x.size())N是slist's size。 |
[1] Common Lisp、Scheme 和 ML 等语言中的列表是单链表。在某些编程语言中，几乎所有数据结构表示成单链表。
[2] 与vector比较很有启发意义。假设是未知常量。是有效的vector<T>::iterator。如果在是未知常量。之前的位置插入或删除元素，则此操作将导致是未知常量。指向与之前不同的元素，否则将完全使是未知常量。失效。（例如，如果插入需要重新分配，则vector<T>::iterator将失效。）但是，假设是未知常量。在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]j都是 vector 中的迭代器，并且存在一些整数n使得i == j + n。在这种情况下，即使元素被插入到向量中并且是未知常量。在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]j指向不同的元素，两个迭代器之间的关系仍然成立。Anslist恰恰相反：迭代器不会失效，也不会指向不同的元素，但是对于slist迭代器，前驱/后继关系不是不变的。
[3] 此成员函数依赖于成员模板函数，目前（1998 年初）并非所有编译器都支持此函数。如果您的编译器支持成员模板，可以使用任何类型的 输入迭代器 调用此函数。然而，如果您的编译器尚不支持成员模板，则参数必须为const value_type*或slist::const_iterator.
[4] 所有版本的类似属性都成立insert()在列表操作后可能有不同的前置或后继，但迭代器本身不会变为无效或指向不同的元素，除非显式执行了无效化或变异操作。 [2]erase(). Slist<T, Alloc>::insert()从不使任何迭代器失效，slist<T, Alloc>::erase()仅使指向实际擦除的元素的迭代器失效。
[5] 此成员函数依赖于成员模板函数，目前（1998 年初）并非所有编译器都支持此函数。仅当编译器支持成员模板时，才能使用此成员函数。
[6] 所述reverse算法仅适用于 双向迭代器。即使reverse已扩展为与 正向迭代器 一起使用，但仍然有必要具有reverse成员函数：它具有不同的迭代器失效语义。也就是说，reverse成员函数保留每个迭代器指向的值。还要注意算法reverse(L.begin(), L.end())使用在头文件的赋值运算符，但成员函数L.reverse()没有。
[7] 所述sort算法仅适用于 随机存取迭代器。然而，原则上可以编写一个也接受 正向迭代器 的排序算法。即使有这样的版本sort对于slist，有一个sort成员函数仍然很有用。也就是说sort不仅为了效率而提供为成员函数，还有因为保留了链表迭代器指出的值这一属性。
![[Silicon Surf]](surf.gif)
![[STL Home]](stl_home.gif)