TimothyQiu's Blog

keep it simple stupid

Windows 核心编程:字符串查漏补缺

趁着双十一买了好几本想买的书,其中就有这本《Windows 核心编程》。首先需要吐槽的就是好好的《Windows via C/C++》这么高端大气上档次的名字怎么就被翻译成了这么个蛋疼样,而且中文版的封面也是扑面而来的一股浓郁的上个世纪气息,以至于在正文里看到 Vista 的字样都感觉各种穿越……

本文是关于这本书的第一篇读书笔记。天知道会不会有第二篇。

虽说之前已经写过好几篇关于字符编码的文章,都快写吐了,不过读了这本书的开篇还是感觉相见恨晚。这里对于前面这几篇里关于字符串的说明进行一下查漏补缺。

Unicode 和 UTF-16

前文书说到,Unicode 定义的是码位(Code Point),即为每一个字符赋一个唯一编号,记作 U+XXXX。Unicode 目前实际占用了 016 到 10FFFF16 的码位,有些已经分配了字符,有些还没有。

Unicode 中最初推出的 U+0000 到 U+FFFF 这 216 个码位称为基本多文种平面(Basic Multilingual Plane,BMP)。早年只有这一个平面的时候,Unicode 与 UTF-16 是等价的,因为可以做到一一对应。然而时过境迁,区区 16 位已经满足不了 U+10000 到 U+10FFFF 的码位了。

与 UTF-8 编码规则的爽快不同,UTF-16 在沦为实实在在的「编码」时,还需要考虑到向后兼容性问题。如何在维持 U+0000 到 U+FFFF 一一对应的同时,把剩余的 U+10000 到 U+10FFFF 编进来?

答案是:把 U+D800 到 U+DFFF 命名为 UTF-16 编码专用字符。即如果 UTF-16 数据流中出现了这一范围内的字符,意味着它本身不是一个字符,紧接着它的 16 位数据需要加上一定的偏移值才是真正的数据。

这一土豪做法让我目瞪口呆。至于 UTF-32,目前来说与它与 Unicode 码位一一对应起来绰绰有余。当然,如果哪天发现了外星文明,需要把他们的字符也编码进来,导致 Unicode 占用的码位暴增,说不定这一一对应的任务就只能交给未来的 UTF-64 了。这就是把问题留给子孙后代去解决的大智慧啊!

CHARLPSTR

前文书里吐槽过 Windows API 的丑陋不堪,也说过这也是历史遗留、不得已而为之。

没错的,CHARchar 在语义上并不等价,前者专指 8 位字符,后者则只是字符而已,说不定在哪个古董机器上就是 7 位了。(尽管我不认为你会在那上面跑 Windows……)

LPSTR 尽管被定义为 CHAR *,但它实际上还借助了编译器扩展实现了「以 NUL 结尾」的语义:

typedef __nullterminated CHAR *LPSTR;

Unicode 和 ANSI 版本

说实话我依旧不喜欢官方的这两个名字,我更喜欢「宽字符版本」和「多字节字符版本」这两个更拗口但更准确的名字。

由于现代 Windows 内部都是以 UTF-16 存储(承袭自 UCS-2),实际提供的 API 本身也都是 Unicode 版本的,即以 W 结尾的版本。而相应的 A 结尾的 ANSI 版本则是在 W 版本基础上的封装。

于是可以想象,全局使用 ANSI 相比全局使用 Unicode 而言要占更多的内存,理论上也要更慢一些。

以上。

Direct Access

由于众所周知的原因,Google Search 是不稳定的。作为一个怕麻烦的小朋友,我几乎把所有 Google 相关的高危域名都列在 Proxy SwitchySharp 的切换规则里。

我这么做也算是牺牲速度带来省心吧,然而 Google Search 有一个蛋疼的地方,就是所有的搜索结果在你点击时都会先走 Google 自己的页面,重定向一下之后才会进入搜索结果对应的 URL。

生命在于折腾。忍了很久以后,今天突然兴起,囫囵吞枣地看了下 Chrome 官方的扩展开发文档,于是就有了这个 Chrome 扩展,代码和成品放在了 Github 上。尽管统计功能还存在已知的 Bug,但目前来说还是比较够用的,留待日后慢慢完善吧~

过段时间有空估计会折腾下放 Chrome Store 里去……

Ok 一段时间过去了,在同学的大力帮助下成功注册了 Chrome 开发者帐号,现在已经可以在 Chrome Store 里找到啦~(虽说估计应该没什么人会去用……)

来自 2020 年的说明:因为 Google 的改版,以及现在基本都随时翻墙,所以我已经放弃更新这个项目了。

p.s. 发现一个非常不错的生成简单图标的网站: iconmonstr

小试 Variadic Template

本文源自于今天对 neuront 童鞋的这篇文章的末尾的那段代码的 C++ 实现的思考。(好多「的」……)

尽管 std::accumulate() 和 Python 的 reduce() 类似,但因为 C艹 的 std::map<std::string, std::map<std::string, int>>std::map<std::string, int> 是不同的类型,所以似乎只能自己用可变参数模板写一个了。

简单起见,我们还是退一步,来解决一个更简单、更不通用、而且似乎和 reduce() 完全无关的问题吧:如何才能一次性取得任意层次的字典值?用更直白的代码表达,就是我们需要一个 GetMapValue() 函数,实现这样的功能:

// 用于缓解眼花缭乱感的宏
#define MAP_LITERAL(...) { __VA_ARGS__ }

// 简单映射
std::map<std::string, std::string>
simple_dict = MAP_LITERAL({"Hello", "World"});

// 「我勒个去居然这么麻烦」映射
std::map<std::string,
         std::map<std::string,
                  std::map<std::string,
                           int>>>
nested_dict = MAP_LITERAL( { "x", MAP_LITERAL( { "y", MAP_LITERAL( { "a", 10 } ) },
                                               { "z", MAP_LITERAL( { "b", 20 } ) } ) });

auto value1 = GetMapValue(simple_dict, "Hello");
std::cout << value1 << std::endl;

auto value2 = GetMapValue(nested_dict, "x", "y", "a");
std::cout << value2 << std::endl;

初始的版本

初步分析,GetMapValue() 需要接受一个 Map 以及至少一个 Key。如此,参数可变,首选 C++11 的可变参数模板。一次性将所有 Key 拿到手后,每次用第一个 Key 获取下一级 Map,而后用余下的 Key 递归,最终获取所要的值。而要写递归,最好先从最简单的情况写起。

template <typename MapType>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key)
    -> typename MapType::mapped_type
{
    return map.at(key);
}

鉴于本人目前对于右值引用还不熟悉,就只用 const& 了(& 只能引用左值;const& 既能引用左值、又能引用右值,但无法修改)。

这里需要注意的是 STL 的几种 Map 里 typedef 到的数据类型,略坑:

不过这样一来,我们的 GetMapValue() 就可以在 STL 的这几种 Map 里通用了。

不被支持的递归 decltype 模板

本来我想,递归版本按照上面这个最简版本写一下就 OK 了。可变参数模板的基本用法我以前的日志有写过;这里唯一麻烦的是返回值,因为通用性,只有最终被调用的版本才知道确切的返回值,不过 decltype 似乎可以救场:

template <typename MapType, typename... MoreKeyTypes>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key,
                 typename MapType::mapped_type::key_type const& anotherKey, MoreKeyTypes... moreKeys)
    -> decltype(GetMapValue(map.at(key), anotherKey, moreKeys...))
{
    return GetMapValue(map.at(key), anotherKey, moreKeys...);
}

然而,编译器不给面子,直接提示模板推导失败,decltype 时找不到接受两个 Key 版本的 GetMapValue()(三个参数)。

似乎,decltype 是不支持递归调用的,亦或者推导时自身还不存在。decltype 以及模板的一些规则真心还不是很熟,所以暂时没有找到真凭实据。

Traits

于是我终于知道为什么世界上会有 Traits 这种东西存在了。(比如 std::basic_string 的模板参数之一就是 class Traits = std::char_traits<CharT>。)Traits 是用来描述某个类型周边信息的东西。这里,我们需要一个 Traits 来计算一个 Map 被使用若干次 Key 后的 Value 类型。

那么很显然的,这个 MapTraits 依旧是可变参数模板、依旧是递归实现。

template <typename MapType, typename KeyType, typename... KeyTypes>
struct MapTraits
{
    typedef typename MapTraits<typename MapType::mapped_type, KeyTypes...>::mapped_type mapped_type;
};

template <typename MapType, typename KeyType>
struct MapTraits<MapType, KeyType>
{
    typedef typename MapType::mapped_type mapped_type;
};

完全体

不出所料,最终的代码是一番如此纠结的景象。看这样的代码眼睛压力山大。

template <typename MapType>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key)
    -> typename MapType::mapped_type
{
    return map.at(key);
}

template <typename MapType, typename... MoreKeyTypes>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key,
                typename MapType::mapped_type::key_type const& anotherKey, MoreKeyTypes... moreKeys)
    -> typename MapTraits<typename MapType::mapped_type, typename MapType::mapped_type::key_type, MoreKeyTypes...>::mapped_type
{
    return GetMapValue(map.at(key), anotherKey, moreKeys...);
}

完整的测试代码见这个 Gist:https://gist.github.com/timothyqiu/6877974

Traits 的小插曲

我第一次写的时候,把 MapTraits 的特化形式写成了这样:

template <typename MapType>                             // 正式版本: typename MapType, typename KeyType
struct MapTraits<MapType, typename MapType::key_type>   // 正式版本: MapType, KeyType
{
    typedef typename MapType::mapped_type mapped_type;
};

其实只是用 typename MapType::key_type 替换了一个正式版本里的模板参数 KeyType 而已。这样做其实也并非不可,只不过产出的是「高标准、严要求」的代码:

// 正式版本可行,但是在这个版本里一堆模板错误
auto value2 = GetMapValue(nested_dict, "x", "y", "a");

// 两个版本都可行
auto value2 = GetMapValue(nested_dict, std::string("x"), std::string("y"), std::string("a"));

原理大致是,这个版本因为把特化形式的第二个模板参数固定成了第一个参数的 key_type,所以如果使用了和 key_type 不同但是可以隐式转换的类型,会导致模板推导失败。

字符串之惑

C 语言中的字符串

抽象数据类型

C 语言贴近机器模型,所以并不提供字符串数据类型。但是,字符串却在 C 语言中作为 ADT 存在着:使用字符指针代表字符串,同时提供了 string.h 作为字符串的操作库,而在实际存储时则使用字符数组。

虽说单引号引起的字符是该字符对应的一个整型常量,但是 'A' 和 65 没有任何关系。因为 C 语言并没有要求每个实现都用 ASCII 字符集作为执行字符集。

事实上,C 语言标准要求每个 C 语言实现都要定义两个字符集:代码字符集、执行字符集。每个字符集又都由基础字符和扩展字符构成。扩展字符可有可无,完全由该实现所支持的区域设置决定;基础字符只划定了字符,字符对应的码位留由实现决定。

字符与 char 类型

字符集顾名思义就是字符的集合,字符集除了划定所包含的字符外,还将其所包含的字符按照一定顺序编号,这样的编号称作码位。著名的 ASCII 参照已有电报报文设计,分别用数字 0 到 127 作为英文大小写字母、阿拉伯数字、标点符号等的码位。由于出现早、使用广,后辈字符集、字符编码几乎都与之兼容为荣。

然而 ASCII 本身并不完美,尽管名字叫「美国信息交换标准代码」,但是却连英语中的一些诸如 naïve、café、élite 的外来词都无法表示,欧洲各国那些稀奇古怪的字母就更别提了。所幸,我们很快来到了一个字节 8 位的年代,char 能够容纳 0 到 255 一共 256 个值,于是各国纷纷物尽其用,将一个字节中 ASCII 并没有用到的 128 到 255 对应为自己国家所需要用到字符。这些五花八门的对应规则便是后来的代码页(code page),同样的值可以在不同的代码页中表示不同的字符。

到目前为止,char 类型还算是名副其实的字符类型。然而,东亚文化圈广泛使用的汉字成千上万,少说也需要上千个码位,一个字节所能提供的这区区 256 个码位实在是杯水车薪。

计算机科学里的任何问题都可以通过增加一个中间层来解决。

既然码位不得不超过 255,一个字节放不下,那么将以前的「码位→字节」变成「码位→编码→字节序列」如何?

举个栗子:Unicode 字符集中,字符「汉」的码位是 27721(十六进制 6C49),一个字节显然容不下,我们可以通过 UTF-8 编码将其变成字节序列。

  1. 通过字符集找到对应码位:汉→ U+6C49
  2. 根据 UTF-8 编码规则,介于 U+0800U+FFFF 之间的码位需要按照 1110xxxx 10xxxxxx 10xxxxxx 的形式编码为三个字节;
  3. 6C49 的二进制形式是 0110 1100 0100 1001,代入上面的模板得到 11100110 10110001 10001001
  4. 得到最终的字节序列 E6 B1 89

看上去不错,但这样一来,char 这个「字符」类型就有点名不副实了:一个 char 可能只是一个字符的一部分,只有两个或者更多的 char 拼起来才能够表示一个字符。更为麻烦的是,相关的标准库也变得不再可靠了:类似 strlen() 这种 too simple, sometimes naive 的方法顿时从返回字符串的字符数降级成了返回字符串的字节数。

printf("%zu\n", strlen("\xE6\xB1\x89"));  // 输出 3;但实际上只有一个字:汉

多字节字符串

为了解决 strlen() 的这种尴尬,C 语言中引入了「多字节字符串」(multibyte string)的概念,一个字符可以对应多个字节;而原先的字符串则对应称为「字节字符串」(byte string),一个字符只能对应一个字节。

char const *multibyteString = "Hello 世界";  // 和普通字符串没什么区别

多字节字符串依旧是 char *,所以这两者的区别其实只是抽象概念上的,何况严格来说,字节字符串也是一种特殊的多字节字符串。

不同的编码每个字符占用的字节数可能不同,即便是同一种编码,不同的字符也可能占用不同的字节数。所以多字节字符串面临的主要问题便是「下一个字符到底占几个字节」。C 语言引入了 mblen() 函数来回答这个问题:

int mblen(char const *s, size_t n);

其中 s 是一个多字节字符串,而 n 表示至多检查多少个字节;这个函数会根据当前区域设置(Locale)的 LC_CTYPE 分类中所指定的编码来解析这个多字节字符串,返回该字符串的字一个字符占几个字节。

char const *multibyte= "\xE6\xB1\x89"; // 「汉」的 UTF-8 编码
printf("%d\n", mblen(multibyte , 5));  // 输出 -1;因为默认区域设置为 C,无法识别这样的序列。
setlocale(LC_CTYPE, "en_US.UTF-8");    // 非 Windows 平台用,Windows 平台不支持 UTF-8 的区域设置 
printf("%d\n", mblen(multibyte, 5));   // 输出 3;因为当前区域设置为 UTF-8 编码。

宽字符 wchar_t

多字节字符串的引入终于算是「一定程度上解决了问题」,但这种做法实在繁琐。于是,C 语言同时引入了宽字符类型 wchar_t 和配套支持库 wchar.h,试图一劳永逸地解决这个问题。

wchar_t const *wideString = L"Hello World";  // 使用前缀 L

char 的一个字节不同,wchar_t 类型本身可以占多个字节,保证永远与字符一一对应,省下了编码的步骤。如此就可以通过 wchar.h 中提供的 wcslen() 函数正确计算 wchar_t * 字符串中的字符数了。

多字节字符串和宽字符串的转换

mblen() 类似,C 语言提供了两组共四个函数,根据当前的区域设置进行多字节字符(串)和宽字符(串)的转换。

误区

看到这里,你是否想过这个能够保证与字符一一对应的 wchar_t 类型到底需要占几个字节呢?没错,不一定占多少,但总之至少一个字节就对了!

事实上,关于 wchar_t 的准确要求是:能够容纳下所支持的区域设置中,最大的扩展字符集中的每一个码位。

an integer type whose range of values can represent distinct codes for all members of the largest extended character set specified among the supported locales.

也就是说,如果有一个只支持 ASCII 字符集的奇葩的 C 语言实现存在,那么在这个实现下,wchar_t 完全可以只占 8 位。

如此,我们经常听到的「宽字符和 Unicode 有关」的说法也就不攻自破了。

C11 中引入的定长字符类型

时过境迁,转眼到了 2011 年。正如 C99 中在 stdint.h 中加入了 uint32_t 之类的定长整数类型一样,C11 也引入了两种定长字符类型以满足 Unicode 的需要:

同时,继 string.hwchar.h 后,又进入了 uchar.h 作为这两种字符类型的支持库。

char16_t *utf16String = u"Hello UTF-16";  // 使用前缀 u
char32_t *utf32String = U"Hello UTF-32";  // 使用前缀 U

C++ 中的字符串

C++ 极尽所能兼容 C 语言,陆续支持了和 C 语言相同的那些 charwchar_tchar16_tchar32_t 类型,这里就不再重复了。

至于 std::string,用 C++ 不可能没听说过,它封装了常用的字符串操作。但你是否知道 std::wstring 的存在呢?

如果有心,你会发现 std::string 实际上是对 std::basic_string<T> 模板的特化,形式类似于:

typedef std::basic_string<char>    std::string;
typedef std::basic_string<wchar_t> std::wstring;

至于 C++11 中,由于 char16_tchar32_t 的引入,也对应增加了 std::u16stringstd::u32string 的特化版本。

std::basic_string::data() 在 C++11 以来的改变

std::basic_string<T> 其实只是对 T 字符数组的封装,如果需要使用 C 风格的字符串 T *,可以通过 c_str() 方法获取。

而如果说 c_str() 方法表示「获取该类对应的 C 字符串表示」的语义,那么 data() 方法则表示「获取该类实际保存的数据」的语义。

在 C++11 之前,通过 data() 方法获取的 T * 并不保证 NUL 结尾,即仅保证 [data(), data() + size()) 有效。而自 C++11 起,data() 变为保证 NUL 结尾,与 c_str() 的行为完全相同。

从 C++17 开始,我们还可以 data() 方法获取可修改的缓冲。

Windows API 中的字符串类型

不得不说,Windows 的各种大写的自定义类型实在丑陋得令人发指。经常不由得让人发出「好好起名字会死么?」的感叹。

#define CHAR    char
#define LPSTR   char *
#define LPCSTR  char const *

#define WCHAR   wchar_t
#define LPWSTR  wchar_t *
#define LPCWSTR wchar_t const *

当然,微软如此做法自然有其历史原因,我对所谓的「向前兼容」表示非常无奈。不过话说回来,除了 Windows API 如此大张旗鼓地使用 wchar_t,其余地方真不怎么能见到宽字符的身影。现代 Windows 内部使用 UTF-16,所以 wchar_t 能够保证是 16 位的。

Windows API 中所有与字符串相关的函数、数据结构等,都存在 ANSI 和 Unicode 两个版本,可以通过宏 UNICODE 来切换。比如一个普通的 MessageBox() 函数,实际定义是这样的:

int MessageBoxW(HWND hWnd, LPCWSTR text, LPCWSTR caption, UINT type);  // 宽字符串版本
int MessageBoxA(HWND hWnd, LPCSTR  text, LPCSTR  caption, UINT type);  // 多字节字符串版本

#ifdef UNICODE
#define MessageBox MessageBoxW
#else
#define MessageBox MessageBoxA
#endif

字符类型也是类似,使用 TCHAR 作为一个通用的字符名字。字符常量则使用 TEXT() 宏来定义。

#ifdef UNICODE
#define TCHAR    WCHAR
#define TEXT(s)  L ## s
#else
#define TCHAR    CHAR
#define TEXT(s)  s
#endif

如果你用的是 Visual C++,这个 UNICODE 宏通常并不需要手动设置,而是作为工程属性的一员出现的。

p.s. 不要被这个宏的名字骗了,还记得之前我们说过的 wchar_t 和 Unicode 一点关系都没有吗?可以这么理解:wchar_t 只在 Windows API 中表示 UTF-16 数据。

宽窄字符串的转换

Windows 平台也可以用之前提到的四个函数转换 char 字符串和 wchar_t 字符串。但 Windows 本身提供的 API 似乎更有效率:

再次吐槽 M$ 这蛋疼的命名,命名是转换字符串,起名字起得跟转换单个字符一样。

BSTR

BSTR 可以解释为 Basic String 或者 Binary String,是 Windows 下用于 COM、自动化的字符串类型。定义为:

typedef OLECHAR *BSTR;

OLECHAR 是 Windows 的历史遗留,类似于根据宏 OLE2ANSI 转换的 TCHAR,但 OLE2ANSI 是 16 位时代的产物,于是 Win32 环境下,OLECHAR 永远是 WCHAR,也就是 wchar_t

尽管如此,BSTR 并不能等同于 OLECHAR *,因为它们的内存布局不同:BSTR 在它自身前拥有一个四个字节的前缀、以双 NUL 结尾。其中,前缀用于描述字符串内容所占的字节数,它本身所指向的是字符串内容而非长度。

-4          0           2           4           6           8          10        
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|     6     |     H     |     i     |     !     |    NUL    |    NUL    |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            ↑
            bString

这一点,从用于创建 BSTR 的接口 SysAllocString() 便可以看出:

BSTR SysAllocString(OLECHAR const *psz);

倘若 BSTROLECHAR * 相同,那么岂不变成了鸡生蛋、蛋生鸡的问题?

虎头蛇尾

呃……前面讲 C 语言字符串的时候似乎还是觉得挺有说头,足足规划了一个星期之久,但后面似乎越来越不知道该讲什么,留待日后积累到新的东西再完善吧~

以上。

无锡求职有感

回到无锡一年了,能让人感觉有归属感的工作始终没有找到。因为这一年间换了两份工作,所以在面试时经常被质疑人品;尽管我也尽力解释,但还是感觉不吐个槽迟早会憋出心理疾病。

我起初有些太理想主义,但很快就不得不对现实作出妥协:我曾下决心,但凡在职位要求上写「精通 C++」的公司一律无视;无奈现实是,无锡这样的二线城市的公司,几乎没有不写这个让自己显得很外行的要求的。

家人总是说我自命清高、不明事理。回无锡后的第一份工作我就是因为受不了公司从上到下的各种「国企范儿」的陋习才离职的。为了图省事,我喜欢以「环境压抑,马屁随处可见,而且给人感觉公司的主业是混补助」作为总结。有一次面试时,面试官听毕,带着一副「你是怎么活到这么大的」的理所当然的表情陈述道:「这样的公司很多呀!」我哭笑不得,只好耸耸肩说:「我个人比较……呃……看不得这些吧……」。

我的运气大抵都消耗在毕业后的第一份工作上了,所以辞职回无锡后接二连三碰见奇葩公司。在无锡的第二份也就是最近这份工作简直是不堪回首:

千言万语汇成一句话:老板太奇葩,以致于我和同事经常对这公司是不是一个大型实景整人秀表示怀疑。

有一个 HR 在交流中不断流露出「你这么频繁地换工作,是为了钱么」的暗示,我感觉我的玻璃心碎了,于是当晚写了一封长信去辩解。

有一位 HR 的话我觉得还是有道理的:这里很多软件公司都是趁着员工年轻赶紧压榨型的。我感觉,悲剧在于:一方面,程序员作为一个常见职业的时间并不长,但社会却已经把程序员自嘲的「苦逼」二字当真了,于是是个人就觉得程序员就应该很苦逼;另一方面,不少老板并非技术出身,不了解软件行业,以为软件开发是劳动力密集型产业,以为多干一小时就能多产出效果。

诶,不该心高气傲,找到个差不多的工作做着就行了……吧?

定公問:君使臣,臣事君,如之何。孔子對曰:君使臣以禮,臣事君以忠。 《论语·八佾》

所謂大臣者:以道事君,不可則止。 《论语·先进》

君有過則諫,反覆之而不聽,則去。 《孟子·万章》