Tag Archives: C Language

Leveldb 编译错误背后的C++标准变化

在编译 Levedb 时,我遇到了这个错误:

g++ -c -I. -I./include -fno-builtin-memcmp -DLEVELDB_PLATFORM_POSIX -pthread -DOS_LINUX -O2 -DNDEBUG db/version_set.cc -o db/version_set.o
db/version_set.cc: In member function `void leveldb::VersionSet::Builder::Apply(leveldb::VersionEdit*)':
./db/version_edit.h:100: error: `std::vector, std::allocator > > leveldb::VersionEdit::compact_pointers_' is private
db/version_set.cc:461: error: within this context
...

在网上容易搜到解决方案,由于归根结底是访问控制问题,方法是把所有涉及到的的 private 变量或类型修改为 public。由于不是所有的编译器都会报错,我就很好奇产生这个错误的根本原因。

BTW: 一种不修改代码的 work around 方法是,在编译这个文件时加上 -fno-access-control 参数,这样 g++ 就不会进行访问控制检查,自然也就没问题了。这个参数同样可以用于对 private 成员函数进行单元测试。

简单地分析一下这个错误。发生错误的地方是在 VersionSet::Builder 这个类的成员函数中,而错误则是其成员函数无法访问 VersionEdit 和 Version 类的私有成员变量。VersionSet 是 VersionEdit 和 Version 类的友元类,Builder 是 VersionSet 的嵌套类。简化一下,代码如下所示:

class VersionSet;

class VersionEdit {
    friend class VersionSet;
    static int compact_pointers_;
};

class VersionSet {
    class Builder {
        int foo()
        {  
            return VersionEdit::compact_pointers_;
        }  
    }; 
};

把这段代码拿给编译器去编译,g++ 3.4.4/5 会报类似的 `int VersionEdit::compact_pointers_' is private 错误,但是 g++ 4.5.3 则能够编译通过。

由于 VersionSet 是 VersionEdit 的友元类,那么 VersionSet 是能够访问 VersionEdit 私有成员的,这样问题就集中在 Builder 是否能够获得与 VersionEdit 的友元关系。如果语法规定嵌套类 Builder 能够从 VersionSet “获得”友元关系,那么 Builder就能够访问 VersionEdit::compact_pointers_,反之就不能访问。

在 C++98 标准中,关于嵌套类的权限有如下描述:

$11.8/1 [class.access.nest],

The members of a nested class have no special access to members of an enclosing class, nor to classes or functions that have granted friendship to an enclosing class; the usual access rules (clause 11) shall be obeyed. The members of an enclosing class have no special access to members of a nested class; the usual access rules (clause 11) shall be obeyed.

Example:

class E {
    int x;
    class B { };
    class I {
        B b;                 // error: E::B is private
        int y;
        void f(E* p, int i) {
           p->x = i;         // error: E::x is private
        }
   };
   int g(I* p)
   {
       return p->y;          // error: I::y is private
   }
};

但是在 C++11 中,这段描述变更为:

$11.7/1 Nested classes [class.access.nest]

A nested class is a member and as such has the same access rights as any other member. The members of an enclosing class have no special access to members of a nested class; the usual access rules (Clause 11) shall be obeyed.

Example:

class E {
    int x;
    class B { };
    class I {
        B b;                  // OK: E::I can access E::B
        int y;
        void f(E* p, int i) {
            p->x = i;         // OK: E::I can access E::x
        }  
    }; 
    int g(I* p) {
        return p->y;          // error: I::y is private
    }  
};

从上面的描述和示例代码对比中我们可以明显看出,在旧标准中嵌套类和“被嵌套类”没有什么特殊的关系,就像两个普通类一样;但是在新标准中嵌套类已经完全视为“被嵌套类”的成员,那么自然也获得了“被嵌套类”成员应该有的访问控制权限。这也就意味着“被嵌套类”的普通成员拥有的访问“被友元类”私有成员变量的权限,嵌套类也能够获得,那么 Leveldb 在新版本的编译器下能够编译通过也不足为奇了。

不过 gcc3.4 的编译错误问题还不能单单归究于标准的变化。因为 gcc3.4 已经能够支持嵌套类访问“被嵌套类”的私有成员(因为在很早以前这就被确认为一个缺陷),只是不能够支持友元关系到嵌套类的传递。友元关系的传递可能是在 4.1 或者 4.2 版本中实现的,应该属于上述标准变化的衍生特性。

僵尸对象或 RAII

我最近在想这个问题,到底要不要在程序中使用异常?

以前写的 C 代码比较多,即使写 C++,基本上也是把它当成 C with object 来用。对异常的了解偏少,使用更是极少。最近评审别人代码的时候遇到一个问题:如果构造函数中 new 失败了,会发生什么事情?

工程的代码一般提倡哪里出错在哪里处理,不能恢复的要返回错误码给调用者。在一般情况下,使用 new(std::no_throw) 保证 new 不抛出异常(否则结果是灾难性的),并且检查分配是否成功是可以实现这一点的。

遗憾的是构造函数没有返回值,我们不能返回构造失败。那么只有用迂回的办法,为类定义一个成员变量 bool inited。初始化为 false,只有在构造的工作都完成之后,才将它置为 true。如果一个对象的 inited 成员为 false,就意味着它构造过程中出了问题,不能被使用。这就是一个僵尸对象,“活死人”。

看,我们成功地规避了使用异常。但是慢着,不是只有 bad_alloc 这一个异常啊!还有 bad_cast、runtime_error、logic_error,还有:

$ grep class /usr/include/c++/4.5/stdexcept
// Standard exception classes  -*- C++ -*-
// ISO C++ 19.1  Exception classes
   *  program runs (e.g., violations of class invariants).
   *  @brief One of two subclasses of exception.
  class logic_error : public exception
  class domain_error : public logic_error
  class invalid_argument : public logic_error
  class length_error : public logic_error
  class out_of_range : public logic_error
   *  @brief One of two subclasses of exception.
  class runtime_error : public exception
  class range_error : public runtime_error
  class overflow_error : public runtime_error
  class underflow_error : public runtime_error 

天那,我未曾注意过标准库有那么多异常!那么如果在使用标准库时,不小心触发了什么异常,OMG!

这样看来,使用异常是很有必要的。但是,麻烦的问题又来了,一旦使用异常,函数的退出过程就变了。使用错误码有一个好处,就是你可以在函数返回前擦干净自己的屁股;但是使用异常呢?你既要保证对象能够自己擦屁股(RAII),还要保证函数能自己擦屁股(在正确的位置使用异常处理),这样才能在 stack unwinding 时不会导致内存泄露。哦,auto_ptr 可以帮上一些忙,但如果是分配的资源是数组呢?

还有一个麻烦是,你要遵从约定——特别是对于一个程序库作者来说。如果约定出错时抛出异常,那么可以抛;如果约定出错时返回错误码,或者这个库可能被 C 调用,那么抛出异常就可能是灾难。

现在看来,如果想实现更健壮的 C++ 程序,那么异常处理是不可或缺的。但在使用异常处理之前,必须得了解在哪里、怎样抛出和捕获异常,如果是团队合作,可能还需要有简单的操作指导手册,否则使用不当或者过量的异常也可能带来麻烦。

我还在路上!

Math in CS:置换的轮换分解

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候,应该都会讲到这样一个定理:
任何一个置换都可以表示为不相交轮换的乘积,若不计因子的顺序,其分解式是唯一的。

一、简单解释

没有数学背景的人,这句话很难读懂,下面我们来看一个简单的例子。假设我们有这样一个置换 P:

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢?我们先从 1 出发,1 被换到 2,2 被换到 5,5 又被换到 1,这就是一个轮换;然后再从 3 出发,3 被换到 4,4 又被换到 3,这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用:全排列判断问题

下面我们来看这个定理有什么作用,考虑下面这道题目[1][2]:

给一个 n 长的数组,判断它是否为一个 1, 2, ..., n 的全排列,要求在线性时间,常数空间内实现。

我们可以容易看到,每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知,我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子,怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢?首先从 1 开始,a[1]=2,那么再检查 a[a[1]]=a[2]=5,然后再检查a[a[a[1]]]=a[5]=1,这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个,第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢?我们每次检查完一个数,就将它置负,这样遇到负值,循环就终止了。如果终止前检查的那个数与起始的数相同,那么我们就发现了一个轮换,否则它就不是一个轮换,说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值,所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值,且循环正常终止,那么说明它们都在不相交的轮换里,那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值,到最后把所有置负的元素都重新置正即可。

代码实现如下[2]:

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用:100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢?考虑下面这道题目[3][4]:

100 个囚犯,每人有一个从 1 到 100 的不重复不遗漏的号码,国王把这些号码收集起来,打乱放进 100 个箱子里,每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前,每人可以打开至多 50 个箱子来寻找自己的号码,可以一个一个打开(即可以根据之前箱子里看到的号码来决定后面要打开的箱子)。如果有一个囚犯没有找到自己的号码,那么这 100 个人一起被处死;只有当所有的囚犯都找到了自己的号码,他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策,但是一但打开了箱子,他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率?

显然,每个人随机选 50 个箱子打开,100 个人的存活概率会是 1/2 的 100 次方,即1/1267650600228229401496703205376,可以小到忽略不计。但是事实上有一种极简单的办法,其存活概率高达 30% 。至于有没有更好的办法?我不知道。

存活率达 30% 的策略就是:

囚犯打开自己号码对应的箱子,就按照箱子中的号码打开另一个箱子,一直到找到自己号码或者选50 次为止,这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢?其实国王所作的事情,就是一个 1 到 100 元素集合的置换,囚犯所做的事情,就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢?就是这个置换中所有的轮换长度都不大于 50,因为每个囚犯号码的轮换都不大于 50,那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢?{这个置换中所有的轮换长度都不大于 50 的概率},就是 1 - {存在轮换长度大于 50 的概率},进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率},由此,我们可以得到下面的等式:

P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100}%20\frac{1}{k}=1-(H_{100}-H_{50})

其中,Hn 代表调和数(Harmonic Number)。虽然调和数没有精确的公式,但是我们知道调和数和自然对数有着密切的联系[5],那么我们就可以用自然对数来近似:

P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059[6]

因此,我们可以得到,使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是:0.31182782068980479698,Bash 代码:

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

Cygwin GCC qsort 函数错误(续)

上一篇文章中提到我在为 qsort 写 compare 函数时犯了一个愚蠢的错误:我脑袋陷入了一个错误的逻辑,以为 compare 函数嘛,就是要 compare … Continue reading

Cygwin GCC qsort 函数错误

我平时在 Windows 下写代码时,经常使用 Cygwin 的 gcc。但是今天我居然发现 Cygwin 下 … Continue reading

将文本文件读入数组-C语言实现

要求:使用 C 语言将文本文件的每一行读入为数组的一个元素,返回一个 char ** 指针。 由于行长度和文本文件行数均未知,相当于二维 char … Continue reading

vasprintf 会将空间分配到栈上吗?

由于提交过几次 Linux Fetion 的 bug 和 patch,Linux Fetion … Continue reading

多余的逗号?

晚上看了两页 The Art of Unix Programming,其中提到了一个我以前一直感觉困惑的地方: 在我看过的 C/C++ … Continue reading

Something About Scanf() In C (1)

一. scanf 函数输入格式中的字符串 scanf 函数输入格式中也可以含有普通字符串,但他的含义是这些字符必须在输入中出现,例如: int num; scanf("hello … Continue reading

About "double" in C

昨天发现一个很有趣的现象,在 Turbo C 里 double 类型的变量无法用通常模式进行输入操作,即无法用 scanf() 进行赋值,程序举例: … Continue reading