STL库之单链表:forward_list

class template

forward_list

<forward_list>

template < class T, class Alloc = allocator<T> > class forward_list;

Forward list

前向链表(单链表)是序列容器,使固定时间插入和擦除操作序列内的任何地方。

前向链表的实现方式和单链表相同;单链表可以存储所包含的每个元素在不同的和无关的存储位置。

在序列中顺序保存每个元素指向下一个元素的关联。

forward_list容器与list容器的主要设计区别是list保持内部唯一的一个链接到下一个元素,而后者则保持每个元素的两个链接:一个指向下一个元素和一个前一个。(即通俗意义上的双端链表)允许高效在两个方向迭代,但每个元素的消耗额外的存储空间,并轻微较高的时间开销插入和删除元素的迭代。forward_list对象,从而比list对象更有效率,虽然他们只能向前遍历。

与其他的基本标准序列容器(arrayvector和deque)相比,forward_list一般在容器内的任何位置中的元素的插入、提取和移动操作效率更高,因此在算法中较密集的使用这些操作,例如排序算法。

相比其他序列容器,forward_list的主要缺点是缺乏直接访问他们的位置的元素,例如,要进入第六个元素在forward_list的一个遍历从一开始就到那个位置,这需要线性时间之间的距离。他们也消耗了一些额外的内存保持连接信息相关联的每个元素(这可能是一个小型的元素的大链表的重要因素)。

考虑到forward_list类模板设计的性能:根据设计,它是作为一个简单的手写C风格的单链表一样高效,实际上是仅有的一个标准容器故意缺乏其大小的成员函数是出于效率的考虑。由于其作为一个链表的性质,有一个大小成员在固定的时间,需要保持一个内部的计数器保存其大小(和链表一样)。这会消耗一些额外的存储和使插入和删除操作,效率较低。为了获得一个forward_list对象的大小,可以用其开始和结束,这是一个线性时间的操作距离算法。

 

容器属性

序列

    在一个严格的线性序列中序列容器的元素是有序的。个别元素的访问是通过他们在这个序列中的位置。

链表

   每个元素保持如何找到下一个元素的信息,允许常量时间在特定元素(甚至整个范围)后进行插入和擦除操作,但没有直接随机存取。  

分配器的获取

   容器使用一个分配器对象动态地处理其存储需求。

模板参数

T

   元素的类型。
    作为成员类型forward_list:: value_type的别名。

Alloc

   用来定义存储分配模型的分配器对象的类型。默认情况下使用了分配器类模板,它定义了最简单的内存分配模式和单独存在。   

   别名成员类型forward_list的::allocator_type的。

 

在参考的forward_list成员函数,这些相同的名称被假定为模板参数。

成员类型   

成员类型

定义

备注

value_type

The first template parameter (T)

 

allocator_type

The second template parameter (Alloc)

defaults to: allocator<value_type>

reference

value_type&

 

const_reference

const value_type&

 

pointer

allocator_traits<allocator_type>::pointer

for the default allocator: value_type*

const_pointer

allocator_traits<allocator_type>::const_pointer

for the default allocator: const value_type*

iterator

a forward iterator to value_type

convertible to const_iterator

const_iterator

a forward iterator to const value_type

 

size_type

an unsigned integral type

usually the same as size_t

difference_type

a signed integral type

usually the same as ptrdiff_t

 

 成员函数

构造函数

构造函数 forward_list  (公有成员函数 )

析构函数

析构函数 forward_list (公有成员函数 )

=操作运算符

分配内容 (公有成员函数)

迭代器

before_begin

返回指向开始之前的迭代器指针 (公有成员函数 )

begin

返回指向开始的迭代器指针 (公有成员类型 )

end

返回指向结束的迭代器指针  (公有成员函数 )

cbefore_begin

返回指向开始之前的常迭代器指针 (公有成员函数 )

cbegin

返回指向指向开始的常迭代器指针 (公有成员函数 )

cend

返回指向结束的常迭代器指针 (公有成员函数 )

容量

empty

判断是否为空 (公有成员函数 )

max_size

返回容量的最大值 (公有成员函数 )

元素的获取

front

获得第一个元素值 (公有成员函数 )

修饰符

assign

分配内容 (公有成员函数 )

emplace_front

构造并插入元素到首位置 (公有成员函数 )

push_front

插入元素到首位置 (公有成员函数 )

pop_front

删除首位置的元素 (公有成员函数 )

emplace_after

 构造并插入元素 (公有成员函数 )

insert_after

插入元素 (公有成员函数 )

erase_after

擦除元素 (公有成员函数 )

swap

交换内容 (公有成员函数 )

resize

改变容量大小 (公有成员函数 )

clear

清除内容 (公有成员函数 )

操作

splice_after

移动元素从另一个前向链表 (公有成员函数 )

remove

删除特定值的元素 (公有成员函数 )

remove_if

删除符合条件的元素 (公有成员模板函数 )

unique

删除重复值 (成员函数 )

merge

合并排序链表 (公有成员函数 )

sort

容器中的元素排序 (公有成员函数 )

reverse

反转元素的顺序 (公有成员函数 )

观察者

get_allocator

获取分配器 (公有成员函数 )

全局函数

operators (forward_list)

链表的全局关系运算函数 (函数模板 )

swap (forward_list)

 交换两个前向链表的内容(函数模板 )   

更多相关文章
  • package com.ds.link; /** * <p> * <strong>数据结构之Java单链表</strong> * </p> * <p> * 单链表提供了在列表头的高效插入和删除操作,不过在单链表的末尾的插入操作效率很低. * ...
  • 数据结构之单链表区第i个元素的算法算法思路: 1.声明一个结点p指向第一个结点,初始化j从1开始 2.当j<i时就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1 3.若到链表末尾p为空,则说明第i个元素不存在 4.否则查找成功,将欲删除的结点p->pNext赋值给q 5.将q ...
  • 02-1. Reversing Linked List (25) http://www.patest.cn/contests/mooc-ds/02-1 时间限制  400 ms  内存限制   65536 kB   代码长度限制  8 B  判题程序  Standard  作者CHEN, Yue G ...
  •     总结1:今天找到了昨天scanf的问题答案,scanf与printf一样的神奇而复杂,稍不留神,就会被坑.scanf函数在读入非空白符分割的多个字符串的解决方法是这个:/* 以 分割 */ scanf("login%d%[^]%[^]", &type, name, ...
  • 单链表的熟悉使用,注意测试用例的全面 //使用引用的作用等同于使用二级指针,在传递指针时 //传引用是可能改变Link,而有的函数只需改变->next,此时不需传引用 #include<stdio.h> #include<malloc.h> #include<st ...
  • Description 建立长度为n的单链表A和长度为m的单链表B,n>0,m>0.编程实现将B表链接在A表的尾端,形成一个单链表A.数据类型指定为字符型. Input 第一行为A表的长度n: 第二行为A表中的数据元素 第三行为B表的长度m: 第四行为B表中的数据元素. Output 输 ...
  • 方法: 1.在jni文件夹下新建Application.mk; 增加 APP_STL := stlport_static右边的值还能够换成以下几个: system - 使用默认最小的C++执行库,这样生成的应用体积小,内存占用小,但部分功能将无法支持 stlport_static - 使用STLpo ...
  • 1:SList结构 typedef struct _GSList GSList; struct _GSList { gpointer data; GSList *next; }; 2: SList 原型 GSList* g_slist_append (GSList *list, gpointer d ...
一周排行