★ FEATURED ARTICLE std::advance(it, n)对vector的迭代器能用it n一步到位O(1)对list的迭代器却只能循环itO(n)。同一个函数名凭什么在编译期自动选对实现答案就是tag dispatch标签派发用几个空类型当「标签」配合重载偏序overload resolution 里更特化的优先让编译器在编译期就把正确的重载挑出来运行时零开销。1. 引子一个函数两种复杂度先看需求。我想写一个my_advance(it, n)把迭代器前进 n 格随机访问迭代器vector::iterator能直接it nO(1)双向迭代器list::iterator只能一次一步it/--itO(n)。如果写两个不同名字的函数调用方得自己记住哪个容器用哪个很蠢。理想是一个名字编译器自动分派。这就是 tag dispatch 要解决的。有人会问为什么不干脆用虚函数虚函数是运行期多态dynamic dispatch每次调用都要查虚表、多一次间接跳转而且vector::iterator这种平凡类型根本塞不进类继承体系。tag dispatch 是编译期多态static dispatch重载在编译期就定死了生成的机器码里直接就是it n或循环没有任何运行期开销——这正是「零开销抽象zero-overhead abstraction」的体现。2. 核心概念空类型当标签 重载偏序标准库把迭代器分成了若干「类别iterator category」每一类用一个空 struct当标签它们之间有继承关系std 迭代器类别 tag都是空 struct零大小纯编译期标记 input_iterator_tag - 最弱单向、单遍 ▲ forward_iterator_tag - 可多遍 ▲ bidirectional_iterator_tag - 可双向 ▲ random_access_iterator_tag - 最强可 O(1) 跳转tag dispatch 的流程分三步std::iterator_traitsIt::iterator_category从迭代器类型里「读」出它的类别 tag用这个 tag 构造一个空对象category{}零开销作为实参传给重载函数重载解析按「参数类型更特化优先」的规则选中对应类别的那份实现。my_advance(it, n) │ typename std::iterator_traitsIt::iterator_category ▼ category{} 空 tag 对象编译期信息运行时无成本 │ ▼ 重载解析参数越特化继承链越靠下越优先 ┌─────────────────────────────────────────────┐ │ random_access - it n O(1) │ │ bidirectional - 循环 /-- O(n) │ │ input - 循环 O(n) │ └─────────────────────────────────────────────┘官方文档std::iterator_traits —— 从迭代器类型里取出iterator_category的入口。3. 最小实现按迭代器类别派发的 advance#includecstdio#includecstddef#includeiterator#includelist#includevector// 三个重载第三参用不同的 tag 类型区分templatetypenameItvoidadvance_impl(Itit,std::ptrdiff_t n,std::random_access_iterator_tag){std::printf( [随机访问] it nO(1)\n);itn;}templatetypenameItvoidadvance_impl(Itit,std::ptrdiff_t n,std::bidirectional_iterator_tag){std::printf( [双向] 逐次移动O(n)\n);if(n0){while(n--)it;}else{while(n)--it;}}templatetypenameItvoidadvance_impl(Itit,std::ptrdiff_t n,std::input_iterator_tag){std::printf( [输入] 单向逐次移动O(n)\n);while(n--)it;}// 入口读 category - 构造 tag 对象 - 交给重载解析templatetypenameItvoidmy_advance(Itit,std::ptrdiff_t n){usingcategorytypenamestd::iterator_traitsIt::iterator_category;advance_impl(it,n,category{});}intmain(){std::vectorintv{1,2,3,4,5};autovitv.begin();std::printf(vector 前进 3 格:\n);my_advance(vit,3);std::printf( 现在指向 %d\n,*vit);std::listintl{10,20,30,40,50};autolitl.begin();std::printf(list 前进 2 格:\n);my_advance(lit,2);std::printf( 现在指向 %d\n,*lit);}vector 前进 3 格: [随机访问] it nO(1) 现在指向 4 list 前进 2 格: [双向] 逐次移动O(n) 现在指向 30输出证明vector::iteratorrandom_access_iterator_tag走进了it n那条list::iteratorbidirectional_iterator_tag走进了循环那条。同一个my_advance编译器在编译期就替调用方选好了。为什么vector不会误进bidirectional那个重载因为random_access_iterator_tag继承自bidirectional_iterator_tag两个重载都可行但「参数精确匹配」优于「派生类到基类的转换」所以随机访问版本胜出。这就是重载偏序候选函数里参数类型更特化的优先。官方文档迭代器 tag 类型iterator tags ——input/forward/bidirectional/random_access的继承关系是偏序的前提。4. 另一种 tagtrue_type/false_type做编译期 iftag dispatch 不只用于迭代器。std::true_type/std::false_type即std::integral_constantbool, …是现成的「布尔标签」可以用它把「编译期 if」写成两个重载#includecstdio#includetype_traits// 两个重载std::true_type / std::false_type 区分templatetypenameTvoiddescribe_impl(T,std::true_type){std::printf(是整型\n);}templatetypenameTvoiddescribe_impl(T,std::false_type){std::printf(不是整型\n);}templatetypenameTvoiddescribe(T v){// std::is_integralT 继承自 true_type 或 false_type用它做 tagdescribe_impl(v,std::is_integralT{});}intmain(){describe(42);// int - true_typedescribe(3.14);// double - false_typedescribe(x);// char - true_type}是整型 不是整型 是整型std::is_integralT直接继承自std::true_type或std::false_type把它构造成对象传给重载编译器就替我们选了「是整型」还是「不是整型」的分支。这比if更彻底不是运行期判断而是编译期就定死不合格的分支根本不会被实例化。官方文档std::true_type / std::integral_constant —— 布尔 tag 的出处。易错点一forward 迭代器会落到哪一格前面只写了 random_access / bidirectional / input 三个重载。如果你的迭代器类别是forward_iterator_tag比如std::forward_list的迭代器它不派生自bidirectional_iterator_tag所以三个候选里只有input_iterator_tag那个重载能匹配forward → input 是合法的派生类到基类转换。于是 forward 迭代器会走「单向循环it」的实现。这恰好正确因为 forward 迭代器确实不支持--it。易错点二tag 只是「类型标记」别存起来tag 对象永远是按值传的空结构体sizeof 1编译器甚至能直接优化掉它只用来在重载解析里「选中」某份实现没有任何数据含义。千万别把它存进容器、当成员变量、或者拿去参与运行期判断——那会彻底本末倒置。tag dispatch 的价值恰恰在于它只存在于编译期运行期彻底消失。5. 对比tag dispatch vs if constexprC17 的if constexpr能做同样的事而且写在一个函数里、可读性更好。下面用distance求两个迭代器间的元素个数做对比#includecstdio#includecstddef#includeiterator#includetype_traits#includelist#includevector// 方案 Atag dispatch —— 靠重载偏序templatetypenameItstd::ptrdiff_tdistance_impl(It first,It last,std::random_access_iterator_tag){returnlast-first;// O(1)}templatetypenameItstd::ptrdiff_tdistance_impl(It first,It last,std::input_iterator_tag){std::ptrdiff_t n0;while(first!last){first;n;}// O(n)returnn;}templatetypenameItstd::ptrdiff_tmy_distance(It first,It last){usingcategorytypenamestd::iterator_traitsIt::iterator_category;returndistance_impl(first,last,category{});}// 方案 Bif constexpr —— 编译期丢弃不匹配的分支templatetypenameItstd::ptrdiff_tdistance_ic(It first,It last){usingcategorytypenamestd::iterator_traitsIt::iterator_category;ifconstexpr(std::is_same_vcategory,std::random_access_iterator_tag){returnlast-first;}else{std::ptrdiff_t n0;while(first!last){first;n;}returnn;}}intmain(){std::vectorintv{1,2,3,4,5};std::listintl{10,20,30};std::printf(vector 距离(tag dispatch): %td\n,my_distance(v.begin(),v.end()));std::printf(list 距离(tag dispatch): %td\n,my_distance(l.begin(),l.end()));std::printf(vector 距离(if constexpr): %td\n,distance_ic(v.begin(),v.end()));std::printf(list 距离(if constexpr): %td\n,distance_ic(l.begin(),l.end()));}vector 距离(tag dispatch): 5 list 距离(tag dispatch): 3 vector 距离(if constexpr): 5 list 距离(if constexpr): 3两种写法结果一样。区别在于组织方式手段机制优点缺点tag dispatch空 tag 多个重载 偏序老标准兼容C98 就能用扩展新类别 加一个重载要定义 tag 和多个重载代码分散if constexprC17编译期丢弃分支逻辑集中在一个函数更直观需要 C17分支多时代码变长SFINAE /enable_if替换失败从候选集移除能精确控制「哪些类型能调用」写法繁琐、报错难读ConceptsC20约束模板参数报错最友好、意图最清晰需要 C20官方文档if constexpr编译期 if —— tag dispatch 的现代替代方案。实际工程里新代码优先if constexpr或 Concepts可读性更好但读std::advance、std::distance、std::sort这些标准库实现时里面还满是 tag dispatch。读懂它才能看懂标准库源码。官方文档重载解析overload resolution —— tag dispatch 依赖的「更特化优先」规则在这里有完整定义。本知识库内的相关篇目《类型列表与编译期算法手写 typelist 的 map/filter》 —— 编译期想对「一组类型」做运算取第 N 个、映射成指针、筛选整型《类型擦除手写 any 与 function 的原理》 —— std::any 和 std::function 看起来是两种不同的东西《编译期反射模拟C 没有反射怎么办》 —— C 至今没有运行时反射想「遍历结构体成员」「自动序列化」只能靠模拟6. 一句话总结tag dispatch 用「空 tag 类型 重载偏序」让编译器在编译期选出正确实现iterator_traits读出类别 → 构造空 tag 对象 → 重载解析按「参数越特化越优先」选函数运行时零开销C17 起多数场景可以用if constexpr写得更集中但理解 tag dispatch 是读懂标准库算法的前提。
阅读完成 · 觉得有帮助？
