= m[key] 覆盖式写入，要用 m.insert_or_assign(key, val) 不覆盖写入，要用 m.insert({key, val}) 判断是否存在，用 m.count(key) 若存在则删除，用 m.erase(key) 第四章：迭代与遍历 物理格式 逻辑格式 面壁者罗辑监督你鞋习 ! 面壁者罗辑监督你鞋习 ! map 的元素类型是…… • set::value_type 规则是： • 设要找的数为 X ，则 set.find(X) 首先从根节点开始寻找。 • 若 X == 当前节点，则这个节点就是我要找的，返回指向该节点的迭代器； • 若 X < 当前节点，则移动左子节点，继续重复以上步骤； • 若 X > 当前节点，则移动右子节点，继续重复以上步骤； • 若已经没有子节点了，但仍未找到 X ，则说明 X 在集合中不存在，返回 end() 来表示。 1

内部是怎么确定 两个元素 a 和 b 相等的： • !(a < b) && !(b < a) • 也就是说他 set 内部没有用到 == 运算符，而是调用了两次 比较函子来判断的。逻辑是： • 若 a 不小于 b 且 b 不小于 a ，则视为 a 等于 b ，所以 这就是为什么 set 只需要一个 比较函子，不需要相等函子的 原因。 set 的排序：自定义排序函数 • 所以我们这里写了 insert 的第二个返回值：表示插入是否成功 • insert 函数的返回值是一个 pair 类型，也就是说他同时 返回了两个值。其中第二个 返回值是 bool 类型，指示 了插入是否成功。 • 若元素在 set 容器中已存有 相同的元素，则插入失败， 这个 bool 值为 false ；如 果元素在 set 中不存在，则 插入成功，这个 bool 值为 true 。 • pair

0 码力 | 83 页 | 10.23 MB | 1 年前

3

std::mutex 。 spin_mutex （基 于硬件原子指令）会让 CPU 陷入循环等待，而不像 mutex （操作系统提供调度）会让线程进入休眠状态的等待 。 若上锁的区域较小，可以用轻量级的 spin_mutex 。若上锁 的区域很大，则循环等待只会浪费 CPU 时间。这里锁的区 域是 std::copy ，比较大，所以 spin_mutex 效果不如 mutex 好。 加速比： 5

= 2; // 拷贝赋值函数 • 拷贝赋值函数≈解构函数 + 拷贝构造函数 • 拷贝构造：直接未初始化的内存上构造 2 • 拷贝赋值：先销毁现有的 1 ，再重新构造 2 • 因此若对提高性能不感兴趣，可以这样写： 拷贝赋值函数：提高性能 • 区分两种拷贝可以提高性能。 • 内存的销毁重新分配可以通过 realloc ，从 而就地利用当前现有的 m_data ，避免重 新分配。 移动构造≈拷贝构造 + 他解构 + 他默认构造 • 移动赋值≈拷贝赋值 + 他解构 + 他默认构造 • 只要不定义移动构造和移动赋值，编译器会自 动这样做。虽然低效，但至少可以保证不出错 。 • 若自定义了移动构造，对提高性能不感兴趣： • 移动赋值≈解构 + 移动构造 注： 降低时间复杂度： O(n) >>> O(1) 提高性能： O(1) >>> O(0.1) 小技

器数量急 剧缩小。而如果你的程序恰好用到了非常多的寄存器，那就没办法全部装在高效的寄存器 仓库里，而是要把一部分“打翻”到一级缓存中，这时对这些寄存器读写的速度就和一级缓存 一样，相对而言低效了。若一级缓存还装不下，那会打翻到所有 SM 共用的二级缓存。 • 此外，如果在线程局部分配一个数组，并通过动态下标访问（例如遍历 BVH 时用到的模 拟栈），那无论如何都是会打翻到一级缓存的，因为寄存器不能动态寻址。

stoi 略去。 • 那如何才能知道哪些字符被 stoi 略去了呢？或者说，数字部分从哪里结束？ • 这就要用到 stoi 的第二参数，他是一个 size_t 的指针，默认为 nullptr 。 • 若该指针不为 nullptr ，则会往他指向的变量写入一个整数，表示数字部分结 束的那个字符所在的位置，很绕口？来看个例子就懂了。 • 例如 stoi(“42yuan”, &pos) 会返回 42 ，并把