Author Archives

A Quiz of C++ const

在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++吗?

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

宁静之雨

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

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

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

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

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

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

Shortcut for Google Bookmarks

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++临时变量的生命周期

下面这段程序:

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

在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

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;
}

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

退役感言

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

{ZJU}{3408}{Gao}

-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

Continue Reading »

{HDU}{3613}{Best Reward}

-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

Continue Reading »

{HDU}{3225}{Flowers Placement}

-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

Continue Reading »

Page 1 of 15{1}{2}{3}{4}{5}{10}...Last »