TimothyQiu's Blog

keep it simple stupid

std::error_code 和它的朋友们

分类:技术

前几天看 API 文档时候遇到了 std::error_code 这个东西,当时以为是 errno 的 Alias,后续查阅文档才发现并没有那么简单。

阅读剩余部分...

《C++ 并发编程实战》读书笔记: 管理线程

分类:技术

最近终于找到本有兴趣的书啦,就是这本《C++ 并发编程实战》。我会找一些自己觉得没想到、好玩、或者有自己想法的地方整理下。

顺带吐个槽:In Action 系列的封面人物真心诡异,还是 O'reilly 萌萌哒的奇怪可爱小动物看着顺心。

join() 的异常安全

std::thread 要求在析构函数被调用时,该对象必须没有与之相关联的线程,否系统分分钟自尽给你看(调用 std::terminate())。

一般情况下,我们主要需要注意的地方是析构前对 join() 或者 detach() 的调用。如果要分离线程,线程启动后就可以立即调用 detach(),基本不会带来什么问题。而 join() 则没法立即调用,这样就会带来可能会被忽视的异常安全问题:线程启动后,如果某处抛出异常,可能把本应执行的 join() 跳过,导致程序自行退出。

void foo()
{
    std::thread t(thread_func);
    do_something();  // 如果抛出异常,就可能把下面的 join() 跳过
    t.join();
}

do_something();try / catch 包裹起来,并在 catch 里调 t.join() 最后把异常重新 throw 出去的方案固然可行,但对于 C++ 而言,更好的方案是 RAII:

class thread_guard
{
public:
    explicit thread_guard(std::thread& t)
        : thread_(t)
    {
    }

    ~thread_guard()
    {
        if (thread_.joinable()) {  // join() 前对象必须满足 joinable
            thread_.join();
        }
    }

    thread_guard(thread_guard const&) = delete;
    thread_guard& operator=(thread_guard const&) = delete;

private:
    std::thread& thread_;
};

void foo()
{
    std::thread t(thread_func);
    thread_guard g(t);

    do_something();
}

当然你也可以考虑把 std::thread 移动进去而不是传引用,书里管那种东西叫 scoped_thread,调用时不必为 std::thread 对象单独开一个名字。

线程传参二三事

给线程函数传参是通过 std::thread 的构造函数完成的,其原理与 std::bind 类似。所有参数先在当前线程被复制 / 移动到对象内部,然后在新线程中完成对线程函数的调用。

这两步的划分会导致会被一些人说「坑」(虽然实际上是他们自己没注意)。

比如从「被复制」到「实际调用线程函数」之间可能并不连续,那么被复制的参数届时是否还有效就可能成为问题,例如:

void thread_func(std::string const& s);

void foo(int bar)
{
    char buffer[1024];
    sprintf(buffer, "%d", bar);
    std::thread t(thread_func, buffer);
    t.detach();
}

前面说过构造函数仅负责原样复制 / 移动参数,所以 char *std::string 的转换是在新线程中的第二步时做的,于是例子中 t 对象构造函数暂存的其实是指向栈上的 buffer 的指针。而由于 detach()foo 返回后可能新线程还未正式启动。如果 thread_func 真正被调用时 foo 已经返回,那么这个指针参数就无效了。

一个解法是把代码改成 std::thread t(thread_func, std::string(buffer));这样构造函数就会把实参 std::string 移动进去(即便在 std::string 无法移动只能复制的平行宇宙,这样做也是安全的)。

用 STL 寻找前 K 个最大的数

分类:技术

前几天找资料,顺手看到了这篇博文,讲了博主如何优化自己以前的算法的过程。于是立马想起了 GoingNative 2013 上的演讲 C++ Seasoning 以及前不久看到的这篇 From goto to std::transform。于是不禁想,「寻找前 K 大数」这样的任务,能不能直接用 C++ 标准库来完成?如果能的话,性能又如何呢?于是我重新登录了那个以前做了两道题就尘封多年的 OJ 帐号……

凭着最直观最 naïve 想法,第一个版本我用了 std::sort 来代替手工排序。不出所料,这样的做法跑了 562 ms,要排到 700 名开外的样子。

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>

int main()
{
    int numVillagers;
    int topCount;

    while (scanf("%d %d\n", &numVillagers, &topCount) == 2) {
        if (numVillagers == 0 && topCount == 0) {
            break;
        }

        std::vector<int> wealth(numVillagers);
        for (int i = 0; i < numVillagers; i++) {
            scanf("%d", &(wealth[i]));
        }
        std::sort(wealth.begin(), wealth.end(), std::greater<int>());

        if (topCount > numVillagers) {
            topCount = numVillagers;
        }

        for (int i = 0; i < topCount - 1; i++) {
            printf("%d ", wealth[i]);
        }
        printf("%d\n", wealth[topCount - 1]);
    }
}

于是优化:考虑到每次新建 std::vector 的开销,把 wealth 拎出来放到循环外,reserve() 题目中的最大值,每次在循环里重新 resize() 后,时间顿时缩短到了 296 ms,可以排到 180+ 的样子。

std::vector<int> wealth;
wealth.reserve(100000);

而在前面说过的演讲中,我还听到了一个之前从未留意的函数 std::nth_element。其作用是确保调用后第 N 个元素是范围内第 N 大的元素。调用后,[begin, N) 内的任意元素都小于 (N, end) 内的任意元素。

std::nth_element(wealth.begin(), wealth.begin() + topCount, wealth.end(), std::greater<int>());
std::sort(wealth.begin(), wealth.begin() + topCount, std::greater<int>());

尝试修改成以上的略显罗嗦的代码后,程序运行时间缩短到了 171 ms,可以排到 70+ 的样子。时间上和博文中给出的最小堆实现相同,但是内存占用要比它大很多。

既然上面是先用 std::nth_element 大致排序了一下,而后再用 std::sort 排序前半部分,那么,STL 里是否存在一次性只排 [begin, N] 范围内的数,而无视 (N, end) 内的顺序的函数呢?答案是存在,可以直接使用 std::partial_sort 解决。

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>

int main()
{
    int numVillagers;
    int topCount;

    std::vector<int> wealth;
    wealth.reserve(100000);

    while (scanf("%d %d\n", &numVillagers, &topCount) == 2) {
        if (numVillagers == 0 && topCount == 0) {
            break;
        }

        wealth.resize(numVillagers);
        for (int i = 0; i < numVillagers; i++) {
            scanf("%d", &(wealth[i]));
        }

        if (topCount > numVillagers) {
            topCount = numVillagers;
        }

        std::partial_sort(wealth.begin(), wealth.begin() + topCount, wealth.end(), std::greater<int>());

        for (int i = 0; i < topCount - 1; i++) {
            printf("%d ", wealth[i]);
        }
        printf("%d\n", wealth[topCount - 1]);
    }
}

此时的程序执行时间 156 ms,排名第 25 位。而截止到此时,我个人其实什么都没有干,实际任务都交给了 STL。

如同各种 MyStringMyVector 一样,一般情况下自己去实现这些通用算法在 STL 面前几乎没有任何优势。尤其是 C++11 带来 lambda 表达式以来,大大方便了 <algorithm> 中各种算法的使用,我觉得不去用 STL 的理由越发稀少了。

以上。

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 存储,实际提供的 API 本身也都是 Unicode 版本的,即以 W 结尾的版本。而相应的 A 结尾的 ANSI 版本则是在 W 版本基础上的封装。

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

以上。

小试 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;

阅读剩余部分...