C++ 那些事

文常

本文介绍一些有关 c++ 的文常

数据类型大小

类型 含义 字节数 /byte
void 0
bool 布尔类型 1
(unsigned) char 字符型 1
(unsigned) short 短整型 2
(unsigned) int/long 整型 4
float 浮点数 4
(unsigned) long long 长整型 8
double 双精度浮点数 8

运算符优先级

以下将 C++ 常用运算符的优先级做了列表,从优到低。

I

从左到右

符号 含义
:: 作用域解析

II

从左到右

符号 含义
a++ a-- 后缀自增与自减
type() type{} 函数风格转型
a() 函数调用
a[] 下标
. -> 成员访问

III

从右到左

符号 含义
++a --a 前缀自增与自减
+a -a 一元加与减
! ~ 逻辑非和逐位非
(type) C 风格转型
*a 间接(解引用)
&a 取址
sizeof 取大小
new new[] 动态内存分配
delete delete[] 动态内存分配

IV

从左到右

符号 含义
.* ->* 指向成员指针

V

符号 含义
a*b a/b a%b 乘法、除法与余数

VI

符号 含义
a+b a-b 加法与减法

VII

符号 含义
<< >> 逐位左移与右移

VIII

符号 含义
< <= 分别为 < 与 的关系运算符
> >= 分别为 > 与 的关系运算符

IX

符号 含义
== != 分别为 = 与 的关系运算符

X

符号 含义
a&b 逐位与

XI

符号 含义
^ 逐位异或(排除或)

XII

符号 含义
` ` 逐位或(包含或)

XIII

符号 含义
&& 逻辑与

XIV

符号 含义
` ` 逻辑或

XV

从右到左

符号 含义
a?b:c 三元条件
throw throw 运算符
= 直接赋值( C++ 类默认提供)
+= -= 以和及差复合赋值
*= /= %= 以积、商及余数复合赋值
<<= >>= 以逐位左移及右移复合赋值
&= ^= ` =` 以逐位与、异或及或复合赋值

XVI

从左到右

符号 含义
, 逗号

真 · 快速读入 | fread

C++ 程序除了算法的高效,数据读入的高效也是十分重要的。在面对大数据流时(尤其指 10^6 以上的数字),高效的读入能节省很多的时间。

原理

先来看知乎大佬翻译源代码为人类语言的 getchar()

作者:Pallad
链接:https://www.zhihu.com/question/39909689/answer/88523074
来源:知乎
int 缓存初始化为空; // 缓存不会被清空,除非 main() 执行完.
char getchar(){if( 缓存是空的){
        屏幕上跳出光标并且开始监听输入;
        if(回车键被按下){ 系统 (不是 getchar 函数) 命令光标跳至新行;
            将所有输入的字符末尾加上 '\n' 并存入缓存;
            读取缓存的第一个字符到 temp; // 即使第一个字符是 '\n'
            将缓存左移一个字符;
            return temp; // 即使 temp 是 '\n'
        }
    } else {
        读取缓存的第一个字符到 temp; // 即使第一个字符是 '\n'
        将缓存左移一个字符;
    }
    return temp; // 即使 temp 是 '\n'
}

相比之下,scanf() 会涉及到将字符放回缓冲流,处理格式字符,判断文件尾等操作,运行时自然速度不那么快。

模板

快读绝大多数时候用于读数字。
利用 getchar 读取无符号 int:

int rd(){
    int res=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res;
}

这里的 isdigit() 判断是否为数字,比你直接写 if 判断要快 见知乎 - 常优
其他快读在此模板上加判断即可,不赘述。

真 · 快速读入

fread()

fread() 的声明如下
size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream)

  • void *ptr :指向内存块的指针(比如字符串的名字)
  • size_t size :内存块中单个元素的大小(单位为字节)
  • size_t nmemb :读取次数(内存块中的元素数)
  • FILE *stream :指向 FILE 对象的指针
  • size_t : 它是一种能够以字节为单位表示任何对象大小的类型:size_t 是 sizeof 运算符返回的类型,在标准库中广泛用于表示大小和计数。
  • fread() 返回成功读取的元素总数。

应用 fread 写快读

使用 fread() 代替 getchar

char nc(){// 据传为 Manchery 大神所作
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
  • 不得不说,这种压行代码是非常玄学的
  • static 表示静态变量,作用域在函数 nc() 里,存活时间为程序运行时间。
  • buf 为数组的首地址,为其分配 100000 字节的空间;p1,p2 为指向字符的指针。
  • 至于这一行 return 的操作分解如下:
    • p1==p2 为真,则计算 (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) 的值:
      • 赋值表达式的值为其本身,所以 (p1=buf) 的值为 buf;
      • fread 从标准读入流读取了以 1 字节为单个元素大小的 100000 个元素并存储到 buf 数组中,fread() 返回了读取字符的总数,加上 buf,即为读取的最后一个字符的后一位的地址。因此 p2p1 遍历数组的边界。
      • 逗号表达式的值是以逗号分隔的列表中的最后一个表达式的值,因此经过上面的读取后,整个表达式的值仍为 p1==p2 的值,当然这时的 p1 p2 是读取后的 p1 p2,如果仍然相等,说明没有字符了,返回 EOF
    • p1==p2 为假,则将不判断逻辑与(&&)后面的表达式,直接返回三目运算符最后一目的表达式,即 p1 指向的字符,然后 p1 指针后移一位。

因此,上述代码的正常版是这样的:

char nc(){static char buf[100000],*p1=buf,*p2=buf;
    if(p1==p2)retrn *p1++;
    p1=buf;
    p2=buf+fread(buf,1,100000,stdin);
    if(p1==p2)return EOF;
    else return *p1++;
}

利用这个函数代替 getchar,再来读入,效果显著。
当然,上述代码每次将 100000 个字符读到 buf 里面,显然不能再用 scanfcin 了,因为都读到 buf 里面去了。不过,速度感人。

一个栗子

  • BZOJ4195,用 scanf() 读入:
    TIM20180731154526.png

  • getchar() 快读:
    TIM20180731154559.png

  • nc() 代替 getchar()
    TIM20180731154613.png

总时间减少将近一半!

总结

虽然快读的优化显著,但并不用每次都快读。读入的数据少,就不需要,否则就是增加代码长度,很累赘。读入的数据多,用快读,才能有效果。

任何优化,都要优化在有用的地方。

C++ 输入输出格式控制符

printf

% [flags] [width] [.precision] [length] specifier

起始字符 %

表示格式控制的开始

类型控制 specifier

specifier 控制输出对象的类型.
常用:

  • d| 整型
  • f| 浮点数
  • s| 字符串
  • %| 输出一个 %.

不常用:

  • o| 八进制整数
  • x| 十六进制整数
  • e| 科学计数法输出
  • g| 浮点数宽度最短输出
  • p| 指针地址
  • n| 无输出,它会将目前输出的字符数量存储到参数列表中对应的变量中(类型为signed int*

前置标记 [flag]

  • -| 在域宽中左对齐。没有的话默认右对齐。
  • +| 强制在数字前加符号(包括正数)
  • 0| 在域宽中剩余部分补 0,没有的话默认补空格。

域宽 [width]

  • (number)| 指定最小域宽,如果宽度不足指定数,则补齐,如果超过指定数,照常输出。
  • *| 不定域宽,须在参数列表中指定对应的整型变量。

精度控制 [.precision]

  • .number| 指定精度
    • d x o| 指定最小长度,不足的补前导 0;超过的照常输出
    • f lf Lf| 控制小数位数
    • s| 控制字符串输出的最大字符数
    • 如果指定的句点没有显式的精度值,则假定为 0
  • .*| 不定精度,须在参数列表中指定对应的整型变量。用法同上。

长度 [length]

指定数据类型的长度
TIM20180729121830.png

典例

%.5lf| 对象类型为 double, 且输出五位小数
%-+5.4d| 左对齐,加符号,域宽为 5,数字部分长度为 4(补前导 0),整型。
%s%n| 输出字符串,%n 将返回已输出的字符数,这里指字符串长度。

详见 C++Reference

scanf

%[*][width][length]specifier

  • 空白字符:该函数将读取并忽略在下一个非空白字符之前遇到的任何空白字符(空白字符包括空格,换行符和制表符)。格式字符串中的单个空格验证从流中提取的任何数量的空白字符(包括无)。
  • 非空白字符,格式说明符(%)除外:任何不是空格字符(空格,换行符或制表符)或格式说明符的一部分的字符都会导致该函数读取下一个字符从流中,将其与此非空白字符进行比较,如果匹配,则将其丢弃,并且函数将继续使用格式的下一个字符。如果字符不匹配,则函数失败,返回并保留流的后续字符未读。
  • 格式说明符:由初始百分号(%)组成的序列表示格式说明符,用于指定要从流中检索并存储到其他参数指向的位置的数据的类型和格式。

类型控制 specifier

specifier 控制输出对象的类型.
常用:

  • d| 整型
  • f| 浮点数
  • s| 字符串
  • %| 匹配一个 %.

不常用:

  • i| 任意整型(8,10,16 进制)
  • o| 八进制整数
  • x| 十六进制整数
  • p| 指针地址
  • n| 无输入,它会将目前输入的字符数量存储到参数列表中对应的变量中(类型为signed int*
  • [characters]| 括号之间指定的任意数量的字符(对于 [ ] - 的字符应紧挨在左括号后面)
  • [^characters]|括号之间指定的任意数量的字符(对于 [ ] - 的字符应紧挨在 ^ 后面)

忽略读取 [*]

将格式字符串所读取到的东西舍去(不用匹配参数列表)

域宽 [width]

读取的最大宽度。

长度 [length]

指定数据类型的长度。
TIM20180729135040.png

参数列表中的变量应该是它的地址(&)

详见 C++Reference

STL memset 小记

函数声明

void * memset (void * ptr, int value, size_t num);

  • 强调,value 的类型虽然声明是 int,不过它只按 8 位赋值到数组中(unsigned char).

无穷大

memset 最常用于初始化:
memset(a,0,sizeof(a));

不过 memset 只是 8 位一组地赋值,如何赋值无穷大呢?

  • 赋值 0x3f,二进制表示为 00111111,int 每 8 位赋值后的数是 1,061,109,567, 与 2^31-1 是同一个数量级,并且相加后也不会溢出。
  • 赋值 0x7f,二进制表示为 01111111,int 赋值后为 2,139,062,143,与 2^31-1 同级。

无穷小

  • 赋值 0xc0,二进制表示为 11000000,int 赋值为 -1061109568,同级,可加
  • 赋值 0x80,二进制表示为 10000000,int 赋值后为 -2139062144,同级。

C++ 程序对拍

前置技能

  • API 函数 system(),包含于头文件 <cstdlib>
  • CMD 中的 fc 命令或 shell 中的 diff
  • 管道 IO(即 <> 操作符)

对拍模板

#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;

int main(){
    system("g++ cake_gen.cpp -o .gen");
    system("g++ cake2.cpp -o .vio");
    system("g++ cake3.cpp -o .my");
    int t=0;
    while(++t){system("./.gen> .in");// 生成数据
        system("./.vio < .in> .ansout");
        double s=clock();//ms 为单位
        system("./.my < .in>.outout");
        double e=clock();
        if(system("diff .outout .ansout"))break;
        else if(e-s>1000)printf("TLE #%d %lf\n",t,e-s);
        else printf("AC #%d %lf\n",t,e-s);
    }
    printf("WA #%d",t);
    return 0;
}

注:产生的以英文句点开头的文件在 linux 下是隐藏的

C++ 随机数据生成

前置技能

  • <cstdilb>: rand() srand().
  • <ctime>:time()
  • <cstdio> | <iostream> : 用于标准输出
  • shell 管道命令(对拍用)

重置随机数种子

  • rand() 作为一个伪随机函数,需用 srand() 重置种子来使得每组数据不同
  • 一般用系统时间作种子(time(0)
    srand(time(0)*233+17);
    

随机数取模

  • 限制随机数范围
  • 以后直接用 r(p) 而不是 rand()%p
    int r(int p){return (long long)rand()*rand()%p;}
    

随机生成一颗树

void random_tree(int v){//vetrix,root=1
    printf("%d %d\n",v,v-1);//vetrix,edge
    for(int i=2;i<=v;i++)printf("%d %d\n",r(i-1)+1,i);
}

随机生成无向连通图

void random_graph(int v,int e){// 无向图,保证连通
    printf("%d %d\n",v,e);//vetrix,edge
    for(int i=2;i<=v;i++)
        printf("%d %d\n",r(i-1)+1,i);// 先生成一颗树
    e-=v-1;
    for(int i=1;i<=e;i++)
        printf("%d %d\n",r(v)+1,r(v)+1);// 生成其余的边
}

  转载请注明: Sshwy's Blog C++ 那些事

 上一篇
[LuoguP1156] 垃圾陷阱 [LuoguP1156] 垃圾陷阱
一道很恶心的背包 DP 需要考虑很玄学的的细节 总之,要精心判断是否能转移,再转移 结合刷表法和填表法 详细的看 Luogu 题解去吧 #include<bits/stdc++.h> using namespace std; con
2018.10.01
下一篇 
AC 自动机 ·Automaton AC 自动机 ·Automaton
摘要 之前洛谷日报上发了一篇《强势图解 AC 自动机》,现在复习一下,重新整理思路 2019.6.16:编入精选文章 前言声明:代码部分的字符串都以 1 为起点 另外,有小伙伴问我 GIF 图片是怎么生成的。在此我以个人名誉担保—— 这
2018.10.01
  目录