Conan 作为一个 C++ 包管理工具，相对于之前介绍的 CMake FetchContent 或者 ExternalProject 方式添加第三方依赖会更加简单，但是凡是碰上了 C++，都简单不到哪去，学习成本还是有一点的，就用一篇笔记介绍一下 Conan 的基本使用。

安装 Conan

由于我们后面会大量使用 conanfile.py，且也可以借助 Python 插件实现 conanfile.py 的代码补全，直接使用 python 库的方式安装 conan，安装命令如下：

1

python -m pip install conan

安装之后例行检查一下版本

1

conan --version

Powershell 设置

通过 $PROFILE 变量，可以查询到 Powershell 默认加载的配置文件路径，如下所示

如果文件不存在，直接创建一个即可，然后填入下面两个预定义的函数（默认代理的地址为 127.0.0.1:7890，纪念天国的CFW🙏）

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

function proxy_on {
    $proxy="http://127.0.0.1:7890"
    $Env:http_proxy = "$proxy"
    $Env:https_proxy = "$proxy"
    Write-Host "Proxy enabled: $proxy"
}

function proxy_off {
    Remove-Item Env:\http_proxy -ErrorAction SilentlyContinue
    Remove-Item Env:\https_proxy -ErrorAction SilentlyContinue
    Write-Host "Proxy disabled"
}

当更改完 $PROFILE 文件后，使用 . $PROFILE 加载更新后的配置文件，并通过简单的 curl 命令判断是否可用

git clone

1

git clone <repo-url>

示例命令如下

1

git clone https://github.com/boostorg/boost.git

一些常用的参数（全部参数选项可以通过 git clone --help 查看）

• --recursive 或 --recurse-submodules（在较新版本的 git 中使用，命令的语义更加清晰）：当要拉取的仓库中包含 submodule 时，是默认不会拉取子仓库的，而指定这个参数即可拉取所有的子仓库。

  如果我们在下载的时候忘记指定 --recursive，也可以通过下面命令重新拉取子仓库

  1	git submodule update --init --recursive

• --depth：当我们只想下载指定更新次数的分支（这样可以减少下载的大小，在我们只需要最新的提交记录时很有用，当然也可以直接下载 zip 或 tar.gz 等压缩文件来解决。

• -b 或者 --branch：指定要拉取的分支名称，例如下载 boost-1.86.0 （这个实际上是一个 tag，但也可以通过这种方式下载）。

  1	git clone https://github.com/boostorg/boost.git --branch boost-1.86.0

对于一个\(2^n\times2^n\)的二维网格由于地址空间都是一维的（例如0x0000到0xffff），其实际在计算机中会将多维压缩成一维，可以形式化表示为

\[ \begin{align} M_{\text{2D}}&:(x,y)\to v \\ M_{\text{2D}}^{-1}&:v\to (x,y) \\ \end{align} \]

对于\(M_{\text{2D}}(x,y)\)也可记作\(\text{encode}(x,y)\)，\(M^{-1}_{\text{2D}}(v)\)为\(decode(v)\)

Linear Curve

一种最为简单的存储方式就是逐行地或逐列地存储二维数据，对于一个指定大小的二维方块（\(w\times h\)），从0开始的坐标\((x,y)\) 对应的一维地址为（一行包含\(w\)个元素） \[ v = x \times w + y \] 同理，将一维坐标\((v)\)转换二维方块坐标也很简单，只需要对行/列进行整除和取余操作即可 \[ \begin{align} x &= \lfloor v / w \rfloor \\ y &= v - x \times w \end{align} \] 上面这种方式在一般情况下足够使用，但是对于纹理/体素等数据的读取时，通常会利用到二维/三维坐标的局部性（即当我们访问坐标\((x,y)\)时，我们有很大概率将访问该坐标周围的坐标），而使用线性存储方式则会丢失这种局部性。

例如对于一个\(16 \times 16\)的方块中坐标\((4,4)\)和坐标\((6,6)\)，其二维曼哈顿距离为 \[ (6-4)+(6-4) = 4 \] 而经过线性存储映射后距离为 \[ (6*16+6)-(4*16+4)=38 \] ，可以观察到经过一维映射后两个数据距离相差较远。

下图展示了 linear curve 的示意图

直接说距离似乎难以理解这种差距，考虑一个实际读取场景，假设CPU的cache一次可以存放16个数据，当我们读取纹理中\((4,4)\)位置的数据后，下一个准备读取其周围\((6,6)\)的数据，由于\((6,6)\)的数据在内存中地址距离\((4,4)\)数据地址较远，无法一次加载到cache中，即出现cache miss，这样我们就只能从内存中重新加载数据，无法利用高速缓存，影响数据读取性能。

针对这个问题，可以使用Hilbert曲线或者Morton曲线这类特殊的映射方式进行坐标映射

Hello，ANTLR4

ANTLR 是一个用 Java 写的语法分析工具，类似 Lex Yacc 以及 Flex Bison（这两个都有点太老了，而且Windows上也不好用），通过编写一个内嵌代码的文件（.g4）来定义文法，然后由 ANTLR 对文件进行分析，生成不同后端的分析程序，例如 C++、Python、Java 等，相比我们手写分析程序，只要我们定义好文法，就可以完成解析过程，提高开发效率。

使用 ANTLR4 的最简单方式就是 Python 了，我们直接通过 pip 安装即可

1

pip install antlr4-tools

由于 ANTLR 需要 Java ，如果没有安装 Java 环境会在第一次运行时自动安装。

之后我们可以定义一个简单的表达式文法来测试效果

Expr.g4

1
2
3
4
5
6
7
8
9

grammar Expr;		
prog:	expr EOF ;
expr:	expr ('*'|'/') expr
    |	expr ('+'|'-') expr
    |	INT
    |	'(' expr ')'
    ;
NEWLINE : [\r\n]+ -> skip;
INT     : [0-9]+ ;

（注意到文法中包含左递归，但是 ANTLR 会自动帮我们处理好）

Git Submodule 管理依赖

由于 C++ 自身的特殊性，要想实现跨平台代码，只能使用源码分发（也有类似于 Conan 的 C++ 依赖解决方案，但是对于一些冷门的库可能就不支持，还是得自己写）。

最简单的办法就是通过 git 的子模块将其添加到项目中，这种依赖管理方式确保可以访问到源代码，其缺点也很明显，我们在下载库的时候需要通过下载依赖库（也就是子模块），如果子模块较大可能下载起来比较耗时。

前面一个笔记中也提到了，要想删除添加的 git submodule 十分麻烦，没有一个简单的命令可以直接删除，需要手动调整需要文件才能删除干净。

FetchContent 模块添加依赖

而 FetchContent 是 CMake 提供的一种新式依赖管理方案（在 3.11 版本首次出现），其在 CMake 的配置过程中自动下载依赖项并配置（或者由用户自行配置）。这样可以保持我们的代码库整洁。

所有排列

由于排列本身的递归形式，可以通过回溯不断生成所有的排列。例如序列为 [1,2,3,4]，当我们确定第一个位置为 1 后，剩下三个位置，此时有效的排列就变成了 剩下三个数 [2,3,4] 在剩下三个位置上的全排列了，这样我们就从求 [1,2,3,4] 的全排列变成了求 [2,3,4] 全排列，当序列长度为 1 时其排列就为其本身，递归终止。

根据这个思路我们就可以写出所有的全排列了

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

void permutations(const std::vector<int>& numbers,
                  std::vector<int>& curr,
                  std::vector<int>& visited,
                  const std::vector<std::vector<int>>& output) {
    if(curr.size() == numbers().size()) {
        output.emplece_back(curr);
        return;
    }
    for(int i=0;i<numbers.size();i++) {
        if(visited[i]) {
            continue;
        }
        visited[i] = true;
        curr.emplace_back(numbers[i]);
        permutations(numbers,curr,visited,output);
        curr.pop_back();
        visited[i] = false;
    }
}

二叉树实现

不同语言实现起来都差不多，给出 C++ 版本的模版实现

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

template <typename T> struct TreeNode {
  using value_type = T;
  using ptr_type = TreeNode<T> *;

  value_type val{};
  ptr_type left{nullptr};
  ptr_type right{nullptr};
};

template <typename T>
std::ostream &operator<<(std::ostream &os, const TreeNode<T> &node) {
  return os << node.val;
}

递归遍历

由于二叉树本身的递归特性，通过递归函数可以很简单的遍历二叉树，根据访问根节点顺序不同可以分为前序、中序和后序，对应代码如下

首先定义访问函数以及递归遍历函数

1
2
3
4

template <typename T> void visit(TreeNode<T> *node) {
  std::cout << "visit: " << *node << std::endl;
}
std::function<void(node_ptr)> recursive;

整体结构

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

.
├── .gitignore
├── .gitmodules
├── CMakeLists.txt
├── LICENSE
├── README.md
├── build
├── cmake
│   ├── CMakeLists.txt
│   └── ...
├── data
│   ├── .gitkeep
│   └── ...
├── extern
│   ├── CMakeLists.txt
│   └── ...
├── src
│   ├── CMakeLists.txt
│   ├── glad
│   ├── lumos
│   └── stb
└── test
    ├── CMakeLists.txt
    ├── test_gl.cpp
    ├── test_imageio.cpp
    ├── test_imgui.cpp
    ├── test_pcg.cpp
    ├── test_random_permutation.cpp
    └── test_viewer.cpp