能否用C++20 Concepts约束特定时间复杂度？可行性探讨

结论先行：C++20 Concepts没办法直接检查时间复杂度这类语义特性。

为什么做不到？ #

• Concepts是编译期静态检查工具，只能验证类型的语法层面属性：比如有没有某个成员函数、表达式能不能编译、返回值类型是否符合要求这类从代码结构就能直接判断的内容。
• 时间复杂度是运行时行为的语义约定——编译器根本没法在编译期判断一个操作是O(1)还是O(n)。哪怕你写了个看起来是常数级的函数，内部偷偷藏了循环或者动态扩容逻辑，编译器也不可能精准推导所有执行路径的成本。你贴的那个linear concept里，不存在能实现时间复杂度检查的所谓"magic"代码。

那这类时间复杂度的要求合理吗？ #

非常合理。很多标准库算法的性能保证完全依赖于操作的时间复杂度：比如std::sort要求随机访问迭代器的移动操作是O(1)，不然整个排序的O(n log n)复杂度就无从谈起；再比如std::unordered_map的查找操作，依赖哈希函数的计算是常数时间。

但这种要求只能靠文档约定、代码评审或者专门的静态分析工具来保障，没法通过Concepts或者编译期检查强制实现——就像cppreference里的命名要求一样，大多是语义层面的规则，而非编译期能验证的语法约束。

如果要在代码里强调这类约定，通常的做法是在concept的注释里明确写清楚：

template <class T>
concept linear = requires (T val) {
    /* 要求对T执行的核心操作具备线性时间复杂度 */
    // 这里仅编写语法层面的必要约束，比如val支持的操作
};

内容的提问来源于stack exchange，提问作者David