Home C++知识点整理及常见STL函数的使用
Post
Cancel

C++知识点整理及常见STL函数的使用

Posted Mar 13, 2022 Updated Mar 30, 2022
By CompetitiveLin
17 min read

本篇博客不阐述原理，只是记录一些知识点以及常用的C++函数代码。

知识点整理

点运算符和箭头运算符

这两个符号都是C++成员运算符1，主要用于确定类对象和成员之间的关系，用于引用类、结构和共用体的成员。

箭头运算符->与一个指针对象的指针一起使用。如果是指针访问数据成员或成员函数，用->;

点运算符.与实际的对象一起使用。如果是某个数据类型的对象，访问自己的数据成员和成员函数用.;

举个例子：

1
2
3
4

string s1 = "a string",*p = &s1;
int n = s1.size();                  //运行string对象s1的size()成员
n = (*p).size();                    //运行p所指对象的size成员
n = p->size(;)                      //等价于(*p).size

左移右移运算符

左移乘，右移除

bitset.count()函数用于统计二进制数中1的数量。

__builtin_popcount()函数也可以统计二进制中1的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<bits/stdc++.h>
using namespace std;
int main() {
    unsigned short short1 = 4;
    bitset<16> bitset1(short1);   // the bitset representation of 4
    cout << bitset1 << endl;  // 0b00000000'00000100

    unsigned short short2 = short1 << 1;     // 4 left-shifted by 1 = 8
    bitset<16> bitset2(short2);
    cout << bitset2 << endl;  // 0b00000000'00001000

    unsigned short short3 = short1 >> 2;     // 4 right-shifted by 2 = 1
    bitset<16> bitset3(short3);
    cout << bitset3 << endl;  // 0b00000000'00000001
    
    int int1 = 5;
    bitset<4> bitset4(int1);			// 0b1001 
    cout << bitset4.count() << endl;	// number of set bits in bitset4 = 2
    cout << __builtin_popcount(5) << endl;	// same as above
}

前中后序遍历

前序(preorder): 根结点 -> 遍历左子树 -> 遍历右子树 （首先访问根结点）

中序(inorder): 遍历左子树 -> 根结点 -> 遍历右子树

后序(postorder): 遍历左子树 -> 遍历右子树 -> 根结点 （最后访问根结点）

约瑟夫环

简介：n 个人围成一个圈，每次数 k 个数，被数到的那个人出局。

数学解法：

1
2
3
4
5
6
7

int findTheWinner(int n, int k) {
    int p = 0;
    for (int i = 2; i <= n; i++) {
        p = (p + k) % i;
    }
    return p + 1;
}

队列：

1
2
3
4
5
6
7
8
9
10
11
12

int findTheWinner(int n, int k) {
    queue<int> q;
    for(int i = 0; i < n; i++) q.push(i + 1);
    while(q.size() != 1){
        for(int i = 0; i < k - 1; i++){
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    return q.front();
}

常见STL函数的使用

STL: Standard Template Library

list

emplace可以代替insert. emplace_back可以代替push_back. emplace_front可以代替push_front.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

mylist.front()
mylist.back()
mylist.begin()
mylist.end()
mylist.empty()

mylist.erase()
mylist.remove()

mylist.insert()

mylist.pop_back()
mylist.pop_front()
mylist.push_back()
mylist.push_front()

mylist.reverse()
mylist.sort()

mylist.unique()

vector

emplace可以代替insert. emplace_back可以代替push_back. emplace_front可以代替push_front.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

myvector.front()
myvector.back()
myvector.size()

myvector.begin()
myvector.end()

for(vector<int>::iterator it = myvector.begin();it!=myvector.end();it++){
    cout<<*it<<endl;
}

myvector.clear()

myvector.pop_back()
myvector.push_back()

myvector.empty()
myvector.insert()

queue

emplace可以代替push

1
2
3
4
5
6

myqueue.push()
myqueue.pop()
myqueue.empty()
myqueue.size()
myqueue.front()
myqueue.back()

stack

emplace可以代替push

1
2
3
4
5

mystack.empty()
mystack.pop()
mystack.push()
mystack.size()
mystack.top()  //栈顶，即出入口

map & unordered_map

emplace可以代替insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 不需要对key进行排列或数据量不小于10000的时候，用unordered_map.

unordered_map<char,int> mymap;
mymap['a'] = 100;
mymap['b'] = 200;

for(map<char,int>::iterator it = mymap.begin();it != mymap.end(); it++){
    cout<<it->first<<" => " <<it->second<<endl;
}

mymap.size()

mymap.clear()

mymap.count(k)  //return 1 if found or 0 otherwise

mymap.erase(key)
mymap.erase(iterator first,iterator last)

it = mymap.find('b')
mymap.insert()

set & unordered_set

emplace可以代替insert

1
2
3

unordered_set<int> myset;

unordered_set<pair<int, string>> myset;

priority_queue

优先队列与堆类似。默认大顶堆。

和队列基本操作相同:

  • top() 访问队头元素
  • empty() 队列是否为空
  • size() 返回队列内元素个数
  • push() 插入元素到队尾 (并排序)
  • emplace() 原地构造一个元素并插入队列
  • pop() 弹出队头元素
1
2
3
4
5

//大顶堆，即降序队列
priority_queue<int> big_heap;
priority_queue<int, vector<int>, less<int> > big_heap2; 
//小顶堆，即升序队列
priority_queue<int, vector<int>, greater<int> > small_heap;

pair的比较，先比较第一个元素，第一个相等比较第二个

1
2
3
4

//大顶堆，即降序队列
priority_queue<pair<int, int> > big_pair_heap;
//小顶堆，即升序队列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> small_pair_heap;

lower_bound

lower_bound()和upper_bound()是利用二分查找的方法在一个排好序的容器中进行查找，比如set,vector,map容器。具体用法如下所示：

  • lower_bound(value): 第一个大于等于（可以是字典序，也可以是值）value的下标或者指针
  • upper_bound(value): 第一个大于（可以是字典序，也可以是值）value的下标或者指针

map:

1
2
3
4
5
6
7
8
9
10

map<char,int> mymap;
mymap['a']=20;
mymap['b']=40;
mymap['c']=60;
mymap['d']=80;
mymap['f']=100;
map<char,int>::iterator itlow=mymap.lower_bound ('b');  // itlow points to b
map<char,int>::iterator temp=mymap.upper_bound ('d');   // temp points to f (not d!)
map<char,int>::iterator itup=mymap.upper_bound ('e');   // there's no e, so itup points to f
mymap.erase(itlow,itup);                                // erases [itlow,itup)

set:

1
2
3
4
5
6
7

set<int> myset;
for (int i=1; i<10; i++) myset.insert(i * 10);        // 10 20 30 40 50 60 70 80 90
set<int>::iterator  temp1=myset.lower_bound (25);     // 30 >= 25,so temp1 points to 30
set<int>::iterator  temp2=myset.lower_bound (60);     // 70 > 60,so temp2 points to 70
set<int>::iterator  itlow=myset.lower_bound (30);     // itlow points to 30
set<int>::iterator  itup=myset.upper_bound (65);      // itup  points to 70
myset.erase(itlow,itup);                              // erases [itlow,itup)

string::find

int index = mystring.find(s, pos);

其中 s 可以是字符也可以是字符串，pos 是寻找字符或字符串的起始位置。

1
2
3

string str = "abcdefgabc";
int index = str.find("abc");    // index = 0
int index = str.find("abc", 3); // index = 7

string::substr

string str = mystring.substr(pos, len);2

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// string::substr
#include <iostream>
#include <string>

int main ()
{
  std::string str="We think in generalities, but we live in details.";  // (quoting Alfred N. Whitehead)

  std::string str2 = str.substr (3,5);     // "think"

  std::size_t pos = str.find("live");      // position of "live" in str

  std::string str3 = str.substr (pos);     // get from "live" to the end

  std::cout << str2 << ' ' << str3 << '\n';

  return 0;
}

Output:

think live in details.

string::to_string

string str = to_string(a); 3

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

include<bits/stdc++.h>

struct person{                   // structure
 double a;
 double b;
}temp[100];

getline(cin,s);

int a;                           // int to string
string str = to_string(a);     

string b;                        // string to int
int int1 = atoi(b.c_str());      //遇到字母会自动停下，如果没有数字，则定义为0 。b为string类型的情况下还需要使用c_str()函数
int int2 = stoi(b);              //遇到字母会自动停下，如果没有数字，运行会出错

string str;                      // length(string)
int res = str.length();

char *test;                      // length(char)
int res = strlen(test);

int num = 3;
temp = string(num, 'a');        // "aaa"

int i = 1, j = 4;
int res = (i + j)/2;    // 向下取整，res = 2;
cout<<res<<endl;

malloc

动态分配与释放内存。与vector相比，使用malloc的效率更高。

分配一维与二维数组代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<bits/stdc++.h>
using namespace std;

int main(){
	// 1-dimensional
	int len = 10;
	int *p;
	p  = (int *)malloc(len * sizeof(int));
	free(p);
	// 2-dimensional 
	int **a;
    int row = 3; int col = 3;
    a = (int **)malloc(row * sizeof(int*));
    for(int i = 0; i < row; i++)
    {
        a[i] = (int *)malloc(col * sizeof(int));
    }
    
    for(int i = 0; i < row; i++)
    {
        free(a[i]);
    }
    free(a);
}

代码备忘录

素数判断

1
2
3
4
5
6

bool is_prime(int s){
    if(s <= 3) return s > 1;
    int sqt = sqrt(s);
    for(int i = 2; i <= sqt; i++)  if(s % i == 0) return false;
    return true;
}

自定义排序

1
2
3
4
5
6
7
8
9

bool cmp(string a, string b){
    if(a.length() != b.length()) return a.length() < b.length(); // 按长度升序：a的长度小于b的长度，所以从左到右长度变大。
    return a > b;                   // 按字典序降序：a的字典序大于b的字典序，所以从左到右字典序降低。
}

int main(){
	sort(temp1, temp1 + 4, cmp);            // temp1为数组
	sort(temp2.begin(), temp2.end(), cmp);  // temp2为向量
}

最大最小值

与sort()函数类似，可对数组、向量的任意区间求最大或最小值。

1
2
3
4
5
6
7
8

#include<bits/stdc++.h>
using namespace std;
int main(){
	int temp_myv[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	vector<int> myv(temp_myv, temp_myv + 10);
	cout<<*min_element(temp_myv, temp_myv + 10)<<endl;
	cout<<*max_element(myv.begin(), myv.end())<<endl;
}

所有元素求和

1
2
3
4

int a[5] = {1, 2, 3, 4, 5};
vector<int> v(a);
int sum = accumulate(a, a + 5, 0);
int sum2 = accumulate(v.begin(), v.end(), 0);

输出标准化

输出标准化参考此博客45。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

cout<<fixed<<setprecision(1)<<a<<endl;  // accurate to 1 decimal place

cout<<setw(3)<<setfill('0')<<a<<endl;    // filled with '0'
printf("%03d",a);   //  if a=1;   输出001


cout<<hex<<12<<endl;                    // 十六进制输出
cout<<oct<<12<<endl;                    // 八进制输出
         
cout<<left<<setw(5)<<10<<endl;        // 左对齐  
cout<<right<<setw(5)<<10<<endl;       // 右对齐

string a; 
int b,c;
scanf("%s : %d :%d", &a[0], &b, &c);     //可以隔着冒号取值,记得引用符号&
printf("%s\n",a);

回文判断

用于判断字符串s中的任意子串是否回文。

动态规划法：

judge[start][end]表示字符串s中[start, end]的子串是否为回文串。

1
2
3
4
5
6
7
8
9
10
11

int n = s.length();
vector<vector<bool> > judge(n, vector<bool>(n, true));
// 从后往前去遍历
for (int i = n - 1; i >= 0; --i)
{
    for (int j = i + 1; j < n; ++j)
    {
        // 判断i和j是否相等，相等则扩展
        judge[i][j] = (s[i] == s[j]) && judge[i + 1][j - 1];
    }
}

双指针遍历法：

描述同动态规划法，适用于单次简单判断。若要判断字符串s的每个子串是否为回文串，复杂度则为O(n^3)。

1
2
3
4
5
6

bool judge(string s, int start, int end){                               // 双指针遍历
    for(int i = start; i <= (start + end) / 2; i++){
        if(s[i] != s[end + start - i]) return false;
    }
    return true;
}

二分查找

详细的二分查找分析见此。

1
2
3
4
5
6
7
8
9
10
11
12

int nums[5] = {10, 20, 30, 40, 50};
int flag = -1, target = 16;
int i = 0, j = n - 1;           // 前闭后闭
while(i <= j){                  // 因此i > j(即i == j + 1)时退出循环
    int mid = i + (j - i)/2;
    if(target == nums[mid]){
        flag = mid;
        break;
    }
    else if(target > nums[mid]) i = mid + 1;    // mid已经遍历，所以新的区间为[i, mid - 1]或[mid + 1, j]
    else j = mid - 1;
}

排列组合

排列(permutation)：

\[A_{n}^{m} = \frac{n!}{(n - m)!} = (n - m + 1) * \cdots * (n - 1) * n\]
1
2
3
4
5
6
7

int A(int n, int m) {
    int res = 1;
    for(int i = n - m + 1; i <= n; i++){
        res *= i;
    }
    return res;
}

组合(combination)：

\[C_{n}^{m} = \frac{ A_{n}^{m} }{m!} = \frac{n!}{(n - m)!m!} = C_{n}^{n-m}\]
1
2
3
4
5
6

int C(int n, int m) {
    m = min(m, n - m);
    int numerator =   A(n, m);	//分子
    int denominator = A(m, m);	//分母
    return numerator / denominator;
}

字符串大小写判断及转换

大小写判断：

1
2

for (int i = 0; i < str.size(); i++) if(islower(str[i])) return false;      // bool islower(int c);
for (int i = 0; i < str.size(); i++) if(isupper(str[i])) return false;      // bool isupper(int c);

大小写转换：

1
2

for (int i = 0; i < str.size(); i++) str[i] = tolower(str[i]);      // int tolower(int c);
for (int i = 0; i < str.size(); i++) str[i] = toupper(str[i]);      // int toupper(int c);

三个及以上的数字取最大最小值

max()、min()函数中只有两个参数，意味着只能在两个数中取最大或者最小值。

当需要对三个及以上的数字取最大或最小值时，可用以下方法。

1
2
3
4
5
6
7
8
9

int x = 6, y = 2, z = 10;
int m1 = max({x,y,z});
int m2 = max<int>({x,y,z});
int m3 = max({(int)x,y,z});

double a = 9.2, b = 2.4, c = 5.5555;
double n1 = min({a,b,c});
double n2 = min<double>({a,b,c});
double n3 = min({(double)a,b,c});

或者：

1
2
3

int maxn(int x, int y, int z){
    return max(max(x, y), z);
}

随机数生成

伪随机数：

  • rand() / double(RAND_MAX) 产生随机数的范围是 [0, 1]

  • rand() / double(RAND_MAX) * 2 * r 产生随机数范围为 [0, 2r]

  • rand() / double(RAND_MAX) * 2 * r - r + x 产生随机数范围为 [x - r, x + r]

真随机数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;  // random_device 是一个“真随机数”发生器，它的缺点就是耗能太大，所以尽量别奢侈地一直用它
    std::mt19937 gen(rd()); // 用 random_device产生一个真随机数，用作“伪随机数发生器”的种子，此后就雪藏之
    std::uniform_int_distribution<> dis(1, 6); // 一个正态“分布器”，高斯分布器是 std::normal_distribution
 
    for (int n=0; n<10; ++n)
        // 用 dis 变换 gen 所生成的随机 unsigned int 到 [1, 6] 中的 int
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

Reference

  1. C++ 成员运算符 ↩

  2. string::substr ↩

  3. string::to_string ↩

  4. C++ cout格式化输出（输出格式） ↩

  5. C++ 基本的输入输出 ↩

C++
stl c++ syntax
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

申请软著的时间周期记录以及注意事项

C++中vector的初始化及赋值方式