Helanic Abyss

A Quiz of C++ const

Answeror — Mon, 25 Apr 2011 23:52:10 +0800

在vs2010环境下, 如下程序会输出什么?

#include <string>
#include <iostream>
using namespace std;

template<class T>
struct print;

template<>
struct print<int> { static string name() { return "int"; } };

template<class T>
struct print<T&> { static string name() { return print<T>::name() + " &"; } };

template<class T>
struct print<const T> { static string name() { return "const " + print<T>::name(); } };

// just utility functions above

struct S { int i; };

template<class T>
void foo(T) { cout << print<T>::name() << endl; }

template<class T>
void bar(T&) { cout << print<T>::name() << endl; }

int main() {
    int i;
    const int ci = 0;
    const int *pci = &i;
    S s;
    const S *pcs = &s;

    foo(i);
    foo(ci);
    foo(*pci);
    foo(pcs->i);

    bar(i);
    bar(ci);
    bar(*pci);
    bar(pcs->i);

    {
        auto a1 = i;
        auto a2 = ci;
        auto a3 = *pci;
        auto a4 = pcs->i;
        cout << print<decltype(a1)>::name() << endl;
        cout << print<decltype(a2)>::name() << endl;
        cout << print<decltype(a3)>::name() << endl;
        cout << print<decltype(a4)>::name() << endl;
    }

    {
        auto& a1 = i;
        auto& a2 = ci;
        auto& a3 = *pci;
        auto& a4 = pcs->i;
        cout << print<decltype(a1)>::name() << endl;
        cout << print<decltype(a2)>::name() << endl;
        cout << print<decltype(a3)>::name() << endl;
        cout << print<decltype(a4)>::name() << endl;
    }

    cout << print<decltype(i)>::name() << endl;
    cout << print<decltype(ci)>::name() << endl;
    cout << print<decltype(*pci)>::name() << endl;
    cout << print<decltype(pcs->i)>::name() << endl;

    cout << print<decltype((i))>::name() << endl;
    cout << print<decltype((ci))>::name() << endl;
    cout << print<decltype((*pci))>::name() << endl;
    cout << print<decltype((pcs->i))>::name() << endl;

    return 0;
}

现在还敢说你精通C++吗?

答案参见此文, 以及我的笔记.

宁静之雨

Answeror — Wed, 20 Apr 2011 22:48:32 +0800

曾经无数次, 我有戳破自己耳膜的冲动.

可是终究因为懦弱和理智无法将之付诸实践, 于是只好借助于音乐, 耳塞, 耳罩, 或者鼓起勇气去与噪音源交涉.

以前无论我用何种方法, 都不可能做到在嘈杂的火车上心无旁骛地看书. 音乐大多会使我分心, 耳塞会伴随耳鸣, 耳罩又几近于隔靴搔痒, 每一种尝试均告失败.

而今天晚上我竟然在回杭州的火车上拿着kindle饶有兴致地看了一个多小时的scheme, 读书效率估计达到了在实验室时的70%.

一周前了解到白噪音的降噪妙用, 并在{ http://www.naturesoundsmp3.net/thunderstorm-cd/ }找到了这一段噪音终结者. 整整一小时的磅礴大雨, 伴随着远方隆隆的雷鸣, 让我得以随时随地感受到那种持久的宁静. 我一直以来对雨天的那种莫名的好感可能也来源于此.

万物的嘈杂都被这雨水冲刷干净, 那种无法言喻的快乐久久回荡在我心头.

Shortcut for Google Bookmarks

Answeror — Thu, 24 Mar 2011 21:13:47 +0800

Click to add bookmark, and double click to manage bookmark. Assign any keyboard shortcut as you wish.

一年前写给自己用的插件. 功能极其简陋. 应Google的要求把名字从”Pure Google Bookmark”改成现在的样子.

下载: { http://goo.gl/gKjTh }

代码: { http://goo.gl/HFKOb }

写这个有几点心得:

chrome没有提供监听双击事件的api, 自己用js计时器实现.
chrome没有给插件提供快捷键支持, 需要自己写js注入到前台页面中去, 我用的是{ http://goo.gl/6xpf }.
localStorage, 正如其名字所示, 是每个页面独有的, 所以background.html和被注入js的页面的localStorage是不能共享的.
前台页面不能使用chrome.extension.getBackgroundPage(), 只能通过消息传递获得options.html里的设置.

什么时候Google Reader, Google Docs和Google Bookmarks的标签功能集成到一块就好了. 或者是不是可以写个插件做集成呢…

C++临时变量的生命周期

Answeror — Sat, 22 Jan 2011 21:16:41 +0800

下面这段程序:

template<class T>
struct bar {
    T t;
    bar(T t) : t(t) {} //#3
    template<class U>
    bar(bar<U> other) : t(other.t) {} //#4
};
void foo(bar<const double&> b) {
    printf("%lf\n", b.t);
}
int main() {
    int a = 42;
    foo(bar<const double&>(a));//#1
    foo(bar<int>(a));          //#2
    return 0;
}

#1和#2虽然都能通过编译, 但是其中有一句是错的. 当然, 很明显#2看上去比较奇怪, 错的八成就是它, 可是初看上去却说不出它为什么错了.

我们来看一个简单一点的例子:

void foo(const double &arg) {}
int main() {
    int a = 42;
    foo(a);
    return 0;
}

相信这样一段代码没人会说它错. a被隐式转换为一个临时的double, 然后arg引用这个临时的double, 直到foo返回, 临时double销毁了. 我们很自然的认为这个临时的double的生命会延续到foo调用结束, 事实的确如此, 下面是C++标准对于这个过程的描述:

12.2.3 [...] Temporary objects are destroyed as the last step in evaluating the fullexpression (1.9) that (lexically) contains the point where they were created. [...]

1.9.12 A fullexpression is an expression that is not a subexpression of another expression.

这个”fullexpression”显然就是指foo(a);了.

现在再来看看开头的例子.

#1中, 在进入bar<const double&>的构造函数#3之前, int被转换成一个临时的double, 这个double作为参数进入#3, 构造出一个临时的bar, 然后这个bar通过bar的拷贝构造函数(注意这时调用的是默认拷贝构造函数, 而不是#4)把这个临时的double传递给foo的形参. 根据上述标准, 这个临时的double是#1的一部分, 所以其生命周期一直延续到#1结束.

#2中, 我们构造了一个临时对象bar<int>, 我们暂且称其为x, 然后在将其赋给foo的形参b时调用了#4, 此时x.t在构造给b.t的时候产生了一个临时的double, 我们称其为y, 然后b.t引用了y, 进入函数foo…

问题在于y属于#2吗? 如果你把”fullexpression”理解成从取a的地址到foo返回CPU所执行的指令序列, 那么显然y当然是这一序列的一部分. 然而事实并非如此, “fullexpression”仅仅指#2这一行C++代码, 一串符号. 而y属于另一串符号t(other.t), 因为y的是在那里创建的, 于是也应该在那里销毁.

最上面的代码原型是我在使用boost::tuple时遇到的, 为了简化问题, 就写了bar代替boost::tuple. 所以并不是说输入参数都写成const引用就好, 当遇到隐式类型转换的时候就要特别小心. 比如把tuple的模板参数写成某个类型的引用作为形参就不是什么好主意. 其它的比如optional, 内部保存引用也有很大风险. 不过因为optional没有泛型的单参数非explicit构造函数, 所以用它作为形参表示可选参数的时候被误用的概率通常比较小.

这个问题的讨论参见这里.

boost::implicit_cast

Answeror — Wed, 29 Dec 2010 18:08:04 +0800

在stackoverflow上看到这个帖子, 于是发现了boost::implicit_cast这个小东西.

先来看看这段代码:

struct top {};
struct mid_a : top {};
struct mid_b : top {};
struct bottom : mid_a, mid_b {};

void foo(mid_a&) {}
void foo(mid_b&) {}
void bar(bottom &arg) {
    foo(arg); // 想要调用"void foo(mid_a&)"
}

int main() {
    bottom x;
    bar(x);
    return 0;
}

是无法编译通过的, 因为foo的重载解析有歧义. 那么把bar里的代码改一改, 为了保持C++风格, 我们使用static_cast, 而不是C风格的转换:

foo(static_cast<mid_a&>(arg));

程序编译通过了, 运行起来也没有问题, 然而…

一个月以后我把bar的参数类型修改了一下:

struct top {};
struct mid_a : top {};
struct mid_b : top {};
struct bottom : mid_a, mid_b {};

void foo(mid_a&) {}
void foo(mid_b&) {}
void bar(top &arg) {
    // ... 过了一个月, 这里已经添加了很多代码.
    foo(static_cast<mid_a&>(arg));
}

int main() {
    top x;
    bar(x);
    return 0;
}

代码依旧编译通过, 可是运行时程序挂掉了(假设这几个类里面有许多成员, 并且在foo里对其进行了访问).

发现问题了吗? 原因就在于static_cast太强大了, 强大到可以进行”down-cast”. 于是编译器没有给你任何警告, 就把一个top类型的引用给强制转换成了min_a的引用.

这个时候轮到boost::implicit_cast出场了. 把bar里面的那句foo调用改一改:

foo(boost::implicit_cast<mid_a&>(arg));

于是一个月前的代码依旧可以通过编译, 而一个月后的代码中的错误被编译器揪出来了. 原因在于隐式类型转换不允许”down-cast”, 只能”up-cast”.

这里简要说一下所谓显式和隐式类型转换的区别. 在C++世界的英文里, 我们说”convert”通常指”implicit convert”, 而”cast”指”explicit cast”. 隐式类型转换好理解, 就是你写了个a=b, 而ab不同类型, 编译又不报错, 就说明隐式类型转换发生了, 类似的情况还有在函数调用的参数传递时. 而显式类型转换特指C风格的强制转换((type)obj或者C++中等价的type(obj)), 以及C++风格的四个关键字(static_cast, const_cast, dynamic_cast, reinterpret_cast). 然而这个定义是相当模糊的, 比如一个int类型的x, bool(x)是显式的, 而!!x是隐式的, 其实效果上并没有区别, 只是字面上的不同罢了. (关于cast和convert的区别, 参见这里和这里)

所以在bar里我们需要的仅仅是一个隐式类型转换, 然而直接把arg传递给foo的话会出现重载歧义, 于是我们需要告诉编译器到底要进行哪个隐式类型转换. 然而static_cast又太过强大, 它还能做隐式类型转换之外的事情(up-cast), 于是在日后代码演化的过程中留下了bug.

于是boost::implicit_cast应运而生, 它比static_cast弱, 正如它的名字一样, 它只能用来告诉编译器执行什么隐式类型转换.

而它的代码呢? 简单到令人发指:

template <typename T>
inline T implicit_cast (typename mpl::identity<T>::type x) {
    return x;
}

而mpl::identity的定义也极其简单:

template<typename T> struct identity { typedef T type; };

有人要问这个identity干什么用的, 看起来很累赘. 如果没有这个identity, 像”implicit_cast(obj)”这样的代码也能通过编译, 然而它其实什么也没做, obj的类型仍然没变. identity的存在使得函数模板的参数类型推导失效, 因为要推导出T, 首先得知道identity是什么, 而identity又是依赖于T的. 于是就形成了循环依赖, 参数类型推导就失效了. 于是编译器就要求你显式地指定T的类型.

Koenig Lookup

Answeror — Wed, 22 Dec 2010 23:13:16 +0800

Koenig Lookup, 别名ADL, 今天看[The Boost Graph Library]的时候才想起来C++里还有这么一个东西.

下面这段代码解释一切:

namespace ns {
    struct type {};
    void foo(type) {}
    void foo(int) {}
    template<class T&gt
    void bar(T) {}
}
int main() {
    // Koenig Lookup
    foo(ns::type());
    //foo(1); // compile error
    bar(ns::type());
    //bar(1); // compile error
    return 0;
}

用来做什么呢? wiki上有句话说得很好:

Within C++, functions found by ADL are considered part of a class’s interface.

BGL里对图结构的操作几乎都是通过非成员函数进行的, 非成员函数就是其接口的一部分, 于是ADL也就成了不可或缺的东西.

以前从来没有对于大量非成员接口的需求, 所以也从没考虑过语言为什么会设计成这个样子, 这个语法为什么会存在, 所以即使看过, 并且经常用到(比如自定义swap), 到了该用的地方还是会傻乎乎的在函数前面加上个名字空间前缀. 类似的基础问题还有前几天写元函数平展tuple的时候(就是把嵌套的tuple平展开, 貌似很容易, 想想tuple里有引用类型和const限定符的话就没那么简单了)刚刚搞明白的关于const对于成员引用的作用, 具体说来就是下面的代码能够通过编译:

struct foo {
    int &a;
    foo(int &a) : a(a) {}
};
int main() {
    int a;
    const foo f(a);
    f.a = 1;
    return 0;
}

“勿在浮沙筑高台”, 说起来容易做起来难, 恐怕有时候只有自己去搭一搭高台才能自知是浮沙.

退役感言

Answeror — Tue, 19 Oct 2010 19:51:52 +0800

ACM-ICPC不应该成为大学生活的全部, 但是我却时常后悔没有把我的全部投入进去.

{ZJU}{3408}{Gao}

Answeror — Thu, 07 Oct 2010 19:14:42 +0800

-problem: 求10000个点50000条边的有向图上, 从0号点到所有点的所有最短路共经过i号点几次.
solution: dijkstra+拓扑排序/树形dp
--source: ZOJ Monthly, October 2010
----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3408
----code: http://goo.gl/LmMT

题目有点拗口, 简单说就是把0号点到所有点的所有最短路径列出来, 然后看看其中i出现了几次.

设答案为ans[i], 则ans[i]=before[i]*after[i].
before[i]表示从0到i的最短路径数量, 这个可以在Dijsktra的过程中求出来.
after[i]表示以i为起点, 在0号点的到所有点的的最短路径图中有多少条路径.

最短路径图是一个有向无环图, 可以用Dijkstra过程中记录的前驱来表示.
after的求法有两种: 树形DP或者拓扑排序, 本质是一样的.
用拓扑排序的话就是先将所有after置1, 然后对最短路径图做拓扑排序, 每次把当前点的after值累加到直连的点上.

注意before和after的求解是分来的, 千万不要混在一起.

题目的输出很阴险, 要求10位, 最后的乘法可能爆int64, 需要用到如下技巧:

设 M=10^10, S=10^5,
则 a * b % M = (a / S * b % M * S + a % S * b) % M

另外注意区分unidirectional和undirected, 根本没有undirectional这个词…

{HDU}{3613}{Best Reward}

Answeror — Mon, 04 Oct 2010 23:51:22 +0800

-problem: 小写字母组成的长500000的串, 每种字母有一定的价值(可以为负), 要你一刀切成两个串, 总价值为两个串价值和, 若是回文, 则串的价值为每个字母价值和, 否则为0. 问最大价值多少.
solution: KMP求回文前缀
--source: 2010 ACM-ICPC Multi-University Training Contest（18）——Host by TJU
----link: http://acm.hdu.edu.cn/showproblem.php?pid=3613
----code: http://goo.gl/BcQ6

一开始用后缀数组+RMQ. TLE, MLE什么的都出来了.

想了一个晚上, 想到把反串接在原串后, 中间夹个$, 然后做KMP, 于是末尾的next域就指向了原串的最长回文前缀的末尾.
但是想到这里就想不下去了, Google一下”回文前缀”找到了Roba的一篇博文: http://roba.rushcj.com/?p=439

其实是KMP很简单的一个性质: 对一个回文串s做一次KMP, 末尾的next域指向s的最长回文前缀的末尾.
然后通过next, 从这个最长回文前缀继续往前跳, 就找到了下一个最长回文前缀…

于是这就是求一个串所有的回文前缀的方法了, 时空复杂度都是O(n).

对于这题, 做完上述步骤之后把原串反过来, 重复上述步骤, 就找到了所有回文后缀, 于是只要线性扫一遍找最大值即可.

为了保持[)区间的一贯风格, 我把KMP也写成了next指向有效位下一位的形式.
这种好处只可意会不可言传, 一旦养成了这种前开后闭的思考习惯, 很多区间类问题就不容易写错了, 特别是字符串, 二分, DP等等.
真的很佩服STL的发明者.

{HDU}{3225}{Flowers Placement}

Answeror — Mon, 04 Oct 2010 16:24:00 +0800

-problem: 求n=200的二分图的完美匹配, 要求结果序列字典序第k小.
solution: dfs+继续增广路
--source: 2009 Asia Shanghai Regional Contest Host by DHU
----link: http://acm.hdu.edu.cn/showproblem.php?pid=3225
----code: http://goo.gl/zkhk

去年上海的Regional让我纠结了一整场的题目, 今天想起来把它过掉了.

类似于一道网络流题目的连续增广路方法, 实现起来还是要想一会的.

要求第k小的完美匹配, 很容易想到O(n^5)的dfs+hungary, 从编号最小的x点开始人为设定匹配的y点, 然后判断剩下的点是否能构成完美匹配.
这样当然要TLE的.

我们在dfs之前先做一次hungary, 构造一个完美匹配.
然后回到之前的想法, 在dfs中枚举第x集第i个点的匹配点j的过程. 当j从j1变到j2时, 我们并不需要把之前构造好的lny(y集到x集的映射)全部清除. 我们只关心当i匹配j2的时候剩余点是否还能保持完美匹配, 换句话说就是撤销i到j1的匹配(lny[j1]=-1)之后是不是还能找到一条包含(i,j2)的增广路. 这不正是hungary算法的find过程干的事情吗? 如此一来只需要记录好上层dfs已经匹配好的点, 然后在枚举本层的匹配点时不断修改lny然后找增广路即可.

复杂度O(n^3).

需要注意的是每次找增广路之前都需要清空hungary算法的use(记录y集点是否被访问过)数组, 以及找增广路的时候不要破坏上层dfs已经建立好的匹配.