Bit Focus

对空结构体求 sizeof

C++ 声称完全兼容了 C, 这一点在某些细节上不尽然. 比如对空结构体 --- 没有成员, 不含虚函数, 虽然 C 还生活在没有虚函数的三叠纪 --- 求 sizeof 的结果. 具体地说就是下面这个表达式

Code Snippet 0-0

struct empty {};

sizeof empty; // 值为 0

在 C 和 C++ 中会得到不同的值: C 中其值为 0 (在主流编译器中如此), 而 C++ 中其值为 1. 这个微妙的不同步源于 C 中的一个指针相减问题, 如下代码

Code Snippet 0-1

#include <stdio.h>

struct empty {};

int main()
{
    struct empty x;
    struct empty y;
    printf("%ld", &x - &y);
    return 0;
}

以 C 语言编译并运行, 程序会直接崩溃掉, 因为在 C 中计算表达式 &x - &y 的值等同于 ((char*)&x) - ((char*)&y) / sizeof struct empty. 这个整数除法非常糟糕, 毫无疑问 C 编译器应该了解到危险所在了: 在编译期, 它完全能够发现该除法算式的常数分母是整数 0, 但是它还是义无反顾地生成了代码, 甚至连警告也不给, 将程序推入运行时崩溃的深渊.

本来这种事情应该偷偷改掉拉倒, 可是 C 标准对这个事情讳而不谈, 丢出一张王牌 "对空结构体或联合求 sizeof 将会是*未定义*行为". 对此 C++ 只好吐了个槽, 说*任何对象至少要占用 1 字节空间*. 所以其实 C++ 标准也没有明确说出 "对空结构体或联合求 sizeof 将会是 1" 这样的话, 但是根据前面这个规定, 由编译器厂商演绎出来的结果就是这样的, sizeof 纷纷得到结果 1, 包括下面这样的情况

Code Snippet 0-2

struct empty_base_a {};
struct empty_base_b {};
struct empty_inherit : empty_base_a, empty_base_b {};

sizeof empty_inherit; // 值为 1

即对从空类上 (多重) 继承的空子类求 sizeof 也将得到 1.

这一招看起来很挫, 但还真的管用了, 用 C++ 编译器编译并运行上述程序, 零也不除了, 程序也不会崩了, 还能给出正确地结果.

虽然把两个什么空的东西用继承的方式捏在一起不会产生体积变大, 但是一个数组的什么空的东西则会导致体积累加, 如

struct empty {};

int main()
{
    struct empty x[4];
    printf("%ld", sizeof x); /* 4 */
    return 0;
}

这段 C++ 代码的运行结果将是 4, 也就是 x 占用了 4 个 1 字节. 这又扯到 C++ 另一个核心编程思维 --- 面向迭代器. 例如下面一坨代码

Code Snippet 0-3

struct empty {};

void echo(empty)
{
    std::cout << "echo" << std::endl;
}

int main()
{
    struct empty x[4];
    std::for_each(x, x + 4, echo);
    return 0;
}

如果认为整个数组是一个对象, 打个包求 sizeof 才能得到 1, 而 x[0] 与 x[4] 等等有相同的地址, 那么 std::for_each 中的循环将一次也不被执行. 类似的, 让多个空类对象聚合在一个空类对象中时, 它们占用的空间大小是会累加的, 如

Code Snippet 0-4

struct empty {};
struct twin {
    empty a;
    empty b;
};

sizeof twin; // 2

Posted at Oct 07 2011 - 09:15:26

Permanent Link: /p/438 Load full text

Post tags:

sizeof
C
C++

正确重载 operator=

以一个整数数组类型为例, 下面的写法

class int_array {
    int* array;
    int size;
public:
    int_array& operator=(int_array const& rhs)
    {
        if (this == &rhs) {
            return *this;
        }

        delete[] array;
        array = new int[];
        std::copy(rhs.array, rhs.array + rhs.size, array);
        size = rhs.size;
        return *this;
    }

    /* other members */
};

是完全错误的.
设想在下面这样的上下文中

int_array a /* init */;
int_array b;
try {
    b = a;
} catch (std::bad_alloc) {
}
/* ''b'' is bad now! */

进入 operator= 之后, 先执行了 delete[], 这一句没问题, 如果之后的
array = new int[];
内存分配失败, 这时 b 的成员 array 已经崩坏掉了, 以后再继续使用 b 显然是一件很糟糕的事情.

为了保持对象状态一致性, 很自然地应该将对象状态的切换放入一个尽可能安全的环境中. 一个方法是使用先复制一份对象, 然后利用绝对安全的 std::swap 将副本与当前对象交换. 假如在复制过程中出错, 并不会破坏当前对象的状态一致性.

class int_array {
public:
    int_array& operator=(int_array const& rhs)
    {
        if (this == &rhs) {
            return *this;
        }

        int_array copy(rhs);
        swap(copy);
        return *this;
    }

    void swap(int_array& other)
    {
        std::swap(array, other.array);
        std::swap(size, other.size);
    }

    /* other members */
};

一个与之类似的例子是维护程序配置文件, 当程序在退出或者某个其它时机需要将配置写回文件时, 直接清空原来的文件然后提笔并不是一个好主意, 而应该先写入一个临时文件, 再将临时文件 mv 到配置文件.

Posted at Sep 30 2011 - 11:25:19

Permanent Link: /p/430 Load full text

Post tags:

Operator Overload
C++
RAII

日常的算法 - 顺序统计

顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同)

template <typename _Iterator>
_Iterator find_min(_Iterator begin, _Iterator end)
{
    _Iterator min = begin;
    for (++begin; begin != end; ++begin) {
        if (*begin < *min) {
            min = begin;
        }
    }
    return min;
}

将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数.
在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出

+-------+-----------+----- | begin | begin + 1 | ... +-------+-----------+----- | | +--( < )--+ / \ / \ +----------+ +-------------+ +-----+ | less one | | greater one |--( < )--| max | +----------+ +-------------+ +-----+ | | +-----+ +-------------------------( < )--| min | +-----+

这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率.
下面是实现的例子

Posted at Sep 30 2011 - 09:20:03

Permanent Link: /p/426 Load full text

Post tags:

Generic Programming
STL
C++
Order Statistic
Algorithm
Template

头文件禁区: C++ 中的 ABI

    在上一篇文章中写到了 C 的 ABI (application binary interface) 有关的内容. 而 C++ 这货也采用 header / cpp 分离的方式来组织代码, 并在编译时将头文件直接在 cpp 中插入, 这种暴力方法已经不能简单说是为了兼容 C 的各种编译期行为, 完全就是彻头彻尾地重蹈覆辙, 甚至有过之而无不及.

    首先, C++ 也会遇到 "如果直接用了动态库中修改过签名的函数怎么办" 这个全静态语言的千古难题. 而且比起 C 语言更要命的是, C++ 的类是不能进行前置声明来回避对象内存布局耦合: 前置声明就没有引用成员函数了, 那还怎么面向坑爹的对象呢? 不仅仅对象成员布局有此问题, 连同 C++ 藉由实现多态的虚函数亦面临着同样的窘境. 试想动态库中虚函数表都改得面目全非时, 使用该对象的代码却还用原来的方式访问, 那还不是各种鸡飞狗跳.
    对于如此恶劣环境下仍然想保持 ABI 兼容性的 C++ 程序员来说, 倒也不是完全无路可走. 具体的方案就不在这篇文章中赘述了, 请转到陈硕老师的 C++ 工程实践: 二进制兼容性和 C++ 工程实践: 避免使用虚函数作为库的接口. 两篇文章都写得非常详细.

    撇开这些跟 C 语言有关的孽缘不谈, C++ 本身也提供了一些机制来帮助程序员养成编码恶习, 比如一些函数实现可以直接写进头文件中, 而无须担忧任何链接错误. 首当这个批评的就是成员函数, 包括静态或非静态, 虚或非虚. inline 函数或者 template 函数实现要写头文件这点可以理解可以忍, 但成员函数来凑什么热闹? 成员函数的不往头文件里面写, 可以避免一些 ABI 耦合, 比如

class Date {
    int month;
    int day;
public:
    int getDay() const;
    int getMonth() const;
};

这种情况下, 在使用

Date* date /* initialize */;
date->getDay();

不必担心内存布局耦合, 因为作为非虚的成员函数, Date::getDay() const 这样的函数签名正如 getday(Date const*) 一样, 这就回到了上一篇文章最后提到的解决方法了. 但是如果用得不恰当, 比如头脑发热认为 inline 一下能提高效率什么的, 而活生生地写成

class Date {
    int month;
    int day;
public:
    inline int getDay() const
    {
        return day;
    }

    inline int getMonth() const
    {
        return month;
    }
};

Posted at Aug 31 2011 - 06:52:02

Permanent Link: /p/404 Load full text

Post tags:

C++
Template
ABI
STL
inline

C++ inline 坑爹真相

准备两个文件 a.cpp b.cpp, 内容如下

/* a.cpp */

#include <iostream>

void b();

inline void echo()
{
    std::cout << 0 << std::endl;
}

int main()
{
    echo();
    b();
    return 0;
}

/* b.cpp */

#include <iostream>

inline void echo()
{
    std::cout << 1 << std::endl;
}

void b()
{
    echo();
}

然后执行

$ c++ a.cpp b.cpp -o a.out && ./a.out

也许会出现两个 0, 或者两个 1, 但是不会出现 0 1 这样的组合, 更不会链接冲突了. 如果有任何跳过生成目标文件直接到生成可执行文件的顾虑, 尝试下面的方法结果是一样的

$ c++ -c a.cpp
$ c++ -c b.cpp
$ c++ -o a.out a.o b.o
$ ./a.out

甚至最直接地, 如果查看两个中间文件的符号

$ nm a.o
$ nm b.o

    会在两次结果中都看到一条名为 _Z4echov 的记录, 这就是 echo 函数被 name-mangling 之后的标识.

    C++ 文档和标准中过度赞扬 inline 这个关键字, 然而一笔带过的是, 编译器可以选择忽略 inline 标记, 至于忽略了会有什么后果, 如何链接等细节都一字不提. 如果这是一个封装行非常良好的编译器特性, 那也就没什么. 但实际上这里敷衍了一些重要事实, 既然 0) 有的函数即使程序员写了 inline, 编译器可以不进行 inline, 则 1) 很有可能出现这样的函数, 并在编译后被生成到目标文件中去, 而且 2) 由于 inline 函数一般实现在头文件中, 那么 3) 编译器在编译每一个包含了这个头文件的 cpp 文件时, 都会将该函数符号生成到对应目标文件中去, 而若要 4) 链接这多个目标文件不发生链接冲突, 只好由 5) 编译器或者链接器耍一些手段来保证, 可是 6) 耍了手段, 却有可能造成上面的问题发生.

    与 inline 失败的函数有关的真相是, 编译器会为 inline 函数做上标记, 链接器根据这个标记, 从目标文件中找到这个函数的多处实现, 不负任何责任地选取其中一个作为正身, 并抛弃其它的实现, 无论这些实现是否相同 (链接器也无从判断是否相同).
    开头的例子非常猎奇, 但是也不排除这样日常的情况: 0) lib 作者因为各种原因, 让 inline 失败的函数编入 lib; 1) 这个函数没有在文档中被提及, 头文件也隐藏得很好; 2) 引用 lib 的程序员定义了一个同 namespace 且同名的 inline 函数 (当然最有可能在全局名字空间这么干了). 于是就悲催了.

    现在再回头看一下 inline 的描述

要想 inline, 得先 inline
若是 inline, 未必 inline

这是不是有种在看葵花宝典开头的感觉?

Posted at Jul 24 2011 - 04:24:52

Permanent Link: /p/379 Load full text

Post tags:

inline
C++

C++ 对象构造时的异常与 RAII 的救赎

在上一篇文章中简单介绍了一下 RAII 的原理, 举了个读文件的例子. 这个例子稍微单薄了一些, 它只封装了一个需要 RAII 机制管理的资源 (FILE*). 软件工程中流行的观念是, 不具备扩展性, 经不起追加功能的东西注定会悲剧. 现在假如需要给这货增加个缓冲区, 也许这样是可以的

struct File {
    File(char const* filename, int buffer_size)
        : file(fopen(filename, "r"))
        , buffer(new char[buffer_size])
    {
        if (NULL == file) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    ~File()
    {
        fclose(file);
        delete[] buffer;
    }
private:
    FILE* file;
    char* buffer;

/* other members */
};

    在 buffer 分配失败时, 一般会抛出 std::bad_alloc.
    这个类型的破绽相当多, 稍不注意就有可能漏资源. 首先是刚刚提到的 buffer 分配失败抛异常, 那么假如这个时候 file 已经打开成功了, 它会被关闭么? 其次, 假设 buffer 成功分配, 但这时 file 打开失败, 那么 buffer 是否会被释放呢?
    很不幸的, 两者的答案都是否. 还是那句话, 因为 File 的构造函数没有走完, 这时抛出异常, 那么析构函数不会被执行. 因此, 不要尝试构造控制多于一个资源的类型. 而遇到这种需求, 应该拆分资源, 然后将这些单元类型进行聚合, 如

struct File {
    explicit File(char const* filename)
        : file(fopen(filename, "r"))
    {
        if (NULL == file) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    ~File()
    {
        fclose(file);
    }
private:
    FILE* file;

/* other members */
};

struct Buffer {
    explicit Buffer(int buffer_size)
        : buffer(new char[buffer_size])
    {}

    ~Buffer()
    {
        delete[] buffer;
    }
private:
    char* buffer;

/* other members */
};

struct BufferedFile {
    BufferedFile(char const* filename, int buffer_size)
        : file(filename)
        , buffer(buffer_size)
    {}

    File file;
    Buffer buffer;

/* other members */
};

Posted at Jun 21 2011 - 13:27:55

Permanent Link: /p/363 Load full text

Post tags:

RAII
Exception Handling
C++

从 Python 的 with 到 RAII

在上一篇文章中提到了 Python 的 with 结构, 其背后的思想正是 RAII. 在 C++ 中, RAII 的样子看起来跟 Python 中的会非常不一样, 还是以打开读取文件为例子

#include <cstdio>
#include <stdexcept>
#include <iostream>

struct File {
    explicit File(char const* filename)
        : f(fopen(filename, "r"))
    {
        if (NULL == f) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    std::string readLine()
    {
        char buffer[256] = { 0 }; // just for demo
        if (NULL == fgets(buffer, 256, f)) {
            if (!feof(f)) {
                throw std::runtime_error("error occurs while reading file");
            }
            throw std::out_of_range("end of file")
        }
        return buffer;
    }

    ~File()
    {
        fclose(f);
    }
private:
    FILE* const f;
};

int main()
{
    try {
        File file("litsu");
        while (true) {
            std::cout << file.readLine();
        }
    } catch (std::runtime_error e) {
        std::cerr << e.what() << std::endl;
    } catch (std::out_of_range) {}
    return 0;
}

注意看 try 块中间的语句, 看起来流程很清晰, 完全不像 Python 里面那样, 还要弄个 with 块, 多一级缩进. 都说 C++ 代码没 Python 的精神, 然而在这种小地方 C++ 反而超过了 Python 呢.

其实, Python 的 with 块更像个语法糖, 上篇文章中有提到, 双层 try 在 Python 中能等效地解决这个问题, 只是看起来丑很多. 这个问题的根本在于, Python 这样不具备 RAII 特性的语言没能处理好对象从不可用状态切换到可用状态的状态过渡. 回顾一下双层 try 结构的处理方式

def readFile():
    try:
        f = open('sawako', 'r')
        pass
        try:
            process(f.readlines())
        except:
            print 'error occurs while reading file'
        finally:
            f.close()
    except:
        print 'error occurs while reading file'

Posted at Jun 20 2011 - 08:43:07

Permanent Link: /p/358 Load full text

Post tags:

Exception Handling
C++
RAII
Python

Python 中函数交叉引用中的问题与解决方法

Python (下面的讨论都是基于 2.7 版本的) 中, 先定义的函数可以调用后定义的函数, 比如下面这段代码

def first():
    return second()

def second():
    return 0

x = first()

不过, 这种调用是有局限性的, 稍作修改为下面这个样子

def first():
    return second()

x = first()

def second():
    return 0

就会产生符号错误, 解释器给出的信息是符号 second 不存在.

Python 作为一门解释型语言, 出现这样的事情很有可能是这样的原因, 假设现在正在交互模式下执行, 那么输入

def first():
    return second()

x = first()

到此为止, second 这个符号确实还没有被定义, 故产生错误. 但是如果上述代码内容是写在文件里的, 那么 Python 完全可以扫描整个文件以获得充分的上下文信息, 并正确地检测出 second 函数定义, 只是 Python 没有这么做.

熟悉 C++ 的同学这时候肯定跳出来了, 因为在 C++ 类空间中, 这种引用是合法的, 如

struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return 0;
    }

    int x;
};

不过, C++ 这种事情其实极其危险的, 比如下面这一段代码

struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return x;
    }

    int x;
};

这实际上使用了还处于量子态的 x 来初始化它自身, 虽然这样的代码只有手贱的程序员在极其罕见的情况下才会写出这样的代码 (比如我在写这篇博客的时候), 但是本着编译器的职责, 完全应该想方设法让这种情况编不过去.

好了, 还是先回到 Python 上来, Python 不允许这样的代码编译过去, 是因为这个原因么? 假设有下面的程序成功被解释执行

def first():
    return second()

x = first()

def second():
    return x

Posted at May 16 2011 - 13:38:21

Permanent Link: /p/314 Load full text

Post tags:

Compiler Construction
Python
C++

0 Page 1 2 3 4

对空结构体求 `sizeof` C++ 声称完全兼容了 C, 这一点在某些细节上不尽然. 比如对空结构体 --- 没有成员, 不含虚函数, 虽然 C 还生活在没有虚函数的三叠纪 --- 求 `sizeof` 的结果. 具体地说就是下面这个表达式 Code Snippet 0-0 `struct empty {}; sizeof empty; // 值为 0` 在 C 和 C++ 中会得到不同的值: C 中其值为 0 (在主流编译器中如此), 而 C++ 中其值为 1. 这个微妙的不同步源于 C 中的一个指针相减问题, 如下代码 Code Snippet 0-1 `#include <stdio.h> struct empty {}; int main() { struct empty x; struct empty y; printf("%ld", &x - &y); return 0; }` 以 C 语言编译并运行, 程序会直接崩溃掉, 因为在 C 中计算表达式 `&x - &y` 的值等同于 `((char)&x) - ((char)&y) / sizeof struct empty`. 这个整数除法非常糟糕, 毫无疑问 C 编译器应该了解到危险所在了: 在编译期, 它完全能够发现该除法算式的常数分母是整数 0, 但是它还是义无反顾地生成了代码, 甚至连警告也不给, 将程序推入运行时崩溃的深渊. 本来这种事情应该偷偷改掉拉倒, 可是 C 标准对这个事情讳而不谈, 丢出一张王牌 "对空结构体或联合求 `sizeof` 将会是未定义行为". 对此 C++ 只好吐了个槽, 说任何对象至少要占用 1 字节空间. 所以其实 C++ 标准也没有明确说出 "对空结构体或联合求 `sizeof` 将会是 1" 这样的话, 但是根据前面这个规定, 由编译器厂商演绎出来的结果就是这样的, `sizeof` 纷纷得到结果 1, 包括下面这样的情况 Code Snippet 0-2 `struct empty_base_a {}; struct empty_base_b {}; struct empty_inherit : empty_base_a, empty_base_b {}; sizeof empty_inherit; // 值为 1` 即对从空类上 (多重) 继承的空子类求 `sizeof` 也将得到 1. 这一招看起来很挫, 但还真的管用了, 用 C++ 编译器编译并运行上述程序, 零也不除了, 程序也不会崩了, 还能给出正确地结果. 虽然把两个什么空的东西用继承的方式捏在一起不会产生体积变大, 但是一个数组的什么空的东西则会导致体积累加, 如 `struct empty {}; int main() { struct empty x[4]; printf("%ld", sizeof x); /* 4 */ return 0; }` 这段 C++ 代码的运行结果将是 4, 也就是 x 占用了 4 个 1 字节. 这又扯到 C++ 另一个核心编程思维 --- 面向迭代器. 例如下面一坨代码 Code Snippet 0-3 `struct empty {}; void echo(empty) { std::cout << "echo" << std::endl; } int main() { struct empty x[4]; std::for_each(x, x + 4, echo); return 0; }` 如果认为整个数组是一个对象, 打个包求 `sizeof` 才能得到 1, 而 `x[0]` 与 `x[4]` 等等有相同的地址, 那么 `std::for_each` 中的循环将一次也不被执行. 类似的, 让多个空类对象聚合在一个空类对象中时, 它们占用的空间大小是会累加的, 如 Code Snippet 0-4 `struct empty {}; struct twin { empty a; empty b; }; sizeof twin; // 2` Posted at Oct 07 2011 - 09:15:26 Permanent Link: /p/438 Load full text	Post tags: sizeof C C++
正确重载 `operator=` 以一个整数数组类型为例, 下面的写法 `class int_array { int* array; int size; public: int_array& operator=(int_array const& rhs) { if (this == &rhs) { return this; } delete[] array; array = new int[]; std::copy(rhs.array, rhs.array + rhs.size, array); size = rhs.size; return this; } /* other members / };` 是完全错误的. 设想在下面这样的上下文中 `int_array a / init /; int_array b; try { b = a; } catch (std::bad_alloc) { } / ''b'' is bad now! /` 进入 `operator=` 之后, 先执行了 `delete[]`, 这一句没问题, 如果之后的 `array = new int[];` 内存分配失败, 这时 `b` 的成员 `array` 已经崩坏掉了, 以后再继续使用 `b` 显然是一件很糟糕的事情. 为了保持对象状态一致性, 很自然地应该将对象状态的切换放入一个尽可能安全的环境中. 一个方法是使用先复制一份对象, 然后利用绝对安全的 `std::swap` 将副本与当前对象交换. 假如在复制过程中出错, 并不会破坏当前对象的状态一致性. `class int_array { public: int_array& operator=(int_array const& rhs) { if (this == &rhs) { return this; } int_array copy(rhs); swap(copy); return this; } void swap(int_array& other) { std::swap(array, other.array); std::swap(size, other.size); } / other members */ };` 一个与之类似的例子是维护程序配置文件, 当程序在退出或者某个其它时机需要将配置写回文件时, 直接清空原来的文件然后提笔并不是一个好主意, 而应该先写入一个临时文件, 再将临时文件 `mv` 到配置文件. Posted at Sep 30 2011 - 11:25:19 Permanent Link: /p/430 Load full text	Post tags: Operator Overload C++ RAII
日常的算法 - 顺序统计顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同) `template <typename _Iterator> _Iterator find_min(_Iterator begin, _Iterator end) { _Iterator min = begin; for (++begin; begin != end; ++begin) { if (begin < min) { min = begin; } } return min; }` 将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数. 在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出 +-------+-----------+----- \| begin \| begin + 1 \| ... +-------+-----------+----- \| \| +--( < )--+ / \ / \ +----------+ +-------------+ +-----+ \| less one \| \| greater one \|--( < )--\| max \| +----------+ +-------------+ +-----+ \| \| +-----+ +-------------------------( < )--\| min \| +-----+ 这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率. 下面是实现的例子 Posted at Sep 30 2011 - 09:20:03 Permanent Link: /p/426 Load full text	Post tags: Generic Programming STL C++ Order Statistic Algorithm Template
头文件禁区: C++ 中的 ABI 在上一篇文章中写到了 C 的 ABI (application binary interface) 有关的内容. 而 C++ 这货也采用 header / cpp 分离的方式来组织代码, 并在编译时将头文件直接在 cpp 中插入, 这种暴力方法已经不能简单说是为了兼容 C 的各种编译期行为, 完全就是彻头彻尾地重蹈覆辙, 甚至有过之而无不及. 首先, C++ 也会遇到 "如果直接用了动态库中修改过签名的函数怎么办" 这个全静态语言的千古难题. 而且比起 C 语言更要命的是, C++ 的类是不能进行前置声明来回避对象内存布局耦合: 前置声明就没有引用成员函数了, 那还怎么面向坑爹的对象呢? 不仅仅对象成员布局有此问题, 连同 C++ 藉由实现多态的虚函数亦面临着同样的窘境. 试想动态库中虚函数表都改得面目全非时, 使用该对象的代码却还用原来的方式访问, 那还不是各种鸡飞狗跳. 对于如此恶劣环境下仍然想保持 ABI 兼容性的 C++ 程序员来说, 倒也不是完全无路可走. 具体的方案就不在这篇文章中赘述了, 请转到陈硕老师的 C++ 工程实践: 二进制兼容性和 C++ 工程实践: 避免使用虚函数作为库的接口. 两篇文章都写得非常详细. 撇开这些跟 C 语言有关的孽缘不谈, C++ 本身也提供了一些机制来帮助程序员养成编码恶习, 比如一些函数实现可以直接写进头文件中, 而无须担忧任何链接错误. 首当这个批评的就是成员函数, 包括静态或非静态, 虚或非虚. `inline` 函数或者 `template` 函数实现要写头文件这点可以理解可以忍, 但成员函数来凑什么热闹? 成员函数的不往头文件里面写, 可以避免一些 ABI 耦合, 比如 `class Date { int month; int day; public: int getDay() const; int getMonth() const; };` 这种情况下, 在使用 `Date* date /* initialize /; date->getDay();` 不必担心内存布局耦合, 因为作为非虚的成员函数, `Date::getDay() const` 这样的函数签名正如 `getday(Date const)` 一样, 这就回到了上一篇文章最后提到的解决方法了. 但是如果用得不恰当, 比如头脑发热认为 `inline` 一下能提高效率什么的, 而活生生地写成 `class Date { int month; int day; public: inline int getDay() const { return day; } inline int getMonth() const { return month; } };` Posted at Aug 31 2011 - 06:52:02 Permanent Link: /p/404 Load full text	Post tags: C++ Template ABI STL inline
C++ `inline` 坑爹真相准备两个文件 a.cpp b.cpp, 内容如下 `/* a.cpp / #include <iostream> void b(); inline void echo() { std::cout << 0 << std::endl; } int main() { echo(); b(); return 0; } / b.cpp / #include <iostream> inline void echo() { std::cout << 1 << std::endl; } void b() { echo(); }` 然后执行 `$ c++ a.cpp b.cpp -o a.out && ./a.out` 也许会出现两个 0, 或者两个 1, 但是不会出现 0 1 这样的组合, 更不会链接冲突了. 如果有任何跳过生成目标文件直接到生成可执行文件的顾虑, 尝试下面的方法结果是一样的 `$ c++ -c a.cpp $ c++ -c b.cpp $ c++ -o a.out a.o b.o $ ./a.out` 甚至最直接地, 如果查看两个中间文件的符号 `$ nm a.o $ nm b.o` 会在两次结果中都看到一条名为 `_Z4echov` 的记录, 这就是 `echo` 函数被 name-mangling 之后的标识. C++ 文档和标准中过度赞扬 `inline` 这个关键字, 然而一笔带过的是, 编译器可以选择忽略 `inline` 标记, 至于忽略了会有什么后果, 如何链接等细节都一字不提. 如果这是一个封装行非常良好的编译器特性, 那也就没什么. 但实际上这里敷衍了一些重要事实, 既然 0) 有的函数即使程序员写了 `inline`, 编译器可以不进行 `inline`, 则 1) 很有可能出现这样的函数, 并在编译后被生成到目标文件中去, 而且 2) 由于 `inline` 函数一般实现在头文件中, 那么 3) 编译器在编译每一个*包含了这个头文件的 cpp 文件时, 都会将该函数符号生成到对应目标文件中去, 而若要 4) 链接这多个目标文件不发生链接冲突, 只好由 5) 编译器或者链接器耍一些手段来保证, 可是 6) 耍了手段, 却有可能造成上面的问题发生. 与 `inline` 失败的函数有关的真相是, 编译器会为 `inline` 函数做上标记, 链接器根据这个标记, 从目标文件中找到这个函数的多处实现, 不负任何责任地选取其中一个作为正身, 并抛弃其它的实现, 无论这些实现是否相同 (链接器也无从判断是否相同). 开头的例子非常猎奇, 但是也不排除这样日常的情况: 0) lib 作者因为各种原因, 让 `inline` 失败的函数编入 lib; 1) 这个函数没有在文档中被提及, 头文件也隐藏得很好; 2) 引用 lib 的程序员定义了一个同 `namespace` 且同名的 `inline` 函数 (当然最有可能在全局名字空间这么干了). 于是就悲催了. 现在再回头看一下 inline 的描述要想 inline, 得先 `inline` 若是 `inline`, 未必 inline 这是不是有种在看葵花宝典开头的感觉? Posted at Jul 24 2011 - 04:24:52 Permanent Link: /p/379 Load full text	Post tags: inline C++
C++ 对象构造时的异常与 RAII 的救赎在上一篇文章中简单介绍了一下 RAII 的原理, 举了个读文件的例子. 这个例子稍微单薄了一些, 它只封装了一个需要 RAII 机制管理的资源 (`FILE`). 软件工程中流行的观念是, 不具备扩展性, 经不起追加功能的东西注定会悲剧. 现在假如需要给这货增加个缓冲区, 也许这样是可以的 struct File { File(char const filename, int buffer_size) : file(fopen(filename, "r")) , buffer(new char[buffer_size]) { if (NULL == file) { throw std::runtime_error(std::string("fail to open ") + filename); } } ~File() { fclose(file); delete[] buffer; } private: FILE* file; char* buffer; /* other members / }; 在 `buffer` 分配失败时, 一般会抛出 `std::bad_alloc`. 这个类型的破绽相当多, 稍不注意就有可能漏资源. 首先是刚刚提到的 `buffer` 分配失败抛异常, 那么假如这个时候 `file` 已经打开成功了, 它会被关闭么? 其次, 假设 `buffer` 成功分配, 但这时 `file` 打开失败, 那么 `buffer` 是否会被释放呢? 很不幸的, 两者的答案都是否. 还是那句话, 因为 `File` 的构造函数没有走完, 这时抛出异常, 那么析构函数不会被执行. 因此, 不要尝试构造控制多于一个资源的类型. 而遇到这种需求, 应该拆分资源, 然后将这些单元类型进行聚合, 如 struct File { explicit File(char const filename) : file(fopen(filename, "r")) { if (NULL == file) { throw std::runtime_error(std::string("fail to open ") + filename); } } ~File() { fclose(file); } private: FILE* file; /* other members / }; struct Buffer { explicit Buffer(int buffer_size) : buffer(new char[buffer_size]) {} ~Buffer() { delete[] buffer; } private: char buffer; /* other members / }; struct BufferedFile { BufferedFile(char const filename, int buffer_size) : file(filename) , buffer(buffer_size) {} File file; Buffer buffer; /* other members */ }; Posted at Jun 21 2011 - 13:27:55 Permanent Link: /p/363 Load full text	Post tags: RAII Exception Handling C++
从 Python 的 `with` 到 RAII 在上一篇文章中提到了 Python 的 `with` 结构, 其背后的思想正是 RAII. 在 C++ 中, RAII 的样子看起来跟 Python 中的会非常不一样, 还是以打开读取文件为例子 #include <cstdio> #include <stdexcept> #include <iostream> struct File { explicit File(char const* filename) : f(fopen(filename, "r")) { if (NULL == f) { throw std::runtime_error(std::string("fail to open ") + filename); } } std::string readLine() { char buffer[256] = { 0 }; // just for demo if (NULL == fgets(buffer, 256, f)) { if (!feof(f)) { throw std::runtime_error("error occurs while reading file"); } throw std::out_of_range("end of file") } return buffer; } ~File() { fclose(f); } private: FILE* const f; }; int main() { try { File file("litsu"); while (true) { std::cout << file.readLine(); } } catch (std::runtime_error e) { std::cerr << e.what() << std::endl; } catch (std::out_of_range) {} return 0; } 注意看 `try` 块中间的语句, 看起来流程很清晰, 完全不像 Python 里面那样, 还要弄个 `with` 块, 多一级缩进. 都说 C++ 代码没 Python 的精神, 然而在这种小地方 C++ 反而超过了 Python 呢. 其实, Python 的 `with` 块更像个语法糖, 上篇文章中有提到, 双层 `try` 在 Python 中能等效地解决这个问题, 只是看起来丑很多. 这个问题的根本在于, Python 这样不具备 RAII 特性的语言没能处理好对象从不可用状态切换到可用状态的状态过渡. 回顾一下双层 `try` 结构的处理方式 `def readFile(): try: f = open('sawako', 'r') pass try: process(f.readlines()) except: print 'error occurs while reading file' finally: f.close() except: print 'error occurs while reading file'` Posted at Jun 20 2011 - 08:43:07 Permanent Link: /p/358 Load full text	Post tags: Exception Handling C++ RAII Python
Python 中函数交叉引用中的问题与解决方法 Python (下面的讨论都是基于 2.7 版本的) 中, 先定义的函数可以调用后定义的函数, 比如下面这段代码 `def first(): return second() def second(): return 0 x = first()` 不过, 这种调用是有局限性的, 稍作修改为下面这个样子 `def first(): return second() x = first() def second(): return 0` 就会产生符号错误, 解释器给出的信息是符号 `second` 不存在. Python 作为一门解释型语言, 出现这样的事情很有可能是这样的原因, 假设现在正在交互模式下执行, 那么输入 `def first(): return second() x = first()` 到此为止, `second` 这个符号确实还没有被定义, 故产生错误. 但是如果上述代码内容是写在文件里的, 那么 Python 完全可以扫描整个文件以获得充分的上下文信息, 并正确地检测出 `second` 函数定义, 只是 Python 没有这么做. 熟悉 C++ 的同学这时候肯定跳出来了, 因为在 C++ 类空间中, 这种引用是合法的, 如 `struct type { int first() { return second(); } type() : x(first()) {} int second() { return 0; } int x; };` 不过, C++ 这种事情其实极其危险的, 比如下面这一段代码 `struct type { int first() { return second(); } type() : x(first()) {} int second() { return x; } int x; };` 这实际上使用了还处于量子态的 `x` 来初始化它自身, 虽然这样的代码只有手贱的程序员在极其罕见的情况下才会写出这样的代码 (比如我在写这篇博客的时候), 但是本着编译器的职责, 完全应该想方设法让这种情况编不过去. 好了, 还是先回到 Python 上来, Python 不允许这样的代码编译过去, 是因为这个原因么? 假设有下面的程序成功被解释执行 `def first(): return second() x = first() def second(): return x` Posted at May 16 2011 - 13:38:21 Permanent Link: /p/314 Load full text	Post tags: Compiler Construction Python C++
0 Page 1 2 3 4

	Back to Bit Focus
	NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
	About this site