C++:异质查找( heterogeneous lookup )

太久没更新博文了,水一篇凑数 从 String View 说起 C 风格的字符串常常需要自己记录长度、管理生命周期,涉及长度变化时更是比较麻烦。于是在 C++ 中我们有了std::string,并且有了与之配套的一系列函数,比如std::stoi,对应 C 里面的atoi。这个函数的声明如下: 1 int stoi(const std::string& str, std::size_t* pos = 0, int base = 10); 这个接口接受一个const std::string&,乍看或许是理所应当的:我是 C++ 函数,我需要读取字符串,但是我不需要修改它。实际上,C++ 中有很多接受const std::string&的函数,然而很遗憾,这个设计是失败的。 考虑这样一种情况,我们需要读取一个std::string里的子串,但我们不需要修改它。比如对一个拥有很多数字的字符串进行连续 parse ,或者在某个大文本里找到某个模板再对匹配结果进行进一步筛选。这种情况下,这些接受const std::string&的函数就变得不好用了,因为子串不是一个std::string对象。我们往往不得不把子串复制到一个新的std::string对象里,造成了额外的开销。 类似的常见情况还有,我们接收到了一个 C 风格的字符串,以char* str+size_t len的形式,而我们希望能在这个字符串上使用各种 C++ 函数的功能。比如跟 C 接口交互的时候,或者用 buffer 从别的地方接收字符串数据的时候。 所以要怎么解决呢?我们可以采用 C 风格的接口,即char* str+size_t len,或者采用迭代器风格的接口,即char* begin+char* end。而将这两个参数合起来,我们就得到了std::string_view——只读字符串接口的正确答案。它不仅比const std::string&更泛用,而且在没有发生 SSO 的情况下,它还比const std::string&减少了一次指针跳转。 Rust 很早就想明白了这个问题,一开始就提供了String(对应 C++ 的string)和&str(对应 C++ 的string_view),并且在各个接口上统一了用法。而 C++ 则是群魔乱舞,什么样的接口都有。 泛型的困境 假设你现在在写一个泛型容器map<K, V>,你要给他添加一个.find成员来进行查找。那么.find的参数应该是什么呢?一般来说const K&就可以了,但要是K = std::string,那么就会遇到前面所说的问题了。给std::string做一个特化吗?不,我们要考虑更一般的问题,即如何在泛型里处理一个类型有多种表示的情况。我们应该允许....

2021-10-16 · QuarticCat

C++ 名称查找的又一个恶心设计

众所周知,C++ 的名称查找一直以来都很反直觉。比如这个 ADL ,其恶心程度在 C++ 的各种 feature 里绝对排得上号。 这玩意经常在意想不到的地方恶心到你,还往往难以排查。具体表现为你在当前的命名空间里自己定义了一个函数,结果在调用它的时候编译器却找到了十万八千里外的另一个同名函数,而你明明没有在当前命名空间引入该函数。这种情况甚至不会有一个提示。假如是不知道这个 feature 的 C++ 新人,怕是 debug 一天也找不到哪里出了问题。 这种行为直接破坏了命名空间的封装意义,要知道无数的 header only 库都在用命名空间来对外隐藏内部符号(谁让 C++ 的模块机制拖延了这么久呢),你都没法知道什么时候就和别人函数名字撞上了。 最近发现了 C++ 名称查找的又一个恶心设计。来请出我们的主角,C++ Standard Draft N3337 10.2 Member name lookup [class.member.lookup]: Member name lookup determines the meaning of a name (id-expression) in a class scope (3.3.7). Name lookup can result in anambiguity, in which case the program is ill-formed. For an id-expression, name lookup begins in the class scope of this; for a qualified-id, name lookup begins in the scope of the nested-name-specifier....

2021-06-23 · QuarticCat

C++:更好的访问者模式

引言 C++ 作为一门没有直接在语言层面支持 tagged union 的 OOP 语言,在进行诸如操作 AST 一类的处理时常常会采用访问者模式。我大一时写的一个弱智解释器中也是如此。很可惜当时在编程水平和 deadline 的双重限制下没能好好研究,时隔近一年,我对访问者模式也有了更多的理解,打算讲讲这个设计模式的问题和 C++ 中的对应解决办法。 起步 相信所有人初学访问者模式的时候见到的都是类似下面这样的代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 struct FooAcc; struct BarAcc; struct Visitor { void visit(FooAcc&); void visit(BarAcc&); }; struct AccBase { virtual void accept(Visitor& visitor) = 0; }; struct FooAcc: AccBase { void accept(Visitor& visitor) override { visitor....

2021-03-10 · QuarticCat

C++:把字符串编码进类型里

又到了我第 114514 喜欢的类型体操环节。这篇文章不当正经人了,想到啥写啥。 这玩意有什么用 非要举一个具有实用意义的场景的话,PEGTL 是我能想到的一个很好的例子。这是一个 parser combinator 库,它使用类型来组合 parser ,比如这样: 1 struct separater: star<one<' ', '\t', '\r', '\n'>> {}; 那么要 parse 一段字符串的时候当然就要把字符串信息编码进类型里面了。 我在自己的玩具 parser combinator 库里也用了这种方法,只不过我写法上使用变量来组合。 除此之外,著名的 fmt 库也用到了这个东西来进行大量的编译期字符串操作。但它为了兼容性,实现方式都比较原始,而且重复实现了大量标准库中后来加入或者被标记为constexpr的东西,也许我有时间会用 C++20 实现一个简易版的 fmt 库。 不就是个char...吗 看了上面的例子,肯定有人会这么想。但其实再想想,我们可以有好几种方案在模板参数里接收一个字符串: 1 2 3 4 5 6 7 8 9 template<const char* /* , size_t N */> struct Str1 {}; template<char...> struct Str2 {}; // Need C++20, will explain later template<SomeUserDefinedString> struct Str3 {}; 为什么这里不写数组类型呢,因为在模板参数里,数组类型会被自动替换成指针,和第一种方案实际上是一样的。总之就这么三个,我们一个一个来讲。...

2021-03-05 · QuarticCat

C++:编译期类型信息

引言 尽管标准库中已经有了typeid运算符,但是由于其需要支持检查多态类型,带来了非常多的限制: 它必须启用 RTTI(Run-Time Type Information)。而很多项目是禁用 RTTI 的,所以无法使用typeid。 它可能对表达式进行求值,详见 cppreference 。这可能带来意外的运行时开销甚至副作用,尤其是常用的sizeof和decltype都是完全静态的,不熟悉typeid的程序员可能完全意识不到这种动态行为的产生。 它不是constexpr的,即使其类型本可以静态求出。这意味着很多场景都无法使用 typeid,比如模板参数、switch-case 语句的 case 值等。 这就是我们为什么需要编译期类型信息,即 CTTI(Compile-Time Type Information)。 实现原理 C++ 标准中并没有提供相关的设施供我们实现这一功能。但通过 GCC 和 Clang 的一个特殊的预定义变量__PRETTY_FUNCTION__,CTTI 得以实现。这个变量的值是当前函数完整签名的字符串。当在一个模板函数内部调用的时候,也会包含模板参数的类型名,这就达到了我们获取类型名字的目的。 注意,类似于标准中提供的__func__,__PRETTY_FUNCTION__是一个变量,因此它没法被用来初始化字符数组或者跟字符串字面量拼接在一起。MSVC 没有__PRETTY_FUNCTION__,但是有一个类似功能的宏__FUNCSIG__,它被替换为一个字符串字面量。 1 2 3 4 template<typename T> constexpr std::string_view pretty_function() { return __PRETTY_FUNCTION__; } 在 Clang 上,调用pretty_function<int>()会返回std::string_view pretty_function() [T = int],可以看到T的类型正在其中。 请注意,这里的typename T不能直接省略成typename,否则将不会出现T的类型名。 当我们确定了函数名之后,返回的字符串的格式就确定了。我们可以去掉无用的前后缀,从而提取出我们实际需要的类型名。 1 2 3 4 5 6 7 8 9 10 constexpr const char PREFIX[] = "std::string_view pretty_function() [T = "; constexpr const char SUFFIX[] = "]"; template<typename T> constexpr std::string_view type_name() { auto name = pretty_function<T>(); name....

2021-02-14 · QuarticCat