Interview II: C++模板元与并发编程

Dependent Name
#

模板编译分为定义阶段和实例化阶段, 定义阶段解析语法, 实例化阶段约束类型. C++默认将::, ->, .后的名字解析为变量, 若为依赖名字即依赖尚未实例化的模板, 定义阶段可能无法正确解析, 例如:

struct A {
    template<typename T>
    using B = int;
};

template<typename T>
auto f() {
    T::B<T> x; // 语法错误, T::B默认解释为非类型
    typename T::B<T> y; // 语法错误, typename T::B默认解释为非模板
    T::template B<T> z; // 语法错误, T::template B默认解释为非类型
    typename T::template B<T> w;
}

Concept
#

要求子句在重载决议时检查布尔值为真, 只接收初等表达式(比如: 字面量, 标识符, 要求表达式, 折叠表达式, 括号表达式)和由&&或||连接的初等表达式. 例如:

template<typename T> requires std::is_same_v<T, int> auto f() {} // is_same_v是布尔变量标识符
template<typename T> requires std::same_as<T, int> auto f() {} // same_as是概念标识符
template<typename T> requires sizeof(T) > 4 auto f() {} // 错误, 非初等表达式
template<typename T> requires (sizeof(T) > 4) auto f() {} // 括号表达式为初等表达式
template<typename T> requires (sizeof(T) > 4) && (sizeof(T) < 8) auto f() {} // &&连接的初等表达式

要求表达式在模板实参代换时检查要求是否满足, 代换失败时为假, 只接收以下检查: 表达式合法, 类型存在, 嵌套要求布尔值为真以及复合要求. 可引入无存储与生存期的记号形参, 例如:

requires { sizeof(int) > 8; } // 表达式合法, 返回真
requires { typename std::vector<int>::value_type; } // 类型存在, 返回真
requires { requires sizeof(int) > 8; } // 嵌套要求为假, 返回假

复合要求按固定顺序检查: 表达式合法, 若有noexcept不潜在抛出异常, decltype((x))满足->后的概念. 例如:

requires(int x) { { x + x } noexcept -> std::same_as<int>; } // 表达式合法, 不抛异常且满足概念, 返回真
requires(int x) { { x + x } -> int; } // 错误, 裸类型不是概念
requires(int x) { { x } -> std::same_as<int>; } // decltype((x))为int&, 返回假
requires(int x) { { x } -> std::same_as<int&>; } // 形参为左值, 返回真
requires(int x) { { x + 0 } -> std::convertible_to<long>; } // convertible_to<int, long>, 返回真

概念是具名的布尔常量表达式, 不可特化与递归. 若有多个候选, 有偏序关系时选择更强的约束, 否则有歧义. 例如:

template<typename T> concept integral = std::is_integral_v<T>; // 布尔常量
template<typename T> concept addable = requires(T x) { x + x; }; // 要求表达式
template<integral T> auto f(T) {} // 约束模板形参
auto g(std::convertible_to<long> auto) {} // 约束auto
template<typename T> requires std::integral<T> auto h(T) {}
template<typename T> requires std::integral<T> && std::signed_integral<T> auto h(T) {} // 约束更强, h(0)选中

Pack
#

C++参数包用于定义不定长的参数, 除函数模板外定义模板参数时参数包必须位于尾部. 例如:

template<typename... Ts> struct T: Ts... {}; // 类型包
template<int n, int... ns> using M = Matrix<int, n, ns...>; // 非类型包
template<auto... xs> auto static x = std::make_tuple(xs...); // 可推导非类型包
template<Concept... Cs> struct T {}; // 概念包
template<template<typename...> typename... Ts> struct T { using v = std::variant<Ts<int, float>...>; }; // 模板模板形参包

对于函数模板参数包, 若不位于尾部, 只要后续模板参数不产生歧义即合法. 例如:

template<typename F, typename... Ts, std::size_t N>
auto foreach(F f, Vector<Ts, N>... vectors); // 所有模板参数都可自动推导, 不产生歧义
template<typename... Ts, typename R>
auto reduce(R init, Ts... xs); // 函数中参数包位于尾部, 无歧义, 模板参数可不位于尾部
template<typename... Ts, typename R>
auto make(Ts... xs) -> R; // R不参与推导, 需写make<T1, T2, R>, R是否位于参数包有歧义

由于[]和()的优先级高于*, &等前缀, 函数/数组的指针/引用需要额外添加(), 对这些类型添加参数包时, ...需要位于括号内, 例如:

template<int... N> auto f(int (&... arrs)[N]) -> void;
template<typename... Ts> auto f(Ts (*... ptrs)(int)) -> void;
template<typename... Ts> auto f(auto (Ts::*... ptrs)() -> void) -> void;

C++20支持lambda捕获参数包, C++26支持结构化绑定参数包和参数包索引. 两种新参数包需要定义新名字, ...前置以解决与参数包展开的冲突, 例如:

template<typename... Ts>
auto defer(Ts... args) { return [...xs = args] { return g(xs...); }; }
auto [first, ...rest] = std::tuple{1, 2.0, '3'};
template<typename... Ts>
auto front(Ts... xs) -> Ts...[0] { return xs...[0]; }

展开参数包时以左侧最大语法树节点为单位展开, 若有嵌套则先展开内层, 例如:

f(&xs...); // f(&x0, &x1, &x2)
f(n, ++xs...); // f(n, ++x0, ++x1, ++x2);
f((Args const*)&xs...); // f((T0 const*)&x0, (T1 const*)&x1, (T2 const*)&x2)
f(g(xs...) + xs...); // f(g(x0, x1, x2) + x0, g(x0, x1, x2) + x1, g(x0, x1, x2) + x2)
f<Ts&...>(T{&xs...}) // f<T0&, T1&, T2&>(T{&x0, &x1, &x2})
template<typename Bs> struct A: public Bs... {}; // public B0, public B1, public B2

折叠表达式来自函数式语言, 例如Haskell的foldl和foldr, 使得参数包之间可以直接通过运算符连接, 可以区分左右折叠并添加初值. 为不与参数包展开冲突, 必须添加括号. 例如:

template<int... ns>
auto f() -> int {
    return 0
    + (... - xs) // 一元左折叠: ((1 - 2) - 3) = -4
    + (xs - ...) // 一元右折叠: (1 - (2 - 3)) = 2
    + (10 - ... - xs) // 二元左折叠: (((10 - 1) - 2) - 3) = 4
    + (xs - ... - 10) // 二元右折叠: (1 - (2 - (3 - 10))) = -8
    ;
}

Deduction
#

若非类模板的模板参数需要推导, 与T&&和auto&&严格一致, 触发转发引用, 例如:

template<typename T> auto f(T&&); // T需要被推导
template<typename T> auto f(T const&&); // 不满足T&&
template<typename T> auto f(std::type_identity_t<T>&&); // 不满足T&&

auto f(auto&&); // auto需要被推导
auto f(auto volatile&&); // 不满足auto&&

template<typename T> struct S {
    S(T&&); // auto s = S{x}; 类模板推导不触发转发, x为左值时报错
    auto f(T&&); // auto s = S<int>{}; 已实例化T, 调用s.f(x)不需要推导
    template<typename U> auto f(U&&); // U需要被推导
};

若参数为左值, T推导为T&, 从而T& && = T&得到左值; 右值时推导为T, 类型为T&&. 由于具名变量都是左值, 即使推导出右值引用, 使用参数时仍然触发左值重载, 因此需要std::forward<T>将T的具体引用类型传播, 实现如下:

template<typename T>
auto constexpr forward(std::remove_reference_t<T>& t) noexcept -> T&& {
    return static_cast<T&&>(t); // T& && = T&
}

template<typename T>
auto constexpr forward(std::remove_reference_t<T>&& t) noexcept -> T&& {
    static_assert(!std::is_lvalue_reference_v<T>);  // avoid forward<int&>(std::move(x))
    return static_cast<T&&>(t); //  T&& && = T&&
}

template<typename... Args>
auto f(Args&&... args) { g(std::forward<Args>(args)...); } // g接收到的引用类型和f一致

使用auto推导会删除cv限定符和引用, 需要用auto&&, auto const&等方式添加限定符, 若使用decltype(auto)则保留表达式类型.

auto x = 1; // int
auto& rx = x; // int&
auto const& crx = x; // int const&
auto y = crx; // int
decltype(auto) z = crx; // int const&

template<typename T> auto f(T&& x) { return x; } // return std::decay_t<T>
template<typename T> decltype(auto) f(T&& x) { return x; } // return T&&

CRTP
#

当模板类在构造时不需要模板类型参数的完整定义时, 将派生类型传给基类不会导致循环依赖, 从而实现奇异递归模板模式. C++23支持this推导, 首参为this Self&&时Self推导为调用者类型, 且有推导的成员函数可以直接取指针并传入this. lambda是实现了operator()的匿名对象, 但this会捕获外围对象, 无法再使用lambda自身的this, this推导使得lambda可以递归.

struct B {
    auto f(this auto&& self) { self.g(); }
    auto g() { return; }
    auto p() { auto r = &f; r(*this); } // this deduction
    auto q() { auto r = &g; this->(*r)(); } // member pointer
};

struct D: B {
    auto g() { auto x = 0; }
    auto h() { f(); } // f执行D::g
};

auto fib = [](this auto self, int n) -> int {
    return n < 2 ? n : self(n - 1) + self(n - 2);
};

Atomic
#

std::atomic使得对同一原子变量的操作在多线程下串行化, load/store保证不存在并发的读取和写入. wait传入期望值, 原子变量等于该值时阻塞, notify_one/notify_all唤醒一个或多个等待线程. compare_exchange比较期望值与原子变量实际值, 相等时执行修改, 否则写回实际值. 例如上次读取原子变量的结果是期望值, 我们期望它未被其它线程修改. compare_exchange保证修改一定进入缓存以对后续compare_exchange可见.

ARM等架构为LL/SC, 即load-linked/store-conditional一对指令: load-linked读取值并对该地址登记独占监视, store-conditional仅当监视未被上下文切换, 中断, 其它核心触碰同一缓存行等操作破坏才写入. 这导致compare_exchange_weak伪失败即值相等时也由于store-conditional而返回假. LL/SC架构的compare_exchange_strong需在内部循环重试以消除伪失败, 因此开销更高.

Memory Order
#

编译器重排和乱序执行导致并发内存读写顺序不被保证, 存储缓冲和失效队列导致可见性延迟, 可通过内存序std::memory_order解决. relaxed只保证原子操作本身语义正确, 不约束周围内存读写.

release保证原子操作前的内存读写不重排到之后, 保证之前的内存写入先于release本身进入缓存和发出失效消息. acquire保证原子操作之后的内存读写不重排到之前, 并处理已入队的失效消息, 当acquire读到release的写入, release前的写入已被失效队列处理, 因此已经可见.

acq_rel兼具acquire/release的特性, 而seq_cst在此基础上要求原子写入执行后立即排空存储缓冲并发送失效消息, 后续acquire触发的失效队列排空令写入可见, 因此acquire读取执行顺序在seq_cst写入之后时能立即获取写入结果.

Promise
#

std::promise<T>是一次性值/异常的写端, 配对的读端std::future<T>由get_future获得. 生产者调用set_value/set_exception写入, 消费者调用future.get(), 未就绪时阻塞, 就绪后返回值或重抛异常.

std::packaged_task包装可调用对象, 自动用返回值填充内部promise. std::async启动任务并返回std::future. std::launch::async立即执行, 对应的future析构时会阻塞. std::launch::deferred延迟到首次future读取, 相当于在调用线程同步执行. std::shared_future将返回值以T const&的形式暴露, 可被多个消费者重复读取.

Value Category
#

具有身份即有稳定存储空间的表达式是泛左值, 否则为纯右值. 纯右值分为两种情况, 示例:

auto x = 1 + 2 * 3;
x = 1 + 2 * 4;
struct A { int x; auto f(float x) { return x + 1.f; } };
auto y = A{1 + 2 * 5};
auto z = y.f(1.f);
auto w = z;
y.f(0.f);

计算内建运算符的操作数
- 1 + 2 * 3中的1, 2, 3, 2 * 3都是纯右值表达式
- 1 + 2 * 3是初始化语法=的操作数, 不符合定义
- 1 + 2 * 4是内建赋值运算符=的操作数, 符合定义
表达式初始化了一个对象
- 1 + 2 * 3用于初始化x, 符合定义
- 1 + 2 * 5用于初始化A::x, 符合定义
- 1.f用于初始化A::f的形参x, 符合定义
- w = z的z具有身份, 不符合定义
- y.f(0.f)为丢弃表达式, 触发临时实体化对象的初始化, 符合定义

将亡值为标记资源可被复用的泛左值, 不具有名称, 如何复用取决于移动构造函数, 示例:

auto pi = 3.14f;
struct A { int x; float&& y; };
A a{0, pi};
A&& b = static_cast<A&&>(a);
A&& c = std::move(a);
A{1, pi}.x; A{}.y;

强制转换为右值引用
- static_cast<A&&>(a)
函数返回右值引用
- std::move(a)执行强制转换, 返回右值引用, 符合定义
- A&& b和A&& c都是具名引用, 不符合定义
临时实体化并向下传播
- A{}.x由于需要访问x, A{}被临时实体化, 符合定义
- A{}.x为将亡值的成员, 符合定义
- A{}.y访问引用成员, 访问引用的结果一定为左值, 不符合定义

如果期望使用std::memcpy复制或移动对象, 需要满足std::is_trivially_copiable, 通常只有聚合类型和标量能满足, 否则需要调用复制或移动构造函数. 许多对象是可重定位的, 例如对象内部只持有指针, 保证复制后不再使用原对象, 即可正确析构.

C++17后标准要求纯右值的赋值直接在对象内存上初始化, 不执行复制或移动构造. 有提案主张引入reloc运算符, 将非引用对象转为纯右值并禁止再次使用, 引入重定位构造函数T(T x)以接收纯右值, 若类型满足重定位要求该函数优化为memcpy.

Reflection
#

C++26引入静态反射, 可通过反射运算符^^在编译期获取命名空间, 类型和具名表达式的std::meta::info, 以及拼接器[::]将其还原. std::meta中提供membors_of, template_of等函数以在编译期操作反射信息.

auto constexpr iinfo = ^^int;
using i32 = [:iinfo:];

ABI
#

应用二进制接口规定二进制层面的交互, 系统层面和C/C++语言层面都存在ABI, 例如:

ELF会做全局符号去重, LTO开启后跨动态库的符号为默认可见
Mach-O只将符号绑定到动态库内部, LTO开启后跨动态库符号不共享
System V AMD64和AAPCS64中小于16字节的对象使用寄存器传递参数
Itanium名称修饰以_Z开头, Windows以?开头
Itanium将虚基类偏移按序存储在负偏移, Windows在8字节偏移添加虚偏移指针

Dependent Name #

Concept #

Pack #

Deduction #

CRTP #

Atomic #

Memory Order #

Promise #

Value Category #

Reflection #

ABI #