Programming¶

2023年10月13日
分类于 Programming
需要 14 分钟阅读时间

C Program Compile Problems

TODO:[5] please fix all in free time 重复了和另一篇

2023年10月10日
分类于 Programming
需要 1 分钟阅读时间

C++ ABI

摘要

ABI被人熟知，就是编译时，接口不匹配导致运行时的动态库undefined symbol报错。

2023年10月9日
分类于 Programming
需要 9 分钟阅读时间

[C++ Basic] Grammar

概要

C++ 基础知识和语法,包括C++11，C++17,C++23的各种语言支持。

C++编程语言历史和设计思路

在纷繁多变的世界里茁壮成长：C++ 2006–2020

C 与 C++、java 的区别

支持范式模板编程 (generic programming)

模板代码（增加泛型编程能力，类似python），
泛型编程是一种以通用性为中心的编程范式。在泛型编程中，程序通过使用参数化类型（或称为模板）来实现数据类型无关的算法和数据结构
强⼤的 Standard Template Library (STL) 标准库，也是基于泛型编程的产物。
包括：容器、迭代器、算法和函数对象四类
元编程（e.g., constexpr ）编译时推导出变量是否为固定常数。
一些语法和关键字，增加了 new 和 delete，auto

支持面向对象编程 (object-oriented programming) 的拓展

类和对象：C++允许定义类和创建对象。类是一种用户自定义的数据类型，可以包含成员变量和成员函数。对象是类的一个实例，可以通过类来创建多个对象。C语言中没有类和对象的概念，只能使用结构体和函数来组织数据和行为。
封装：C++支持封装，可以将数据和相关的操作封装在一个类中，并使用访问修饰符来控制对类成员的访问权限。C语言没有封装的概念，所有的数据和函数都是公开的。
继承：C++支持继承，允许创建派生类从基类继承属性和行为。继承可以实现代码重用和类的层次化。C语言没有继承的概念。
多态：C++支持多态，允许通过基类指针或引用来调用派生类的虚函数，实现动态绑定和运行时多态性。C语言没有多态的概念。
异常处理：C++提供异常处理机制，可以通过抛出和捕获异常来处理程序中的错误和异常情况。C语言没有内置的异常处理机制。

C++ 与 java 的区别

内存管理：C++中的内存管理是手动的，程序员需要显式地分配和释放内存。C++提供了new和delete关键字来进行动态内存分配和释放。Java中的内存管理是自动的，使用垃圾回收机制来自动管理内存，程序员不需要手动释放内存。
指针：C++支持指针操作，允许直接访问和修改内存地址。Java中没有指针的概念，所有的数据访问都是通过引用进行的。
运行环境：C++是一种编译型语言，源代码在编译后被转换为机器码，并直接在操作系统上运行。Java是一种解释型语言，源代码在编译后生成字节码，然后由Java虚拟机（JVM）解释执行。
平台依赖性：C++代码在不同的平台上需要重新编译，因为它直接与底层系统交互。Java代码是平台无关的，一次编译的字节码可以在任何支持Java虚拟机的平台上运行。
C++更适合系统级编程、游戏开发等需要更高的性能和底层控制的场景。
Java更适合企业级应用开发、网络编程等需要跨平台和可移植性的场景。

基础知识与坑

程序执行入口

The default program entry function is main, but can be changed in two situations:

use stupid #define xxx main in header file to replace the name which maybe ignored by silly search bar in VSCODE.
use -exxx compile flag

语句末尾的分号

在 C++ 中，是否需要在语句的末尾使用分号（;）取决于上下文。
C++ 语法的基本规则是：分号用来标识一条语句的结束，而有些结构并不是严格的语句，因此不需要分号。
声明（变量、类、结构体、枚举、函数原型、类型别名）：都需要分号作为结束。
函数定义、控制语句（如 if, while, for）、复合语句（{}）不需要分号。
预处理指令（如 #define, #include）：不需要分号，因为它们不是 C++ 语法层面的内容。
作用域结束的 } 不需要分号，但声明类或结构体时 } 后要加分号。

为什么类/结构体需要分号

C++ 中的类和结构体定义实际上是一种声明，它们的定义是一种复杂的声明语句，因此必须用分号来结束它们。

总结来说，分号用来结束语句，包括声明、表达式和执行体等，但当你定义一个复合结构（如函数定义、控制语句）时，不需要分号来结束复合结构的定义。

重名变量的优先级

int getKthAncestor(int node, int k) {
    int node= getKthAncestor(saved[node],--k);  
    return node;
}
 //为什么第二行的node会提前被修改为0，导致传入函数getKthAncestor的saved[node]的node值为0
 //如下去掉int，也不会错。因为int node 会初始化node为0
 int getKthAncestor(int node, int k) {
    node= getKthAncestor(saved[node],--k);  
    return node;
}

根据C++的作用域规则，内层的局部变量会覆盖外层的同名变量。因此，在第二行的语句中，node引用的是函数参数中的node，而不是你想要的之前定义的node。

为了避免这个问题，你可以修改代码，避免重复定义变量名。例如，可以将第二行的变量名改为newNode或其他不同的名称，以避免与函数参数名冲突。

运算符优先级

运算符性质：

接受的操作数，
优先级，
- 特殊：逻辑和(&&)先于逻辑或(||)、四则运算先于位运算
- 位运算优先级低于判断符号，记得写括号。
- 赋值(=)优先级最低
结合性，
- 左结合性：大部分运算(加减乘除)
- 右结合性：赋值运算符。程序会先计算它右边的表达式的值，然后再计算它左边的表达式的值
返回值
- 赋值运算符的返回值是赋值后左操作数的引用

变量类型以及Macro constants

https://en.cppreference.com/w/cpp/language/types

https://en.cppreference.com/w/cpp/types/integer

//返回与平台相关的数值类型的极值
std::numeric_limits<double>::max()
std::numeric_limits<int>::min()

#include<limits.h>
INT_MAX
FLT_MAX (or DBL_MAX ) 
-FLT_MAX (or -DBL_MAX )

关键词

extern 
const
constexpr //C++11引入的关键字，用于编译时的常量与常量函数。
volatile    //是指每次需要引用某个变量的数据时，都必须从内存原地址读取,而不是编译器优化后寄存器间接读取.(必须写回内存，为了多进程并发而设计的。)
inline

static 关键字

static 作⽤：控制变量的存储⽅式和作用范围(可⻅性)。

修饰局部变量
- 存放位置：栈区 -> 静态数据区(data段或者bss段)
- 生命周期：程序结束才会释放
- 作用域：还是局部代码块
修饰函数与全局变量
- 使其作用范围由全工程文件可见变成了本文件可见

多文件共用static变量，需要添加 extern 关键字, 去掉static关键字

在 C++ 中，如果你希望 static 变量可以在多个文件中访问，直接写在头文件中是 不正确的，因为每个包含该头文件的源文件都会生成自己的独立 static 变量，导致它们互相独立，无法共享状态。

正确的解决方案

如果需要共享（全局变量的方式） 你应该将 encounteredAclops 声明为 extern 变量，并将其定义在一个 .cpp 文件中。

头文件：globals.h

#ifndef GLOBALS_H
#define GLOBALS_H

extern bool encounteredAclops;

#endif // GLOBALS_H

源文件：globals.cpp

#include "globals.h"

bool encounteredAclops = false;

在其他源文件中使用：

#include "globals.h"

void someFunction() {
    if (!encounteredAclops) {
        // Do something
        encounteredAclops = true;
    }
}

通过 extern，所有引用 encounteredAclops 的源文件都会共享同一个变量。

如果每个文件需要独立的变量

如果每个源文件都需要独立的 encounteredAclops，你可以将 static bool encounteredAclops = false; 放在各自的源文件中，而不需要放在头文件中。这是因为 static 的作用域仅限于当前编译单元。

每个源文件：

static bool encounteredAclops = false;

void someFunction() {
    if (!encounteredAclops) {
        // Do something
        encounteredAclops = true;
    }
}

如果需要在类中管理（推荐做法） 可以考虑将 encounteredAclops 作为一个类的静态成员变量来实现共享状态。

头文件：AclopsManager.h

#ifndef ACLOPS_MANAGER_H
#define ACLOPS_MANAGER_H

class AclopsManager {
public:
    static bool encounteredAclops;
};

#endif // ACLOPS_MANAGER_H

源文件：AclopsManager.cpp

#include "AclopsManager.h"

bool AclopsManager::encounteredAclops = false;

在其他源文件中使用：

#include "AclopsManager.h"

void someFunction() {
    if (!AclopsManager::encounteredAclops) {
        // Do something
        AclopsManager::encounteredAclops = true;
    }
}

这种方式既可以共享变量，又能保持代码组织清晰。

结论 - 如果需要共享变量：使用 extern 或类的静态成员变量。 - 如果需要独立变量：将 static 声明放在各自的源文件中。 - 不要直接在头文件中定义 static bool encounteredAclops，否则会导致每个包含头文件的源文件都生成自己的副本，违背初衷。

修饰类内函数
- 静态成员函数：使用"static"修饰的成员函数称为静态成员函数。静态成员函数与类的对象无关，可以在没有创建对象的情况下直接通过类名调用。这意味着它们不需要通过类的对象来访问，而是属于整个类的。举例
- 静态成员函数没有隐式的this指针，因此不能直接访问非静态成员变量和非静态成员函数。静态成员函数可以访问类的静态成员变量和其他静态成员函数。
- static 成员函数不能被 virtual 修饰， static 成员不属于任何对象或实例，所以加上 virtual没有任何实际意义；
  - 静态成员函数没有 this 指针，虚函数的实现是为每⼀个对象分配⼀个vptr 指针，⽽ vptr 是通过 this 指针调⽤的，所以不能为 virtual；虚函数的调⽤关系，this->vptr->ctable->virtual function。
修饰类内的变量
- 存放位置：栈区 -> 静态数据区(data段或者bss段)
- 生命周期：程序结束才会释放
- 意味着下一次调用函数时，静态局部变量将保持上一次调用时的值。
- 由于不再属于某个类对象，可以直接通过类名初始化 int MyClass::staticVariable = 10;

多线程场景，修饰局部变量，会导致多线程共用，建议使用thread_local来避免竞争

static 局部变量在第一次被访问时初始化，且初始化过程是线程不安全的。如果两个线程几乎同时首次访问这个变量，可能会导致初始化竞争，进而引发未定义行为。

static 修饰初始化命令，只会执行一次，无论是否多次经过

问题场景：

static auto thread_core_map = GetCpuAffinityMap(device_id); 即使程序多次调用函数经过这行，但是这行命令也只会执行第一次。但是如果我把static关键词去除，就正常执行多次了。

当在一行代码中使用了 static 关键字时，变量的初始化只会在它第一次被执行时进行，之后即使多次经过这行代码，初始化的代码块也不会被重复执行。

在例子中，thread_core_map 是一个静态局部变量，它在第一次经过时会调用 GetCpuAffinityMap(device_id) 函数并保存结果。在后续的函数调用中，即使再次经过这行代码，GetCpuAffinityMap(device_id) 不会被重新调用，因为 thread_core_map 已经被初始化过了。

去除 static 后，thread_core_map 会在每次经过这行代码时重新初始化，也就是每次都会调用 GetCpuAffinityMap(device_id)。

解决方法：

如果你需要这行代码每次执行时都重新调用 GetCpuAffinityMap(device_id)，那么应该去掉 static 关键字，或根据不同条件进行显式地重新初始化静态变量。

比如，可以这样实现惰性初始化或重置的功能：

static auto thread_core_map = GetCpuAffinityMap(device_id);
// 根据条件重新初始化
if (/* 条件 */) {
    thread_core_map = GetCpuAffinityMap(device_id);
}

这样你就可以在特定条件下让 thread_core_map 被重新赋值。

如果你对静态变量的初始化行为没有问题，但是希望特定场景下重新执行初始化函数，可以根据场景调整条件逻辑。

静态成员函数

#include <iostream>

class MyClass {
public:
    static void staticFunction() {
        std::cout << "This is a static member function." << std::endl;
    }
};

int main() {
    MyClass::staticFunction(); // 直接通过类名调用静态成员函数
    return 0;
}

const 关键字

当const修饰基本数据类型时，可以将其放置在类型说明符的前面或后面，效果是一样的。const关键字用于声明一个常量，即其值在声明后不可修改。

const int constantValue1 = 10; // const在类型说明符前
int const constantValue2 = 20; // const在类型说明符后

当const关键字位于指针变量或引用变量的左侧时，它用于修饰指针所指向的变量，即指针指向的内容为常量。当const关键字位于指针变量或引用变量的右侧时，它用于修饰指针或引用本身，即指针或引用本身是常量。

修饰指针指向的变量, 它指向的值不能修改：

int x = 5;
const int* ptr = &x;  // 指向常量整数的指针
// *ptr = 10;        // 错误：不能通过const指针修改值
x = 10;               // 合法：可以修改变量本身的值

修饰指针本身，它不能再指向别的变量，但指向（变量）的值可以修改。：

const int y = 10;
int* const ptr = &y;  // 常量指针指向整数
// ptr = &x;         // 错误：不能修改指针本身
// *ptr = 5;         // 合法：可以修改常量变量的值

const int *const p3; //指向整形常量的常量指针。它既不能再指向别的常量，指向的值也不能修改。

explicit

在C++, explicit 是一个关键字，用于修饰单参数构造函数，用于禁止隐式类型转换。

当一个构造函数被声明为 explicit 时，它指示编译器在使用该构造函数进行类型转换时只能使用显式调用，而不允许隐式的类型转换发生。

通过使用 explicit 关键字，可以防止一些意外的类型转换，提高代码的清晰性和安全性。它通常用于防止不必要的类型转换，特别是在单参数构造函数可能引起歧义或产生意外结果的情况下。

preprocessor directive

#include_next 的作用是在寻找头文件时的头文件搜索优先级里，去除该文件所在的当前目录，主要是为C++头文件的重名问题提供一种解决方案。
- 正确的用法：代码b.cpp想使用自己拓展修改的stdlib.h, 那么在代码的目录下创建stdlib.h，并在该文件里#include_next "stdlib.h" 防止递归引用。

define、 const、 typedef、 inline

define：
- define是一个预处理器指令，用于创建宏定义。它在编译之前对源代码进行简单的文本替换。可以用来定义常量、函数宏和条件编译等。
- 优势：灵活性上占优，特别是在需要获取文件名、行号或控制编译(不同平台编译)时行为的场景
- 缺点：宏的调试和排错难度相对较高，因为宏的展开发生在编译前，出错时通常不容易直接定位到宏展开的具体代码。相比函数，宏的类型检查不严格，容易导致隐含的错误。
- 例如：#define PI 3.14159，在代码中将PI替换为3.14159。

# 是字符串化操作符（Stringizing operator）

在 C/C++ 宏中，# 是 字符串化操作符（Stringizing operator），它的作用是将宏参数转换为字符串文字（string literal）。

当在宏中使用 #key 时，key 被转换为一个字符串文字，即在代码中实际变为 "key"（包括引号）。如果不加 #，key 将直接作为标记被使用，不会转为字符串。

示例：

以下是一个宏的例子，演示了 # 的作用：

宏定义：

#define TO_STRING(x) #x
#define CONCAT_AND_PRINT(a, b) printf("Concatenation: %s\n", TO_STRING(a##b));

宏使用：

int main() {
    int HelloWorld = 42;

    // 使用字符串化操作
    printf("%s\n", TO_STRING(HelloWorld)); // 输出: HelloWorld

    // 使用标记粘贴操作和字符串化操作
    CONCAT_AND_PRINT(Hello, World);        // 输出: Concatenation: HelloWorld
}

宏展开与作用：

TO_STRING(HelloWorld)
宏 TO_STRING 将参数 HelloWorld 转换为字符串文字，展开为：
```
printf("%s\n", "HelloWorld");
```
输出：HelloWorld
CONCAT_AND_PRINT(Hello, World)
a##b 将 Hello 和 World 拼接成 HelloWorld。
TO_STRING(a##b) 将拼接后的标识符 HelloWorld 转换为字符串 "HelloWorld"。展开为：
```
printf("Concatenation: %s\n", "HelloWorld");
```
输出：Concatenation: HelloWorld

## 是 C/C++ 宏预处理器的标记粘贴操作符（Token-pasting operator）

操作符将 valueName 粘贴到 aaa 和 bbb 之间，形成新的标识符。例如，使用 aaa##valueName##bbb 这样的语法是完全有效的。

用于将宏参数和宏内的其他标记连接起来。具体来说，##Value 和 ##Initialized 这两个标记会与宏参数（如 valueName）进行拼接，形成新的标识符。

#define REGISTER_OPTION_CACHE(type, valueName, ...)                 \
    static thread_local type valueName##Value;                      \
    static thread_local bool valueName##Initialized = false;        \
    inline type GetWithCache##valueName() {                         \
        if (!valueName##Initialized) {                              \
            valueName##Value = __VA_ARGS__();                       \
            valueName##Initialized = true;                          \
        }                                                           \
        return valueName##Value;                                    \
    }                                                               \
    inline void SetWithCache##valueName(type value) {               \
        valueName##Value = value;                                   \
        valueName##Initialized = true;                              \
    }

宏展开解释

假设你在代码中使用了如下调用：

REGISTER_OPTION_CACHE(int, MyValue, 42);

这将会将宏中的 type 替换为 int，valueName 替换为 MyValue，并且 __VA_ARGS__ 代表了传递给宏的可变参数 42。

展开后的代码：

static thread_local int MyValueValue;
static thread_local bool MyValueInitialized = false;

inline int GetWithCacheMyValue() {
    if (!MyValueInitialized) {
        MyValueValue = 42;  // 使用了 __VA_ARGS__
        MyValueInitialized = true;
    }
    return MyValueValue;
}

inline void SetWithCacheMyValue(int value) {
    MyValueValue = value;
    MyValueInitialized = true;
}

关键点解释：

valueName##Value 被展开为 MyValueValue。## 操作符将宏参数 MyValue 与 Value 连接，形成新的标识符 MyValueValue。
valueName##Initialized 被展开为 MyValueInitialized，同样是将宏参数 MyValue 与 Initialized 连接，形成新的标识符 MyValueInitialized。

结果

MyValueValue 存储了缓存的值（在这个例子中是 42）。
MyValueInitialized 是一个布尔值，用来标记缓存是否已经初始化。
GetWithCacheMyValue() 函数首先检查 MyValueInitialized 是否为 true，如果没有被初始化，它会使用 42 来初始化缓存并设置标志。
SetWithCacheMyValue(int value) 函数允许你更新缓存的值，并将 MyValueInitialized 设置为 true。

const：
- const用于声明一个常量，指示标识符的值在程序执行期间不能被修改。
- const可以用于变量、函数参数、函数返回类型和成员函数。使用const可以提高代码的可读性和安全性。
- 例如：const int MAX_VALUE = 100;，声明一个名为MAX_VALUE的常量。
typedef：
- typedef用于为数据类型创建别名。它可以用于为复杂的数据类型提供更简洁的名称，增强代码的可读性和可维护性。
- typedef创建的别名可以像原始类型一样使用，并且不会引入新的类型，只是为已有类型提供了一个新的名称。
- 例如：typedef int Age;，为int类型创建了一个别名Age。
inline：
inline用于声明内联函数，它是一种编译器的建议，用于将函数的定义直接插入到调用处，以避免函数调用的开销。
内联函数通常在函数体较小且频繁调用的情况下使用，可以提高程序的执行效率。
inline关键字只是给编译器一个提示，编译器可以选择忽略该提示。在大多数情况下，编译器会自动进行内联优化。
例如：inline int add(int a, int b) { return a + b; }，声明了一个内联函数add。
define主要用于宏定义，const用于声明常量，typedef用于创建类型别名，inline用于内联函数的声明。

#ifndef & #pragma once

为了避免同一个文件被include多次，C/C++中有两种方式，一种是#ifndef方式，一种是#pragma once方式。在能够支持这两种方式的编译器上，二者并没有太大的区别，但是两者仍然还是有一些细微的区别。

new & delete

new和delete 相对于 malloc/free 分配和释放堆空间。
额外会执行构造函数和析构函数

#include <iostream>

class MyClass {
public:
    MyClass() {
        std::cout << "Constructing MyClass" << std::endl;
    }

    ~MyClass() {
        std::cout << "Destructing MyClass" << std::endl;
    }
};

int main() {
    // 使用new动态分配内存，并调用构造函数
    MyClass* obj = new MyClass();

    // 执行一些操作...

    // 使用delete释放内存，并调用析构函数
    delete obj;

    return 0;
}

namespace

namespace 会影响 typedef 的作用范围，但不会直接限制 #define 宏的作用范围。

头文件

相互引用，前置声明
include头文件其实就是将对应的头文件内容贴在include的位置

A.h, B.h 都需要string.h的头文件，然后B.h 会include A.h,那么我在B.h里是不是可以省略include string.h

不应该省略,

防止代码变更引发的问题：如果某天 A.h 中移除了 #include ，而 B.h 依赖 A.h 提供的 #include ，那么 B.h 将会因找不到 std::string 而编译失败。因此，显式包含依赖的头文件可以避免这种隐含依赖引发的问题。
提高可读性和自包含性：每个头文件应该尽量做到自包含，意思是每个头文件应该独立地包含所有它所需要的头文件。这样做的好处是，任何其他文件都可以安全地单独包含 B.h，而无需额外关心它依赖于哪些头文件。
减少隐式依赖：隐式依赖（依赖另一个头文件帮你包含所需的头文件）可能导致维护性问题。显式 #include 可以让代码更具可预测性和可维护性。

include的位置有什么规则和规律吗，头文件和cpp文件前都可以吗？

在编写代码时，往往A.cpp需要include A.h。那A.cpp需要的头文件，我是写在A.cpp里还是A.h里？

头文件 (A.h)：只包含声明所需的头文件，不包含仅在实现中需要的头文件。
源文件 (A.cpp)：包含所有实现需要的头文件，特别是那些仅在实现部分用到的头文件。此外，A.cpp 应该总是包含 A.h。6.

函数的特殊写法

函数传参

值传递
引用传递
指针传递

//值传递
change1(n);
void change1(int n){
    n++;
}

//引用传递，操作地址就是实参地址 ，只是相当于实参的一个别名，在符号表里对应是同一个地址。对它的操作就是对实参的操作
    change2(n);
    void change2(int &n){
        n++;
    }
    //特殊对vector
    void change2(vector<int> &n)
    //特殊对数组
    void change2(int (&n)[1000])

//指针传递，其实是地址的值传递
change3(&n);
void change3(int *n){
    *n=*n+1;
}

引用传递和指针传递的区别：

引用被创建的同时必须被初始化（指针则可以在任何时候被初始化）。
不能有NULL引用，引用必须与合法的存储单元关联（指针则可以是NULL）。
一旦引用被初始化，就不能改变引用的关系（指针则可以随时改变所指的对象）。

指针传递和引用传递的使用情景：

函数内部修改参数并且希望改动影响调用者。
当一个函数实际需要返回多个值，而只能显式返回一个值时，可以将另外需要返回的变量以指针/引用传递

闭包、匿名函数

闭包是捕获并持有了外部作用域变量的函数。

闭包（Closure）是指在程序中，函数可以捕捉并记住其作用域（环境）中的变量，即使在函数执行完成后，这些变量依然保存在内存中，并能在后续的函数调用中被使用。闭包的一个重要特性是，它不仅保存了函数本身的逻辑，还“闭合”了函数执行时的上下文环境（即该函数所在的作用域）。

闭包通常用于实现函数内部的状态保持、回调函数等场景。在 C++ 中，闭包通过 lambda 表达式 实现，lambda 表达式可以捕获外部变量并在其内部使用。

例子

auto add = [](int x) {
    return [x](int y) {
        return x + y;
    };
};

auto add5 = add(5);
std::cout << add5(3); // 输出 8

在上面的例子中，add 函数返回了一个闭包，捕获了变量 x 的值。即使 x 在原作用域中不再可用，返回的闭包仍然可以访问并使用 x 的值。

匿名函数是一种没有被绑定标识符的函数
lambda 是一种匿名函数
lambda 可以表示闭包

匿名函数（lambda）和闭包的关系就如同类和类对象的关系

匿名函数和类的定义都只存在于源码（代码段）中，而闭包和类对象则是在运行时占用内存空间的实体；

Lambda在C++中的实现方式

传参默认值

虽然理论上可以通过类似void f(bool x = true)来实现默认值。但是我在PTA和CPPRINTER上编译.so不过, 会出现undefied的符号。实际实现如下

// hpp
void SetDeterministic();
void SetDeterministic(bool isOpapi = true);

//cpp
void SetDeterministic() {
    SetDeterministic(true);
}
void SetDeterministic(bool isOpapi)
{
    //xxx
}

类型变参模板

template<typename T>
void swap(T& t1, T& t2)
{
    T temp = t2;
    t2 = t1;
    t1 = temp;
}
swap<int>(a,b);

条件模板类

假设我们有一个模板类 Wrapper，我们希望禁止 VirtualGuardImpl 类型作为模板参数：

template <
    typename T,
    typename U = T,
    typename = typename std::enable_if<!std::is_same<U, VirtualGuardImpl>::value>::type>
class Wrapper {
public:
    void function() {
        // 实现
    }
};

在这个例子中，如果用户尝试创建 Wrapper<VirtualGuardImpl> 或 Wrapper<VirtualGuardImpl, VirtualGuardImpl> 的实例，编译器将报错，因为 std::enable_if 的条件不满足。但如果使用其他类型，比如 int 或自定义类型，就可以正常编译。

这段代码是 C++ 中的一个模板函数或模板类模板参数的定义，它使用了模板默认参数、std::enable_if 条件编译技术以及类型萃取（type traits）。下面是对这段代码的详细解释：

模板参数 U:
- typename U = T 定义了一个模板类型参数 U，并给它一个默认值 T。这意味着如果在使用模板时没有指定 U 的话，它将默认使用模板参数 T 的值。
std::enable_if:
- std::enable_if 是一个条件编译技术，它只在给定的布尔表达式为 true 时启用某个模板。
- 在这个例子中，std::enable_if 后面的布尔表达式是 !std::is_same<U, VirtualGuardImpl>::value。这意味着只有当 U 不等于 VirtualGuardImpl 类型时，这个模板参数才有效。
typename 关键字:
- typename 关键字用于告诉编译器 std::enable_if 的结果是一个类型。std::enable_if 返回的是一个类型，如果条件为 true，它返回一个空的类型，否则会导致编译错误。
std::is_same:
- std::is_same<U, VirtualGuardImpl>::value 是一个编译时检查，用于判断 U 和 VirtualGuardImpl 是否是相同的类型。::value 是类型特征 std::is_same 的一个成员，它是一个布尔值，如果类型相同则为 true，否则为 false。
组合解释:
- 这段代码的意思是：定义一个模板参数 U，默认值为 T，并且这个模板参数只有在 U 不是 VirtualGuardImpl 类型时才有效。
- 这是一种常见的模板编程技巧，用于约束模板参数的类型，以确保它们符合特定的要求。

个数变参模板

#include <stdarg.h>
void Error(const char* format, ...)
{
    va_list argptr;
    va_start(argptr, format);
    vfprintf(stderr, format, argptr);
    va_end(argptr);
}

VA_LIST 是在C语言中解决变参问题的一组宏，变参问题是指参数的个数不定，可以是传入一个参数也可以是多个;可变参数中的每个参数的类型可以不同,也可以相同;可变参数的每个参数并没有实际的名称与之相对应，用起来是很灵活。

（1）首先在函数里定义一具VA_LIST型的变量，这个变量是指向参数的指针；（2）然后用VA_START宏初始化变量刚定义的VA_LIST变量；（3）然后用VA_ARG返回可变的参数，VA_ARG的第二个参数是你要返回的参数的类型（如果函数有多个可变参数的，依次调用VA_ARG获取各个参数）；（4）最后用VA_END宏结束可变参数的获取。

系统提供了vprintf系列格式化字符串的函数，用于编程人员封装自己的I/O函数。

int vprintf  / vscanf   (const char * format, va_list ap);                  // 从标准输入/输出格式化字符串 
int vfprintf / vfsacanf (FILE * stream, const char * format, va_list ap);   // 从文件流 
int vsprintf / vsscanf  (char * s, const char * format, va_list ap);        // 从字符串

返回多个数

使用结构体

struct RowAndCol { int row;int col; };

RowAndCol r(string fn) {
    /*...*/
    RowAndCol result;
    result.row = x;
    result.col = y;
    return result;
}

左值与右值

在 C++ 中，左值（lvalue） 和 右值（rvalue） 是两个重要的概念，用来描述表达式的值和内存的关系。它们帮助开发者理解变量的生命周期、赋值和对象管理，特别是在现代 C++ 中引入了右值引用后，优化了移动语义和资源管理。

1. 左值（lvalue）

左值（lvalue，locatable value） 是指在内存中有明确地址、可持久存在的对象，可以对其进行赋值操作。通俗地说，左值是能够取地址的值，可以出现在赋值操作符的左边。

特点：

左值具有持久的内存地址。
左值可以取地址（使用 & 运算符）。
左值通常表示已经存在的变量或对象。

示例

int x = 10;   // x 是左值
int* p = &x;  // 可以取 x 的地址

x = 20;       // 可以对左值进行赋值

在这个例子中，x 是一个左值，因为它表示了内存中的某个对象，并且可以通过赋值语句修改它的值。

2. 右值（rvalue）

右值（rvalue，readable value） 是没有明确地址、临时存在的对象，不能对其进行赋值操作。它们通常是字面值常量或表达式的结果。右值只能出现在赋值操作符的右边，表示一个临时对象或数据。

特点：

右值是临时的，通常会在表达式结束时销毁。
右值不能取地址（即不能使用 & 获取右值的地址）。
右值表示表达式的计算结果或临时对象。

示例

int y = 10;       // 10 是右值
int z = y + 5;    // y + 5 是右值表达式

在这个例子中，10 和 y + 5 是右值，因为它们表示计算出的临时数据，并且不能直接对这些值进行赋值操作。

3. 现代 C++ 中的右值引用（rvalue reference）

C++11 引入了 右值引用，即通过 && 符号表示。这使得右值也能通过引用进行操作，特别是在实现移动语义（move semantics）和避免不必要的拷贝时非常有用。右值引用允许我们通过右值管理资源，避免性能上的损失。

示例：右值引用与移动语义

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2 = std::move(vec1);  // vec1 资源移动到 vec2

    std::cout << "vec1 size: " << vec1.size() << std::endl;
    std::cout << "vec2 size: " << vec2.size() << std::endl;

    return 0;
}

在这个例子中，std::move 将 vec1 变为一个右值引用，使其内部的资源（如动态分配的内存）直接转移给 vec2，避免了拷贝。

4. 区分左值与右值

通常，左值是表示持久存在的对象，可以通过取地址符 & 获取其地址，而右值是临时的、短暂存在的值，不能直接获取其地址。理解这两者对于编写高效的 C++ 代码和使用现代特性（如右值引用和移动语义）非常重要。

常见误区

字面值常量（如 42、'a'）是右值。
表达式的结果（如 x + y）通常是右值。
函数返回值若返回的是值，而不是引用，则该返回值是右值。

左值（lvalue） 是可以取地址的值，通常是变量或持久的对象。
右值（rvalue） 是临时值，通常是表达式的结果或字面量。
右值引用（&&）是 C++11 引入的新特性，用来优化资源管理和避免不必要的拷贝操作。

C++11: 花括号初始化列表

使用

在C++98/03中我们只能对普通数组和POD(plain old data，简单来说就是可以用memcpy复制的对象)类型可以使用列表初始化，如下：

//数组的初始化列表： 
int arr[3] = {1,2,3}
//POD类型的初始化列表：
struct A
{
 int x;
 int y;
}a = {1,2};

在C++11中初始化列表被适用性被放大，可以作用于任何类型对象的初始化。如下：

X x1 = X{1,2};
X x2 = {1,2}; // 此处的'='可有可⽆
X x3{1,2};
X* p = new X{1,2};

//列表初始化也可以用在函数的返回值上
std::vector<int> func() {
    return {};
}

变量类型的适用范围

聚合类型可以进行直接列表初始化

聚合类型包括

普通数组，如int[5]，char[]，double[]等
一个类，且满足以下条件：
1. 没有用户声明的构造函数
2. 没有用户提供的构造函数(允许显示预置或弃置的构造函数)
3. 没有私有或保护的非静态数据成员
4. 没有基类
5. 没有虚函数
6. 没有{}和=直接初始化的非静态数据成员
7. 没有默认成员初始化器

原理

对于一个聚合类型，使用列表初始化相当于使用std::initializer_list对其中的相同类型T的每个元素分别赋值处理，类似下面示例代码；

struct CustomVec {
    std::vector<int> data;
    CustomVec(std::initializer_list<int> list) {
        for (auto iter = list.begin(); iter != list.end(); ++iter) {
            data.push_back(*iter);
        }
    }
};

优势

方便，且基本上可以替代括号初始化
可以使用初始化列表接受任意长度
可以防止类型窄化，避免精度丢失的隐式类型转换

参考文献

https://zh.cppreference.com/
https://leetcode-cn.com/problems/path-with-maximum-gold/solution/huang-jin-kuang-gong-by-leetcode-solutio-f9gg/
https://blog.csdn.net/qq_33221533/article/details/82119031
⼩贺 C++ ⼋股⽂ PDF 的作者，电⼦书的内容整理于公众号「herongwei」
https://blog.csdn.net/hailong0715/article/details/54018002

https://shaojiemike.notion.site/C-11-a94be53ca5a94d34b8c6972339e7538a

2023年10月8日
分类于 Programming
需要 7 分钟阅读时间

[C++ Basic] STL Data Structure

迭代器知识

随机访问迭代器

定义：随机访问迭代器是一种迭代器类型，允许在常数时间内访问序列中的任何元素，并支持灵活的迭代器操作。
运算支持：
- 支持指针算术运算，如 + 和 - 运算符，允许轻松地在迭代器位置上进行移动。
- 支持下标运算符 []，使其用法与指针类似。
- 例如，对于一个指向数组的随机访问迭代器 it，可以通过 *(it + i) 或 it[i] 语法访问第 i 个元素。
使用场景：
- STL 容器：vector 和 deque 都提供随机访问迭代器。
- 算法：一些标准库算法（例如 std::sort、std::nth_element）要求输入的迭代器必须是随机访问迭代器，以便快速定位和排序。

正向迭代器与反向迭代器

概述：在 C++ 中，容器一般提供正向迭代器（begin() 到 end()）和反向迭代器（rbegin() 到 rend()），二者在遍历方向上相反。
转换：正向迭代器和反向迭代器可以相互转换，但类型不同，需要显式转换。
- 正向迭代器到反向迭代器：可以将一个正向迭代器转换为反向迭代器。
```
Iterator it;  // 假设 it 是正向迭代器
std::reverse_iterator<Iterator> rit(it);  // 将 it 转换为反向迭代器 rit
```
- 反向迭代器到正向迭代器：反向迭代器的 base() 成员函数可以返回一个指向反向迭代器当前元素的下一个位置的正向迭代器。
```
std::reverse_iterator<Iterator> rit;
Iterator it = rit.base();  // 转换为正向迭代器，指向 rit 所指位置的后一个元素
```
注意：
反向迭代器 rit.base() 指向的并不是 rit 当前元素本身，而是 rit 指向元素的下一个位置。

迭代器之间的减法是被允许的，两个迭代器相减返回是它们之间的距离，这个距离是一个符号类整型（signed），意味着两个迭代器之间相减可能是正数、零或者负数。

反向遍历

C++ 提供了 rbegin() 和 rend() 来支持容器的反向遍历：

rbegin() 返回一个反向迭代器，指向容器的最后一个元素。
rend() 返回一个反向迭代器，指向容器反向遍历时的“结束位置”，即第一个元素之前的一个位置。
在循环中，注意使用 ++it 而非 --it，因为反向迭代器的递增操作相当于在正向迭代器上进行递减操作。

for (auto it = collection.rbegin(); it != collection.rend(); ++it) {
    std::cout << *it << std::endl;
    // 或者如果是键值对容器：
    // std::cout << it->first << ", " << it->second << std::endl;
}

如果非要使用 end() 和 begin()

可以这样写：

auto it = showedPositive.end();
while (it != showedPositive.begin()) {
    --it;  // 注意：先递减迭代器，再访问元素
    std::cout << *it << std::endl;
}

前后第k个元素

std::prev 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向前移动指定偏移量后的迭代器。
std::next 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向后移动指定偏移量后的迭代器。

auto prevIt = std::prev(it);

auto next2It = std::next(it, 2);

auto it2 = it;
advance(it2,k);

advance

std::advance 形似index的随机访问，函数的实现方式取决于迭代器的类型：

对于随机访问迭代器（后面解释），它会直接使用 += 运算符来实现移动。
对于双向迭代器和输入迭代器，它会使用循环来实现移动。
例如，以下是 std::advance 的一个简单实现, 这个实现使用了 C++17 的 if constexpr 特性，以便在编译时选择不同的实现方式。：

template <typename InputIt, typename Distance>
void advance(InputIt& it, Distance n) {
    if constexpr (std::is_same_v<std::random_access_iterator_tag,
                typename std::iterator_traits<InputIt>::iterator_category>) {
        it += n; //如果迭代器是随机访问迭代器（后面解释），它会使用 += 运算符来移动；
    } else {
        if (n >= 0) {
            while (n--) {
                ++it; //否则，它会使用循环来移动。
            }
        } else {
            while (n++) {
                --it;
            }
        }
    }
}

bitset

bitset类型存储二进制数位。

初始化

std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));

//foo: 0000000000000000
//bar: 0000111110100010
//baz: 0000000101111001

格式转换

将数转化为其二进制的字符串表示

int i = 3;
string bin = bitset<16>(i).to_string(); //bin = "0000000000000011"
bin = bin.substr(bin.find('1'));        //bin = "11"

pair

#include <utility>
pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

tuple

#include <tuple> // 包含 tuple

std::tuple<int, std::string, double> t1(1, "one", 1.0);

// 使用 make_tuple 函数
auto t2 = std::make_tuple(2, "two", 2.5);

//使用 tuple 时，访问/修改元素使用 std::get<index>。
std::cout << "Tuple t2: ("
            << std::get<0>(t2) << ", "
            << std::get<1>(t2) << ", "
            << std::get<2>(t2) << ")"
            << std::endl;

char 与字符串

元音与index的相互映射

string vowel = "AEIOUaeiou";
if vowel.find(c) != std::string::npos;

voewl[0] = 'A';

string

初始化与读取

std::string s0 ("Initial string");

// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);
std::string s3 (s0, 8, 3);
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);
std::string s6a (10, 'x');
std::string s6b (10, 42);      // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);

std::cout << "s1: " << s1 << "\ns2: " << s2 << "\ns3: " << s3;
std::cout << "\ns4: " << s4 << "\ns5: " << s5 << "\ns6a: " << s6a;
std::cout << "\ns6b: " << s6b << "\ns7: " << s7 << '\n';

//output
s1: 
s2: Initial string
s3: str
s4: A character sequence
s5: Another char
s6a: xxxxxxxxxx
s6b: **********
s7: Initial

读取空格分割的

stringstream txt(s);
string word;
while(txt>>word){
    // to do
}

删

string erase

三种情况

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

int main ()
{
std::string str ("This is an example sentence.");
std::string str1(str) ;
std::cout << str << '\n';
                                        // "This is an example sentence."
str.erase (10,8);                        //            ^^^^^^^^
//去除index=10的连续8个元素，

//去除从index=3开始的所有元素, 后面全删除
str1.erase (3);
// "Thi"

std::cout << str << '\n';
                                        // "This is an sentence."
str.erase (str.begin()+9);               //           ^
//去除itr指向的元素
std::cout << str << '\n';
                                        // "This is a sentence."
str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
//去除[first,last).的元素
std::cout << str << '\n';
                                        // "This sentence."
return 0;
}

删除最后一个元素

std::string s = "C,C++,Java,";
if (!s.empty()) {
s.pop_back();
}

if (!s.empty()) {
s.resize(s.size() - 1);
}

if (!s.empty()) {
s.erase(std::prev(s.end()));
}

if (!s.empty()) {
s.erase(s.size() - 1);
}

改

截取

// Copy three characters of s1 (starting
// from position 1)
//第一个参数是要截取的字符串，第二个参数是截取的开始位置，第三个参数是截取长度（可选）1。如果没有指定长度，则子字符串将延续到源字符串的结尾。
string r = s1.substr(1, 3);

// Take any string
string s = "dog:cat";
// Find position of ':' using find()
int pos = s.find(":");
// Copy substring after pos(include pos)
string sub = s.substr(pos);
// Copy substring before pos(not include pos)
string sub = s.substr(0 , pos);

反转string

reverse(greeting.begin(),greeting.end());

查

长度

//总长度
len = str3.size();
// strlen 大部分情况结果和size一样，但是字符串里有\0, strlen会提前返回。
len = strlen(s1);

遍历

string s;
for(auto && x : s)

打印

printf("%s", your_string.c_str()); //不推荐
cout << your_string;

查找子元素位置

// log1 中找空格
int pos1 = log1.find_first_of(" ");

// 判断是否找到
if(s.find(goal) != string::npos){
}

npos是一个常数，表示size_t的最大值（Maximum value for size_t）。许多容器都提供这个东西，用来表示不存在的位置，类型一般是std::container_type::size_type。

判断数字

isdigit 是 C 标准库中的函数，用于检查一个字符是否为数字字符。它定义在头文件中（在 C++ 中）或者头文件中（在 C 中）。

#include <cctype>  // 对应 isdigit 函数
// 判断数字
bool isDigit1 = isdigit(log1[pos1 + 1]);

判断前缀

要检查一个 std::string 是否以某个前缀开头，std::string 没有直接提供“检查前缀”的方法，但可以使用 compare 或 find 方法实现。

方法 1：使用 compare 检查前缀

std::string::compare 可以比较字符串的部分内容，适合用于前缀检查。

#include <iostream>
#include <string>

bool hasPrefix(const std::string& str, const std::string& prefix) {
    return str.compare(0, prefix.size(), prefix) == 0;
}

int main() {
    std::string text = "Hello, world!";
    std::string prefix = "Hello";

    if (hasPrefix(text, prefix)) {
        std::cout << "The string starts with the prefix." << std::endl;
    } else {
        std::cout << "The string does not start with the prefix." << std::endl;
    }

    return 0;
}

方法 2：使用 find 检查前缀

可以使用 std::string::find，但需要确认找到的位置是否是 0 才能确定是前缀。

#include <iostream>
#include <string>

bool hasPrefix(const std::string& str, const std::string& prefix) {
    return str.find(prefix) == 0;
}

int main() {
    std::string text = "Hello, world!";
    std::string prefix = "Hello";

    if (hasPrefix(text, prefix)) {
        std::cout << "The string starts with the prefix." << std::endl;
    } else {
        std::cout << "The string does not start with the prefix." << std::endl;
    }

    return 0;
}

方法 3：使用 std::string::starts_with (C++20)

如果你使用的是 C++20 或更高版本，可以直接使用 starts_with 方法。

#include <iostream>
#include <string>

int main() {
    std::string text = "Hello, world!";
    std::string prefix = "Hello";

    if (text.starts_with(prefix)) {
        std::cout << "The string starts with the prefix." << std::endl;
    } else {
        std::cout << "The string does not start with the prefix." << std::endl;
    }

    return 0;
}

总结

如果使用 C++20，可以直接用 starts_with。
否则可以用 compare 或 find，推荐 compare，因为它可以直接比较前缀而不需要判断位置。

查找最后出现的

std::string::rfind 是 C++ 标准库提供的一个方法，用于从字符串的末尾向前查找指定的子字符串或字符。它的功能与 find 类似，但查找方向是从右向左，适用于需要从字符串末尾开始定位子字符串的情况。

函数原型

size_t rfind(const std::string& str, size_t pos = std::string::npos) const;
size_t rfind(const char* s, size_t pos = std::string::npos) const;
size_t rfind(char c, size_t pos = std::string::npos) const;

参数说明

str：要查找的子字符串。
s：C 风格字符串（const char*）。
c：要查找的单个字符。
pos：从字符串的 pos 位置向前查找，默认值为 std::string::npos，表示从末尾开始查找。

返回值

返回找到的子字符串或字符的起始位置索引。
如果没有找到，返回 std::string::npos。

使用示例

查找最后出现的子字符串：

#include <iostream>
#include <string>

int main() {
    std::string text = "Hello, world! Hello, C++!";
    size_t pos = text.rfind("Hello");

    if (pos != std::string::npos) {
        std::cout << "'Hello' found at position: " << pos << std::endl;
    } else {
        std::cout << "'Hello' not found." << std::endl;
    }

    return 0;
}

输出：

'Hello' found at position: 14

查找最后出现的字符：

#include <iostream>
#include <string>

int main() {
    std::string text = "abcdefgabc";
    size_t pos = text.rfind('a');

    if (pos != std::string::npos) {
        std::cout << "'a' found at position: " << pos << std::endl;
    } else {
        std::cout << "'a' not found." << std::endl;
    }

    return 0;
}

输出：

'a' found at position: 7

指定位置查找：

如果想要从特定位置向前查找，可以指定 pos 参数。例如，从索引 10 向前查找字符 'o'：

#include <iostream>
#include <string>

int main() {
    std::string text = "Hello, world! Hello, C++!";
    size_t pos = text.rfind('o', 10);

    if (pos != std::string::npos) {
        std::cout << "'o' found at position: " << pos << std::endl;
    } else {
        std::cout << "'o' not found." << std::endl;
    }

    return 0;
}

输出：

'o' found at position: 4

在这些示例中，rfind 帮助我们从右向左查找字符串或字符，适用于查找最后一次出现的位置或从右边指定位置向左查找的需求。

regex 读取字符串元素， eg undo xxx aaa 4 to 10

在 C++ 中，可以使用 std::regex、std::stringstream 或 std::find_if 等方法对字符串进行解析和分割。以下提供一种基于 std::regex 的方法来提取单个数字和范围（如 4 to 10）。

#include <vector>
#include <regex> //important

// 解析字符串中的所有单个数字和范围
void parseNumbers(const std::string& input, std::vector<std::pair<int, int>>& ranges) {
    // 在 C++ 中，使用 R"(...)" 定义原始字符串，可以避免转义字符
    std::regex rangePattern(R"(\b(\d+)\s+to\s+(\d+)\b)");  // 匹配范围形式

    std::smatch match;
    std::string::const_iterator searchStart(input.cbegin());

    // 找到所有的范围
    while (std::regex_search(searchStart, input.cend(), match, rangePattern)) {
        int start = std::stoi(match[1]);
        int end = std::stoi(match[2]);
        ranges.emplace_back(start, end);
        searchStart = match.suffix().first;  // 更新搜索起点
    }


}

int main() {
    std::string input = "undo xxx aaa 1 2 4 to 10";
    std::vector<std::pair<int, int>> ranges;

    parseNumbers(input, ranges);


    // 输出范围

    return 0;
}

顺序容器与关联容器

顺序容器包括vector、deque、list、forward_list、array、string，
- 支持快速顺序访问元素。
关联容器包括set、map，
- 支持高效的关键字查找和访问。
- 不支持顺序容器的位置相关的操作。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。
- 也不支持构造函数或插入操作这些接受一个元素值和一个数量值得操作。

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

为何map和set的插入删除效率比用其他序列容器高？

因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map和set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。

插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点就OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

二叉树

存储方式

链表，或者数组(如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。)

链式结构如下，注意左右孩子节点

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;

遍历方式

深度遍历：前/中/后序遍历。

注意：这里前中后，其实指的就是中间节点/根节点的遍历顺序

heap 堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值。
- 大顶堆：每个结点的值都大于或等于其左右孩子结点的值；
- 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
堆总是一棵完全二叉树。
make_heap()将区间内的元素转化为heap.
push_heap()对heap增加一个元素.
pop_heap()对heap取出下一个元素.
sort_heap()对heap转化为一个已排序群集.

#include <algorithm>
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;

make_heap (v.begin(),v.end());//male_heap就是构造一棵树，使得每个父结点均大于等于其子女结点
cout << "initial max heap   : " << v.front() << endl;

pop_heap (v.begin(),v.end());//pop_heap不是删除某个元素而是把第一个和最后一个元素对调后[first,end-1]进行构树，最后一个不进行构树
v.pop_back();//删除最后一个的结点
cout << "max heap after pop : " << v.front() << endl;

v.push_back(99);//在最后增加一个结点
push_heap (v.begin(),v.end());//重新构树
cout << "max heap after push: " << v.front() << endl;

//请在使用这个函数前，确定序列符合堆的特性，否则会报错！
sort_heap (v.begin(),v.end());//把树的结点的权值进行排序，排序后，序列将失去堆的特性
std::cout << "sorted array       : ";
for (int i = 0; i < v.size(); ++i) {
    std::cout << v[i] << ' ';
}
std::cout << std::endl;

map / unordered_map / hash_map

map
1. 内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。其中每个键都是唯一的，可以插入或删除，但不能更改。但是与键关联的值可以更改。
2. 红黑树是一种含有红黑结点并能自平衡的二叉查找/搜索树, 别称平衡二叉B树（symmetric binary B-trees）
unordered_map(hash_map)
1. 基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
2. 标准库的unordered_map，底层实现是基于hashtable的，其避免冲突的方法是使用开链（seperate chaining）法，这种做法是在每一个表格元素中维护一个list，每个表格元素称之为buket（桶）

hash_map VS unordered_map

hash_map，unordered_map本质是一样的，只不过 unordered_map被纳入了C++标准库标准：

早期由于在C++标准库中没有定义散列表hash_map，标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的，所以它们在功能和性能保证上都有微妙的差别。
从C++11开始，哈希表实现已添加到C++标准库标准。决定对类使用备用名称unordered_map，以防止与这些非标准实现的冲突，并防止在其代码中有hash_table的开发人员无意中使用新类。unordered_map更具描述性，因为它暗示了类的映射接口和其元素的无序性质。

map和multimap的区别

map不允许相同key值存在，multimap则允许相同的key值存在。

特性	map	unordered_map
元素排序	严格弱序	无
常见实现	平衡树或红黑树	哈希表
查找时间	O(log(n))	平均 O(1)，最坏 O(n)（哈希冲突）
插入时间	O(log(n)) + 重新平衡	同查找时间
删除时间	O(log(n)) + 重新平衡	同查找时间
需要比较器	只需 `<` 运算符	只需 `==` 运算符
需要哈希函数	不需要	需要
常见用例	当无法提供良好哈希函数或哈希	在大多数其他情况下。当顺序不重要时
	函数太慢，或者需要有序时

std::map的优势: 内存池的自动管理

自己实现的map需要自己去new一些节点，当节点特别多，而且进行频繁的删除和插入的时候，内存碎片就会存在，而STL采用自己的Allocator分配内存，以内存池的方式来管理这些内存，会大大减少内存碎片，从而会提升系统的整体性能。

为什么有时unordered_map, 性能比map差

注意到很多代码使用 std::unordered_map 因为“哈希表更快”。但是对于小map，具有很高的内存开销。

网上有许多map和unorderd_map的比较，但是都是大例子。

下载一个，比较N比较小时的速度。前面是插入，后面是读取时间。编译g++ -std=c++11 -O3 map.cpp -o main

初始化

map的value是int，默认为0。可以直接++

#include <map>
#include <unordered_map>
//c++11以上
map<string,int> m3 = {
    {"string",1}, {"sec",2}, {"trd",3}
};
map<string,string> m4 = {
    {"first","second"}, {"third","fourth"},
    {"fifth","sixth"}, {"begin","end"}
};

operator[]为不存在键，构造默认值

比如对于std::map<std::string, int> m; m["apple"]++;

m["apple"]++ 会首先检查 apple 是否存在于容器中。
由于 apple 不存在，容器会插入一个默认值 0。
然后，++ 操作会将 0 增加到 1。

常见默认值

在 C++ 中，map 和 unordered_map 容器的默认值取决于它们存储的值类型的默认构造方式。具体来说：

数值类型：
对于整型（如 int, long 等），默认值是 0。
对于浮点型（如 float, double 等），默认值是 0.0。
指针类型：
指针类型的默认值是 nullptr。
自定义类型：
自定义类型的默认值是该类型默认构造函数构造的对象。如果没有显式定义默认构造函数，则编译器会提供一个默认的构造函数，通常将所有成员初始化为默认值。
标准库类型：
对于标准库类型（如 std::string），默认值是空字符串 ""。
对于 std::vector，默认值是一个空的 vector。

增改

// insert 不能覆盖元素，已经存在会失败
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
// 数组方式可以覆盖
mapStudent[1] = "student_one";

判断insert是否成功

用pair来获得是否insert成功，程序如下

pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));

我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。

删除

mymap.erase ('c');               // erasing by key

查

//unordered_map 类模板中，还提供有 at() 成员方法，和使用 [ ] 运算符一样，at() 成员方法也需要根据指定的键，才能从容器中找到该键对应的值；
//不同之处在于，如果在当前容器中查找失败，该方法不会向容器中添加新的键值对（[]会插入默认值），而是直接抛出out_of_range异常。
cnt.at(num)

// c++17 支持
for (auto &[num, c] : cnt) {
}
for (auto &[x, _] : cnt) {
    //sth
}
// 否则
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    auto& key = it->first;
    auto& value = it->second;
    // 使用 key 和 i 进行操作
}

查找是否存在 find, 判断一般会比count快

通过 find() 方法得到的是一个正向迭代器，有 2 种情况：

当 find() 方法成功找到以指定元素作为键的键值对时，其返回的迭代器就指向该键值对；
当 find() 方法查找失败时，其返回的迭代器和 end() 方法返回的迭代器一样，指向容器中最后一个键值对之后的位置。

unordered_map<string, string>::iterator iter = umap.find("GO教程");
if (iter == umap.end()) {
    //查找失败
    cout << "当前容器中没有以\"GO教程\"为键的键值对";
}else {
    //查找成功
    cout << iter->first << " " << iter->second << endl;
}

查找是否存在 count

用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置。

// 检查键30是否存在
if (mp.count(30))
cout << "键30存在\n";
else
cout << "键30不存在\n";

set

常用于 一个值是否存在 的相关问题

按关键字有序：
1. set(关键字即值，即只保存关键字的容器)；使用红黑树，自动排序，关键字唯一。
2. multiset(关键字可重复出现的set)；
无序集合：
1. unordered_set(用哈希函数组织的set)；
2. unordered_multiset(哈希组织的set，关键字可以重复出现)。

set map 的区别

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。

map和set区别在于：

map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；
Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。
1. set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key
2. 原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。
3. 所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。
map支持下标操作，set不支持下标操作。
map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，
const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。
如果find能解决需要，尽可能用find。

set/map 的有序性

默认红黑树，使用std::less 作为比较器, 升序序列。

存放数据类型	排序规则
整数、浮点数等	按从小到大的顺序排列
字符串	按字母表顺序排列
指针	按地址升序排列
指向某元素的指针	按指针地址递增的顺序排列
类（自定义）	可以自定义排序规则

// 自定义比较器，按降序排列
struct Greater {
    bool operator()(const int& a, const int& b) const {
        return a > b;
    }
};
std::set<int, Greater> s = {5, 3, 8, 1, 4};

自定义set 排序

template < class T,                             // set::key_type/value_type
        class Compare = less<T>,        // set::key_compare/value_compare
        class Alloc = allocator<T>         // set::allocator_type
        > class set;

//初始化
set<char> vowel {'a','e','i','o','u'};

template <class T, class Compare, class Alloc>
bool operator== ( const set<T,Compare,Alloc>& lhs,
                    const set<T,Compare,Alloc>& rhs ); // 和map类似的，重载相等判断

自定义hash函数

auto hash_p = [](const pair<int, int> &p) -> size_t {
static hash<long long> hash_ll;
return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
};
unordered_set<pair<int, int>, decltype(hash_p)> points(0, hash_p); //(0,hash_p)分别为迭代器的开始和结束的标记（数组多为数据源）
//多用于数组 set<int> iset(arr,arr+sizeof(arr)/sizeof(*arr));

类似的例子¹

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

上面的不是用lambda expression隐函数，而是定义函数的写法

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};
std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

增删改查

//增改
insert()–在集合中插入元素
emplace() 最大的作用是避免产生不必要的临时变量

erase()–删除集合中的元素
//删除 set 容器中值为 val 的元素
//第 1 种格式的 erase() 方法，其返回值为一个整数，表示成功删除的元素个数；
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
//后 2 种格式的 erase() 方法，返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素。
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);
clear()–删除集合中所有元素

//查询
find()–返回一个指向被查找到元素的迭代器。返回值：该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中最后一个元素之后的位置end
count()- 查找的bool结果
size()–集合中元素的数目

swap()–交换两个集合变量

并差集

并查集主要用于处理一些不相交集合的合并和查询问题。它在很多算法问题中都有广泛的应用，特别是在图论和动态连通性问题中。

并查集的基本操作

初始化UnionFind(int n)：每个元素初始化为自己的父节点。
查找int find(int x)：查找某个元素的根节点，并进行路径压缩以优化后续查找。
合并int find(int x)：将两个元素所在的集合合并为一个集合。

核心是

同一个并查集内的元素会指向同一个parent
维护并查集深度Rank，来按秩合并。
数据结构用数组和map都行

vector 实现并查集，包括路径压缩和按秩合并

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 5;
    UnionFind uf(n);

    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);

    cout << "Is 0 and 2 connected? " << (uf.connected(0, 2) ? "Yes" : "No") << endl; // Yes
    cout << "Is 0 and 3 connected? " << (uf.connected(0, 3) ? "Yes" : "No") << endl; // No

    return 0;
}

map 实现并查集，处理元素不连续或者数量不定情况

#include <iostream>
#include <map>
using namespace std;

class UnionFind {
public:
    map<int, int> parent;
    map<int, int> rank;

    // 初始化
    void makeSet(int x) {
        parent[x] = x;
        rank[x] = 0;
    }

    // 查找根节点，并进行路径压缩
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            makeSet(x); // 如果 x 不存在，先初始化
        }
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并两个集合
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 判断两个元素是否在同一个集合中
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    UnionFind uf;

    // 初始化一些元素
    uf.makeSet(1);
    uf.makeSet(2);
    uf.makeSet(3);
    uf.makeSet(4);
    uf.makeSet(5);

    // 合并一些集合
    uf.unite(1, 2);
    uf.unite(2, 3);
    uf.unite(4, 5);

    // 查询
    cout << "Is 1 and 3 connected? " << (uf.connected(1, 3) ? "Yes" : "No") << endl; // Yes
    cout << "Is 1 and 4 connected? " << (uf.connected(1, 4) ? "Yes" : "No") << endl; // No

    // 动态添加新元素并合并
    uf.unite(6, 7);
    cout << "Is 6 and 7 connected? " << (uf.connected(6, 7) ? "Yes" : "No") << endl; // Yes

    return 0;
}

容器适配器

C++ 中的容器适配器 stack、queue 和 priority_queue 依赖不同的基础容器来实现特定的数据结构行为。每种容器适配器都有特定的成员函数要求，默认选择的基础容器是为了更好地满足这些要求。

容器适配器	基础容器筛选条件	默认使用的基础容器
stack	基础容器需包含以下成员函数：	`deque`
	- `empty()`
	- `size()`
	- `back()`
	- `push_back()`
	- `pop_back()`
	满足条件的基础容器有 `vector`、`deque`、`list`。
queue	基础容器需包含以下成员函数：	`deque`
	- `empty()`
	- `size()`
	- `front()`
	- `back()`
	- `push_back()`
	- `pop_front()`
	满足条件的基础容器有 `deque`、`list`。
priority_queue	基础容器需包含以下成员函数：	`vector`
	- `empty()`
	- `size()`
	- `front()`
	- `push_back()`
	- `pop_back()`
	满足条件的基础容器有 `vector`、`deque`。

stack 栈

堆栈，先进先出

stack<int> minStack;
minStack = stack<int>();

// 支持初始化，但是注意将整个数组元素推入堆栈，堆栈的顶部元素top将是数组的第一个元素。
std::vector<int> elements = {1, 2, 3, 4, 5};
std::stack<int> myStack(elements.begin(), elements.end());

//增
s.push(x);  // 复制 x 到栈中
std::stack<std::pair<int, int>> s;
s.emplace(1, 2);  // 在栈中直接构造 std::pair<int, int> (1, 2)

//删
minStack.pop(); //该函数仅用于从堆栈中删除元素，并且没有返回值。因此，我们可以说该函数的返回类型为void。

//改

//查
!minStack.empty()
top_value = minStack.top();
stIn.size() //该函数返回堆栈容器的大小，该大小是堆栈中存储的元素数量的度量。

emplace VS push

push() adds a copy of an already constructed object into the queue as a parameter.

emplace() constructs a new object in-place at the end of the queue.

If your usage pattern is one where you create a new object and add it to the container, you shortcut a few steps(creation of a temporary object and copying it) by using emplace().

注意pop仅用于从堆栈中删除元素，并且没有返回值, 一般用法如下

top_value = stIn.top();
stIn.pop();

清空

stack不支持clear, 除开一个个pop

std::stack<int> myStack;
// 添加元素到 myStack

myStack = std::stack<int>(); // 清空 myStack, 丢弃原有对象

std::stack<int> emptyStack;
myStack.swap(emptyStack); // 清空 myStack

queue

队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；
在队尾添加元素，在队头删除元素。

#include <queue>

// 初始化
queue<int> q;

// 相对于stack的操作, 没有top(), 但新增
q.front()               返回队首元素的值，但不删除该元素
q.back()                返回队列尾元素的值，但不删除该元素

清空

直接用空的队列对象赋值

queue<int> q1;
// process
// ...
q1 = queue<int>();

使用swap，这种是最高效的，定义clear，保持STL容器的标准。

void clear(queue<int>& q) {
    queue<int> empty;
    swap(empty, q);
}

队列保存pair

queue<pair<int, int>> gq;
gq.push({ 10, 20 });

pair<int, int> p;
int x,y;
p = gq.front();
x = p.first;
y = p.second;

deque 双端队列

deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。

#include <deque>
using namespace std;
std::deque<int> d;

//相对于stack queue支持迭代器，前两者可以强制通过reinterpret_cast来使用迭代器
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。

size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。

at() 使用经过边界检查的索引访问元素。

front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。

insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素，容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。
// 但是对于原始数据需要提供类型
vec.emplace_back<std::array<int, 4>>({1,2,3,4});
// or
vec.emplace_back(std::array<int, 4>{{1, 2, 3, 4}});

priority_queue(优先队列)

自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队
默认利用max-heap（大顶堆）完成对元素的排序，是以vector为表现形式的complete binary tree（完全二叉树）。
基本操作和queue一样。

初始化

#include <queue>
priority_queue<Type, Container, Functional>

Type 就是数据类型，
Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），
Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

排序规则

//降序队列(默认less<>), map/set默认也是使用less，但是是升序序列
priority_queue <int>q;
priority_queue <int,vector<int>,less<int> >q;
//升序队列
priority_queue <int,vector<int>,greater<int> > q;

自定义降序1 : class & struct

class _c{
public:
    bool operator () (const pair<int, int> &p, const pair<int, int> &q) const {
        return p.first < q.first;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, _c> pq;

struct Compare {
    bool operator()(const std::pair<TimeType, ipType>& a, const std::pair<TimeType, ipType>& b) const {
        if (a.first == b.first)
            return a.second < b.second;  // 第一元素相等时按第二元素降序
        return a.first > b.first;         // 第一元素按升序排列
    }
};
class MyClass {
public:
    std::priority_queue<std::pair<TimeType, ipType>, std::vector<std::pair<TimeType, ipType>>, Compare> _arpQueue;
};

自定义降序2 : decltype

class MyClass {
public:
    // 比较函数作为静态成员函数
    static bool cmp(const std::pair<TimeType, ipType>& a, const std::pair<TimeType, ipType>& b) {
        if (a.first == b.first)
            return a.second < b.second;  // 第一元素相等时按第二元素降序
        return a.first > b.first;         // 第一元素按升序排列
    }

    // 使用比较函数指针初始化优先队列
    std::priority_queue<std::pair<TimeType, ipType>, std::vector<std::pair<TimeType, ipType>>, decltype(&MyClass::cmp)> _arpQueue{cmp};
};

other

//自定义降序2
auto cmp = [](pair<int,int>&a, pair<int,int>&b){return a.second<=b.second;};
priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> q(cmp);

单链表（自定义）

一般是题目要求自己实现链表，而不是使用STL提供的链表list。

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

ListNode* head = new ListNode(5);
//或者
ListNode* head = new ListNode();
head->val = 5;

while(result != nullptr && result->val == val){
    ListNode* tmp_free = result;
    result = result->next;
    delete tmp_free; // 注意释放空间
}

nullptr 关键字

nullptr是一个关键字，可以在所有期望为NULL的地方使用。

与NULL一样，可与任何指针类型相比较。
与NULL不同，只能被赋值给指针类型，它不能隐式转换，也不能与整型相比较。与NULL通常被定义为整数0的宏定义之间来区分。

list 双向链表

STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。

特点：
- 可以看到，list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
- vector是连续的容器，而list是非连续的容器，即vector将元素存储在连续的存储器中，而list存储在不连续的存储器中。
优点: list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势
- 可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。
- 并且在 list 容器中移动元素，也比其它容器的效率高。
缺点
- 不能像 array 和 vector 那样，通过位置直接访问元素。
  - 举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，
- 也不支持find()语法，经常使用unorder_map<key, list<xxx>::iterator> listMap保存元素位置来加速查找。
  - 正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。for (it = list.begin(); it != list.end(); it++) if (it->key == key) break;
- 应用场景：需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。

//插入
push_front：在链表头部插入元素。
emplace_front(value_type&& val)
push_back：在链表尾部插入元素。
emplace_back(value_type&& val)
insert：在指定位置插入元素。list1.insert(list1.begin(), 0);
emplace(iterator pos, value_type val)

//删除
pop_front：删除链表头部的元素。
pop_back：删除链表尾部的元素。
erase：删除指定位置的元素。
remove：删除所有匹配的元素。
clear：清空链表。

//查询
size：返回链表的大小。
empty：检查链表是否为空。
front：返回链表的第一个元素。
back：返回链表的最后一个元素。
reverse：反转链表。
sort：对链表进行排序。

LRU 最久未被命中

LRU需要更新数据结构中的元素信息，并且简单排序(就一个类时间的单指标)。
- 关联容器：虽然map，set能自动排序，但是是对key，不符合当前场景。
- 顺序容器：vector，list，deque。
  - priority_queue：可以排序，但是不能更新。
信息包括，ID 和类似timeTag的顺序。
- 可以使用list，从中间找到(unorder_map加速)，直接插在末尾，利用线性的顺序和list修改中间元素的快速。
- 如果排序算法变复杂，可以用sort(list.begin(), list.end(), cmp)。

数组

int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };

数组 int a[1000] = {0}; 的分配位置

在 C/C++ 中，数组 int a[1000] = {0}; 的分配位置取决于它的声明位置。具体来说：

栈上（Stack）：
如果数组是在函数内部声明的，并且不是 static 类型，那么它会被分配在栈上。
栈上的内存分配速度快，但栈的大小有限，通常为几 MB 到几十 MB，具体取决于操作系统和编译器设置。
静态区（Static）：
如果数组是在全局作用域中声明的，或者在函数内部声明为 static 类型，那么它会被分配在静态区。
静态区的内存分配在程序启动时完成，持续到程序结束，不会在每次函数调用时重新分配。
堆上（Heap）：
如果数组是通过动态内存分配函数（如 malloc、calloc、new 等）分配的，那么它会被分配在堆上。
堆上的内存分配和释放速度较慢，但堆的大小通常比栈大得多。

总结

栈上：函数内部声明的非 static 数组。
静态区：全局声明的数组或函数内部声明的 static 数组。
堆上：通过动态内存分配函数（如 malloc、calloc、new）分配的数组。

初始化为0

//直接初始化为0
int a[SIZE]={0};

#include<string.h>
int a[SIZE];
memset(a, 0, sizeof(a));
memset(a, 0, sizeof(int)*1000);//这里的1000是数组大小，需要多少替换下就可以了。

注意 memset是按照字节进行赋值，即对每一个字节赋相同值。除开0和-1，其他值都是不安全的，不会赋值期望的值。比如int是四个字节。

memset（a，127，sizeof（a）），全部初始化为int的较大值，即2139062143(int 最大值为2147483647)；
memset（a，128，sizeof（a）），全部初始化为一个很小的数，比int最小值略大，为-2139062144。

calloc & malloc

//区分
//calloc() 函数是动态申请内存函数之一，相当于用malloc函数申请并且初始化一样，calloc函数会将申请的内存全部初始化为0。
int *res = (int*)calloc(numsSize, sizeof(int));
//方法二：
int *res = (int*)malloc(numsSize * sizeof(int));
memset(res, 0, numsSize * sizeof(int));
//错误写法： memset(res, 0, sizeof(res)); res是指针变量，不管 res 指向什么类型的变量，sizeof( res ) 的值都是 4。

new的常见用法

int *p = new int();//此时p指向内存的单变量被初始化为0
int *p = new int (5);//此时p指向内存的单变量被初始化为5
int *p = new int[100]()//此时p指向数组首元素，且数组元素被初始化为0
//c++11 允许列表初始化，因此也有了以下几种形式形式
int *p = new int{}//p指向的单变量被初始化为0
int *p = new int{8}//p指向变量被初始化为8
int *p = new int[100]{}//p指向的数组被初始化为0
int *p = new int[100]{1,2,3}//p指向数组的前三个元素被初始化为1，2，3，后边97个元素初始化为0；

new 三维数组

建议老实用vector

int ***array;
// 假定数组第一维为 m， 第二维为 n， 第三维为h
// 动态分配空间
array = new int **[m];
for( int i=0; i<m; i++ )
{
    array[i] = new int *[n];
    for( int j=0; j<n; j++ )
    {
        array[i][j] = new int [h];
    }
}
//释放
for( int i=0; i<m; i++ )
{
    for( int j=0; j<n; j++ )
    {
        delete[] array[i][j];
    }
    delete[] array[i];
}
delete[] array;

Leetcode support VLA

The C++ standard does not officially support Variable Length Arrays (VLA), but some compilers, such as g++ and Clang++, may accept it as valid syntax as an extension to the language.
leetcode uses g++ 5.4.0 compiler for C++ compilation. It supports variable length array definitions. After ISO C99 specification, arrays with variable length declarations are allowed.
- The storage is allocated at the point of declaration and deallocated when the block scope containing the declaration exits.
And memory consumption differ significantly.

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];

array

与数组同样,array对象的长度也是固定的,
分配空间的规则也与数组类似，
其效率与数组相同,但更方便,更安全。

#include <array>

// array<typeName, nElem> arr;
array<int, 5> ai;
array<double, 4> ad = {1.1,1.2,1.2,1.3};

//通过如下创建 array 容器的方式，可以将所有的元素初始化为 0 或者和默认元素类型等效的值：
std::array<double, 10> values {};
//使用该语句，容器中所有的元素都会被初始化为 0.0。

//二维
std::array<std::array<int, 2>, 3> m = { {1, 2}, {3, 4}, {5, 6} };

vector

vector是变长的连续存储：

对于简单的类型，是直接存储
对于复杂的类，存储的是，该元素的信息（比如新构造元素的begin地址,end地址,capacity信息)

打印不同类型的vector存储内容的地址

vector<vector<int>> v2d(3,vector<int>(0));      // 间隔 6 个int
// vector<set<int>> v2d(3);                     // 间隔 12 个int 
// vector<unordered_set<int>> v2d(3);           // 间隔 14 个int 
// vector<map<int,int>> v2d(3);                 // 间隔 12 个int 
// vector<unordered_map<int,int>> v2d(3);       // 间隔 14 个int 

const int STEP = 6;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
    for(int j=0; j<STEP; j++)
        cout << " " << hex << *(int *)((void *)(&v2d[i])+j*4);
    cout << endl;
}

// add elements to v2d[0]
const int ADDNUM = 10;
for(int i = 0; i<ADDNUM; i++){
    v2d[0].emplace_back(2);
    // v2d[0].insert(i);
    // v2d[0][i]=i*i;
}

// check the space change
cout << "Ele[0] size : " << v2d[0].size() << endl;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
}

//check ele[0] location
cout << endl;
for(int i = 0; i<ADDNUM; i++){
    cout << " " << &v2d[0][i];
}

vector具体底层实现

（1）扩容

vector的底层数据结构是数组。

当vector中的可用空间耗尽时，就要动态第扩大内部数组的容量。直接在原有物理空间的基础上追加空间？这不现实。数组特定的地址方式要求，物理空间必须地址连续，而我们无法保证其尾部总是预留了足够空间可供拓展。一种方法是，申请一个容量更大的数组，并将原数组中的成员都搬迁至新空间，再在其后方进行插入操作。新数组的地址由OS分配，与原数据区没有直接的关系。新数组的容量总是取作原数组的两倍。

（2）插入和删除

插入给定值的过程是，先找到要插入的位置，然后将这个位置（包括这个位置）的元素向后整体移动一位，然后将该位置的元素复制为给定值。删除过程则是将该位置以后的所有元素整体前移一位。

（2）vector的size和capacity

size指vector容器当前拥有的元素个数，capacity指容器在必须分配新存储空间之前可以存储的元素总数，capacity总是大于或等于size的。

size() – 返回目前存在的元素数。即： 元素个数
capacity() – 返回容器能存储 数据的个数。 即：容器容量
reserve() --设置 capacity 大小
resize() --设置 size ，重新指定有效元素的个数 ，区别与reserve()指定 容量的大小
clear() --清空所有元素，把size设置成0，capacity不变

针对capacity这个属性，STL中的其他容器，如list map set deque，由于这些容器的内存是散列分布的，因此不会发生类似realloc()的调用情况，因此我们可以认为capacity属性针对这些容器是没有意义的，因此设计时这些容器没有该属性。

在STL中，拥有capacity属性的容器只有vector和string。

array,vector与数组的区别

共同点

（1.）都和数组相似，都可以使用标准数组的表示方法来访问每个元素（array和vector都对下标运算符[ ]进行了重载）

（2.）三者的存储都是连续的，可以进行随机访问

不同点

（0.）数组是不安全的，array和vector是比较安全的（有效的避免越界等问题）

（1.）array对象和数组存储在相同的内存区域（栈）中，vector对象存储在自由存储区（堆）malloc和new的空间也是在堆上，原因是栈的空间在编译代码的时候就要确定好，堆空间可以运行时分配。

（2.）array可以将一个对象赋值给另一个array对象，但是数组不行

（3.）vector属于变长的容器，即可以根据数据的插入和删除重新构造容器容量；但是array和数组属于定长容器

（4.）vector和array提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，使得访问更加安全。而数组只能通过下标访问，在写程序中很容易出现越界的错误

（5.）vector和array提供了更好的遍历机制，即有正向迭代器和反向迭代器

（6.）vector和array提供了size()和Empty()，而数组只能通过sizeof()/strlen()以及遍历计数来获取大小和是否为空

（7.）vector和array提供了两个容器对象的内容交换，即swap()的机制，而数组对于交换只能通过遍历的方式逐个交换元素

（8.）array提供了初始化所有成员的方法fill（）

（9.）由于vector的动态内存变化的机制，在插入和删除时，需要考虑迭代的是否有效问题

（10.）vector和array在声明变量后，在声明周期完成后，会自动地释放其所占用的内存。对于数组如果用new[ ]/malloc申请的空间，必须用对应的delete[ ]和free来释放内存

初始化

//创建一个vector,元素个数为nSize
vector(int nSize)

//指定值初始化，ilist5被初始化为包含7个值为3的int
//vector(int nSize,const t& t)
//创建一个vector，元素个数为nSize,且值均为t
vector<int> ilist5(7,3);

//区分列表初始化, 包含7 和 3两个元素
vector<int> ilist5{7,3};

array 与 vector 默认初始化

std::array 和 std::vector 的默认初始化：
对于基本数据类型，未显式初始化的元素会被初始化为 0。
对于类类型，未显式初始化的元素会调用默认构造函数进行初始化。
未初始化：
如果你使用 new 或其他方式动态分配内存并且没有显式初始化，那么这些元素将包含未定义的值（即“乱码”）。

//改变大小,预分配空间,增加 vector 的容量（capacity），但 size 保持不变。
vals.reserve(cnt.size());
// 将 vector 大小调整为 10，用 0 填充新位置
vec.resize(10, 0);

二维vector

// 二维vector, 两个维度的长度都未知时：
std::vector<std::vector<int>> matrix;

// 假设我们知道行数，但列数未知
int numRows = 3;

// 预先分配行数
matrix.resize(numRows);

// 动态添加列
matrix[0].push_back(1);
matrix[0].push_back(2);
matrix[1].push_back(3);
matrix[1].push_back(4);
matrix[2].push_back(5);

其余情况

//已知一个维度，第二维度为空
// vector<vector<bool>> name (xSize, vector<bool>(ySize, false));
vector<vector<int>> alphaIndexList{26, vector<int>(0)};

//或者
vector<int> alphaIndexList[26];
alphaIndexList[i].push_back(x);

//两个都不知道 ，也可以使用指针
vector<int>* todo;
todo= &alphaIndexList[i];
int n = todo->size(); // (*todo).size();
for(auto &x: *todo)

增加

vector 也支持中间insert元素，但是性能远差于list。

void push_back(const T& x)      //向量尾部增加一个元素X
void emplace_back(const T& x)
//iterator insert(iterator it,const T& x)   :向量中迭代器指向元素前增加一个元素x
result.insert(result.begin()+p,x);     :在result的index为p的位置插入元素
iterator insert(iterator it,int n,const T& x) :向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

删除

iterator erase(iterator it)     :删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back()        :删除向量中最后一个元素
void clear()        :清空向量中所有元素

修改

void swap(vector&)    :交换两个同类型向量的数据
void assign(int n,const T& x) :设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

#include <algorithm> //或者#include <bits/stdc++.h>
reverse(a.begin(), a.end());
std::reverse(a,a+5);  //转换0～5下标的元素

元素排序

如果需要元素有序，考虑stable_sort

#include <algorithm>  // 包含 sort 函数
#include <functional> // 包含 std::greater 比较器

//默认是从低到高，加入std::greater<int>() 变成从高到低排序
sort(nums.begin(),nums.end(),std::greater<int>());

//vector of pair
vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};

//c++11 using lambda and auto
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});
// or
sort(arr.begin(), arr.end(),
    [](const pair<int, char> & p1, const pair<int, char> & p2) {
    return p1.first > p2.first;
    }
);

//origin
struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};
std::sort(v.begin(), v.end(), sort_pred());

片段的截取

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arrs2(First, Second); // 将值直接初始化到Arrs2

迭代器是指可在容器对象上遍访的对象

或者assign()功能函数实现截取

assign() 功能函数是vector容器的成员函数。原型：

1:void assign(const_iterator first,const_iterator last);//两个指针，分别指向开始和结束的地方 2:void assign(size_type n,const T& x = T()); //n指要构造的vector成员的个数， x指成员的数值，他的类型必须与vector类型一致！

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arr2;
Arr2.assign(First,Second); //使用assign() 成员函数将Arrs对应位置的值存入Arrs2数组中

查找

reference at(int pos)  :返回pos位置元素的引用
reference front()   :返回首元素的引用
reference back()   :返回尾元素的引用
iterator begin()   :返回向量头指针，指向第一个元素
iterator end()    :返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin() :反向迭代器，指向最后一个元素
reverse_iterator rend()  :反向迭代器，指向第一个元素之前的位置

// 判断函数
bool empty() const   :判断向量是否为空，若为空，则向量中无元素

// 大小函数
int size() const  :返回向量中元素的个数
int capacity() const :返回当前向量所能容纳的最大元素值
int max_size() const :返回最大可允许的vector元素数量值

其余

返回表示

vector<int> func() {
    //sth
    return {it->second, i}; //no []
    //or
    return {};
}

hash 哈希

#include<functional>
auto hash_p = [](const pair<int, int> &p) -> size_t {
            static hash<long long> hash_ll;
            return hash_ll(p.first + (static_cast<long long>(p.second) << 32));//64位高低一半存储x和y
        };

static_cast 用于良性类型转换，一般不会导致意外发生，风险很低。

hash <K> 模板专用的算法取决于实现，但是如果它们遵循 C++14 标准的话，需要满足一些具体的要求。这些要求如下：

不能拋出异常
对于相等的键必须产生相等的哈希值
对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

参考文献

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

【C++容器】数组和vector、array三者区别和联系 https://blog.51cto.com/liangchaoxi/4056308

https://blog.csdn.net/y601500359/article/details/105297918

How to use unordered_set with custom types? ↩↩↩

2023年9月21日
分类于 Programming
需要 2 分钟阅读时间

Java

Just-In-Time (JIT) 编译器

JIT编译器是一种动态编译技术，它将程序的一部分或者全部源代码或更常见的字节码在运行时编译成机器码，然后将编译后的代码替换原来的代码。
字节码（英语：Bytecode）通常指的是已经经过编译，但与特定机器代码无关，需要解释器转译后才能成为机器代码的中间代码(多为虚拟机代码)。典型应用为Java虚拟机里的Java bytecode。
主要优点是可以在运行时根据程序的运行情况进行优化，从而提高程序的执行效率。
字节码编译是跨平台的，便于移植的。
主要缺点是编译字节码导致的延迟和空间开销较大，因此只有在程序运行时间较长的情况下才能体现出优势。
是提前编译（AOT）和字节码解释器(python的实现)的结合体，它的执行效率介于两者之间。

区别

Java Virtual Machine (JVM) is an abstract computing machine.
Java Runtime Environment (JRE) is an implementation of the JVM.
Java Development Kit (JDK) contains JRE along with various development tools like Java libraries, Java source compilers, Java debuggers, bundling and deployment tools.
Java SE: Java™ Platform Standard Edition 21 Development Kit - JDK™ 21
Just In Time compiler (JIT) is runs after the program has started executing, on the fly. It has access to runtime information and makes optimizations of the code for better performance.

Install

Intall for topcoder

chinese ref

download from website
But the first download choice java 21 SDK seems not contain Java Control Panel (javacpl.exe), you need to install Java SE Development Kit 8u381 which include JDK 1.8 and JRE 1.8
config Java Control Panel, add https://www.topcoder.com to allowed website (Attention: https)
open ContestAppletProd.jnlp
need 127.0.0.1 proxy and HTTP TUNE 1 to connect to server

Python: DataStructure

check if it is empty?

strings, lists, tuples

# Correct:
if not seq:
if seq:

# Wrong:
if len(seq):
if not len(seq):

debug

try:
    # sth
except Exception as e:
    pprint.pprint(list)
    raise e
finally:
    un_set()

for

step

调参需要测试间隔值

for i in range(1, 101, 3):
    print(i)

遍历修改值

使用 enumerate 函数结合 for 循环遍历 list，以修改 list 中的元素。
enumerate 函数返回一个包含元组的迭代器，其中每个元组包含当前遍历元素的索引和值。在 for 循环中，我们通过索引 i 修改了列表中的元素。

# 对于 二维list appDataDict
baseline = appDataDict[0][0] # CPU Total
for i, line in enumerate(appDataDict):
    for j, entry in enumerate(line):
        appDataDict[i][j] = round(entry/baseline, 7)

itertools

itertools --- 为高效循环而创建迭代器的函数

for a,b,c in permutations((a,b,c)):

String 字符串

%c  格式化字符及其ASCII码
%s  格式化字符串
%d  格式化整数
%u  格式化无符号整型
%o  格式化无符号八进制数
%x  格式化无符号十六进制数
%X  格式化无符号十六进制数（大写）
%f  格式化浮点数字，可指定小数点后的精度
%e  用科学计数法格式化浮点数
%E  作用同%e，用科学计数法格式化浮点数
%g  %f和%e的简写
%G  %F 和 %E 的简写
%p  用十六进制数格式化变量的地址

print("My name is %s and weight is %d kg!" % ('Zara', 21))

string <-> list

' '.join(pass_list) and pass_list.split(" ")

对齐"\n".join(["%-10s" % item for item in List_A])

字符串开头判断

text = "Hello, world!"

if text.startswith("Hello"):
    print("The string starts with 'Hello'")
else:
    print("The string does not start with 'Hello'")

format 格式化函数

Python2.6 开始，通过 {} 和 : 来代替以前的 %

>>>"{} {}".format("hello", "world")    # 不设置指定位置，按默认顺序
'hello world'

>>> "{1} {0} {1}".format("hello", "world")  # 设置指定位置
'world hello world'

# 字符串补齐100位，<表示左对齐
variable = "Hello"
padded_variable = "{:<100}".format(variable)

数字处理

print("{:.2f}".format(3.1415926)) # 保留小数点后两位

{:>10d} 右对齐 (默认, 宽度为10)
{:^10d} 中间对齐 (宽度为10)

容器：List

https://www.runoob.com/python/python-lists.html

初始化以及访问

list = ['physics', 'chemistry', 1997, 2000]
list = []          ## 空列表
print(list[0])

切片

格式：[start_index:end_index:step]

不包括end_index的元素

二维数组

list_three = [[0 for i in range(3)] for j in range(3)]

//numpy 创建连续的，可自动向量化，线程并行
import numpy as np
# 创建一个 3x4 的数组且所有值全为 0
x3 = np.zeros((3, 4), dtype=int)
# 创建一个 3x4 的数组，然后将所有元素的值填充为 2
x5 = np.full((3, 4), 2, dtype=int)

size 大小

len(day)

排序

# take second element for sort
def takeSecond(elem):
    return elem[2]

LCData.sort(key=takeSecond)

# [1740, '黄业琦', 392, '第 196 场周赛'],
# [1565, '林坤贤', 458, '第 229 场周赛'],
# [1740, '黄业琦', 458, '第 229 场周赛'],
# [1509, '林坤贤', 460, '第 230 场周赛'],
# [1740, '黄业琦', 460, '第 230 场周赛'],
# [1779, '黄业琦', 558, '第 279 场周赛'],

对应元素相加到一个变量

tmp_list = [[],[],[],[]]
# 注意不需要右值赋值
[x.append(copy.deepcopy(entry)) for x,entry in zip(tmp_list, to_add)]

两个list对应元素相加

对于等长的

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = [x + y for x, y in zip(list1, list2)]
print(result)

如果两个列表的长度不同，你可以使用zip_longest()函数来处理它们。zip_longest()函数可以处理不等长的列表，并使用指定的填充值填充缺失的元素。

from itertools import zip_longest

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8]

result = [x + y for x, y in zip_longest(list1, list2, fillvalue=0)]
print(result)

如果是二维list

list1 = [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]]

list2 = [[10, 11, 12],
         [13, 14, 15]]

rows = max(len(list1), len(list2))
cols = max(len(row) for row in list1 + list2)

result = [[0] * cols for _ in range(rows)]

for i in range(rows):
    for j in range(cols):
        if i < len(list1) and j < len(list1[i]):
            result[i][j] += list1[i][j]
        if i < len(list2) and j < len(list2[i]):
            result[i][j] += list2[i][j]

print(result)

# 将一个二维列表的所有元素除以一个数A
result = [[element / A for element in row] for row in list1]

直接赋值、浅拷贝和深度拷贝

Python append() 与深拷贝、浅拷贝

python赋值只是引用，别名

list.append('Google')   ## 使用 append() 添加元素
alist.append( num ) # 浅拷贝 ，之后修改num 会影响alist内的值

import copy
alist.append( copy.deepcopy( num ) ) # 深拷贝

# delete
del list[2]

for循环迭代的元素也是引用

original_list = [1, 2, 3]

for item in original_list:
    item *= 2 # 每个元素是不可变的

print(original_list) 

original_list = [[1,2,3], [2], [3]]

for item in original_list:
    item.append("xxx") # 每个元素是可变的

print(original_list) 

# [1, 2, 3]
# [[1, 2, 3, 'xxx'], [2, 'xxx'], [3, 'xxx']]

函数传参是引用，但是能通过切片来得到类似指针

参数的传递函数声明时的形参，使用时，等同于函数体内的局部变量。由于Python中一切皆为对象。因此，参数传递时直接传递对象的地址，但具体使用分两种类型： 1.传递不可变对象的引用（起到其他语言值传递的效果）数字，字符串，元组，function等 2.传递可变对象的引用（起到其他语言引用传递的效果）字典，列表，集合，自定义的对象等

def fun0(a):
    a = [0,0] # a在修改后，指向的地址发生改变，相当于新建了一个值为[0,0]

def fun(a):
    a[0] = [1,2]

def fun2(a):
    a[:] = [10,20]

b = [3,4]
fun0(b)
print(b)
fun(b)
print(b)
fun2(b)
print(b)

# [3, 4]
# [[1, 2], 4]
# [10, 20]

return 返回值

可变的也是引用

def fun1(l):
    l.append("0")
    return l 

def fun2(l):
    return l

if __name__=="__main__":
    l = [1,2,3,4,5]

    rel2 = fun2(l)
    print(rel2)   
    rel1 = fun1(l)
    print(rel1)   
    print(rel2)   
    l.append("xxx")
    print(rel1)   
    print(rel2)   
    del rel1[2]
    print(rel1)   
    print(rel2)  

# [1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5, '0']
# [1, 2, 3, 4, 5, '0']
# [1, 2, 3, 4, 5, '0', 'xxx']
# [1, 2, 3, 4, 5, '0', 'xxx']
# [1, 2, 4, 5, '0', 'xxx']
# [1, 2, 4, 5, '0', 'xxx']

容器：元组Tuple

元组和列表类似，但是不同的是元组不能修改，但可以对元组进行连接组合，元组使用小括号。
元组中只包含一个元素时，需要在元素后面添加逗号，否则括号会被当作运算符使用。

#创建元组
tup = (1, 2, 3, 4, 5)
tup1 = (23, 78);
tup2 = ('ab', 'cd')
tup3 = tup1 + tup2

容器：Dict

empty dict

a= {}
a=dict()

key 支持tuple元组

类似c++ 的 pair<int,int>

bblHashDict[(tmpHigherHash,tmpLowerHash)]=tmpBBL

但是这样就不支持json.dump， json.dump() 无法序列化 Python 中元组(tuple)作为字典的 key，这会导致 json.dump() 函数在写入此类字典数据时会进入死循环或陷入卡住状态

初始化以及访问

>>> tinydict = {'a': 1, 'b': 2, 'b': '3'}
>>> tinydict['b']
'3'

a_dict = {'color': 'blue'}
for key in a_dict:
 print(key)
# color
for key in a_dict:
    print(key, '->', a_dict[key])
# color -> blue
for item in a_dict.items():
    print(item)
# ('color', 'blue')
for key, value in a_dict.items():
 print(key, '->', value)
# color -> blue

size 大小

len(day)

修改以及添加

tinydict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

tinydict['Age'] = 8 # 更新
tinydict['School'] = "RUNOOB" # 添加

合并

dict1 = {'a': 10, 'b': 8} 
dict2 = {'d': 6, 'c': 4} 

# dict2保留了合并的结果
dict2.update(dict1)
print(dict2)
{'d': 6, 'c': 4, 'a': 10, 'b': 8}

删除

del tinydict['Name']  # 删除键是'Name'的条目
tinydict.clear()      # 清空字典所有条目
del tinydict          # 删除字典

print by key

from pprint import pprint
pprint

容器：set

无序不重复序列

初始化

a=  set() # 空set

thisset = set(("Google", "Runoob", "Taobao"))
>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # 这里演示的是去重功能

list2set

setL=set(listV)

set2list

my_set = {'Geeks', 'for', 'geeks'}

s = list(my_set)
print(s)
# ['Geeks', 'for', 'geeks']

添加

thisset.add("Facebook")

合并

x = {"apple", "banana", "cherry"}
y = {"google", "runoob", "apple"}

z = x.union(y) 

print(z)
# {'cherry', 'runoob', 'google', 'banana', 'apple'}

删除与清空

s.remove( x )
a.clear()

修改原本的值

修改传入参数

在Python中,函数的参数是按值传递的,也就是说在函数内部修改参数不会影响到函数外部的变量。

但是有几种方法可以实现类似修改参数的效果:

返回修改后的值,在函数外部重新赋值

def func(x):
    x = x + 1 
    return x

a = 10
a = func(a) 
print(a) # 11

使用可变对象作为参数,修改可变对象的内部值

def func(lst):
    lst.append(1)

lst = [1,2,3]
func(lst)
print(lst) # [1,2,3,1]

这里lst是列表,在func内部修改了lst,由于lst是可变的,所以函数外部的lst也被修改了。

使用全局变量

count = 0
def func():
    global count
    count += 1

func()
print(count) # 1

通过global关键字声明count为全局变量,这样就可以在函数内部修改全局变量count了。

所以要修改传入参数的值,主要的方法是:

返回修改后的值并重新赋值
传入一个可变对象并修改可变对象内部的值
使用全局变量

这些技巧可以实现模拟修改参数的效果。

修改for循环对象

在Python中,for循环遍历的是一个迭代器,每次循环会将迭代器的下一个元素赋值给循环变量。

如果想在for循环内部修改迭代器中的元素,可以使用以下方法:

将迭代器转换成列表,然后修改列表中的元素:

all_for_one = ['a', 'b', 'c']

for app_info in list(all_for_one):
    if app_info == 'b':
        all_for_one[1] = 'x' 

print(all_for_one) # ['a', 'x', 'c']

这里通过list()将迭代器转成列表,然后修改列表的元素。

使用循环的索引而不是直接使用元素:

all_for_one = ['a', 'b', 'c']

for i in range(len(all_for_one)):
    if i == 1:
        all_for_one[i] = 'x'

print(all_for_one) # ['a', 'x', 'c']

通过索引 i 来访问并修改元素。

使用enumerate()在循环中获取索引:

all_for_one = ['a', 'b', 'c']

for i, app_info in enumerate(all_for_one):
    if i == 1:
        all_for_one[i] = 'x'

print(all_for_one) # ['a', 'x', 'c']

enumerate()可以同时迭代索引和元素。

所以主要思路就是不直接修改循环变量,而是通过索引或临时列表来修改迭代器中的原始元素。

修改for循环的对象 set

对于 set 这样的不可变对象,不能直接通过索引或者 enumerate 来修改,因为 set 对象不支持索引和切片操作。

对于 set,可以使用以下方法在循环内部进行修改:

将 set 转换成 list,修改后再转换回 set

s = {'a', 'b', 'c'}

for item in list(s):
    if item == 'b':
        s = list(s)
        s[1] = 'x'
        s = set(s)

print(s) # {'a', 'x', 'c'}

创建一个新的 set,在循环中添加修改后的元素

s = {'a', 'b', 'c'}
new_s = set()

for item in s:
    if item == 'b':
        new_s.add('x')
    else:
        new_s.add(item)

s = new_s

print(s) # {'a', 'x', 'c'}

使用 set 的discard()和add()方法在循环中修改

s = {'a', 'b', 'c'}

for item in s:
    if item == 'b':
        s.discard(item)
        s.add('x')

print(s) # {'a', 'x', 'c'}

上面这些方法的关键思路都是:

将不可变对象设置转换成可变类型
在循环中针对可变类型进行修改
再转换回不可变 Set 对象

这样就可以实现循环中修改 Set 的效果。

参考文献

https://blog.csdn.net/weixin_63719049/article/details/125680242

2023年7月28日
分类于 Programming
需要 2 分钟阅读时间

PythonRegex

pattern

^   匹配字符串的开头
$   匹配字符串的末尾。
.   匹配任意字符，除了换行符
a| b    匹配a或b
[a-zA-Z0-9] 匹配任何字母及数字
\d  匹配数字。等价于[0-9]。
[aeiou] 匹配中括号内的任意一个字母
[^aeiou]    除了aeiou字母以外的所有字符
\w  匹配包括下划线的任何单词字符。等价于'[A-Za-z0-9_]'。
(\s*) 或者 ([\t ]*)     来匹配任意TAB和空格的混合字符

\s  匹配任何空白字符，包括空格、制表符、换页符等等。等价于 [ \f\n\r\t\v]。
\S  匹配任何非空白字符。等价于 [^ \f\n\r\t\v]。
\b  匹配一个单词边界，也就是指单词和空格间的位置。例如， 'er\b' 可以匹配"never" 中的 'er'，但不能匹配 "verb" 中的 'er'。
\B  匹配非单词边界。'er\B' 能匹配 "verb" 中的 'er'，但不能匹配 "never" 中的 'er'。

重复

re* 匹配0个或多个的表达式。
re+ 匹配1个或多个的表达式。
re? 匹配0个或1个由前面的正则表达式定义的片段，非贪婪方式
re{ n}  精确匹配 n 个前面表达式。
        例如， o{2} 不能匹配 "Bob" 中的 "o"，
        但是能匹配 "food" 中的两个 o。
re{ n,} 匹配 n 个前面表达式。
        例如， o{2,} 不能匹配"Bob"中的"o"，
        但能匹配 "foooood"中的所有 o。
        "o{1,}" 等价于 "o+"。
        "o{0,}" 则等价于 "o*"。
re{ n, m}   匹配 n 到 m 次由前面的正则表达式定义的片段，贪婪方式

match exactlly str

# find should use \ to represent the (6|12|3)
$ find ~/github/gapbs/ -type f -regex '.*/kron-\(6\|12\|3\).*'
/staff/shaojiemike/github/gapbs/kron-12.wsg
/staff/shaojiemike/github/gapbs/kron-3.sg
/staff/shaojiemike/github/gapbs/kron-3.wsg
/staff/shaojiemike/github/gapbs/kron-6.sg
/staff/shaojiemike/github/gapbs/kron-6.wsg

re.match与re.search的区别

re.match只匹配字符串的开始，如果字符串开始不符合正则表达式，则匹配失败，函数返回None；

而re.search匹配整个字符串，直到找到一个匹配。

re.match函数

从字符串的起始位置匹配

re.match(pattern, string, flags=0)

flags

多个标志可以通过按位 OR(|) 它们来指定。如 re.I | re.M被设置成 I 和 M 标志：

re.I    使匹配对大小写不敏感
re.M    多行匹配，影响 ^ 和 $
re.S    使 . 匹配包括换行在内的所有字符

group

matchObj = re.match( r'(.*) are (.*?) .*', line, re.M|re.I)

if matchObj:
   print "matchObj.group() : ", matchObj.group()
   print "matchObj.group(1) : ", matchObj.group(1)
   print "matchObj.group(2) : ", matchObj.group(2)
else:
   print "No match!!"

打印部分内容

matchObj.group() :  Cats are smarter than dogs
matchObj.group(1) :  Cats
matchObj.group(2) :  smarter

findall

返回元组，可以指定开始，与结束位置。

result = re.findall(r'(\w+)=(\d+)', 'set width=20 and height=10')
print(result)
# [('width', '20'), ('height', '10')]

实例：objdump结果只提取汇编的命令

import re      
# 打开x86汇编代码文件
with open(assembly) as f:
        # 读取文件内容
        content = f.read()

# 使用正则表达式匹配所有汇编指令，
pattern = r'\b([a-zA-Z]{3,6})\b.*'
# 匹配pattern，但是只将()内结果保存在matches中
matches = re.findall(pattern, content)

# 输出匹配结果
for match in matches:
        print(match)

参考文献

https://blog.csdn.net/weixin_39594191/article/details/111611346

https://www.runoob.com/python/python-reg-expressions.html

2023年7月24日
分类于 Programming
需要 2 分钟阅读时间

Python Class

简介

Python从设计之初就已经是一门面向对象的语言，正因为如此，在Python中创建一个类和对象是很容易的。

面向对象技术简介

类(Class): 用来描述具有相同的属性和方法的对象的集合。它定义了该集合中每个对象所共有的属性和方法。对象是类的实例。
实例化：创建一个类的实例，类的具体对象。
方法：类中定义的函数。
- 方法重写：如果从父类继承的方法不能满足子类的需求，可以对其进行改写，这个过程叫方法的覆盖（override），也称为方法的重写。
- 继承：即一个派生类（derived class）继承基类（base class）的字段和方法。继承也允许把一个派生类的对象作为一个基类对象对待。例如，有这样一个设计：一个Dog类型的对象派生自Animal类，这是模拟"是一个（is-a）"关系（例图，Dog是一个Animal）。
对象：通过类定义的数据结构实例。对象包括两个数据成员（类变量和实例变量）和方法。
- 类变量：类变量在整个实例化的对象中是公用的。类变量定义在类中且在函数体之外。类变量通常不作为实例变量使用。
- 实例变量：在类的声明中，属性是用变量来表示的。这种变量就称为实例变量，是在类声明的内部但是在类的其他成员方法之外声明的。

何时使用类

数据与操作紧密相关
对象有许多状态需要维护,可以使用类中的属性来保存状态。
需要生成多个仅在部分属性不同的实例,可以使用类作为模板。
不同对象存在公共parent-child的层次关系,可以使用继承来复用代码。
隐藏对象的实现细节,只对外公开接口。

类变量与实例变量

在Python中,类变量和实例变量是两个不同的概念:

类变量(Class Variable)
定义在类内部,但不在任何方法之内
被该类的所有实例对象所共享
可以通过类名或实例对象访问
用于定义与这个类相关的特征或属性
实例变量(Instance Variable)
定义在类内部的方法之内
每个实例对象拥有属于自己的变量副本
只能通过实例对象访问
用于定义实例对象的个性化特征或状态

例如:

class Person:

    species = 'Human' # 类变量

    def __init__(self, name):
        self.name = name # 实例变量

p1 = Person('John')
p2 = Person('Mary')

print(p1.species) # Human
print(p2.species) # Human 

print(p1.name) # John 
print(p2.name) # Mary

综上,类变量用于定义类的通用属性,实例变量用于定义实例的独特属性。区分二者是理解Python面向对象的关键。

创建

class Employee:
   '所有员工的基类'
   empCount = 0 # 类变量

   def __init__(self, name, salary):
      self.name = name
      self.salary = salary
      Employee.empCount += 1

   def displayCount(self):
     print "Total Employee %d" % Employee.empCount

   def displayEmployee(self):
      print "Name : ", self.name,  ", Salary: ", self.salary

类函数必有参数 ‘self’

必须有一个额外的第一个参数名称, 按照惯例它的名称是 self，self 不是 python 关键字，换成其他词语也行。

创建实例对象与访问

emp1 = Employee("Zara", 2000)
emp1.displayEmployee()

继承

通过继承创建的新类称为子类或派生类，被继承的类称为基类、父类或超类。

继承语法 class 派生类名(基类名)

调用基类

调用基类的方法时，需要加上基类的类名前缀，且需要带上 self 参数变量。区别在于类中调用普通函数时并不需要带上 self 参数 ,这点在代码上的区别如下:

class Base:
    def base_method(self):
        print("Base method")

class Derived(Base):
    def derived_method(self):
        # 调用基类方法要加类名前缀
        Base.base_method(self)

        # 调用普通函数
        print("Hello")  

d = Derived()
d.derived_method()

# 输出
Base method  
Hello

在Derived类中:

调用Base基类的方法base_method(),需要写成Base.base_method(self)
调用普通函数print(),直接写函数名即可

区别在于:

调用基类方法需要指明方法所属的基类
基类方法需要传入self,指代实例自己

而对于普通函数,只需要直接调用即可,不需要self参数。

这与Python的名称空间和面向对象实现有关,是理解Python类继承的关键点。

运算符重载

__init__ : 构造函数，在生成对象时调用
__del__ : 析构函数，释放对象时使用
__repr__ : 打印，转换
__setitem__ : 按照索引赋值
__getitem__: 按照索引获取值
__len__: 获得长度
__cmp__: 比较运算
__call__: 函数调用
__add__: 加运算
__sub__: 减运算
__mul__: 乘运算
__truediv__: 除运算
__mod__: 求余运算
__pow__: 乘方

+=

在Python中可以通过特殊方法__iadd__来对+=符号进行重载。

__iadd__需要定义在类中,用于指定+=操作时的具体行为。例如:

class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self

v1 = Vector(1, 2)
v2 = Vector(3, 4)

v1 += v2
print(v1.x, v1.y) # 4, 6

这里我们定义了__iadd__方法,用于实现两个Vector对象使用+=时的相加操作。

__iadd__方法的参数是另一个要相加的对象,在方法内部我们实现了两个向量的分量相加,并返回self作为结果。这样就实现了+=的运算符重载。

此外,Python还提供了__add__特殊方法用于重载+符号,但是__iadd__和__add__有以下区别:

__add__返回一个新的对象,不改变原有对象。
__iadd__在原有对象的基础上进行操作,并返回对原对象的引用。

所以对可变对象进行+=操作时,通常需要实现__iadd__方法。

参考文献

https://www.runoob.com/python/python-object.html

2023年7月21日
分类于 Programming
需要 2 分钟阅读时间

Language

面向过程 VS 面向对象

面向过程

面向过程是一种以事件为中心的编程思想，编程的时候把解决问题的步骤分析出来，然后用函数把这些步骤实现，在一步一步的具体步骤中再按顺序调用函数。

在日常生活或编程中，简单的问题可以用面向过程的思路来解决，直接有效，但是当问题的规模变得更大时，用面向过程的思想是远远不够的。所以慢慢就出现了面向对象的编程思想。世界上有很多人和事物，每一个都可以看做一个对象，而每个对象都有自己的属性和行为，对象与对象之间通过方法来交互。面向对象是一种以“对象”为中心的编程思想，把要解决的问题分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个对象在整个解决问题的步骤中的属性和行为。

优缺点

面向过程

优点：

流程化使得编程任务明确，在开发之前基本考虑了实现方式和最终结果，具体步骤清楚，便于节点分析。
效率高，面向过程强调代码的短小精悍，善于结合数据结构来开发高效率的程序。

缺点：

需要深入的思考，耗费精力，代码重用性低，扩展能力差，后期维护难度比较大。

面向对象

优点:

结构清晰，程序是模块化和结构化，更加符合人类的思维方式；
易扩展，代码重用率高，可继承，可覆盖，可以设计出低耦合的系统；
易维护，系统低耦合的特点有利于减少程序的后期维护工作量。

缺点：

开销大，当要修改对象内部时，对象的属性不允许外部直接存取，所以要增加许多没有其他意义、只负责读或写的行为。这会为编程工作增加负担，增加运行开销，并且使程序显得臃肿。
性能低，由于面向更高的逻辑抽象层，使得面向对象在实现的时候，不得不做出性能上面的牺牲，计算时间和空间存储大小都开销很大。

静态语言 vs 动态语言

Dynamic Programming Language (动态语言或动态编程语言)
动态语言，准确地说，是指程序在运行时可以改变其结构：新的函数可以被引进，已有的函数可以被删除等在结构上的变化。
比如众所周知的ECMAScript(JavaScript)便是一个动态语言。
除此之外如Ruby、Python等也都属于动态语言，而C、C++等语言则不属于动态语言。
Dynamically Typed Language (动态类型语言)
动态类型语言：是指在运行期间才去做数据类型检查的语言。
在用动态语言编程时，不用给变量指定数据类型，该语言会在你第一次赋值给变量时，在内部将数据类型记录下来。
Statically Typed Language (静态类型语言)
静态类型语言：与动态类型语言刚好相反，它的数据类型检查发生在在编译阶段，也就是说在写程序时要声明变量的数据类型。
C/C++、C#、JAVA都是静态类型语言的典型代表。

两者的优缺点

静态类型语言的

主要优点在于其结构非常规范，便于调试，方便类型安全；
缺点是为此需要写更多的类型相关代码，导致不便于阅读、不清晰明了。

动态类型语言的

优点在于方便阅读，不需要写非常多的类型相关的代码；
缺点自然就是不方便调试，命名不规范时会造成读不懂，不利于理解等。

runtime

runtime 描述了程序运行时候执行的软件/指令，在每种语言有着不同的实现。

可大可小，在 C 中，runtime 是库代码，等同于 C runtime library，一系列 C 程序运行所需的函数。

在 Java 中，runtime 还提供了 Java 程序运行所需的虚拟机等。

总而言之，runtime 是一个通用抽象的术语，指的是计算机程序运行的时候所需要的一切代码库，框架，平台等。

Go中的 runtime

在 Go 中，有一个 runtime 库，其实现了垃圾回收，并发控制，栈管理以及其他一些 Go 语言的关键特性。 runtime 库是每个 Go 程序的一部分，也就是说编译 Go 代码为机器代码时也会将其也编译进来。所以 Go 官方将其定位偏向类似于 C 语言中的库。

Go 中的 runtime 不像 Java runtime （JRE， java runtime envirement ) 一样，jre 还会提供虚拟机， Java 程序要在 JRE 下才能运行。

垃圾回收机制(garbage collection,GC)的设计

C/C++语言为什么没有对指针对象的垃圾回收机制

作为支持指针的编程语言，C++将动态管理存储器资源的便利性交给了程序员。在使用指针形式的对象时(请注意，由于引用在初始化后不能更改引用目标的语言机制的限制，多态性应用大多数情况下依赖于指针进行)，程序员必须自己完成存储器的分配、使用和释放，语言本身在此过程中不能提供任何帮助。

某些语言提供了垃圾回收机制，也就是说程序员仅负责分配存储器和使用，而由语言本身负责释放不再使用的存储器，这样程序员就从讨厌的存储器管理的工作中脱身了。

C++的设计者Bjarne Stroustrup对此做出过解释：

“我有意这样设计C++，使它不依赖于自动垃圾回收(通常就直接说垃圾回收)。这是基于自己对垃圾回收系统的经验，我很害怕那种严重的空间和时间开销，也害怕由于实现和移植垃圾回收系统而带来的复杂性。还有，垃圾回收将使C++不适合做许多底层的工作，而这却正是它的一个设计目标。但我喜欢垃圾回收的思想，它是一种机制，能够简化设计、排除掉许多产生错误的根源。需要垃圾回收的基本理由是很容易理解的：用户的使用方便以及比用户提供的存储管理模式更可靠。而反对垃圾回收的理由也有很多，但都不是最根本的，而是关于实现和效率方面的。已经有充分多的论据可以反驳：每个应用在有了垃圾回收之后会做的更好些。类似的，也有充分的论据可以反对：没有应用可能因为有了垃圾回收而做得更好。并不是每个程序都需要永远无休止的运行下去；并不是所有的代码都是基础性的库代码；对于许多应用而言，出现一点存储流失是可以接受的；许多应用可以管理自己的存储，而不需要垃圾回收或者其他与之相关的技术，如引用计数等。我的结论是，从原则上和可行性上说，垃圾回收都是需要的。但是对今天的用户以及普遍的使用和硬件而言，我们还无法承受将C++的语义和它的基本库定义在垃圾回收系统之上的负担。”

强类型语言和弱类型语言

1.强类型语言：使之强制数据类型定义的语言。没有强制类型转化前，不允许两种不同类型的变量相互操作。强类型定义语言是类型安全的语言，如Rust, Java、C# 和 Python，比如Java中“int i = 0.0;”是无法通过编译的；

2.弱类型语言：数据类型可以被忽略的语言。与强类型语言相反, 一个变量可以赋不同数据类型的值，允许将一块内存看做多种类型，比如直接将整型变量与字符变量相加。C/C++、PHP都是弱类型语言，比如C++中“int i = 0.0;”是可以编译运行的；

注意，强类型语言在速度上略逊色于弱类型语言，使用弱类型语言可节省很多代码量，有更高的开发效率。而对于构建大型项目，使用强类型语言可能会比使用弱类型更加规范可靠。

ispc

a data-parallel languagedesigned specifically to target Intel’s vector extensions

Intel® Implicit SPMD Program Compiler

An open-source compiler for high-performance SIMD programming on the CPU and GPU

ispc is a compiler for a variant of the C programming language, with extensions for "single program, multiple data" (SPMD) programming.