败犬日报 2024-10-20
1. 编译期判断类型是否是类模板的实例
只能判断模板参数都是类型，如下：
#include <type_traits>
#include <vector>
#include <array>
template <class Template>
struct is_instance_of_template : std::false_type {};
template <template <typename...> class Template, typename... Args>
struct is_instance_of_template<Template<Args...>> : std::true_type {};
int main() {
static_assert(is_instance_of_template<std::vector<int>>::value);
static_assert(!is_instance_of_template<int>::value);
static_assert(is_instance_of_template<std::array<int, 2>>::value); // assertion failed
}可以看到非类型参数不行，除非有一种能表示所有类型模板参数的模板参数 —— universal template。
2. concept 实例化失败
代码如下：
template <typename T>
concept A = T::value;
A<int>;https://zh.cppreference.com/w/cpp/language/constraints：
表达式
C<A1, A2, ... , AN>（其中 C 指名某个概念）的范式，是以 A1, A2, ... , AN 对 C 的每个原子约束的形参映射中的 C 的对应模板形参进行替换之后，C 的约束表达式的范式。如果在这种形参映射中的替换产生了无效的类型或表达式，那么程序非良构，不要求诊断。
所以这里的行为是“非良构，不要求诊断”，相当于编译报错但是可以不报错。（一种编译期 UB？）
如果想要标准行为就用 requires。
3. 哈希表怎么处理冲突
常见的两种：std::unordered_map 使用拉链法，更好的实践是开放寻址法（关键词：open addressing, flattened）。
链表空间局部性很差，cache 不友好，性能差。
boost::unordered_map 和 boost::unordered_flat_map 的努力可能会在未来被标准吸纳。
4. 为什么 std::map 用 rbtree 不用 btree
历史局限性，rust 就用 btree 了。
btree cache 友好，性能好，在一些场景下性能远超 rbtree；而且在 k-v pair 比较小的时候 btree 比 rbtree 省内存省得非常明显。
可以看看 google 有一个 btree 实现，里面放了一个 benchmark 结果。
5. 为什么以前的人不注重缓存
因为那会确实差距不算大吧，而且还有各种 cache line 不一样所以考虑 cache oblivious 的情况。
https://colin-scott.github.io/personal_website/research/interactive_latency.html
一个底层的东西一般得好几年才会被上面的感觉到。
关于 cache oblivious，大多数 CPU 都是 64 字节 cache line，可能远古时期有小于 64 的；IBM 可能有 128 的机器。
6. 面试题：cache 和 buffer 的区别
cache 是加速访问，所以有 cache 命中/缺失的说法，而 buffer 没有。
buffer 是协调速度，比如有 Buffer I/O 的说法，而没有 cache IO。