参考:
http://blog.csdn.net/devourheavens/article/details/7497172
http://zh.cppreference.com/w/cpp/container/forward_list
forward_list
<forward_list>
template < class T, class Alloc = allocator<T> > class forward_list;
Forward list
前向链表是序列容器,使固定时间插入和擦除操作序列内的任何地方。
前向链表的实现方式和单链表相同;单链表可以存储所包含的每个元素在不同的和无关的存储位置。
在序列中顺序保存每个元素指向下一个元素的关联。
forward_list容器与list容器的主要设计区别是list保持内部唯一的一个链接到下一个元素,而后者则保持每个元素的两个链接:一个指向下一个元素和一个前一个。允许高效在两个方向迭代,但每个元素的消耗额外的存储空间,并轻微较高的时间开销插入和删除元素的迭代。forward_list对象,从而比list对象更有效率,虽然他们只能向前遍历。
与其他的基本标准序列容器(array,vector和deque)相比,forward_list一般在容器内的任何位置中的元素的插入、提取和移动操作效率更高,因此在算法中较密集的使用这些操作,例如排序算法。
相比其他序列容器,forward_lists的主要缺点是缺乏直接访问他们的位置的元素,例如,要进入第六个元素在forward_list的一个遍历从一开始就到那个位置,这需要线性时间之间的距离。他们也消耗了一些额外的内存保持连接信息相关联的每个元素(这可能是一个小型的元素的大链表的重要因素)。
考虑到forward_list类模板设计的性能:根据设计,它是作为一个简单的手写C风格的单链表一样高效,实际上是仅有的一个标准容器故意缺乏其大小的成员函数是出于效率的考虑。由于其作为一个链表的性质,有一个大小成员在固定的时间,需要保持一个内部的计数器保存其大小(和链表一样)。这会消耗一些额外的存储和使插入和删除操作,效率较低。为了获得一个forward_list对象的大小,可以用其开始和结束,这是一个线性时间的操作距离算法。
容器属性
序列
在一个严格的线性序列中序列容器的元素是有序的。个别元素的访问是通过他们在这个序列中的位置。
链表
每个元素保持如何找到下一个元素的信息,允许常量时间在特定元素(甚至整个范围)后进行插入和擦除操作,但没有直接随机存取。
分配器的获取
容器使用一个分配器对象动态地处理其存储需求。
1、成员函数
|
构造 forward_list (公开成员函数)
explicit forward_list( const Allocator& alloc = Allocator() );
|
(C++11 起) (C++14 前) |
forward_list() : forward_list( Allocator() ) {} explicit forward_list( const Allocator& alloc ); |
(C++14 起) |
forward_list( size_type count,
const T& value,
const Allocator& alloc = Allocator()); |
(2) |
(C++11 起) |
|
(3) |
|
explicit forward_list( size_type count );
|
(C++11 起) (C++14 前) |
explicit forward_list( size_type count, const Allocator& alloc = Allocator() );
|
(C++14 起) |
template< class InputIt >
forward_list( InputIt first, InputIt last,
const Allocator& alloc = Allocator() ); |
(4) |
(C++11 起) |
forward_list( const forward_list& other );
|
(5) |
(C++11 起) |
forward_list( const forward_list& other, const Allocator& alloc );
|
(5) |
(C++11 起) |
forward_list( forward_list&& other );
|
(6) |
(C++11 起) |
forward_list( forward_list&& other, const Allocator& alloc );
|
(7) |
(C++11 起) |
forward_list( std::initializer_list<T> init, const Allocator& alloc = Allocator() ); |
(8) |
(C++11 起) |
|
|
|
从各种数据源构造新容器,可选地使用用户提供的分配器 alloc 。
1) 默认构造函数。构造空容器。
2) 构造拥有 count 个有值 value 的元素的容器。
3) 构造拥有个 count 默认插入的 T 实例的容器。不进行复制。
4) 构造拥有范围 [first, last) 内容的容器。
若 InputIt 是整数类型,则此构造函数拥有的效果同 forward_list(static_cast<size_type>(first), static_cast<value_type>(last), a) 。 |
(C++11 前) |
此重载仅若InputIt 满足 输入迭代器 (InputIterator ) 才参与重载决议,以避免和重载 (2) 的歧义。 |
(C++11 起) |
5) 复制构造函数。构造拥有 other 内容的容器。若不提供 alloc ,则如同通过调用 std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.get_allocator()) 获得分配器。
6) 移动构造函数。用移动语义构造拥有 other 内容的容器。分配器通过属于 other 的分配器移动构造获得。
7) 有分配器扩展的移动构造函数。将 alloc 用作新容器的分配器,从 other 移动内容;若 alloc != other.get_allocator() ,则它导致逐元素移动。
8) 构造拥有 initializer_list init 内容的容器。
参数
alloc |
- |
用于此容器所有内存分配的分配器 |
count |
- |
容器的大小 |
value |
- |
以之初始化容器元素的值 |
first, last |
- |
复制元素的来源范围 |
other |
- |
用作初始化容器元素来源的另一容器 |
init |
- |
用作初始化元素来源的 initializer_list |
复杂度
1) 常数
2-3) 与 count 成线性
4) 与 first 和 last 的距离成线性
5) 与 other 的大小成线性
6) 常数。
7) 若 alloc != other.get_allocator() 则为线性,否则为常数。
8) 与 init 的大小成线性。
异常
到 Allocator::allocate 的调用可能抛出。
注意
在容器移动构造(重载 (6) )后,指向 other 的引用及迭代器(除了尾迭代器)保持合法,但指代现于 *this 中的元素。
|
|
析构 forward_list (公开成员函数)
|
|
赋值给容器 (公开成员函数)
forward_list& operator=( const forward_list& other );
|
(1) |
(C++11 起) |
|
(2) |
|
forward_list& operator=( forward_list&& other );
|
(C++11 起) (C++17 前) |
forward_list& operator=( forward_list&& other ) noexcept(/* see below */);
|
(C++17 起) |
|
(3) |
(C++11 起) |
|
|
|
替换容器内容。
1) 复制赋值运算符。以 other 的副本替换内容。 若 std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value 为 true ,则以源分配器的副本替换目标分配器。若源分配器与目标分配器不比较相等,则用目标( *this )分配器销毁内存,然后在复制元素前用 other 的分配器分配。 (C++11 起).、
2) 移动赋值运算符。用移动语义以 other 的内容替换内容(即从 other 移动 other 中的数据到此容器)。之后 other 在合法但未指定的状态。若 std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value 为 true ,则用源分配器的副本替换目标分配器。若它为 false 且源与目标分配器不比较相等,则目标不能取走源内存的所有权,而必须单独移动赋值逐个元素,用自己的分配器按需分配额外的内存。任何情况下,原先在 *this 中的元素要么被销毁,要么以逐元素移动赋值替换。
3) 以 initializer_list ilist 所标识者替换内容。
参数
other |
- |
用作数据源的另一容器 |
ilist |
- |
用作数据源的 initializer_list |
返回值
*this
复杂度
1) 与 *this 和 other 的大小成线性。
2) 与 *this 的大小成线性,除非分配器不比较相等且不传播,该情况下与 *this 和 other 的大小成线性。
3) 与 *this 和 ilist 的大小成线性。
注意
容器移动赋值(重载 (2) )后,除非不兼容的分配器强制逐元素赋值,否则指向 other 的引用、指针和迭代器(除了尾迭代器)都保持合法,不过指代的元素现在在 *this 中。
|
|
|
|
|
将值赋给容器 (公开成员函数)
void assign( size_type count, const T& value );
|
(1) |
(C++11 起) |
template< class InputIt > void assign( InputIt first, InputIt last ); |
(2) |
(C++11 起) |
|
(3) |
(C++11 起) |
|
|
|
替换容器的内容。
1) 以 count 份 value 的副本替换内容。
2) 以范围 [first, last) 中元素的副本替换内容
若 InputIt 为整数类型,则此重载与 (1) 拥有相同效果。 |
(C++11 前) |
此重载仅若 InputIt 满足输入迭代器 (InputIterator ) 才参与重载决议。 |
(C++11 起) |
3) 以来自 initializer_list ilist 的元素替换内容。
所有指向容器元素的迭代器、指针及引用均被非法化。
参数
count |
- |
容器的新大小 |
value |
- |
用以初始化容器元素的值 |
first, last |
- |
复制来源元素的范围 |
ilist |
- |
复制值来源的 initializer_list |
复杂度
1) 与 count 成线性
2) 与 first 和 last 间的距离成线性
3) 与 ilist.size() 成线性
|
|
|
|
|
返回相关的分配器 (公开成员函数)
allocator_type get_allocator() const;
|
|
(C++11 起) |
|
|
|
返回与容器关联的分配器。
参数
(无)
返回值
关联的分配器。
复杂度
常数。
|
|
example
1 #include<iostream>
2 #include<string>
3 #include<forward_list>
4
5 using namespace std;
6
7 //队列重载<<
8 template<typename T>
9 ostream& operator<<(ostream& s, const forward_list<T>& v)
10 {
11 s.put('[');
12 char comma[3] = { '