程序设计竞赛笔记

竞赛 / 算法 / 基础知识
Word count: 13.6k   |   Reading time≈ 58 min

程序设计竞赛笔记

C/C++基础

std

std：命名空间标识符⟶\longrightarrow一般在调用c++标准库中的函数或是对象时需要在函数或是对象前面怎加std。

size_t 类型

size_t 类型表示C中任何对象所能达到的最大长度，它是无符号整数。

C++索引（切片）

C++中的切片方式一般为：(begin_pos,size)

关于comp方法⭐️

comp实现的源码：
1
2
3
4
template<typename _Iterator, typename _Value>
bool operator()(_Iterator __it, _Value& __val)
{ return bool(_M_comp(*__it, __val)); }
   };

由源码可以看出comp的第一个参数是迭代器，而第二个元素是value值

std::lambda 匿名函数

参考：C++11 lambda表达式精讲 (biancheng.net)

lambda指的是匿名函数

lambda 表达式的语法形式可简单归纳如下：

1
[ capture ] ( params ) opt -> ret { body; };

实例：

1
2
3
4
5
6
auto f = [](int a) -> int { return a + 1; };
std::cout << f(1) << std::endl;  // 输出: 2

//lambda 表达式在没有参数列表时，参数列表是可以省略的
auto f1 = [](){ return 1; };
auto f2 = []{ return 1; };  // 省略空参数表

lambda 表达式还可以通过捕获列表捕获一定范围内的变量：

  • [] 不捕获任何变量。

  • [&] 捕获外部作用域中所有变量，并作为引用在函数体中使用（按引用捕获）。

  • [=] 捕获外部作用域中所有变量，并作为副本在函数体中使用（按值捕获）。

  • [=，&foo] 按值捕获外部作用域中所有变量，并按引用捕获 foo 变量。

  • [bar] 按值捕获 bar 变量，同时不捕获其他变量。

  • [this] 捕获当前类中的 this 指针，让 lambda 表达式拥有和当前类成员函数同样的访问权限。如果已经使用了 & 或者 =，就默认添加此选项。捕获 this 的目的是可以在 lamda 中使用当前类的成员函数和成员变量。

基本用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class A
{
    public:
    int i_ = 0;
    void func(int x, int y)
    {
        auto x1 = []{ return i_; };                    // error，没有捕获外部变量
        auto x2 = [=]{ return i_ + x + y; };           // OK，捕获所有外部变量
        auto x3 = [&]{ return i_ + x + y; };           // OK，捕获所有外部变量
        auto x4 = [this]{ return i_; };                // OK，捕获this指针
        auto x5 = [this]{ return i_ + x + y; };        // error，没有捕获x、y
        auto x6 = [this, x, y]{ return i_ + x + y; };  // OK，捕获this指针、x、y
        auto x7 = [this]{ return i_++; };              // OK，捕获this指针，并修改成员的值
    }
};
int a = 0, b = 1;
auto f1 = []{ return a; };               // error，没有捕获外部变量
auto f2 = [&]{ return a++; };            // OK，捕获所有外部变量，并对a执行自加运算
auto f3 = [=]{ return a; };              // OK，捕获所有外部变量，并返回a
auto f4 = [=]{ return a++; };            // error，a是以复制方式捕获的，无法修改
auto f5 = [a]{ return a + b; };          // error，没有捕获变量b
auto f6 = [a, &b]{ return a + (b++); };  // OK，捕获a和b的引用，并对b做自加运算
auto f7 = [=, &b]{ return a + (b++); };  // OK，捕获所有外部变量和b的引用，并对b做自加运算

std::sort

参考：C++ sort()排序函数用法详解 (biancheng.net)

sort(first,last,Comp)

1
2
3
sort(first, last, Comp);
//根据Comp返回的值为true或false判断是否执行交换，如果为true则证明符合排序标准，不交换；否则，交换位置
//一般Comp写成一个匿名函数
sort的comp方法⭐️

  • sort默认按照升序排序

  • sort设置comp实现降序排序：

1
2
3
4
bool comp(int a,int b)//a是迭代器，a会往后移动？
{
    return a>b;//如果前面的元素a比后面的元素b大则符合我们的降序排序标准，因此不用进行位置交换，如果a>b为false，则需要进行a，b位置的交换。
}

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

//降序
bool comp(const int&a,const int&b){       
 	return a>b;
}

int main() {
	vector<int>c(5);
	for(int i=0;i<5;++i){
		cin>>c[i];
	} 
	sort(c.begin(),c.end(),comp);
	for(int i=0;i<5;++i){
		cout<<c[i]<<" ";
	} 
	return 0;
}

输入输出：

1
2
3
4
//输入
1 5 2 3 4
//输出
5 4 3 2 1
关于C++中vector<vector>array的理解

解释：array用来保存一个3 * 3的二维数组，array的每个元素都是vector类型

1
vector<vector<int> >dp(n,vector<int>(m));//定义二维数组dp[][]，n行 m列

下面是对以上二维数组的两种赋值方式：

1️⃣采用vector模板中的方法push_back()

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
#include<iostream>
#include<vector> 
using namespace std;

int main()
{
    //array用来保存一个3*3的二维数组，array的每个元素都是vector<int>类型
    vector <vector<int>>array;
    std::vector<int> v;
    for (int i = 0; i <3; i++){
        for (int j = 0; j <3; j++){
            int value;
            cin >> value;
            v.push_back(value);
        }
        array.push_back(v); //保存array的每个元素
        v.clear();
    }

    for (int i = 0; i <array.size(); i++)
    {
        for (int j = 0; j <3; j++)
            cout <<array[i][j];
        cout<<endl;
    }
    return 0;
}

2️⃣用分配空间的resize()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<vector> 
using namespace std;

int main()
{
    vector <vector<int> >array(3);//首先给array开辟了三个空间
    for (int i = 0; i <3; i++){
        array[i].resize(3);//给array中每个元素开辟了三个空间
        for (int j = 0; j <3; j++){
            cin >> array[i][j];//直接对开辟的空间赋值即可
        }
    }
    for (int i = 0; i <array.size(); i++)
    {
        for (int j = 0; j <3; j++)
            cout <<array[i][j];
        cout<<endl;
    }
    cout << array.size();
    return 0;
}
array.size()

获得数组的条目数⟶\longrightarrow对于二维数组来说得到的是二维数组的行数

memset()

C 库函数 void *memset(void *str, int c, size_t n) 复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。

声明：

1
void *memset(void *str, int c, size_t n)

参数：

  • str – 指向要填充的内存块。

  • c – 要被设置的值。该值以 int 形式传递，但是函数在填充内存块时是使用该值的无符号字符形式。

  • n – 要被设置为该值的字符数

返回值：

该值返回一个指向存储区 str 的指针。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <string.h>
 
int main ()
{
   char str[50];
 
   strcpy(str,"This is string.h library function");
   puts(str);
 
   memset(str,'$',7);
   puts(str);
   
   return(0);
}

/**
*	输出结果如下：符号$被复制到str的前7个位置上
*/
This is string.h library function
$$$$$$$ string.h library function
unique()

unique函数属于STL中比较常用函数，它的功能是元素去重。

返回值：是一个迭代器，指向的是去重之后容器中不重复序列的最后一个元素的下一个元素。

unique函数的去重过程实际上就是不停的把后面不重复的元素移到前面来，也可以说是用不重复的元素占领重复元素的位置。

unique示例图

  1. 有很多文章说的是，unique去重的过程是将重复的元素移到容器的后面去，实际上这种说法并不正确，应该是把不重复的元素移到前面来

  2. unique函数在使用前需要对容器中的元素进行排序(当然不是必须的，但我们绝大数情况下需要这么做)，由于本例中的元素已经是排好序的，所以此处我没排序，但实际使用中不要忘记

unique函数的函数原型如下：

1.只有两个参数，且参数类型都是迭代器：

1
iterator unique(iterator it_1,iterator it_2);

其中这两个参数表示对容器中[it_1，it_2)范围的元素进行去重(注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。

2.有三个参数，且前两个参数类型为迭代器，最后一个参数类型可以看作是bool类型：

1
iterator unique(iterator it_1,iterator it_2,bool MyFunc);

其中前两个参数和返回值同上面类型的unique函数是一样的，主要区别在于第三个参数。这里的第三个参数表示的是自定义元素是否相等。也就是说通过自定义两个元素相等的规则，来对容器中元素进行去重。这里的第三个参数与STL中sort函数的第三个参数功能类似。

begin()和end()容器⭐️

参考：C++ STL begin()和end()函数用法 (biancheng.net)

begin()和end()容器：

  1. 可以对向量（vector）、集合（set）、map……等有用；

  2. 也对数组有相同的作用；

    • 将指定数组传给 begin() 函数，其会返回一个指向该数组首个元素的指针；将指定数组传给 end() 函数，其会返回一个指向数组中最后一个元素之后位置的指针。

vector 容器

参考：C++ STL vector容器详解 (biancheng.net)

"vector函数的作用就是申请内存空间，vector是一种可以自动扩展的容器，也就是可以根据元素个数自动申请内存，那么有什么必要去主动为它申请内存空间呢？答案是有必要的，我们来看个例子。假如要使用vector存储1000个数据：

方式1：vector vec, 然后调用1000次 vec.push_back()；方式2：vector vec,然后调用vec.reserve(1000)申请1000个元素的内存，再调用1000次 vec.push_back()；

方式1要进行若干次内存分配；而方式2只需要进行1次内存分配。其效率立见高下，所以在需要对大量数据进行处理的时候，使用reserve主动分配内存可以提升程序执行效率。"

vector ::resize()

一、resize
1、resize(n)
调整容器的长度大小，使其能容纳n个元素。如果n小于容器的当前的size，则删除多出来的元素。否则，添加采用值初始化的元素。
2、 resize(n，t)
多一个参数t，将所有新添加的元素初始化为t。

vector ::reserve()

二、reserve
reserver()的用法只有一种：reserve(n)
预分配n个元素的存储空间。

size（长度）：指容器当前拥有的元素个数；
capacity（容量）：则指容器在必须分配新存储空间之前可以存储的元素总数，也可以说是预分配存储空间的大小。

1
2
3
4
5
/**
*@function 申请n个元素的内存空间
*@param n  元素个数
*/
void reserve (size_type n);

容器调用resize()函数后，所有的空间都已经初始化了，所以可以直接访问。而reserve()函数预分配出的空间没有被初始化，所以不可访问。

1）resize()函数对vector的影响。
size：调用resize(n)后，vector的size即为n，且其中元素都为0。
capacity：取决于调整后的容器的size是否大于capacity。如果调整后size大于capacity，则capacity调整为size大小，否则不变

2）reserve()函数对vector影响
capacity：调用reserve(n)后，若容器的capacity<n，则重新分配内存空间，从而使得capacity等于n。如果capacity>=n，capacity无变化。

在 C++ 中，vector 是一种动态数组（可变大小的连续内存块），reserve() 是 vector 的一个成员函数，用于预留容器的存储空间。它接受一个参数，该参数表示要预留的元素个数。

调用 reserve() 函数并不会改变 vector 的大小，而仅仅是分配足够的内存以容纳指定数量的元素。这可以避免在向 vector 添加元素时重复分配内存，从而提高程序性能。

需要注意的是，如果你在 reserve() 函数中传递的参数小于当前容器的大小，则不会发生任何事情。如果你想缩小容器的大小，可以使用 resize() 或 shrink_to_fit() 函数。

容器的begin()、cbegin()、rbegin()、crbegin()函数

总结：

  • begin();end()正序迭代器

  • cbegin();cend() 返回 const 的begin();end()

  • rbegin();rend() 逆序迭代器

  • crbegin();crend() 返回 const 的 rbegin();rend()

find() 函数

find()返回指定元素出现的第一个位置下标。

如下为 find() 函数的语法格式：

1
InputIterator find (InputIterator first, InputIterator last, const T& val);

其中，first 和 last 为输入迭代器，[first, last) 用于指定该函数的查找范围；val 为要查找的目标元素。

正因为 first 和 last 的类型为输入迭代器，因此该函数适用于所有的序列式容器。

当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。

erase() 函数

erase() 函数三种用法：

1
2
3
4
5
6
7
8
//1、删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
erase(pos,n);

//2、删除position处的一个字符(position是个string类型的迭代器)
erase(position);

//3、删除从first到last之间的字符（first和last都是迭代器）
erase(first,last);
vector::begin()

vector::begin()是 “vector” 头文件的库函数，用于获取向量的第一个元素。它返回一个指向向量第一个元素的迭代器。

vector::back()

**vector :: back()是“ vector”**标头的库函数，用于访问矢量的最后一个元素，它返回对矢量的最后一个元素的引用。

1
2
3
4
5
6
7
/**
*定义一个没有初始化空间的向量（也可以说是数组）
*这个时候不能用数组的形式对其赋值：dp[i]=23，是不被允许的
*/
vector<int>dp;
dp.push_back(23);//合法

vector::push_back()

vector::push_back()在vector尾部加入一个数据;

vector::pop_back()

vector::pop_back() 是"vector" 头文件的库函数，用于从vector 尾部删除一个元素，从vector 后面删除元素并返回void。

iota() 函数

C++中 iota() 是用来批量递增赋值vector的元素的。

实例：

1
iota(id.begin(), id.end(), 0); // iota函数可以把数组初始化为0到n-1

注意与atoi()函数区分开

atoi() 函数

扫描str字符串，将数字或正负号转换为int型

实例：

1
2
3
4
5
6
7
8
9
10
11
void func()
{
    char str1[] = "-10";
    int num1 = atoi(str1);
    printf("num1 = %d\n", num1);
}

//结果： 
num1 = -10

而 char str1[] = "abc-1100def";结果是： num1 = 0

vector::insert()与vector::emplace()

参考：C++ STL vector插入元素（insert()和emplace()）详解 (biancheng.net)

emplace()的插入效率更高

array 容器

参考：C++ array(STL array)容器用法详解 (biancheng.net)

它就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。在使用上，它比普通数组更安全（原因后续会讲），且效率并没有因此变差。

1
2
3
4
5
6
//创建具有 10 个 double 类型元素的 array 容器
std::array<double, 10> values;
//
std::array<double, 10> values{};
//
std::array<double, 10> values {0.5,1.0,1.5,,2.0};

list 容器

参考：C++ STL list添加（插入）元素方法详解 (biancheng.net)

成员方法：

  • push_front()：向 list 容器首个元素前添加新元素；

  • push_back()：向 list 容器最后一个元素后添加新元素；

  • emplace_front()：在容器首个元素前直接生成新的元素；

  • emplace_back()：在容器最后一个元素后直接生成新的元素；

  • emplace()：在容器的指定位置直接生成新的元素；

  • insert()：在指定位置插入新元素；

  • splice()：将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。

list splice()成员方法
语法格式 功能
void splice (iterator position, list& x); position 为迭代器，用于指明插入位置；x 为另一个 list 容器。 此格式的 splice() 方法的功能是，将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator i); position 为迭代器，用于指明插入位置；x 为另一个 list 容器；i 也是一个迭代器，用于指向 x 容器中某个元素。 此格式的 splice() 方法的功能是==将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处==。
void splice (iterator position, list& x, iterator first, iterator last); position 为迭代器，用于指明插入位置；x 为另一个 list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域。 此格式的 splice() 方法的功能是==将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处==。 
1
2
3
4
5
6
// 第一种语法格式
void splice (iterator position, list& x);
// 第二种语法格式
void splice (iterator position, list& x, iterator i);
// 第三种语法格式
void splice (iterator position, list& x, iterator first, iterator last);

list 容器底层使用的是链表存储结构，splice() 成员方法移动元素的方式是，将存储该元素的节点从 list 容器底层的链表中摘除，然后再链接到当前 list 容器底层的链表中。这意味着，当使用 splice() 成员方法将 x 容器中的元素添加到当前容器的同时，该元素会从 x 容器中删除。

实例：

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
int main()
{
    //创建并初始化 2 个 list 容器
    list<int> mylist1{ 1,2,3,4 }, mylist2{10,20,30};
    list<int>::iterator it = ++mylist1.begin(); //指向 mylist1 容器中的元素 2
   
    //调用第一种语法格式
    mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                 // mylist2:
                                 // it 迭代器仍然指向元素 2，只不过容器变为了 mylist1
    //调用第二种语法格式，将 it 指向的元素 2 移动到 mylist2.begin() 位置处
    mylist2.splice(mylist2.begin(), mylist1, it);   // mylist1: 1 10 20 30 3 4
                                                    // mylist2: 2
                                                    // it 仍然指向元素 2
   
    //调用第三种语法格式，将 [mylist1.begin(),mylist1.end())范围内的元素移动到 mylist.begin() 位置处                  
    mylist2.splice(mylist2.begin(), mylist1, mylist1.begin(), mylist1.end());//mylist1:
                                                                             //mylist2:1 10 20 30 3 4 2
   
    cout << "mylist1 包含 " << mylist1.size() << "个元素" << endl;
    cout << "mylist2 包含 " << mylist2.size() << "个元素" << endl;
    //输出 mylist2 容器中存储的数据
    cout << "mylist2:";
    for (auto iter = mylist2.begin(); iter != mylist2.end(); ++iter) {
        cout << *iter << " ";
    }
    return 0;
}

//结果
mylist1 包含 0个元素
mylist2 包含 7个元素
mylist2:1 10 20 30 3 4 2
list insert()成员方法
语法格式 用法说明
iterator insert(pos,elem) 在迭代器 pos 指定的位置之前插入一个新元素 elem，并返回表示新插入元素位置的迭代器。
iterator insert(pos,n,elem) 在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,first,last) 在迭代器 pos 指定的位置之前，插入其他容器（例如 array、vector、deque 等）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,initlist) 在迭代器 pos 指定的位置之前，插入初始化列表（用大括号 { } 括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。
list 迭代器 iterator

详细参考：(77条消息) 简单说明C++ STL list中的迭代器（iterator）_Mr.Z2001的博客-CSDN博客_c++ list iterator

迭代器的类型声明是list<Type T>::iterator，当然也可以auto

1
2
3
4
list<int> a {1, 3, 5};
list<int> b {2, 4};//构造函数
list<int>::iterator ita = a.begin();//类似于指针
auto itb = b.begin();//声明一下我们要讨论的迭代器ita和itb，分别作用于链表a和链表b

map 容器

参考：C++ STL map容器详解 (biancheng.net)

map是STL的一个关联容器，存储的都是 pair 对象。

  • 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
  • 第二个可以称为该关键字的值(value)；
  • map中的键值对会自动根据key进行升序排序。⭐️

1️⃣map.first会得到Map中key的有效值;
2️⃣map.second会得到Map中value的有效值。

1
2
3
4
//map类型可以初始化大小
map<int,int>buckets(n);
//但是不能像vector一样初始化值
map<int,int>buckets(n,0);//这是错误的写法

map容器插入键值对的方法一般有三种：

  1. map[“key”] = value;

  2. map.insert(make_pair<>("", “”));

  3. map.emplace("", “”);

1
2
3
4
5
unordered_map<int,pair<int,int>>hash(m);
for(int i=0;i<m;++i){
    cin>>y>>result;
    hash[i]=make_pair<>(y,result);//<>不需要写成<int,int>
}

用下标插入会覆盖 value 值，用 insert 插入键值对则不覆盖（插入失败）

参考：(77条消息) C++ map、unordered_map 插入元素的覆盖问题_cyberickk的博客-CSDN博客

从map中获取第一个键和值

  • 获取键 key：your_map.begin()->first

  • 获取值 value：your_map.begin()->second

img

unordered_map与map的区别

  1. unordered_map使用的hash表存储，无序；map用的平衡二叉搜索树，有序；

  2. unordered_map的搜索的时间复杂度最好情况是O(1)，最坏是O(n)；map搜索的时间复杂度永远是O(log n)（由于平衡二叉搜索树的原因）

  3. 在map中，使用用户自定义的key的时候，需要重写<操作，或者传入一个外部的函数，用于比较key(vector 可以不定义，有默认的)；unordered_map需要为key的类型提供hash函数的定义，并且需要重写==。（注意二者的“或者”与“并且”）

参考：[c++ unordered_map与map - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/468286147#:~:text=总结来说，主要有如下几点区别： 1.unordered_map使用的hash表存储，无序；map用的平衡二叉搜索树，有序； 2.unordered_map的搜索的时间复杂度最好情况是O,(1)，最坏是O (n)；map搜索的时间复杂度永远是O (log n)（由于平衡二叉搜索树的原因）)

unordered_map 容器

详细参考：C++ STL unordered_map容器用法详解 (biancheng.net)

unordered_map 容器，直译过来就是"无序 map 容器"的意思。所谓“无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。

1
2
3
4
5
6
7
8
9
10
//map与unordered_map容器的数组形式
//key代表的时数组下标，val代表的时数组下标对应的值
map<string, string> data;
	data["_id"] = "7846464";
	data["name"] = "老张";
	data["comment"] = "记住：别想着返回数组，都是把外面的数组地址传进去赋值";
    /**
    * 通用式
    */
	data[key]=val;

unordered_map 使用栈形式存储数据，后入先出。

unordered_map 的初始化

  1. 如果不想全部拷贝，可以使用 unordered_map 类模板提供的迭代器，在现有 unordered_map 容器中选择部分区域内的键值对，为新建 unordered_map 容器初始化。例如：

    1
    2
    //传入 2 个迭代器，
    std::unordered_map<std::string, std::string> umap2(++umap.begin(),umap.end());

    通过此方式创建的 umap2 容器，其内部就包含 umap 容器中除第 1 个键值对外的所有其它键值对。

unordered_map的emplace()插入键值对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
    //创建空 umap 容器
    unordered_map<string, string> umap;
    //向 umap 容器添加新键值对
    umap.emplace("Python教程", "http://c.biancheng.net/python/");
    umap.emplace("Java教程", "http://c.biancheng.net/java/");
    umap.emplace("Linux教程", "http://c.biancheng.net/linux/");

    //输出 umap 存储键值对的数量
    cout << "umap size = " << umap.size() << endl;
    //使用迭代器输出 umap 容器存储的所有键值对
    for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}
unordered_multimap容器

参考：C++ STL unordered_multimap容器精讲 (biancheng.net)

std::unordered_multimap是C++STL中的一个关联容器它以无序的方式存储元素。它类似于std::unordered_map，但允许将多个值映射到同一个键。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myMap;

    // Insert some key-value pairs
    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "cherry"));
    myMap.insert(std::make_pair(1, "apricot"));
    myMap.insert(std::make_pair(2, "blueberry"));

    // Iterate over the multimap and print its contents
    for (auto itr = myMap.begin(); itr != myMap.end(); ++itr) {
        std::cout << "Key: " << itr->first << ", Value: " << itr->second << std::endl;
    }

    return 0;
}

结果：

1
2
3
4
5
Key: 1, Value: apple
Key: 1, Value: apricot
Key: 2, Value: banana
Key: 2, Value: blueberry
Key: 3, Value: cherry
for循环：for(int & num : nums)

其中nums是一个vector<int>类型的向量，这里也就是数组的意思。其中for(int & num : nums)的num可以是任意字符，只要保证后一个nums是指定的数组名即可。

迭代器遍历，对于数组来说，等同于

1
2
3
4
5
6
7
8
9
10
11
//for(int & num : nums)
for(int i=0;i<nums.length;i++){
	int num = nums[i];
}


//特别的：
//const int &num:buckets[i]中的buckets[i]指的是一个常向量，那么这里的num直接等于buckets[i]，即num=buckets[i]
for(const int &num:buckets[i]){//buckets[i]是一个常向量
	ans.push_back(num);
}
1
2
3
4
for(auto x : range) // 拷贝元素
for(auto &&x : range)// 修改元素
for(const auto &x : range)// 只读元素（无法修改）

想要拷贝元素：for(auto x:range)

想要修改元素 : for(auto &&x:range)

想要只读元素：for(const auto& x:range)

改变vector本身元素：for(auto x:vector)

不改变vector本身元素：for(bool x:vector)

参考：(77条消息) 算法笔记 C++中const和auto的那些事 HERODING的算法之路_HERODING23的博客-CSDN博客_auto const

auto类型推导

作用：使得编译器会在编译期间自动推导出变量的类型

详细参考：C++ auto（类型推导）精讲 (biancheng.net)

auto 的一些基本用法：

1
2
3
4
5
6
auto x = 5;                 // OK: x是int类型
auto pi = new auto(1);      // OK: pi被推导为int*
const auto *v = &x, u = 6;  // OK: v是const int*类型，u是const int类型
static auto y = 0.0;        // OK: y是double类型
auto int r;                 // error: auto不再表示存储类型指示符
auto s;                     // error: auto无法推导出s的类型
stack栈

详细参考：(77条消息) C++ STACK与pair的基本用法_wqw1672的博客-CSDN博客

1
2
stack<int> first ; // 构造一个存放int类型的空栈，size=0；
stack<int,vector<int>> third;          //指明用vector实现一个栈（存放int），空栈size=0

std::stack<int，std::vector<int>是C++STL中使用std::vector作为底层容器的堆栈容器。这意味着元素存储在由std::vector分配的一个连续的内存块中，堆栈操作在这个内部vector容器上执行。

pair⭐️

参考：

template<class T1,class T2> struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。功能：pair将一对值(T1和T2)组合成一个值，

1
2
3
4
5
6
7
8
9
10
pair<string, string> anon;        // 创建一个空对象anon，两个元素类型都是string
pair<string, int> word_count;     // 创建一个空对象 word_count, 两个元素类型分别是string和int类型
pair<string, vector<int> > line;  // 创建一个空对象line，两个元素类型分别是string和vector类型

/*----------------------------------------------------------------------------*/

pair.first	//获取第一个值
pair.second	//获取第二个值
    
/*----------------------------------------------------------------------------*/

stack<pair<int, int>> island：定义存储类型是pair<int, int>的栈

pair初始化操作：
1
2
3
4
5
6
7
8
//第一种
pair<int,int>hash[m];//定义一个pair类型的数组hash
//第二种
pair<T1, T2> p1(v1, v2);//创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2
//第三种
make_pair(v1, v2);// 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
//第四种

c++ sort 对pair进行排序：

默认情况下会先按照pair的first进行排序，如果first相同则会继续比较second。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

int main() {
	pair<int,int>test[3];
	int a,b;
	for(int i=0;i<3;++i){
		cin>>a>>b;
		test[i]=make_pair(a,b);
	} 
	sort(test,test+3);
	for(int i=0;i<3;++i){
		cout<<test[i].first<<" "<<test[i].second<<endl;
	}
	return 0;
}

输入数据：

1
2
3
1 2
1 1
2 1

输出：

1
2
3
1 1
1 2
2 1
stack:top() 函数

stack:top()的类型是stack

返回栈顶元素，但不在堆栈中删除它。

stack:pop() 函数

注意：stack:pop()的类型是void

返回栈顶元素，并在堆栈中删除它。

queue 容器

详细参考：C++ queue(STL queue)用法详解 (biancheng.net)

queue<pair<int, int>>points创建了存储pair类型的队列

queue 和 stack 有一些成员函数相似，但在一些情况下，工作方式有些不同：

  • front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

  • back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

  • push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。

  • push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。

  • pop()：删除 queue 中的第一个元素。

  • size()：返回 queue 中元素的个数。

  • empty()：如果 queue 中没有元素的话，返回 true。

  • emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。

  • swap(queue &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

priority_queue

priority_queue 模板有 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
29
30
31
32
33
34
35
36
37
38
//priority_queue 具体实例
priority_queue<ListNode*, vector<ListNode*>, Comp> q;

//实现大顶堆
priority_queue<int> a
//等同于 priority_queue<int, vector<int>, less<int>> a;
priority_queue<int, vector<int>, less<int>> a;

//实现小顶堆
priority_queue<int, vector<int>, greater<int>> c;

/**
* 注意queue的push操作是将元素从右边往左边加入，这意味着左边的元素比右边的元素先进入queue
*/

// std::less<T> 的底层实现代码——数组升序、大顶堆
template <typename T>
struct less {
    //定义新的排序规则
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;	//根据返回的值为true或false判断是否执行交换（为false则交换）
    }
};
/**
* 如果左边的元素比右边的大，则返回false，并执行将两个元素位置进行交换的操作，相当于是将将大元素进行上浮操作
*/
 
// std::greater<T> 的底层实现代码——数组降序、小顶堆
template <typename T>
struct greater {
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs > _rhs;	//根据返回的值为true或false判断是否执行交换（为false则交换）
    }
};
/**
* 如果左边的元素比右边的小，则返回false，并执行将两个元素位置进行交换的操作，相当于是将将大元素进行下沉操作
*/

priority_queue优先队列，我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

和队列基本操作相同:

  • top 访问队头元素

  • empty 队列是否为空

  • size 返回队列内元素个数

  • push 插入元素到队尾 (并排序)

  • emplace 原地构造一个元素并插入队列

  • pop 弹出队头元素

  • swap 交换内容

详细参考：(77条消息) c++优先队列(priority_queue)用法详解_吕白_的博客-CSDN博客_priority_queue用法

deque 容器

deque是双向列表，可在头尾进行插入和删除操作。

详细参考：C++ STL deque容器（详解版） (biancheng.net)

deque的部分成员函数：

  • front()：返回第一个元素的引用。

  • back()： 返回最后一个元素的引用。

  • push_back()：在序列的尾部添加一个元素。

  • push_front()： 在序列的头部添加一个元素。

  • pop_back()：移除容器尾部的元素。

  • pop_front()：移除容器头部的元素。

  • begin()：返回指向容器中第一个元素的迭代器。

  • end()：返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。

set 容器

set 容器存储的各个键值对，要求键 key 和值 value 必须相等

语法：

1
std::set<std::string> myset;

参考：C++ STL set容器完全攻略（超级详细） (biancheng.net)

multiset

参考：C++ multiset，STL multiset详解 (biancheng.net)

multiset 是关联容器的一种，是排序好的集合（元素已经进行了排序），并且允许有相同的元素。

不能直接修改 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 multiset 容器中某个元素的值，正确的做法是先删除该元素，再插入新元素。

类模板的定义如下：

1
2
3
template <class Key, class Pred = less<Key>, class B = allocator<Key> > class multiset {
    ...
};

该模板有三个类型参数：Key、Pred 和 B。类型参数可以有默认值，默认值就是某种类型。例如，Pred 类型参数的默认值就是 less 类型，B 的默认值就是 allocator 类型。

第一个类型参数说明 multiset 容器中的每个元素都是 Key 类型的。第二个类型参数 Pred 用于指明容器中元素的排序规则，在被实例化后，Pred 可以是函数对象类，也可以是函数指针类型。

less的类模板定义：

1
2
3
4
5
6
template <class_Tp>
struct less
{
    bool operator() (const _Tp &__x, const _Tp &__y) const
    { return __x < __y; }
};

unordered_set 容器

unordered_set 容器，可直译为“无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。

部分成员函数：

  • insert()： 向容器中添加新元素。

  • erase()： 删除指定元素。

  • empty()： 若容器为空，则返回 true；否则 false。

  • begin()：返回指向容器中第一个元素的正向迭代器。

  • end()：返回指向容器中最后一个元素之后位置的正向迭代器。

  • count(key)：在容器中查找值为 key 的元素的个数。

部分拷贝，可以使用 unordered_set 类模板提供的迭代器。例如：

1
2
//传入 2 个迭代器，
std::unordered_set<std::string> uset2(++uset.begin(),uset.end());

通过此方式创建的 uset2 容器，其内部就包含 uset 容器中除第 1 个元素外的所有其它元素。

参考：C++ STL unordered_set容器完全攻略 (biancheng.net)

substr() 函数

substr(size_type _Off = 0,size_type _Count = npos)

  • size_type _Off：起始位置

  • size_type _Count：字符数目

参考：[(77条消息) Cstring类中substr()函数的使用方法_&Mr.Gong的博客-CSDN博客_c string substr](https://blog.csdn.net/weixin_42258743/article/details/107782394#:~:text=substr（）定义. substr,()是C%2B%2B语言函数，主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。. 如果没有指定长度_Count或_Count%2B_Off超出了源字符串的长度，则子字符串将延续到源字符串的结尾。.)

stoi() 函数

stoi（字符串，起始位置，n进制），将 n 进制的字符串转化为十进制

参考：(77条消息) C++中stoi函数_weixin_30502965的博客-CSDN博客

istringstream

istringstream：实现类用于执行C++风格的串流的输入操作。

参考：(77条消息) C++中的istringstream 的用法_longzaitianya1989的博客-CSDN博客_istringstream

string

参考：C++ string详解，C++字符串详解 (biancheng.net)

compare 函数

类 basic_string 的成员函数 compare() 的原型如下：

int compare (const basic_string& s) const;
int compare (const Ch* p) const;
int compare (size_type pos, size_type n, const basic_string& s) const;
int compare (size_type pos, size_type n, const basic_string& s,size_type pos2, size_type n2) const;
int compare (size_type pos, size_type n, const Ch* p, size_type = npos) const;

若参与比较的两个串值相同，则函数返回 0；若字符串 S 按字典顺序要先于 S2，则返回负值；反之，则返回正值。

算术右移

在汇编语言中，对于算术右移(高位补符号位)，如果最高位为1，则补1，否则补0， 如将10000000算术右移7位，应该变成11111111；

逻辑右移

对于逻辑右移7位，则不考虑符号位，变为00000001，这点就是算术右移和逻辑右移的区别。

算术左移

对于算术左移，在右边补0：比如 00101011算术左移一位:01010110

逻辑左移

对于逻辑左移，同样是在右边补0，如：00010111逻辑左移两位：01011100

⭕️左移一般将低位补0。但右移可以是逻辑右移（高位补0）或算术右移（高位补符号位）。

将一个值左移N位相当于乘以2N。同理，算术右移N位，相当于除以2N。\textcolor{red}{将一个值左移N位相当于乘以2^N。同理，算术右移N位，相当于除以2^N。}

isdigit() 函数

C 库函数int isdigit(int c)检查所传的字符是否是十进制数字字符。

十进制数字是：0 1 2 3 4 5 6 7 8 9

语法：

1
int isdigit(int c);

如果 c 是一个数字，则该函数返回非零值，否则返回 0。

accumulate()

参考：(77条消息) C中accumulate的用法_CV矿工的博客-CSDN博客_accumulate c

accumulate定义在#include中，作用有两个，一个是累加求和，另一个是自定义类型数据的处理。

int sum = accumulate(vec.begin() , vec.end() , 42);

accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

除此之外，accumulate还有第四个参数：一个回调函数来实现自定义数据的处理

如：int sum = accumulate(subject, subject + 3, 0, [](int a, Grade b){return a + b.grade; });

1
2
3
int sum = accumulate(vec.begin() , vec.end() , 42);

int sum = accumulate(subject, subject + 3, 0, [](int a, Grade b){return a + b.grade; });
lower_bound() 函数

参考：C++ lower_bound()函数用法详解 (biancheng.net)

lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。

返回值：返回一个迭代器

基本形式：

1
2
3
4
5
6
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

lower_bound() 返回值是一个迭代器,返回指向大于等于key的第一个值的位置

1
2
3
4
number[8]={4,10,11,30,69,70,96,100}.设要插入数字3,9,111. pos为要插入的位置的下标，则
pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。
pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。

实例：

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
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i,int j) { return i>j; }

//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i>j;
    }
};

int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个不小于 3 的元素
    int *p = lower_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;

    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(),3,mycomp2());	// mycomp2(element, 3),当mycomp2返回为true时即表示当前满足comp结果，所以此时lower_bound将会返回值
    cout << "*iter = " << *iter;
    return 0;
}

/**
*	输出结果：
*  		*p = 3
*  		*iter = 3
*/
lower_bound()如何只对pair的first进行查询

参考：c++ - How to use lower_bound() on set of pairs? - Stack Overflow

lower_bound()可以自定义comp函数。

1
2
3
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

示例：

1
2
// mycomp2(3, element),当mycomp2返回为true时即表示当前满足comp结果，所以此时lower_bound将会返回值

upper_bound() 函数

参考：C++ upper_bound()函数（精讲版） (biancheng.net)

用于在指定范围内查找大于目标值的第一个元素。

基本形式：

1
2
3
4
5
6
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

其它与lower_bound()函数相似

值得注意的是：

由于 upper_bound() 底层实现采用的是二分查找的方式，因此该函数仅适用于“已排好序”的序列。注意，这里所说的“已排好序”，并不要求数据完全按照某个排序规则进行升序或降序排序，而仅仅要求 [first, last) 区域内所有令 element<val（或者 comp(val, element）成立的元素都位于不成立元素的前面（其中 element 为指定范围内的元素）。

count() 函数

C++ 函数 std::algorithm::count() 返回值在范围内的出现次数。 该函数使用 operator == 进行比较。

参数：

  • first − 将迭代器输入到搜索序列的初始位置。

  • last − 将迭代器输入到搜索序列的最终位置。

  • val − 要在范围内搜索的值。

实例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
   vector<int> v = {1, 3, 3, 3, 3};
   int cnt;

   cnt = count(v.begin(), v.end(), 3);

   cout << "Number 3 occurs " << cnt << " times." << endl;

   return 0;
}

输出形式：

1
Number 3 occurs 4 times.
to_string() 函数

功能：将数字常量转换为字符串

reverse函数

实现翻转数组、字符串和向量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//翻转字符串
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string str = "abcdefg";
    //1 显示未翻转的字符串
    cout << str << endl;
    //2 翻转数组，然后显示
    reverse(str.begin(), str.end());
    cout << str << endl;


    return 0;
}
1
2
3
//结果
abcdefg
gfedcba
fmod(double x, double y)

C 库函数 double fmod(double x, double y)返回 x 除以 y 的余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <math.h>

int main ()
{
   float a, b;
   int c;
   a = 9.2;
   b = 3.7;
   c = 2;
   printf("%f / %d 的余数是 %lf\n", a, c, fmod(a,c));
   printf("%f / %f 的余数是 %lf\n", a, b, fmod(a,b));
   
   return(0);
}
1
2
9.200000 / 2 的余数是 1.200000
9.200000 / 3.700000 的余数是 1.800000
log10(double x)

C 库函数 double log10(double x) 返回 x 的常用对数（基数为 10 的对数）。

log(double x)

C 库函数 double log(double x) 返回 x 的自然对数（基数为 e 的对数）。

左/右值以及引用

可见立即数，函数返回的值等都是右值；而非匿名对象(包括变量)，函数返回的引用，const对象等都是左值。

  • 可以取地址的，有名字的，非临时的就是左值；

  • 不能取地址的，没有名字的，临时的就是右值；

左值引用

左值引用要求右边的值必须能够取地址，如果无法取地址，可以用常引用；但使用常引用后，我们只能通过引用来读取数据，无法去修改数据，因为其被const修饰成常量引用了。

1
2
3
4
5
6
7
8
//左值引用
int a = 10;
int &b = a;  // 定义一个左值引用变量，必须在定义时初始化
b = 20;      // 通过左值引用修改引用内存的值

//常引用
const int temp = 10; 
const int &var = temp;
右值引用
1
2
3
类型 && 引用名 = 右值表达式;

int &&var = 10;
std::move

可以参考：C++右值引用（std::move） - 知乎 (zhihu.com)

  • std::move并不能移动任何东西，它唯一的功能是将一个左值强制转化为右值引用，继而可以通过右值引用使用该值，以用于移动语义。从实现上讲，std::move基本等同于一个类型转换：static_cast<T&&>(lvalue);

  • C++ 标准库使用比如vector::push_back 等这类函数时,会对参数的对象进行复制,连数据也会复制.这就会造成对象内存的额外创建, 本来原意是想把参数push_back进去就行了,通过std::move，可以避免不必要的拷贝操作。

  • std::move是为性能而生。

  • std::move是将对象的状态或者所有权从一个对象转移到另一个对象，只是转移，没有内存的搬迁或者内存拷贝。

用法：原lvalue值被moved from之后值被转移,所以为空字符串.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <utility>
#include <vector>
#include <string>
int main()
{
    std::string str = "Hello";
    std::vector<std::string> v;
    //调用常规的拷贝构造函数，新建字符数组，拷贝数据
    v.push_back(str);
    std::cout << "After copy, str is \"" << str << "\"\n";
    //调用移动构造函数，掏空str，掏空后，最好不要使用str
    v.push_back(std::move(str));
    std::cout << "After move, str is \"" << str << "\"\n";
    std::cout << "The contents of the vector are \"" << v[0]
                                         << "\", \"" << v[1] << "\"\n";
}

输出：

1
2
3
After copy, str is "Hello"
After move, str is ""
The contents of the vector are "Hello", "Hello"

前缀和

概念：

img

partial_sum()

对范围[first,last)内的元素逐个求累加和，放在result容器中。

函数签名如下：

1
2
3
4
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first, 
                            InputIterator last,
                            OutputIterator result);

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <numeric>


int main(int argc, char **argv) 
{  
    std::vector<int> nums = { 1,2,3,4,5 };

    std::vector<int> psum;
    psum.resize(nums.size());
    //将前缀和的结果保存在以psum.begin()开始的psum中
    partial_sum(nums.begin(), nums.end(), psum.begin());
	//输出
    for (int num : psum) {
        std::cout << num << "\t";
    }

    return 0;
}

输出：

1
1       3       6       10      15

积分图

相当于前缀和的二维拓展

定义：图像是由一系列的离散像素点组成, 因此图像的积分其实就是求和. 图像积分图中每个点的值是原图像中该点左上角的所有像素值之和.

首先建立一个数组 A 作为积分图像，其宽高与原图像相等. 然后对这个数组赋值，每个点存储的是该点与图像原点所构成的矩形中所有像素的和：

image-20221028101723619

数据类型：

1️⃣有符号类型

使用以下名称可以保证固定长度：

  • 1字节 int8_t —— char

  • 2字节 int16_t —— short

  • 4字节 int32_t —— int

  • 8字节 int64_t —— long long

2️⃣无符号类型

uint32_t,size_t, uint64_t

数据类型转换：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
String S;
s[0]-'0'
//表示将字符s[0]的ASCII码与字符'0'的ASCII码相减，
//如果s[0]是字符0~9，则表示将该字符变为对应的数字（int 型）
    
/**
*将数字转换为对应字母
*/
//方式一
string ans='A'+1;//output:B
string ans='A'+2;//output:C
string ans='A'+3;//output:D

//方式二
//ASCII:65-A...
//ASCII (American Standard Code for Information Interchange)
string ans=char(65+1);//output:B
string ans=char(65+2);//output:C
...
    
//方式三
s+=to_string(13);

参数列表

定义：以一个冒号（：）开始，接着是一个以逗号分隔（,）的数据成员列表，每个"成员变量"后面跟一个放在括号中的初始值或表达式。

1
2
3
4
5
6
7
class Date{
public:
	Date(int year = 1900, int month = 1, int day = 1):
    _year(year),
    _month(month),
    _day(day){}				//参数列表
}

C++ 什么时候用 “.” 什么时候用“->”

假设有一个类: ClassA
1、如果声明的是一个对象: ClassA A
则用 A.function
2、如果声明的是一个对象指针：ClassA* A=new A;则用 A->function

从堆栈的角度来说：
对象放在堆上，就要用指针，也就是对象指针->函数；放在栈上,就对象.函数

构造函数与析构函数

构造函数调用顺序：

  1. 基类构造函数

  2. 对象成员构造函数

  3. 派生类本身的构造函数

析构函数调用顺序：

  1. 派生类本身的析构函数

  2. 对象成员析构函数

  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
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
// 基类
class B {
public:
  B() { cout << "B0::B()" << endl; }
  B(int a) { cout << "B1::B()" <<" "<< "a=" << a << endl; }
  B(const B& b) {cout << "B2::B()" << endl;} // 拷贝构造
  ~B() { cout << "~B()" << endl; }
};
// 派生类
class D :public B {
public:
  D() { cout << "D0::D()" << endl; }
  D(int a) { cout << "D1::D()" <<" "<< "a=" << a << endl; }
  ~D() { cout << "~D()" << endl; }
};

/*--------------------------------main函数-----------------------------------*/
int main() {
  B b;
  return 0;
}
// 先构造再析构
// B0::B()
// ~B()

/*--------------------------------main函数-----------------------------------*/
int main() {
  D d;
  return 0;
}
// 基类构造-子类构造-子类析构-基类析构
// B0::B()
// D0::D()
// ~D()
// ~B()

实例2：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
using namespace std;
class O{
public:
	O(){
		cout << "Constructor O" << endl;
	}
	~O(){
		cout << "Deconstructof O" << endl;
	}
};

class A:O{
public:
	A(){
		cout << "Constructor A" << endl;
	}
	~A(){
		cout << "Deconstructof A" << endl;
	}
};

class B{
public:
	B(){
		cout << "Constructor B" << endl;
	}
	~B(){
		cout << "Deconstructof B" << endl;
	}
};

class C{
public:
	C(){
		cout << "Constructor C" << endl;
	}
	~C(){
		cout << "Deconstructof C" << endl;
	}
};

class D{
public:
	D(){
		cout << "Constructor D" << endl;
	}
	~D(){
		cout << "Deconstructof D" << endl;
	}
};

class E{
public:
	E(){
		cout << "Constructor E" << endl;
	}
	~E(){
		cout << "Deconstructof E" << endl;
	}
};

class Test : E,D{
	B b;
	A a;
public:
	Test(){
		cout << "Constructor Test" << endl;
	}
	~Test(){
		cout << "Deconstructor Test" << endl;
	}
};

/*--------------------------------main函数-----------------------------------*/
int main(){
	Test *t = new Test;
	delete t;
	system("pause");
	return 0;
}
/*结果*/
Constructor E
Constructor D
Constructor B
Constructor O
Constructor A
Constructor Test
Deconstructor Test
Deconstructof A
Deconstructof O
Deconstructof B
Deconstructof D
Deconstructof E

数学算法

向量的内积和叉乘

内积

image-20230312000752499

image-20230312000632698

叉乘

image-20230312000739739

image-20230312000659502

欧几里得算法

gcd(a,b) = gcd(b,a mod b)

形象记忆：

1
2
3
4
5
6
a % b = c
	b % c = d
		c % d = e
			d % e = f
				......

欧几里得算法拓展：

参考：(77条消息) 扩展欧几里得算法超详解_Aloof__的博客-CSDN博客_扩展欧几里得原理

给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)

image-20221011195717705 
1
2
3
4
1=(-7)*47+(11)*30


gcd(a,b)可以表示为a,b的整洗数线性组合，例如：gcd(6,14)=2,而2=(-2)*6+1*14.

绝对值函数abs()

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include<cmath>//C语言是math.h
 
using namespace std;
void main(void)
{
	int a=1,b=10;
	float c=1,d=10;
	double e=1,f=10;
 
	cout<<"b-a="<<abs(b-a)<<endl;
	cout<<"c-d="<<abs(c-d)<<endl;
	cout<<"e-f="<<abs(e-f)<<endl;
	cin.get();
}

//输出：
b-a=9
c-d=9
e-f=9

C++实现四舍五入的几种方法

参考：(101条消息) C实现四舍五入的几种方法_c四舍五入_Xaiver_97的博客-CSDN博客

  1. 函数round()实现四舍五入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
  double a = 1.4999999;
  double b = 1.5000001;
  double n_a = -1.4999999;    
  double n_b = -1.5000001; 
  cout << round(a) << endl;    // 1
  cout << round(b) << endl;    // 2
  cout << round(n_a) << endl;    // -1
  cout << round(n_b) << endl;    // -2
  return 0;
}

round()函数原理为：x=(int)(x+0.5)公式，故可以自己写出round()函数：

1
2
3
4
5
6
#include<stdio.h>

double round(double x)
{
	return (int)(x+0.5);
}

Fisher-Yates 洗牌算法

可以参考：Fisher-Yates洗牌算法！来自算法理论的创始人！ - 知乎 (zhihu.com)

正向洗牌与反向洗牌算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> shuffle() {
    if (origin.empty()) return {};
    vector<int> shuffled(origin);
    int n = origin.size();
// 可以使用反向或者正向洗牌，效果相同。
// 反向洗牌：
    for (int i = n - 1; i >= 0; --i) {
        swap(shuffled[i], shuffled[rand() % (i + 1)]);
    }
// 正向洗牌：
// for (int i = 0; i < n; ++i) {
// int pos = rand() % (n - i);
// swap(shuffled[i], shuffled[i+pos]);
// }
	return shuffled;
}

Knuth-Morris-Pratt（KMP）算法

参考：KMP算法 - 维基百科，自由的百科全书 (wikipedia.org)

C++位运算及其应用

C++ 异或运算及其应用

前置知识：

1.一个整数自己跟自己异或，结果为0。//因为异或的法则为，相同为0，不同为1，注意这里所说的都是二进制位。

2.任意一个整数跟0异或，结果为本身。//因为1异或0得1,0异或0,得0，所以1还是1,0还是0，没发生变化。

img

通过异或运算不用临时变量的情况下进行两个变量的值交换。

示例：

1

C/C++算法

排序算法

参考：1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)

快速排序

  1. 在数组中选一个基准数（通常为数组第一个）。

  2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边

  3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信