由浅入深学习 map 容器 by 彭于斌（ @archibate ） 我负责监督你鞋习 ! 我负责监督你鞋习 ! 本期看点： 用方括号 [ ] 取出 map 元素居然是错误的！ 能不能在遍历的同时删除元素？安全吗？ emplace ， emplace_hint ， try_emplace 的区别？ 课程安排 1. vector 容器初体验 & 迭代器入门 (BV1qF411T7sd) 2 insert_or_assign(key, val) 不覆盖写入，要用 m.insert({key, val}) 判断是否存在，用 m.count(key) 若存在则删除，用 m.erase(key) 第四章：迭代与遍历 物理格式 逻辑格式 面壁者罗辑监督你鞋习 ! 面壁者罗辑监督你鞋习 ! map 的元素类型是…… • set::value_type 是 V 。 • map::value_type • (*it).first; // K 类型 • (*it).second;// V 类型 map 的遍历：用 C++17 range-based loop • 和 vector 等 STL 容器一样， map 也支持 C++17 的 range-based loop 语法进行遍历 。 • for (auto tmp: m) • 由于刚刚说了， map 真正的“元素类型”是 K-V 对，所以这里的

YX 序， ZYX 序。 二维数组的遍历 • 二维数组在内存中的布局有 YX 序， XY 序。 • 二维数组的循环遍历也有 YX 序， XY 序之分。 • 循环遍历，比如 YX 序：表示外层循环是以 Y 轴索 引为变量，内层循环是以 X 轴索引为变量。 • 比如右边的例子，我们分配了一个 YX 序的数组，然 后用 YX 和 XY 的顺序循环遍历他。发现 YX 序遍 历要快很多。 什么序的数组，就用什么序遍历 什么序的数组，就用什么序遍历 • 这是因为 YX 序的数组， X 方向在内存空间中的排布是连续的。 • 而 YX 序的循环，其 X 是内层循环体，因此在先后执行的时间上是连续的。 • 如果是 XY 序的循环，其 X 是外层循环体，在先后执行的时间上是不连续的。 • 从而在硬件看来，以 YX 序遍历，就和顺序访问一维数组没什么两样，从而缓存预取能正 常运作，甚至编译器可以优化成一个 nx*ny nx*ny 的一层循环。 • 而如果以 XY 序遍历，就像跳跃着访问一样，不连续，缓存得不到利用，每次读取只用了 其中 4 字节，浪费了缓存行剩下的 60 字节，非常低效。 • 结论： • 对于 YX 序（列主序， C/C++ ）的数组，请用 YX 序遍历（ x 变量做内层循环体）。 • 对于 XY 序（行主序， Fortran ）的数组，请用 XY 序遍历（ y 变量做内层循环体）。 a[0,0]

list 都可以调用 std::find （ set 则直接提供了 find 作为成员函数，稍后 讨论） set 和 vector 迭代器的不同点 • set 的迭代器对象也重载了 + + 为红黑树的遍历。 • vector 提供了 + 和 += 的重 载，而 set 没有。这是因为 vector 中的元素在内存中是连 续的，可以随机访问。而 set 是不连续的，所以不能随机访 问，只能顺序访问。 lower_bound(2) begin() end() upper_bound(4) set 的遍历 • 遍历方法和上一课 vector 中的一样，背板即可。 • 为什么这样写呢？复习！ 复习 C 语言指针（ 1 ） • 上节课说了，迭代器就是在模仿 C 语言指针。 • 回想一下 C 语言咋遍历数组的： • int arr[n]; • for (int i = 0; i < n; i++) 循环的范围是 [0, n) 。 • 因为这里 arr[i] 等价于 *(arr + i) ，所以…… 复习 C 语言指针（ 2 ） • 上节课说了，迭代器就是在模仿 C 语言指针。 • 回想一下 C 语言咋遍历数组的： • int arr[n]; • for (int *p = arr; p < arr + n; p++) { • int value = *p; • } • 索性用 arr + i 作为迭代的变量，避免一次加法的开销。

omp parallel for 遍历…… tbb::concurrent_unordered_map 可以 tbb::parallel_for 为了支持 std::unordered_map 先把要遍历的坐标和块 指针放到一个数组里，然后再对这个平坦的数组遍历。 指针数组的话，本来就是平坦的二维数组，直接 用 omp parallel for collapse(2) 遍历二维区间。 把 func 捕获为

tbb::simple_partitioner 能够按照给定的粒度 大小（ grain ）将矩阵进行分块。块内部小区 域按照常规的两层循环访问以便矢量化，块外 部大区域则以类似 Z 字型的曲线遍历，这样 能保证每次访问的数据在地址上比较靠近，并 且都是最近访问过的，从而已经在缓存里可以 直接读写，避免了从主内存读写的超高延迟。 • 下次课会进一步深入探讨访存优化，详细剖析 这个案例，那么下周六

因此可改用首地址指针和数组长度做参数 ： • print(char const *a, size_t n); • 这样 print 在无需知道容器具体类型的情 况下，只用最简单的接口（首地址指针） 就完成了遍历和打印的操作。 迭代器模式 • 使用指针和长度做接口的好处是，可以通 过给指针加减运算，选择其中一部分连续 的元素来打印，而不一定全部打印出来。 • 比如这里我们选择打印前三个元素（去掉

仓库里，而是要把一部分“打翻”到一级缓存中，这时对这些寄存器读写的速度就和一级缓存 一样，相对而言低效了。若一级缓存还装不下，那会打翻到所有 SM 共用的二级缓存。 • 此外，如果在线程局部分配一个数组，并通过动态下标访问（例如遍历 BVH 时用到的模 拟栈），那无论如何都是会打翻到一级缓存的，因为寄存器不能动态寻址。 • 对于 Fermi 架构来说，每个线程最多可以有 63 个寄存器（每个有 4 字节）。 https://developer