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 ...
一周排行
  • Python版本2.7.9 模拟POST请求 1 #coding:u8 2 import urllib 3 import urllib2 4 5 url = u"http://192.168.84.182: ...
  • 最近开始看html5,看到html5 canvas 可以直接drawImage ,于是看着文档写了个demo,可是总是空白的,一开始以为路径问题,各种改路径,改图片位置,后来以为是我Chrome 浏览器的问题,于是换
  • 2. Rust的三板斧 安全,迅速,並發
      Rust不是一个拥有前沿科技的革命性语言,但是Rust合并了已经在老的语言中证明了自己
  • 1.编译原理学什么? 答:学习将原程序转换为目标程序的原理以及一系列相关知识,学习编译器的工作原理. 2.为什么学编译原理? 答:为了更好地认识编译器原理,可以提高自己的陈序优化能力,写出更优秀的程序. 3.怎么学编
  • 最近使用mysql数据库的时候遇到了多种数字的类型,主要有int,bigint,smallint和tinyint.其中比较迷惑的是int和smallint的差别.今天就在网上仔细找了找,找到如下内容,留档做个总结:
  • js 操作ASP.NET服务器控件  在ASP.NET中使用js时,js获取DOM元素时,经常获取不到,这是因为获取的方法有误,现在介绍一方法,解决如何使用js获取ASP.NET控件在浏览器端生成html标签对应的i ...
  • 使用花生殼6.5客戶端FTP設置
    1.打开FTP客户端—选项—参数选择   2.设置为主动模式(PORT) 3.连接FTP服
  • blatSrc35.zip下载地址:http://users.soe.ucsc.edu/~kent/src/ 对于下载好的源代码安装包blatSrc35.zip,需进行编译,安装过程如下: 1.用unzip blat
  • 代码一:Timer_A触发转换 1 #include <msp430x14x.h> 2 void main() 3 { 4 WDTCTL = WDTPW + WDTHOLD; 5 P6SEL = BIT0 ...
  • ifconfig eth0 新ip 然后编辑/etc/sysconfig/network-scripts/ifcfg-eth0,修改ip 一.修改IP地址 [[email protected] network-scripts]$