循环

for#

当需要执行某些操作多次时

	for (int i = 0; i < 5; i = i + 1) {
		Log("Hello World");
	}

1. 先创建变量i(为零)
2. 然后检查i<5，是的话执行下面代码块(否则退出)
3. 然后i=i+1
4. 然后再检查i<5，是的话执行下面代码块(否则退出)
5. 3->4->3->4 反复循环直到退出

i的作用域仅限于for代码块

上述代码也可改为

	int i = 0;
	for (; i < 5; ) {
		Log("Hello World");
		i = i + 1;
	}

或者

	int i = 0;
	bool condition = true;
	for (; condition; ) {
		Log("Hello World");
		i = i + 1;
		if (!(i < 5))
			condition = false;
	}

死循环

for(;;)
{
	
}

while#

基本上可以和for语句互转。但是如果有已经存在的条件，优先使用while

	int i = 0;
	while (i < 5) {
		Log("Hello World");
		i++;
	}

do while#

//执行前先判断
bool condition = false;
while (condition)
{

}

//至少执行一次
do
{

} while (condition);

控制流#

continue，break（如果有多重循环，不会影响到外部的循环）

vs用于c++项目的最佳实践

创建新项目#

解决方案下有项目

MySolusion.sln是解决方案文件

项目下是源代码

Project.vcxproj 是项目相关文件 Project.vcxproj.filters 是过滤器

过滤器决定了vs IDE打开该项目时的视图(实际中不存在文件夹)

显示所有文件#

显示磁盘目录下的所有文件

移动文件位置

#include <iostream>
int main() {
	std::cout << "Hello World!" << std::endl;
	std::cin.get();
}

如图，中间文件(.obj)是放在项目文件夹里

项目编译后生成的可执行文件放在解决方案文件夹下

由来

$(Platform)\$(Configuration)\，即 x64\Debug 文件夹结构的由来

修改配置#

OutputDirectory: $(SolutionDir)bin\$(Platform)\$(Configuration)\

如果解决方案有多个项目，如果构建DLL文件或者其他需要的东西，我们需要这些在同一个文件夹中（而不用深入每个项目的文件夹）

IntermediateDirectory: $(SolutionDir)bin\intermediates\$(Platform)\$(Configuration)\

之后右键项目-clean Solution

查看变量值

清理项目#

解决方案下有一个项目

项目下有过滤器及src文件夹

条件及分支

• 先检查一个条件，然后跳转到不同的部分并开始执行指令，意味着条件及分支都有会一点开销。如果想编写稍微快点的代码就不该使用条件语句
• 如果某事是真的，那么跳转到对应的代码块执行

查看汇编#

• mov dword ptr [x],6意思是在内存中名为 x 的位置，写入4个字节的数值 00000006（十六进制）

  • mov:移动
  • cmp 比较
  • jne:是否为零

• 不相等则跳转
  

• 并且将某个位置（代表变量comparisionResult设置为0）

• 其中，dword ptr [rbp+0F4h],0 表示 将0存储到内存地址rbp+0xF4处的4字节空间（双字）中 ，rbp通常指基指针寄存器（Base Pointer Register），通常是栈帧的基地址

• test基本是执行按位与运算
  

  补充：test eax, eax 不会改变 eax 的值，只是临时计算 eax AND eax，然后丢弃结果，唯一目的：设置CPU的标志位 为什么要自己和自己AND？因为 eax AND eax 的结果就是 eax 本身：如果 eax = 0 → 结果是 0 → ZF=1；如果 eax ≠ 0 → 结果非零 → ZF=0；如果 eax < 0（最高位为1） → SF=1

以上都是在Debug模式下看的，所以并没有优化代码，其实comparisionResult的值在编译前就已经知晓

如何调试代码

• 断点
• 读取内存

1. 光标放到要调试的行，然后鼠标移动到最前面点一下/或者按F9，即可在该行插入断点

2. 确保是Debug模式，而且点击LocalWindowsDebugger
   

3. 调试中
   橘黄色指向指令指针目前的位置 stepInto(F11):进入目前行所在函数

   stepOver(F10):继续执行到下一行

   stepOut(shift+F11)：跳出当前函数

此时按F11进入函数(这里和视频不太一样，黄色箭头在左括号处是读不到数值的)

再按一次F10执行到第一行代码前才行

再按一次F10

再按一次F10就继续执行（这里会跳出Log函数）

按F5会继续执行，直到下一个断点

调试#

#include "iostream"
#include "Log.h" 


int main() {
	//InitLog();
	int a = 8;
	a++;
	const char* string = "Hello";
	for (int i = 0; i < 5; i++) {
		const char c = string[i];
		std::cout << c << std::endl;
	}
	Log("hello world!");
	//std::cin.get();
	std::cin.get();
}

箭头在此处，表示改行代码即将执行（未执行），所以此时a为任意可能值(未初始化的内存)

Autos(ide认为比较重要的)，Locals(本地变量)，Watch1(自己添加的监视器)

• 显示所有的程序内存

• 左边是内存地址，右边是实际数据

• Memory中查看变量值(这里1个int变量占用4个字节)

变量#

• 编程实际上就是在操纵数据
• 变量允许我们命名一个我们存储在内存中的数据
• 我们创建的变量存储在堆栈或堆中
• 原始数据是构成任何种类的基石
• 不同的变量类型，唯一的区别，是存储他们需要多少内存(原始数据类型有多大)

整数#

#include <iostream>

int main() {

	int variable = 8;
	std::cout << variable << std::endl;
	variable = 20;
	std::cout << variable << std::endl;
	std::cin.get();
}

• int变量通常上是4字节，取决于编译器
• 可以不用立即赋值
• 大概在-20亿~+20亿之间
• 4字节是32位，int是有符号的，第32位存储符号位。还剩下31位存储数据。2^31=21 4748 3648 。
  • 最大正数：2^31-1=21 4748 3647
  • 最小负数：-(2^31)=21 4748 3648
  • 为什么负数多一个，因为多了一个"-0"但计算机中没有-0的概念，二进制10000000 00000000 00000000 00000000 代表-(2^31)
• unsint 表示无符号整数，能用上所有的位，即最大整数是(2^32) -1
• 其他：char 1字节，short 2字节，int 4字节，long 通常4字节，long long 通常8字节 由于32位系统最大是4字节，所以long也是4字节。后来出了64位系统，64位windows系统中long是4字节，64位Linux/macOS中long是8字节 可以给任何一个前面加unsigned表示无符号

	char cVariable = 'A';
	//char cVariable=65;
	//不管是用65还是'A'赋值，打印出来的都是A
	std::cout << cVariable << std::endl;
	
	
	short sVariable = 'A';
	//short cVariable=65;
	//不管是用65还是'A'赋值，打印出来的都是65
	std::cout << sVariable << std::endl;

小数#

	float fVariable = 8.2f;//4字节
	std::cout << fVariable << std::endl;
	double dVariable = 20.3;//8字节
	std::cout << dVariable << std::endl;

布尔值#

布尔类型只占用1个字节（只需要1位，但我们在处理内存寻址时，即我们要从那里取回我们的值时，或者将它存储在内存体重时，没有办法只处理个别位，所以只能按字节取）

07链接器

介绍#

编译器将C++ 源文件编译成.obj目标文件后，需要进行链接：找到每个符号和函数的位置并将它们链接在一起，在这之前每个文件都已经被编译成了一个单独的目标文件作为翻译单元，它们彼此之间没有任何联系

Ctrl+F7只会编译文件，不会将文件链接；build项目会链接文件。

#include <iostream>
const char* Log(const char* message) {
	return message;
}

int Multiply(int a,int b ) { 

	Log("Multiply");
	return  a * b;
}

编译实际上分为编译和链接两个阶段。如果上面代码去掉一个分号，则出现错误

1>E:\cppStudyTemp\ChernoCpp\HelloWorld01\HelloWorld01\Math.cpp(10,1): error 
C2143: syntax error: missing ';' before '}' 
1>Done building project "HelloWorld01.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
========== Build completed at 17:51 and took 05.115 seconds ==========

这里C2143，C开头表示是编译阶段的错误

补上后将整个项目build构建后，出现另一个错误：

1>MSVCRTD.lib(exe_main.obj) : error LNK2019: unresolved external symbol main referenced in function "int __cdecl invoke_main(void)" (?invoke_main@@YAHXZ)
1>E:\cppStudyTemp\ChernoCpp\HelloWorld01\x64\Debug\HelloWorld01.exe : fatal error LNK1120: 1 unresolved externals
1>Done building project "HelloWorld01.vcxproj" -- FAILED.

这里出现LNK1120，LNK开头表示链接阶段出现错误

编译器的工作原理

介绍#

源文件 编译–> .obj文件 链接–> .exe可执行文件

• 预处理(包括标记) –> 创建一棵抽象语法树(将所有代码转换为常量数据或指令) –> 创建代码(CPU将执行的实际机器码)
• 编译器：为每个C++文件（先经过预处理成为翻译单元）生成目标文件
• 文件只是C++向编译器提供源代码的方式（并不需要像java那样文件名必须和类名等同）
• 将.cpp当做C++文件，把.c当做C文件，把.h当做头文件。(默认，也可以改变这个默认约定)
• C++文件先经过预处理后成为翻译单元，之后编译器将翻译单元生成为一个目标文件，有时将CPP文件包含在其他CPP文件中并创建一个包含大量文件的大CPP文件。这种情况下只需要编译这个大的CPP文件并生成一个翻译单元，从而生成一个目标文件

hash include#

//Math.cpp
int Multiply(int a, int b) {
	int result = a * b;
	return result;
}

并编译

再添加一个文件EndBrace.h

}

修改Math.cpp，修改前删除结束括号，会编译出错，之后修改为：

//Math.cpp
int Multiply(int a, int b) {
	int result = a * b;
	return result;
#include "EndBrace.h"

编译成功

告诉编译器输出一个包含所有结果的文件#

简单例子#

修改配置

这个选项会导致不会生成obj文件

Math.i

#line 1 "E:\\cppStudyTemp\\ChernoCpp\\HelloWorld\\HelloWorld\\Math.cpp"
int Multiply(int a, int b) {
	int result = a * b;
	return result;
#line 1 "E:\\cppStudyTemp\\ChernoCpp\\HelloWorld\\HelloWorld\\EndBrace.h"
}
#line 5 "E:\\cppStudyTemp\\ChernoCpp\\HelloWorld\\HelloWorld\\Math.cpp"

例子增强#

#define INTEGER int

INTEGER Multiply(int a, int b) {
	INTEGER result = a * b;
	return result;
}

Math.i

C++是如何工作的

源代码 –> 程序启动文件

多个源文件 (编译器)–> 二进制(可执行)文件

分析源码#

/*试着编译单个cpp文件 ctrl+f7
会生成Main.obj文件*/

/*/①（编译器处理）include是预处理指令，会在编
译前找到iostream这个文件并插入该文件内容*/
#include <iostream>


/*②.h文件是在预编译时被处理（插入），并不会被编译；只有
.cpp文件会被编译成 .obj文件，链接器把这些合并成 .exe文件*/

/*③声明，确实有Log函数存在*/
/*④链接器，编译整个项目时，链接器链接时才会去查找这个
函数是否真是存在,如果不存在，则会提示"unresolved external
symbol"：未解析的外部符号，链接器无法找到定义
---链接器的工作是将函数体链接到其标识符(名称)
*/
//参数名message可以省略
//void Log(const char* message);


int main() {
	// << 重载运算符, 运算符可以理解成函数
	//类似下面这句：
	// std::cout.print("hello world!").print(std:endl);//!!编译无法通过
	
	std::cout << "hello world!" << std::endl;
	
	//Log("helloworld!");
	
	//等待按下回车键来移动到程序的下一行
	std::cin.get();
	//可以不写return，默认返回0，表示正确返回程序
}

编译#

项目配置：Debug/Release

平台配置：x64(windows64位系统),x86(windows32位系统)，android….

项目属性#

Release的时候，Optimization这里都是Maximize（最佳优化）

按钮添加#

WelcomeToCpp#

• 使用c++可以控制CPU应该执行的每条指令
• C++的代码编译后可以在任何平台运行，前提是有一个为对应平台生成机器代码的编译器
• 与C++不同，C#或JAVA，他们在虚拟机中运行，运行时将代码从“中间语言”转换为机器代码
• 学习新事物的关键就是对事物进行实验
• 将讨论如何利用C++库
• C++实际上如何工作
• 关于内存和指针：内存区域，智能指针，移动语义，模板
• 宏，以及为多个平台编程
• 编写自己的数据结构，学习如何使他们比C++标准库中的结构更快
• 低级优化，与编译器和汇编相关

设置C++#

windows平台#

1. 需要文本编辑器，将C++代码编写为文本文件，传递给编译器以生成某种可执行二进制文件，以便可以运行

2. 或者跳过1，直接用IDE，即有一套帮助你编写和调试代码的工具。（Visual Studio，视频用的2017，我这里下载的 Visual Studio Community 2022）

3. 安装勾选：
   

4. 新建项目
   
   不要勾选 Place solution and project in the same directory

   解决方案，solution，是一组相互关联的项目，他们有各种项目类型，解决方案就像工作台，每个项目本质上是一组文件，会编译成目标二进制文件（无论是库还是实际的可执行文件）

5. 添加新项
   

6. 代码文件(Main.cpp)

#include <iostream>
int main() {
	std::cout << "hello world!" << std::endl;
	std::cin.get();
}

配置文件修改#

下载ChernoVS.vssettings文件，并放到下面的位置
C:\Users\ly\AppData\Local\Microsoft\VisualStudio\17.0_f89cedea\Settings

在vs工具栏中-tools-ImportAndExportSettings-

ImportSelectedEnvironmentSettings

选择no,just Import new，选择 ChernoVS.vssetings即可

运行#

1. 右键，构建（项目）
   
   
   文件系统查看：

   

2. 双击.exe文件，结果：

   
   按任意键终止

或者单机本地的Windows调试器来运行它

C++ 标准模板库 (STL, Standard Template Library)：包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).

示例：

• 算法：sort(a.begin(), a.end())
• 容器：priority_queue<int> pque
• 仿函数：greater<int>()
• 迭代器：vector<int>::iterator it = a.begin()

1 前言#

STL 作为一个封装良好，性能合格的 C++ 标准库，在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间，这一点不仅是由于可以直接调用，还是因为它封装良好，可以让代码的可读性变高，解题思路更清晰，调试过程 往往 更顺利。

不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能，它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此，STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此，在实际比赛中要权衡 STL 的利弊，不过这一点就得靠经验了。

接下来，我会分享在算法竞赛中常用的 STL 容器和算法，对于函数和迭代器，就不着重展开讲了。

2 常用容器#

2.1 内容总览#

打勾的是本次将会详细讲解的，加粗的是算法竞赛中有必要学习的。

• 顺序容器

  • array

  • vector

  • deque

  • forward_list

  • list

• 关联容器

  • set
  • map
  • multiset
  • multimap

• 无序关联容器

  • unordered_set
  • unordered_map
  • unordered_multiset
  • unordered_multimap

• 容器适配器