历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

c++语法知识

作者：

哥哥姐姐给我点点赞吧 , 2021-05-17 15:25:23 , 所有人可见 , 阅读 623

7

7

```
网站：https://blog.csdn.net/zb1593496558/article/details/80987071
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
v.at(0)//等价于v[0]
支持比较运算，按字典序

pair[HTML_REMOVED]
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> q;

stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, – 返回前驱和后继，时间复杂度 O(logn)

set/multiset
    insert()  插入一个数
    find()  查找一个数
    count()  返回某一个数的个数
    erase()
        (1) 输入是一个数x，删除所有x   O(k + logn)
        (2) 输入一个迭代器，删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x)  返回大于等于x的最小的数的迭代器
        upper_bound(x)  返回大于x的最小的数的迭代器
map/multimap
    insert()  插入的数是一个pair
    erase()  输入的参数是pair或者迭代器
    find()
    []  注意multimap不支持此操作。 时间复杂度是 O(logn)
    lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()，迭代器的++，–

bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]

count()  返回有多少个1

any()  判断是否至少有一个1
none()  判断是否全为0

set()  把所有位置成1
set(k, v)  将第k位变成v
reset()  把所有位变成0
flip()  等价于~
flip(k) 把第k位取反

一、数组

include [HTML_REMOVED]

void array_study(void)
{
static int cnt; //static静态变量修饰符，静态变量相当于只能在该函数中使用的全局变量，
//自动初始化为0，即在调用该函数时，只有第一次调用才会初始化，之后的调用都会直接跳过初始化这一步
int a[10],b[10]; //局部数组最大长度大概为510000;
//全局数组最大长度大概为490000000即4(10^8)，二维数组为2200022000
memset(a,-1,sizeof(a)); //memset按字节初始化，1位8个字节，int为32位，此为将值全赋值为-1
memset(a,0,sizeof(a)); //将a全赋值为0，初始化
memcpy(b,a,sizeof(a)); //数组拷贝函数
//cout<<(char)98<<endl; //b
//字符串为字符数组后面加上’\0’
char arr[10]=”Hello”; //用字符串初始化字符数组
//空：0,\0,null,NULL,false
cout<<arr+1<<endl; //数组首地址改为arr+1,即输出一个数组，输入同理
cout<<*(arr+1)<<endl; //输出一个值
int ar[10]={1,2,3,4,5};//将前k个数放到最后面
reverse(ar,ar+5);//reverse翻转函数，参数为起点，终点，左闭右开
reverse(ar,ar+2);
reverse(ar+2,ar+5);//45123
puts(“a”); //puts自动换行
char s[100]=”comic”;
cout<<sizeof(s)<<endl;
//scanf(“%s”,s);//遇到空格，回车等结束读取，或用cin
//fgets(s,sizeof(s),stdin);//fgets取代gets，读取一行到字符串中，fgets会把回车读进来
//cin.getline(s,sizeof(s));//接收一行字符串，需指明接收长度，即第二个参数
//cout<<s<<endl;
cout<<strlen(s)<<endl; //不读取\0，且strlen是遍历了整个字符串（一层循环），
//因此使用时要提前用变量存下来节约时间
char c[100]=”domic”;
strcpy(c,s);
cout<<strcmp(s,c)<<endl; //相等则返回0
for(int i=0;s[i];i) //不用strlen作为结束条件，因为需循环计算，当s[i]为\0时结束
cout<<s[i]-‘a’<<” “; //将a,b,c···映射为1,2,3···
for(int i=0;s[i];i)
cout<<i+’a’<<” “; //将1,2,3···变为a,b,c···
}

二、字符串string

include [HTML_REMOVED]

void string_study(void)//string,空间可变字符串，不需要设定空间
{
string s=”comic”;
string a=s; //string直接拷贝
string b(10,’x’); //重复10次x
//cin>>a;//遇到空格，回车等结束，不能用scanf
//getline(cin,a);//类似fgets，读取一行
cout<[HTML_REMOVED],>=,!=
string s1=”Hello”,s2=”world”;
string st=s1+’,’+s2+’!’; //在相加时，参与对象都会被转换成string类型
cout<<st<<endl; //string相加时，+两边至少有一个值需要为string型，且为从左至右相加
for(char c:st){
c=c+1;
cout<<c<<’ ‘;//c的改变不会使得st改变
}
cout<<endl;//c++范围遍历，格式为：单个元素数据类型 c:string名，顺次遍历
for(char &c:st){
c=c+1; //加上&,使得当c的值变化时，st的值也随之改变
}
for(auto &c:st){ //auto自动类型推导，让编译器自己去猜，猜不出来会报错
c–;
}
cout<<st<<endl;
for(auto &c:st)
c=(c-‘a’+1)+’a’; //处理后c仍为char类型
cout<<st<<endl;
st.pop_back(); //删除string中最后一个元素
cout<<st.substr(0,3)<<endl; //截取部分字符串,从0开始截取长度为3的字符串,若无长度则默认截取到结尾
st.assign(“ABC”); //将字符串的内容修改为ABC,还可以设置修改范围
st.swap(a); //交换字符串st与a
a.push_back(‘a’); //在末尾添加一个字符
a.append(“DEF”); //在末尾添加一个字符串
a.insert(0,”z”); //在位置为0处添加字符串
reverse(a.begin(),a.end()); //借助algorithm中的reverse实现string的逆序
a.replace(0,3,”abc”);
a.erase(6); //删除6后面的所有值
//a.clear(); //删除a中所有值
cout<<a<<endl;
cout<<a.find(‘a’)<<endl; //成功查找则返回位置，失败返回-1
cout<<a.find(“abc”)<<endl;
char * str;
a.copy(str,3,0); //拷贝到字符数组str中
cout<<str<<endl;
cout<<a.compare(“xx”)<<endl; //字符串比较，相等返回0，小于返回-1，大于返回1
cout<<a.back()<<endl; //字符串最后一个元素
cout<<a.front()<<endl; //字符串第一个元素
string x=”1223”;
cout<<stoi(x); //stoi将string转化为整数
cout<<atoi(x.c_str()); //atoi将字符数组转化为整数
}

三、结构体，输入输出，time，goto，浮点数比较
编程题里1s内大概是运行进行1e7~1e8数量级的运算，超过的话就会TLE了

include [HTML_REMOVED]

const double eps=1e-6;
int z[100000];//全局数组默认都初始化为0，全局变量会放到堆空间，没有空间限制（有内存限制）
//main中有空间限制(栈)
struct stu{
string name;
int score,height;
stu(){}
stu(string n,int s,int h):name(n),score(s),height(h){} //结构体的构造函数
};
void struct_study(void)
{
struct stu ss = {“zhangsan”,18,170}; //两种初始化方法
//struct stu ss(“zhangsan”,18,170);
//class 和 struct 类似，区别是class默认成员变量为私有，struct默认成员变量为公有，
class中既有函数又有变量，struct中一般只有变量
}

bool decimal_compare(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0); //加速cin,cout读入输出
char x;
cin >> x;
scanf(” %c”,&x); //scanf读入单个字符时，在%c前加个空格，防止回车的影响
cout << x;
char op[2];
scanf(“%s”,op); //当想读入单个字符时，用字符串读入，这样就不会读入多余的空格和回车
cout << op[0] << endl;//然后再对单个字符op[0]做处理

int start_time=clock();
double a=1.232345;
double b=a*a;
b=sqrt(b);
return (fabs(a-b)<eps);
cout<<clock()-start_time<<endl;    //计算运行时间，单位为ms

for(int i = 0; i < 10; ++i)
    for(int j = 0; j < 10; ++j)
        for(int k = 0; k < 10; ++k)
            goto end;   //goto,跳出多重循环时使用，可以跳到指定的位置
end:;  //直接从循环中跳到end:这里

}

四、vector

include [HTML_REMOVED]

struct stu{
string name;
int score,height;
stu(){}
stu(string n,int s,int h):name(n),score(s),height(h){} //结构体的构造函数
};
void vector_study(void)
{
vector[HTML_REMOVED] arr; //自动变长是倍增思想
vector[HTML_REMOVED] array{1,2,3}; //初始化，若函数返回值为vector,则可return {a,b,c···}
vector[HTML_REMOVED]> arra; //vector二维数组，即{{1,2},{1,3},{3,4,5}···}等
vector[HTML_REMOVED] a({11,111,1111}); //vector动态int型可变长数组
vector[HTML_REMOVED] b[123]; //vector二维数组，第一维为静态（123），第二维为动态
vector[HTML_REMOVED] str;
vector[HTML_REMOVED] boo; //vector内可以套各种各样的东西，形成如字符串数组，bool数组
vector[HTML_REMOVED] c; //结构体类型vector
cout<[HTML_REMOVED]::iterator it=a.begin(); //此时it就相当于a(数组名),即a[0]的地址
*it=3; //a[0]=3
for(int i=0;i[HTML_REMOVED]::iterator it=a.begin();it[HTML_REMOVED],==等，依次比较每一位数大小
copy(a.begin(),a.end(),arr.begin()); //将a.begin()-a.end()赋值到arr上
arr = a; //直接赋值
}

五、栈，双端队列

include [HTML_REMOVED]

void stack_deque_study(void)
{
stack[HTML_REMOVED] s; //栈，先入后出，只能在栈顶（即尾部）出栈入栈
s.push(1); //入栈，stack为push，无push_back
cout<<s.top()<<endl; //输出栈顶元素
s.pop(); //弹出栈顶元素

deque<int> d;//双端队列，可在两端进行高效插入，删除操作的线性连续存储空间
//但总的来说比stack,queue等要慢一些
//类似queue与vector的结合体,与queue相比可以进行数组的随机访问
//与vector相比可以在队头进行O(1)的插入删除操作
d.push_front(111);    //队头插入
d.push_back(2222);     //队尾插入
for(auto i=d.begin();i<d.end();++i)     //支持iterator,begin()->end()
    cout<<*i<<" ";
cout<<endl;
for(int i=0;i<d.size();++i)     //数组类型的随机访问，可用d[i]来表示
    cout<<d[i]<<" ";
cout<<endl;
cout<<d.front()<<endl;  //返回队头元素
d.pop_back();       //弹出队尾元素
cout<<d.back()<<endl;   //返回队尾元素
d.pop_front();      //弹出队头元素
d.clear();

}

六、队列，堆

include [HTML_REMOVED]

void queue_study(void)
{
//头文件#include[HTML_REMOVED]中包含queue和priority queue(堆)两个容器
queue[HTML_REMOVED] a; //queue，队列，即循环队列，先入先出，即队头弹出，队尾插入
a.push(1); //入队，插入到队头，queue为push，无push_back
a.pop(); //出队，弹出队头元素
a.front(); //返回队头元素
a.back(); //返回队尾元素
//注意点，队列和优先队列无clear(),其他容器都有clear()
a=queue[HTML_REMOVED](); //通过初始化实现队列的清空

priority_queue<int> b;  //优先队列-堆，默认为大根堆，即插入随意，输出时每次弹出堆中最大的元素
b.push(1);
b.top();    //返回最大值
b.pop();    //出队，弹出根元素，即最大值
priority_queue<int,vector<int>,greater<int>> c;     //小根堆
priority_queue<pair<int,int>> q;    //pair，双关键字的二元组

cout << q.top().first << endl;//返回pair第一个元素

struct sch{
    int a,b;
    bool operator< (const sch& t) const
    //!!!当自写结构体为堆时，若要大根堆，则需在结构体内修改operator后的符号为<即可
    //若要小根堆则修改operator后的符号为>即可
    {
        return a < t.a;
    }
};//结构体记得加分号
priority_queue<sch> s;  //自定义结构体作为堆，默认为大根堆，小根堆的话重载比较运算符即可
s.push({1,2});
cout << s.top().a;//s.top().a或s.top().b

}

七、集合set,multiset,unordered_set

include [HTML_REMOVED]

void set_study(void)
{
//set特点：有序，无重复！遍历元素时用迭代器实现
//set相关容器-动态有序无重复元素的集合，有size(),empty(),clear()等函数
set[HTML_REMOVED] s; //不能包含重复元素，实现基础为红黑树中的平衡二叉搜索树
multiset[HTML_REMOVED] m; //可用有重复元素
s.insert(12); //插入元素,O(logN)
auto x=s.find(12); //查找，成功则返回对应元素的迭代器，否则返回s.end()
cout<<x<<”**”<[HTML_REMOVED]::iterator it=s.begin(); //set存在迭代器，但只能实现,–操作，迭代器获取为O(1)
it; //即寻找有序集合中it的下一个元素（后继），O(logN)
–it; //即寻找有序集合中it的上一个元素（前驱）
s.erase(it); //删除迭代器对应的元素，O(logN)
s.erase(12); //删除集合中所有x,O(k+logN),k为删除元素个数
s.count(12); //集合中x的个数,set返回1或0,multiset返回个数,其余函数multiset与set的相同,O(k+logN)
//可用count判断一个元素是否在集合中，find也可
auto a=s.lower_bound(12); //查找大于等于x中最小元素的迭代器，二分，O(logN)，使用前应保证序列有序
auto b=s.upper_bound(12); //查找大于x中最小元素的迭代器
unordered_set[HTML_REMOVED] us;//哈希表,无序不重复元素集合,无lower_bound和upper_bound以及迭代器的++，–
//其余与set一致，查找，插入等操作均为O(1)，效率较高，但不支持二分
unordered_multiset[HTML_REMOVED] um; //无序可重复元素集合
//unordered_set和unordered_multiset需要额外头文件#include [HTML_REMOVED]

struct sch{
    int a,b;
    bool operator< (const sch& t) const 
    //当用自己写的结构体为堆时，若要大根堆，则需在结构体内重载<,若要小根堆则重载>
    {
        return a>t.a;
    }
};
set<sch> _struct;   //使用自定义结构体要重载‘<’运算符

}

八、键值对map，二进制串，pair

include [HTML_REMOVED]

void map_study(void)
{//map实现原理，红黑树中的平衡二叉搜索树
map[HTML_REMOVED] a; //二元键值对,key和value可以为任意类型
a[12]=1; //”[]”为操作符，类似数组操作，返回value为O(logN)
cout<[HTML_REMOVED]> b;
b[“xtu”]=vector[HTML_REMOVED]({1,2,3});
cout<[HTML_REMOVED] um; //不支持二分及迭代器的,–,其余和map相同(虽然map本来就没什么二分233)
//查找等操作效率都为O(1),比map快，所以一般不用map，而用unordered_map
//unordered_map需要额外头文件#include [HTML_REMOVED]
map[HTML_REMOVED] ma;//map的遍历
for(map[HTML_REMOVED]::iterator it = ma.begin(); it != ma.end(); it)
cout << it -> first << ” ” << it -> second << endl;//it->first/second
for(map[HTML_REMOVED]::reverse_iterator it = ma.rbegin(); it != ma.rend(); ++ it)
cout << it -> first << ” ” << it -> second << endl;//反向迭代器，从大到小输出

bitset<100> bit;//定义了长度为100的01串,包括size(),empty()等,无clear(),支持所有位运算
bit[1]=1;   //默认为0
bit[3]=1;
bit.set(12);    //将第12位默认设为1
bit.set(11,0);  //把第11位设为0
bit.reset(1);   //将第1位默认设为0
cout<<"*"<<(bit&bit).count()<<endl; //位运算
cout<<(bit|bit).count()<<"*"<<endl;
cout<<bit.count()<<endl;    //返回01串中1的个数
cout << bit.any() << endl;  //是否至少有1个1
cout << bit.none() << endl; //是否全为0
cout << bit.flip() << endl; //等价于~
cout << bit.flip(1) << endl;    //把第一位求反

pair<int,int> p;//普通二元组,可为任意类型,对pair类型进行排序时先按first进行排序
//然后再排second，所以把要排序的元素放到first里，不要排序的放到second里
p={2,3};    //pair赋值
pair<int,int> q;
q=make_pair(3,5);   //第二种赋值方法
cout<<p.first<<" "<<p.second<<endl;     //依次输出二元组中第一个，第二个元素
if(q > p) cout<<"1"<<endl;    //pair具有比较功能，依次比较pair中两个元素,类似字典序
pair<int, pair<int,int>> pa;    //实现三元组

}

九、位运算，常用库函数

include [HTML_REMOVED]

bool cmp(int a,int b) //从左至右看排序
{
return a>b; //从大到小排
}
struct per{
int x,y;
bool operator <(const per & p) const
{
return x[HTML_REMOVED]b.y;
}
void func_study(void)
{
int a=14;
int k=2;
cout<<(a>>k&1)<[HTML_REMOVED]>i&1);
cout<<endl;
cout<<(~k)<<endl; //not,取反
cout<<(a^k)<<endl; //xor,异或
lowbit_a = a & (-a);
//lowbit（n）取出非负整数n在二进制表示下最低位的1，以及它后面的0构成的数值,lowbit=n&(-n)

vector<int> v({5,4,3,2,1});
int arr[] = {1,2,3,4,5};
reverse(v.begin(),v.end());     //翻转vector，起点到终点，左开右闭
reverse(arr,arr+5);     //翻转数组，起点到终点，左开右闭
for(auto x:v)
    cout<<x<<" ";
cout<<endl;
auto ptr=lower_bound(v.begin(),v.end(),3);  
//查找，二分查找大于等于3的元素，返回对应迭代器，前提是数组为从小到大排序好的
cout<<*ptr<<endl;
auto pt=upper_bound(v.begin(),v.end(),3);   //查找严格大于3的元素，返回对应迭代器
int l=lower_bound(v.begin(),v.end(),3)-v.begin();   //返回查找到的元素的下标
cout<<l<<endl;

vector<int> x({1,1,1,2,2,3,3,4});
int m=unique(x.begin(),x.end())-x.begin();  
//unique将排序好的数组进行去重，原理是把不重复的数依次放到前面，最后返回重复的数的第一个位置
cout<<"m:"<<m<<endl;    //m即为不重复的元素个数，实际上x经过unique后为1,2,3,4,1,1,2,3
返回位置为第一个1即第4个数的位置
//数组也是上述类似unique用法
x.erase(unique(x.begin(),x.end()),x.end());//vector去重一般是先sort,再unique结合erase使用
for(int i=0;i<m;++i)
    cout<<x[i]<<" ";
cout<<endl;
srand(time(0));     //设置随机数种子
random_shuffle(v.begin(),v.end());  //将数组随机打乱，生成随机数据
sort(v.begin(),v.end());    //排序,O(nlogn),默认从小到大排序
sort(v.begin(),v.end(),greater<int>()); //从大到小排序
sort(v.begin(),v.end(),cmp);    //通过自己定义的cmp函数来规定排序方式
for(int i=5;i>0;--i){
    p[i].x=i;
    p[i].y=-1;
}
//sort(p,p+5,cmp);    //结构体排序第一种方式，用cmp
sort(p,p+5);    //结构体排序第二种方式，结构体内部重载小于号或大于号

}
int a[10] = {8, 6, 3, 7}, k = 0, n = 4;
nth_element(a, a + k, a + n);//(数组起始地址，要求的第k个元素地址，数组的结束地址)
cout << a[k] << endl; //返回数组中第k小的元素

vector[HTML_REMOVED] a{45, 3, 4, 1};
int k = 0;
nth_element(a.begin(), a.begin() + k, a.end());
cout << a[k];

杂
debug添加变量:数组：(int()[10])(arr)
vector:比如说有一个长度为3的vector v，如果想要查看v[0]的值，就在添加查看中写 (&v[0])
如果想要查看整个数组的值，就可以写(&v[0])@3，@后面的数字表示想要查看的长度
n进制转10进制求和，数组转
for(int i=0;i<len;++i){
sum=sum*进制+a[i];
}
用scanf（“”，%s）,gets（），getchar()时，前面加上一个getchar()吸收回车;

全错排公式:d[n]=(n-1)*(d[n-1]+d[n-2])
错排公式:d(n,m)=d(m,m)+c(n,m);

判断两数相等可以用异或，如
if(!(a ^ b))
printf(“a == b”);
一个圈有n个数，起始位置为point（0<=point<n），则顺时针移动num个数后的新位置point为
point = (point + num) % n;
逆时针移动num个数后的位置point为
point = (point - num % n + n) % n;

开全局数组比较大，最大约等于5*10^8，也就是开不到10^9级别的数组
当遇到这种情况，可以考虑离散化。所以一般全局数组，一维可以开到10^8,二维可以开到10^4.

sstream:作用：从字符串中读取各种信息 #include [HTML_REMOVED]
string str;
getline(cin,str); //读入 “20 xtu 20 3.14”
stringstream ssin(str);
int a,b;
double c;
string s;
ssin >> a >> s >> b >> c;
cout << a <<endl << s << endl << b << endl << c <<endl;
输出：20 xtu 20 3.14

作者：litchi__mango
链接：https://www.acwing.com/solution/content/44372/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```**