OI

【杂记】做题时的盲点（持续更新）

记录一些可能是盲点或者隐形杀手的东西。

1.字符串函数

不止是字符串函数，调用所有库函数的时候都要注意复杂度问题。然而在STL的时候会十分谨慎，在用cstring(string.h)的时候却可能有盲点：很多字符串函数都是$n$级别的。

绝不能当做常数： 

1
for(i=0;i<strlen(a);i++);

而是：

1
2
int alen=strlen(a);
for(i=0;i<alen;i++);

2.数组初始化

数组的操作一般认为是$n$级别的，但是如果只是声明不初始化的化将是常数级的，所以能不初始化就不初始化，更不能重复初始化，尤其是在重复调用的函数中开数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<iostream>
#include<windows.h>
#include<ctime>
using namespace std;

inline void f1(){
    int t[10000];//4
}

inline void f2(){
    int t[10000]={0};//4
}

int main(){
    clock_t start,end;
    
    start = clock();
    
    for(int i=1;i<=1000;++i)
        for(int j=1;j<=1000;++j)
            ;
    
    end = clock();
    printf("void Use Time:%f\n",(end-start)*1.0/1000);
    
    start = clock();
    
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++)
            f1();//6
    
    end = clock();
    printf("f1 Use Time:%f\n",(end-start)*1.0/1000);
    
    start = clock();
    
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++)
            f2();//6
    
    end = clock();
    printf("f2 Use Time:%f\n",(end-start)*1.0/1000);
    
    return 0;
}

结果：
void Use Time:0.002000
f1 Use Time:0.028000
f2 Use Time:1.096000

3.memset函数

首先，使用memset需要memory.h或cstring(string.h)。
重点是该函数的实际效果：按字节覆盖指定内存。

在单字节的数据类型中是没问题的： 

1
2
3
char c[1000];
memset(c,'A',sizeof(c));
printf("%c",c[1]);

输出：
A

然而对于其他的多字节数据类型，这个函数不能想当然的使用。比如： 

1
2
3
int a[1000];
memset(a,10,sizeof(a));
printf("%d",a[1]);

输出：
168430090

并不是10。这是由于int四个字节，memset了之后是赋值每个字节都是10，二进制就是00001010 00001010 00001010 00001010=168430090

所以如果要memset整型，只能是（补码）四个字节都一样的整型值才可以。其中
一字节 0=00000000
一字节-1=11111111
这两个是一字节值和四字节值一样的，所以一般整型用memset赋值只能是0或-1，其他的就不是原值了。

4.STL容器

一般使用时都会注意到empty时不能pop，但其他涉及到取用容器内数据的函数在empty时都是不能用的。
首先pop时是一定会注意到：

1
while(!q.empty())q.pop();

然而在其它操作是也应一样：

1
if(!s.empty())t=s.top();

撞过的C++保留字……

max/min
map
find