引用在模板推导中的基础逻辑

reference

引用是C++相对于C语言指针引入的一个新语法,可以以简单变量来使用指针。这种语法在使用的时候还是比较方便的,但是也在模板类型推导的过程中也带来了一些需要额外关注的细节。

例子

下面的例子中,rt是一个引用类型,问题是在模板参数函数Harry的定义中,模板参数TSECER并没有包含引用类型,那么此时以rt为参数调用时,模板函数中的Fry参数是什么类型呢,或者更详细的说:引用会被传递给模板吗?

tsecer@harry: cat cpp.tmpl.type.deduction.cpp 
struct tsecer
{};

template<typename TSECER>
void Harry(const TSECER Fry)
{}

void Leela()
{
    tsecer t, &rt = t, *pt = &t;
    Harry(rt);
    Harry(pt);
}

资料

在网络上有关于该问题的一个讨论,答案也是简单明了:如果调用的地方是一个引用表达式,那么此时引用会先被剥离。

If an expression initially has the type “reference to T” ([dcl.ref], [dcl.init.ref]), the type is adjusted to T.

该答案引用了c++语法中的规定

If an expression initially has the type “reference to T” ([dcl.ref], [dcl.init.ref]), the type is adjusted to T prior to any further analysis. The expression designates the object or function denoted by the reference, and the expression is an lvalue or an xvalue, depending on the expression.
[Note 1: Before the lifetime of the reference has started or after it has ended, the behavior is undefined (see [basic.life]). — end note]

大致的意思是,在调用

Harry(rt);

时,此时rt是一个引用类型的表达式(expression),C++规定引用类型表达式在推导的时候会先去掉引用,所以rt作为参数的时候,匹配的argument是单独的tsecer类型—没有引用。所以,此时调用的时候会生成一个临时变量给Harry函数调用时使用,对应的模板函数也是单独的const TSECER类型而没有引用。

模板

前面说调用处类型是引用的话会先去掉引用,对应地,在模板参数定义中的引用也会做相应的处理,这个相对前一个规则来说是一个比较明确的位置。文档中这么说明

If P is a reference type, the referenced type is used for deduction.

这个感觉和调用处的说明相呼应:调用处表达式的引用会被剔除,而模板parameter中也只是使用引用的类型来进行匹配,这样其实两个部分是对应/对等的。或者说:引用不作为类型属性来进行模板匹配

这里再补充说明下,前面说的都是参数推导而不是参数替换(substitute)。当推导完成、参数替换之后,模板定义中就会有引用出现了。以下面代码为例

struct tsecer
{};

template<typename TSECER>
void Harry(const TSECER &Fry)
{}

void Leela()
{
    tsecer t, &rt = t;
    Harry(rt);
}

在调用处,rt先剥夺引用类型,成为简单的tsecer类型;在模板函数中,先去掉const(如果有volatile也会被剥离),然后去掉引用,此时参数中就是一个简单的TSECER类型;这样模板的parameter TSECER和调用处的argument tsecer直接简单匹配,推导出此次调用的模板parameter就是tsecer。最后将这个类型带入到Harry函数(参数替换),Harry就是一个const tsecer &类型为参数的函数了。

gcc

argument

/* In all nodes that are expressions, this is the data type of the expression.
   In POINTER_TYPE nodes, this is the type that the pointer points to.
   In ARRAY_TYPE nodes, this is the type of the elements.
   In VECTOR_TYPE nodes, this is the type of the elements.  */
#define TREE_TYPE(NODE) \
(CONTAINS_STRUCT_CHECK (NODE, TS_TYPED)->typed.type)

/* Like is_bitfield_with_lowered_type, except that if EXP is not a
   bitfield with a lowered type, the type of EXP is returned, rather
   than NULL_TREE.  */

tree
unlowered_expr_type (const_tree exp)
{
  tree type;
  tree etype = TREE_TYPE (exp);

  type = is_bitfield_expr_with_lowered_type (exp);
  if (type)
    type = cp_build_qualified_type (type, cp_type_quals (etype));
  else
    type = etype;

  return type;
}

对于引用类型,在gcc内部是

/* C unary `*' or Pascal `^'.  One operand, an expression for a pointer.  */
DEFTREECODE (INDIRECT_REF, "indirect_ref", tcc_reference, 1)

类型结构,也就是引用在gcc内部就是 ptr这种形式表达了,只是在语言层面屏蔽了指针的dereference。或者说,Harry(rt)和Harry(pt)在gcc看来是一样的。

在访问引用类型标识符时,编译器会自动把标识符转换为间接引用类型

/* We are using a reference VAL for its value. Bash that reference all the
   way down to its lowest form.  */

tree
convert_from_reference (tree val)
{
  if (TREE_TYPE (val)
      && TREE_CODE (TREE_TYPE (val)) == REFERENCE_TYPE)
    {
      tree t = TREE_TYPE (TREE_TYPE (val));
      tree ref = build1 (INDIRECT_REF, t, val);

      mark_exp_read (val);
       /* We *must* set TREE_READONLY when dereferencing a pointer to const,
	  so that we get the proper error message if the result is used
	  to assign to.  Also, &* is supposed to be a no-op.  */
      TREE_READONLY (ref) = CP_TYPE_CONST_P (t);
      TREE_THIS_VOLATILE (ref) = CP_TYPE_VOLATILE_P (t);
      TREE_SIDE_EFFECTS (ref)
	= (TREE_THIS_VOLATILE (ref) || TREE_SIDE_EFFECTS (val));
      val = ref;
    }

  return val;
}

而在build1_stat函数中,也是把引用的类型赋值给了TREE_TYPE,对应代码

TREE_TYPE (t) = type;

也就是说,unlowered_expr_type对于变量引用也同样返回的引用的类型。

tree
build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
{
  int length = sizeof (struct tree_exp);
  tree t;

  record_node_allocation_statistics (code, length);

  gcc_assert (TREE_CODE_LENGTH (code) == 1);

  t = ggc_alloc_tree_node_stat (length PASS_MEM_STAT);

  memset (t, 0, sizeof (struct tree_common));

  TREE_SET_CODE (t, code);

  TREE_TYPE (t) = type;
///...
}

parameter

/* Adjust types before performing type deduction, as described in
   [temp.deduct.call] and [temp.deduct.conv].  The rules in these two
   sections are symmetric.  PARM is the type of a function parameter
   or the return type of the conversion function.  ARG is the type of
   the argument passed to the call, or the type of the value
   initialized with the result of the conversion function.
   ARG_EXPR is the original argument expression, which may be null.  */

static int
maybe_adjust_types_for_deduction (unification_kind_t strict,
				  tree* parm,
				  tree* arg,
				  tree arg_expr)
{
///...
  /* [temp.deduct.call]

     If P is a cv-qualified type, the top level cv-qualifiers
     of P's type are ignored for type deduction.  If P is a
     reference type, the type referred to by P is used for
     type deduction.  */
  *parm = TYPE_MAIN_VARIANT (*parm);
  if (TREE_CODE (*parm) == REFERENCE_TYPE)
    {
      *parm = TREE_TYPE (*parm);
      result |= UNIFY_ALLOW_OUTER_MORE_CV_QUAL;
    }
///...
}

栗子

前面说的都是“顶层”类型说明,在非顶层结构中,依然是要严格匹配const、reference等类型的。

在下面的例子中,foo函数参数有引用,所以能够匹配成功;而bar函数的int没有引用,导致匹配失败。

tsecer@harry: cat -n  ref.in.func.arg.cpp    
     1  int foo(int &);
     2  int bar(int);
     3
     4  template<typename T>
     5  void baz(int(*)(T &))
     6  {
     7      T t;
     8  }
     9
    10  int tsecer()
    11  {
    12      baz(foo);
    13      baz(bar);
    14  }
    15
tsecer@harry: gcc -c ref.in.func.arg.cpp  
ref.in.func.arg.cpp: In function 'int tsecer()':
ref.in.func.arg.cpp:13:12: error: no matching function for call to 'baz(int (&)(int))'
     baz(bar);
            ^
ref.in.func.arg.cpp:5:6: note: candidate: template<class T> void baz(int (*)(T&))
 void baz(int(*)(T &))
      ^~~
ref.in.func.arg.cpp:5:6: note:   template argument deduction/substitution failed:
ref.in.func.arg.cpp:13:12: note:   mismatched types 'T&' and 'int'
     baz(bar);
            ^
tsecer@harry: 
本文转载于网络 如有侵权请联系删除

相关文章

  • 前中电技术总监带你3分钟通晓,互联网架构20年以来的演进

    作为一个Java程序员,你可能也思考过,为什么我还是普通开发,为什么我还是高级开发,普通开发和高级开发有什么区别?你是不是也想过要成为架构师?想要成为合格的架构师,就必须要了解架构的演进,今天,我们就来聊一聊,Java架构的演变历史。1、分布式微服务架构的演进分布式微服务架构的发展,主要经历了四个阶段:单一应用架构、垂直应用架构、分布式架构和弹性SOA架构。这张图是从Dubbo官网上下载的描述分布式架构演进过程的示意图,大家可以收藏一下。1)单体架构(AllinOne)从2000年开始,互联⽹在中国开始盛⾏起来,但是那时候⽹⺠数较少,网站流量也很小,只需要一台机器就可以运行所有的服务,只需要AllinOne单体架构就能满⾜需求。2)垂直应用架构(VerticalApplication)随着网站访问量的增加,一旦服务器或者数据库出现问题,将会导致整个系统故障,造成所有服务不可用,⽽且功能修改发布也不⽅便,所以,就把⼤系统拆分成了多个⼦系统,⽐如将“⽤户”、“商品”、“订单“等按业务进行拆分,也就是”垂直拆分“,并且每个⼦系统都部署到不同的服务器上。3)分布式架构(DistributedS

  • Linux下Tomcat启动报错:port already in use

    Linux下Tomcat启动报错:portalreadyinuse,导致该问题的原因很多,标题说明不了具体问题。在此仅说下我的操作,遇到的问题及其解决方法,希望能起到抛砖引玉的作用。启动tomcat,报错如下:Error:Exceptionthrownbytheagent:Java.rmi.server.ExportException:Portalreadyinuse:7800;nestedexceptionis:java.net.BindException:Addressalreadyinuse检查了${TOMCAT_HOME}/conf/server.xml,context.xml,web.xml等配置文件,未发现配置7800端口的地方。于是google搜索,一篇文章给了我提示:https://bowerstudios.com/node/636于是从${TOMCAT_HOME}/bin/catalina.sh启动文件中找到了答案。JAVA_OPTS="-server-Xms2048m-Xmx2048m-XX:PermSize=512m-XX:MaxPermSize=512

  • 运行你的第一个python程序

    开始吧!运行python程序,可以通过两种方法运行1.通过通过python的交互环境运行,就是如下图显示的这样2.将python代码写成脚本,在终端通过pythonxxx.py运行在交互环境运行1Mac打开终端-->python3进入交互环境,输入print("HelloWorld!")运行结果如下2Windows使用快捷键win+r打开运行输入python或python3(如果提示找不到文件,可能是因为没有配置好python环境变量,还可以通过开始菜单里找到python自带的ide环境)输入print("HelloWorld!")运行结果如下以脚本运行1Mac打开一个文件,输入print("HelloWorld!")保存为以.py结尾的文件,如hello.py 打开终端:输入python3hello.py2Windows同样创建一个以.py结尾的文件,输入相同内容win+r输入cmd,输入pythonhello.py(注意路径问题)如下图Windows添加环境变量把安装的Python程序的路径粘贴,复制到 我的电脑-&

  • javaFx 改变stage的标题条的图标

    原文来自:http://stackoverflow.com/questions/10275841/how-to-change-the-icon-on-the-title-bar-of-a-stage-in-java-fx-2-0-of-my-applicat/15206407#15206407importjavafx.application.Application; importjavafx.scene.Scene; importjavafx.scene.layout.StackPane; importjavafx.scene.image.Image; importjavafx.stage.Stage; publicclassStackoverflowIconextendsApplication { @Override publicvoidstart(Stagestage) { StackPaneroot=newStackPane(); Scenescene=newScene(root,300,250); //seticon stage.getIcons().add(newIm

  • 频繁刷屏网安圈的微软安全,这次给我们什么启示?

    编者按今年以来,微软公司频繁被国内网络安全从业者关注。引起最多讨论的是三件事:1、2021年1月,微软CEO宣布微软在2020年的安全业务收入达到100亿美元,年增长率超过40%。一时之间,安全行业纷纷热议“原来微软才是全球最大的网安厂商”!2、2021年6月25日,微软正式发布Windows11,特别提到Windows11提供了一个“零信任安全防护模式”的操作系统,来保护数据和跨设备访问。3、2021年7月14日,微软正式发布Windows365,再次提及Windows365服务遵从“零信任”原则,从设计源头确保安全。频繁在网安圈刷屏的微软安全给了国内厂商什么启发?此次发布Windows365对零信任市场有什么影响?本期产业安全TALK分享一篇来自“零信任产业标准工作组”的分析文章,从另一个角度分析微软的举措。作者:黄超编辑:罐子原标题:《微软发布Windows365因零信任刷了屏,“原生”零信任时代加速到来》微软Windows365这两天刷了屏,朋友圈里也看到大家很兴奋,“有了Win365就不需要其他零信任产品了”、“微软出颠覆性零信任方案了”、“零信任新玩法诞生”……好像没有人太

  • HDOJ(HDU) 2524 矩形A + B(推导公式、)

    ProblemDescription 给你一个高为n,宽为m列的网格,计算出这个网格中有多少个矩形,下图为高为2,宽为4的网格.Input 第一行输入一个t,表示有t组数据,然后每行输入n,m,分别表示网格的高和宽(n<100,m<100).Output 每行输出网格中有多少个矩形.SampleInput 2 12 24SampleOutput 3 30此方格其实就是求其中所有格子数,如果按宽度来算的话,1,2,3,…m,种情况,对每一种情况,有(1+2+3+…+n)个,所以归纳起来应该是(1+2+3+…+m)*(1+2+3+…+n)个,所以有了上面的代码,属于简单的数论题有n行和m列。 如果只看一行的话,它有多少个矩形呢?单个地数有m个,两个地数有m-1个……,m个地数有1个。 每一行就有:1+2+3+……+m个=m*(m+1)/2。 我们把每一行抽象成一个矩形,也就只剩一列了。一列的话,有:1+2+……+n=n*(n+1)/2个。 总结起来,就有:(1+m)*m/2*(1+n)*n/2那么多个了。importjava.util.Scanner; publicclass

  • 动画(CSS3) animation

    动画是CSS3中具有颠覆性的特征之一,可通过设置多个节点来精确控制一个或一组动画,常用来实现复杂的动画效果。动画序列0%是动画的开始,100%是动画的完成。这样的规则就是动画序列。 在@keyframes中规定某项css样式,就能创建由当前样式逐渐改变为新样式的动画效果 动画是使元素从一种样式逐渐变化为另一种样式的效果,可以改变任意多的样式任意多的次数。 用百分比来规定变化发生的时间,或用关键词"form"和"to",等同于0%和100%。 动画基本使用先定义动画 再调用动画 动画简写格式:animation:动画名称动画时间运动曲线何时开始播放次数是否反方向动画起始或结束方向;复制属性描述@keyframes规定动画。animation所有动画属性的简写属性,除了animation-play-state属性。animation-name规定@keyframes动画的名称。(必须的)animation-duration规定动画完成一个周期所花费的秒或毫秒,默认是0。(必须的)animation-timing-function规定动画的速度曲线,默

  • 浙大版《C语言程序设计(第3版)》题目集 习题3-1 比较大小

    习题3-1比较大小本题要求将输入的任意3个整数从小到大输出。输入格式:输入在一行中给出3个整数,其间以空格分隔。输出格式:在一行中将3个整数从小到大输出,其间以“->”相连。输入样例:428 输出样例:2->4->8 代码:#include<stdio.h> intmain() { intarr[3]; scanf("%d%d%d",&arr[0],&arr[1],&arr[2]); inti; intindex; inttemp; intj; for(i=0;i<2;i++) { index=i; temp=arr[i]; for(j=i+1;j<3;j++) { if(arr[j]<=arr[index])index=j; } arr[i]=arr[index]; arr[index]=temp; } printf("%d->%d->%d\n",arr[0],arr[1],arr[2]); return0; }复制

  • 三歪红着眼睛总结了Spring知识点

    上次的Mybatis反响很不错阿,本来想着150个在看就心满意足了,没想到有200多个在看,非常感谢各位的支持啦。我看评论区都想看Spring,三歪红着眼睛都要把这份Spring肝出来。由于Spring家族的东西很多,一次性写完也不太现实。所以这一次先更新Spring「最核心」的知识点:AOP和IOC无论是入门还是面试,理解AOP和IOC都是非常重要的。在校招的时候,我没被问过Mybatis/Hibernate/Struts2这样的框架,而Spring就经常会被问到。这次的PDF共有「142」页,PDF涉及到的内容:IOC和AOP的全面讲解Spring事务详解和相关问题SpringIOC/AOP相关面试题为什么要用Spring当年的我,刚学Spring的时候,会想:『这IOC和AOP』是什么鬼玩意啊?一大堆的名词「控制反转」「依赖注入」「面向切面编程」。这是在给我搞笑的吧。在最开始学的IOC折腾了一大堆的玩意,结果就是在管「创建对象」的事??逗我呢???我直接new一个对象出来不香吗?有这种想法这种明显就是「代码写得少了,想得多了」我们写代码,不仅仅是要能实现功能,实现完了以后我们还得

  • 用Python获取可能是全网最全的杰尼龟表情包(第一弹)

    杰尼龟系列表情包在广大网友之间传递快乐,红极一时。我想是杰尼龟可爱的外表以及憨憨的形态,圆圆的脸蛋、大大的眼睛,并且其经常在剧中摆出各式夸张表情,因而被广大网友制成各式各样的表情包,并且深受沙雕网友的喜爱。正好,我也是这沙雕网友大军中的一员,通过各种渠道收集了一些杰尼龟的表情包。但,我想要更多,只有拥有沙雕表情包最多的人才能在斗图中立于不败之地,于是便有了用Python获取可能是全网最全的杰尼龟表情包这一系列。本系列旨在获取更多更多的杰尼龟表情包,传递更多欢乐。全系列一共三弹,每一弹都运用Python作为编程语言,主要涉及网络爬虫、数字图像处理以及机器学习这几个应用领域,今天便是这第一弹!爬取视频如何获得更多的杰尼龟表情包?这些流传的表情包无非就是截取自动画片《精灵宝可梦》,然后有选择性地缩放或是剪切图片,再对应图片加上相关的文字。因此按照这个逻辑,我们需要首先从这视频入手。作为第一代御三家的一员,杰尼龟主要活跃在《精灵宝可梦》的第一部无印篇,因而我们仅需要考虑第一部的视频,而这第一部中,不乏一些杰尼龟专集。直接下载这第一部的所有视频费时费力,恰好B站有up主上传了所有含杰尼龟的集数合

  • 4.5 服务器上的 Git - Git 守护进程

    Git守护进程接下来我们将通过“Git”协议建立一个基于守护进程的仓库。对于快速且无需授权的Git数据访问,这是一个理想之选。请注意,因为其不包含授权服务,任何通过该协议管理的内容将在其网络上公开。如果运行在防火墙之外的服务器上,它应该只对那些公开的只读项目服务。如果运行在防火墙之内的服务器上,它可用于支撑大量参与人员或自动系统(用于持续集成或编译的主机)只读访问的项目,这样可以省去逐一配置SSH公钥的麻烦。无论何时,该Git协议都是相对容易设定的。通常,你只需要以守护进程的形式运行该命令:gitdaemon--reuseaddr--base-path=/opt/git//opt/git/复制--reuseaddr允许服务器在无需等待旧连接超时的情况下重启,--base-path选项允许用户在未完全指定路径的条件下克隆项目,结尾的路径将告诉Git守护进程从何处寻找仓库来导出。如果有防火墙正在运行,你需要开放端口9418的通信权限。你可以通过许多方式将该进程以守护进程的方式运行,这主要取决于你所使用的操作系统。在一台Ubuntu机器上,你可以使用一份Upstart脚本。因此,找到如下文件

  • leetcode: 67. Add Binary

    Problem#Giventwobinarystrings,returntheirsum(alsoabinarystring). # #Forexample, #a="11" #b="1" #Return"100".复制ACclassSolution(): defaddBinary(self,a,b): num=int(a,2)+int(b,2) returnbin(num)[2:] if__name__=='__main__': assertSolution().addBinary('11','1')=='100'复制

  • 数据挖掘|关联规则Apriori算法

    01— 关联规则挖掘背景和基本概念如下所示的数据集,表中的每一行代表一次购买清单,注意我们只关心记录出现与否,不关心某条记录购买了几次,如购买十盒牛奶也只计一次。 数据记录的所有项的集合称为总项集,上表中的总项集:S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}关联规则就是有关联的规则,形式是这样定义的:两个不相交的非空集合X、Y,如果有X->Y,就说X-->Y是一条关联规则,例如,{啤酒}-->{尿布}就是一条关联规则。关联规则的强度用支持度(support)和自信度(confidence)来描述。支持度support(X-->Y)=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。例如:support({啤酒}-->{尿布})=啤酒和尿布同时出现的次数/数据记录数=3/5=60%自信度confidence(X-->Y)=集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数。例如:confidence({尿布}-->{啤酒})=啤酒和尿布同时出现的次数/尿布出现的次数=3/4=75%。总结支持度和自信度越高,说明规则越强,

  • 五分之四全失败 SaaS创业如何避免高失亡率?

    据IDC报告,未来五年,中国SaaS市场增速将是传统软件市场的10倍,这也是为什么很多创业公司选择以SaaS模式为企点的原因。诚然,这是个利好的市场,但据彭博(Bloomberg)商业调查显示,大约有4/5的创业公司在一年内就宣告失败了,这并非危言耸听。所以,作为一名SaaS创业者,如何构建出用户满意的产品,避免失败,就显得尤为重要。为此,我们不妨听听过来人怎么说:作为一个很有前途的SaaS业务创始人,你可能也经常面临一些难以预料的风险。但冒险和犯错往往是建立一个企业的必经过程,不是吗?身为创始人,我本身非技术出身。现阶段,我经营着一个增速最快的采购平台,帮助数以百计的公司在世界各地进行产出。随着企业的发展扩大,我也犯了很多错误,而如果当初我虚心向别人学习的话,这些错误本可以避免的。一些世界上最知名的SaaS企业公开谈论他们的失败经验,这样就可以帮助业界其他人避免类似的问题。这就是为什么我要在此分享自己最常犯的错误的原因,这些错误是我通过自己及其他人的经历总结而得的,希望大家引以为戒。1)将云环境与SaaS交付模型混淆当我第一次创建Sourcify的时候,我使用了“云”和“SaaS”这

  • mongodb安装脚本

    #!/bin/bashbao_dir="/tmp"bao_name="mongodb-linux-x86_64-rhel70-5.0.0.tgz"#安装依赖yuminstalllibcurlopensslxz-libswget-y#下包cd$bao_dir[-f$bao_name]||wgethttps://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel70-5.0.0.tgztarxvf$bao_name-C/optmv/opt/mongodb-linux-x86_64-rhel70-5.0.0/opt/mongodb#设置环境变量echo'exportPATH=/opt/mongodb/bin:$PATH'>>/etc/profile#增加mongodb启动用户useraddmongod#创建数据库文件夹,并给mongod权限mkdir-p/data/mongochown-Rmongod:mongod/data/mongo#创建日志目录,并给mongod权限mkdir-p/var/log/mongodbchown-R

  • Tekton Tigger使用案例进阶

    [root@master03-trigger-gitlab]#kubectlapply-f. secret/gitlab-webhook-tokencreated serviceaccount/tekton-triggers-gitlab-sacreated role.rbac.authorization.k8s.io/tekton-triggers-gitlab-minimalcreated rolebinding.rbac.authorization.k8s.io/tekton-triggers-gitlab-bindingcreated clusterrole.rbac.authorization.k8s.io/tekton-triggers-gitlab-minimalcreated clusterrolebinding.rbac.authorization.k8s.io/tekton-triggers-gitlab-bindingcreated serviceaccount/helloworld-admincreated clusterrolebinding.rbac.aut

  • [补档题解]后缀树节点数

    题目描述 给定一个长度为\(n\)的字符串\(P\),有\(m\)次询问,每次给定两个参数\(l\),\(r\),询问子串\(P[l,r]\)所构成的后缀树的结点数。 \(n\le10^5,m\le3\times10^5\) 题解 tag:分类计数;后缀树/后缀自动机;线段树/树状数组;哈希。 做法来自2018集训队论文集。 由于构建后缀树需要倒转原串之后建立SAM得到,为方便处理,故我们先倒转原串以及对应询问区间。 下文例子的字符串都是倒转之后的。 记\(node_{[l,r]}\)表示找区间\([l,r]\)对应子串在后缀树上的节点。 考虑传统后缀树节点数的计数方法,对于一个区间\([l,r]\)建后缀自动机的过程,产生出了np和nq两种类型的节点。 np节点对应的是\(i\in[l,r]\)的前缀\([l,i]\)对应的串,暂时称作前缀节点; nq节点对应的是后缀树上必要的分叉,暂时称为分裂节点; example:"pabcqabc" 对于"abc"这个串,子树分成"pabc"和"qabc"两个独立的节点,故"abc"本身新建了一个分裂型节点。 考虑容斥,计算前缀节点个数+分

  • Python高级应用程序设计任务

    Python高级应用程序设计任务要求 用Python实现一个面向主题的网络爬虫程序,并完成以下内容: (注:每人一题,主题内容自选,所有设计内容与源代码需提交到博客园平台) 一、主题式网络爬虫设计方案(15分) 1.主题式网络爬虫名称 爬取B站排行榜中的总站榜的三日排行 2.主题式网络爬虫爬取的内容与数据特征分析 爬取内容:排名、视频名、排放量、弹幕数、up主、综合评分、视频链接 数据特征分析:分析排名、播放量、弹幕数和综合评分的关系 3.主题式网络爬虫设计方案概述(包括实现思路与技术难点) 实现思路: 1.利用xlsxwriter建表 2.使用requests的get方法爬取页面源代码 3.使用re正则表达式爬取数据并存入表格 技术难点: 1.数据爬取时会出现错误 2.数据存入时会变成乱码 二、主题页面的结构特征分析(15分) 1.主题页面的结构特征 按F12查看,发现需爬取的数据皆为静态 2.Htmls页面解析 divclass=“content”标签中的便是要爬取的内容 3.节点(标签)查找方法与遍历方法 (必要时画出节点树结构)  利用requests中的ge

  • 自己编写jQuery动态引入js文件插件 (jquery.import.dynamic.script)

    这个插件主要是结合jquery或者xhr异步请求来使用的,它可以把已经引入过的js文件记录在浏览器内存中,当下次再引入相同的文件就忽略该文件的引入。   当你用$.load("dir/my-page.jsp");或xhr.request("server/to-my-page");等异步请求加载html页面的时候,在页面中导入js文件用本插件进行引入的话, 那么其他请求的页面中也导入了和前面页面相当的js文件的情况下,那这些js文件就不需要重新引入。插件会自动忽略之前已经引入过的文件,来节约开销加快速度。   此插件不支持浏览器刷新保存数据,那需要利用cookie来保存引入数据记录。这里只时候异步加载js文件的方式。     使用本插件必须先引入jquery,后再引入动态导入插件js文件。在不刷新页面的情况下,本插件导入的javascript只需用导入一次,后面都会使用上一次导入的缓存文件 下面简单说下插件用法,使用规则方法:   1、导入一个文件 1//导入一个文件 2$.imports("${pageContext.req

  • linux优先级

    进程调度优先级中PR和NI的含义,用TOP可以看到 PR进程的优先级。在Linux2.6.23之前的版本中PR是一个动态值,在运行的过程中可能出现变化。大体策略是:如果一个进程sleep了比较多的时间,PR值会降低(即优先级提高);如果一个进程占用了大量的CPU时间,PR值会升高(即优先级降低)。在2.6.23版本之后,由于引进了CFS调度策略,不再简单根据一个进程sleep的时间动态调整其优先级了,PR值就固定为NI+20。CFS期望的目标是每个进程均衡地占用CPU,PR作为权重因子。 NInice值,可用来调整进程的优先级,默认为0。如上所述,PR=NI+20,且PR越小优先级越高,因此nice值越小进程优先级越高。运行命令的时候可用nice–nxxcmd来调整cmd任务的nice值,xx的范围是-20~19之间。

  • ndk-stack 使用(分析native代码stack)

    简介:   ndkr6版本之后开始提供该功能。 作用:   ndk-stack可以把不认识的内存地址信息转换成可读的信息。 比如,把下列内容 I/DEBUG(31):************************************************ I/DEBUG(31):Buildfingerprint:'generic/google_sdk/generic/:2.2/FRF91/43546:eng/test-keys' I/DEBUG(31):pid:351,tid:351%gt;%gt;%gt;/data/local/ndk-tests/crasher<<< I/DEBUG(31):signal11(SIGSEGV),faultaddr0d9f00d8 I/DEBUG(31):r00000af88r10000a008r2baadf00dr30d9f00d8 I/DEBUG(31):r400000004r50000a008r60000af88r700013c44 I/DEBUG(31):r800000000r9000000001000000000f

相关推荐

推荐阅读