Bit Focus

找到节点
将节点移动到容易删除的位置
删除节点

找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1.
下面是这一部分的实现

void remove_by(key_type const& key)
{
    remove_by_from(key, &root);
}

void remove_at(int position)
{
    remove_at_from(position, &root);
}

static void remove_by_from(key_type const& key, node** parent)
{
    --((*parent)->load);
    if (key < (*parent)->t.key()) {
        remove_by_from(key, &((*parent)->left));
        return;
    }
    if ((*parent)->t.key() < key) {
        remove_by_from(key, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove_at_from(int position, node** parent)
{
    --((*parent)->load);
    int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
    if (position < left_load) {
        remove_at_from(position, &((*parent)->left));
        return;
    }
    if (left_load < position) {
        position = position - left_load - 1;
        remove_at_from(position, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove(node** n);

这些函数都是 class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改.

找到了节点之后将会有下面 3 种情况

节点是叶子
节点只有一侧子树
节点两侧子树健全

前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)

Posted at Jan 24 2012 - 05:42:01

Permanent Link: /p/481 Load full text

Post tags:

Algorithm
Generic Programming
Order Statistic
B-tree
Data Structure
Template
C++
Binary Search Tree

万能巧械 - 二叉检索树 [零]

堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短

按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构

    前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述.

    较之堆更加全能的索引数据结构非二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况.

    首先还是把二叉树的架子给搭出来

template <typename T>
class binary_search_tree {
    struct node {
        T t;
        node* left;
        node* right;
        int load;

        explicit node(T const& rhs)
            : t(rhs)
            , left(NULL)
            , right(NULL)
            , load(1)
        {}
    };

    node* root;

    typedef typename T::key_type key_type;
public:
    binary_search_tree()
        : root(NULL)
    {}
public:
    void insert(T const& e);

    void remove_by(typename T::key_type const& key);
    void remove_at(int position);

    T& element_by(typename T::key_type const& key);
    T& element_at(int position);
};

Posted at Jan 23 2012 - 05:04:23

Permanent Link: /p/479 Load full text

Post tags:

C++
Generic Programming
Data Structure
Binary Search Tree
Algorithm
Order Statistic
Template

日常的数据结构 - 堆的实现与第 K 最小堆

在前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式.
从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如

+---+ | 4 | +---+ / \ +---+ +---+ | 5 | | 9 | +---+ +---+ / \ +---+ +---+ | 8 | | 5 | +---+ +---+

这样一棵完全二叉树可以被转换成

.----. /--. \ +---+---+---+---+---+---+----- | - | 4 | 5 | 9 | 8 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是

.----. /--. \ +---+---+---+---+---+---+----- | 0 | 1 | 2 | 3 | 4 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如

.----. /--. \ +---+---+---+---+---+---+----- | - | 0 | 1 | 2 | 3 | 4 | ... +---+---+---+---+---+---+----- \______/ / \________/

也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升).
既然堆的逻辑结构是数组, 那么可以采用 std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架

template <typename _T, typename _Less>
class heap {
    std::vector<_T> array;
    _Less const less;
    typedef typename std::vector<_T>::size_type size_type;
public:
    heap()
        : array(1) /* insert a placeholder, array[0] */
        , less(_Less())
    {}

    void push(_T const& value);
    _T pop();
};

Posted at Oct 07 2011 - 09:23:13

Permanent Link: /p/441 Load full text

Post tags:

C++
Algorithm
Template
Heap
Order Statistic
Generic Programming
Data Structure

日常的算法 - 顺序统计

顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 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(++) 之流在平台相关这种水深火热之中挣扎的语言, 对机器字长, 以及整数类型字长在一些情况下是极其敏感的. 所以每个大型项目建设之前, 在某个头文件里面定义一大堆 int32 或者是 unsigned8_t 之类的固定字长类型显得非常必要, 而且让工程看起来很专业的样子. 然而, 由于标准库中没有, 项目之间又互相不信任, 结果是几乎每个库都会自定一套, 比如 boost 就有 int8_t, int_least8_t 等类型, 而 Qt 更是拿出了叫做 qulonglong 的类型来卖萌. 虽然说是跨平台, 但是如果迁移平台时使用了错误版本的库呢? 因此有时依然需要写一个类似下面的程序来人肉验证

int main()
{
    std::cout << sizeof(int4_type) << " "
              << sizeof(int8_type) << std::endl;
    return 0;
}

然而, 人都是不可靠的, 如果有人对你说, 喔, 我跑了上面的程序, 结果是 "4 8", 也许你仍会强迫症一样, 自己再验证一次. 好了, 也许你已经厌烦了, 这么一点破事情, 难道不能交给机器做么?
理想的解决方案是, 只需要这样一个模板就好了

template <int _SizeOf>
struct IWantAnIntegralTypeOf;

int main()
{
    IWantAnIntegralTypeOf<4> this_is_a_4_bytes_int;
    IWantAnIntegralTypeOf<8> this_is_a_8_bytes_int;
    return 0;
}

不是吗?

这是完全可行的, 实际上, 可以把 C 支持的所有内建整数类型先拿出来, 组成一个类型链表来搜索, 像下面这样

struct __null__ {};

struct c_char {
    typedef char type;
    typedef __null__ next;
};

struct c_short {
    typedef short type;
    typedef c_char next;
};

struct c_int {
    typedef int type;
    typedef c_short next;
};

struct c_long {
    typedef long type;
    typedef c_int next;
};

struct c_long_long {
    typedef long long type;
    typedef c_long next;
};

struct __head__ {
    typedef c_long_long next;
};

接下来, 弄个模板来搜, 搜索当然是用模板偏特化的方法

template <typename _TypeNode, int _SizeOf, bool _SizeMatched>
struct type_finder;

template <typename _TypeNode, int _SizeOf>
struct type_finder<_TypeNode, _SizeOf, true>
{
    typedef typename _TypeNode::type type;
};

template <typename _TypeNode, int _SizeOf>
struct type_finder<_TypeNode, _SizeOf, false>
{
    typedef
        typename type_finder<
                typename _TypeNode::next
              , _SizeOf
              , _SizeOf == sizeof(typename _TypeNode::next::type)>::type type;
};

Posted at Mar 26 2011 - 09:08:36

Permanent Link: /p/217 Load full text

Post tags:

Generic Programming
Metaprogramming
C++
Template

泛型编程中的策略类

在编译期想要组合策略, 除开人肉内联不算, 有很多方式. 比如弄很多很多的 bool 参数

template <bool AllowDuplicate, bool SortElements, bool CheckOutOfRange>
struct just_another_container;

这看起来就是一个参数灾难, 如果某个地方出点小的模板编译错误, 哼哼~

当然, 另一种简单的替代方案就是把所有的 bool 整合在一起, 形成一个位段

template <unsigned Policy>
struct just_another_container;

这种情况实际上缺点更多, 比如维护位域会很麻烦, 有可能在这个声明之前有这些枚举

enum {
    ALLOW_DUP_MASK = 1,
    SORT_ELE_MASK = 2,
    CHECK_OUT_OF_RANGE_MASK = 4,
};

考虑这个容器有个 insert 函数, 它很可能需要考虑是否允许重复元素

template <unsigned AllowDuplicate>
void insert(element_type e);

而令人郁闷的是, 在 C++ 中不允许给函数偏特化, 也就是说这样写

template <>
void insert<0>(element_type e);
template <>
void insert<ALLOW_DUP_MASK>(element_type e);

是无法编译的! 要绕过这道坎, 得把 insert 函数放入一个模板结构体

template <unsigned AllowDuplicate> struct insert_s;
template <>
struct insert_s<ALLOW_DUP_MASK>
{
    static void insert(just_a_container& container, element_type& e);
};

这样做代价高昂, 首先, insert 被当作孤儿一样的抛弃, 那么类中的任何非 public 成员都不再对它开放, 当然, 为了这么个简单的小玩意儿声明 friend 也是可行的, 但是多了不觉得烦吗?

另外, 在调用策略行为进行特化时一般只针对特定的位, 那么将该策略位从组合策略中分离出来, 代码中将充斥着这样的运算

Policy & ALLOW_DUP_MASK
Policy & CHECK_OUT_OF_RANGE_MASK

比如

void another_member_function()
{
    element_type ele;
    // wanna call insert function of policy = Policy
    insert_s<*Policy & ALLOW_DUP_MASK*>::insert(*this, ele);
    // ...
}

这样做非常麻烦, 如果某个地方漏了 & 或者跟错误的掩码进行了运算, 哼哼~

不过, 泛型程序设计有自己的方法, 那就是, 多继承!

不要吓到了, 是的, 在 C++ 远古时代, 多继承被认定为獠牙猛兽. 不过那都是跟 C++ 运行时多态相关的. 步入泛型新纪元的 C++ 又迎来了多继承第二春, 它可以显著改善上述问题.

将上面的声明编程

template <*typename Policy*>
struct just_another_container;

然后加上这些结构体声明

struct policy_base {};
struct allow_dup : public policy_base {};
struct sort_ele : public policy_base {};
struct check_out_of_range : public policy_base {};

组合策略, 只需要声明一个策略类型继承想要的策略, 并把它传入容器就能达到目的, 比如

Posted at Nov 22 2009 - 08:56:30

Permanent Link: /p/36 Load full text

Post tags:

Generic Programming
C++
Template

万能巧械 - 二叉检索树 [壹] 二叉检索树的查询与检索操作看这里从二叉检索树中删除一个元素分多个步骤: 找到节点将节点移动到容易删除的位置删除节点找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1. 下面是这一部分的实现 void remove_by(key_type const& key) { remove_by_from(key, &root); } void remove_at(int position) { remove_at_from(position, &root); } static void remove_by_from(key_type const& key, node** parent) { --((parent)->load); if (key < (parent)->t.key()) { remove_by_from(key, &((parent)->left)); return; } if ((parent)->t.key() < key) { remove_by_from(key, &((parent)->right)); return; } remove(parent); } static void remove_at_from(int position, node* parent) { --((parent)->load); int left_load = (NULL == (parent)->left) ? 0 : (parent)->left->load; if (position < left_load) { remove_at_from(position, &((parent)->left)); return; } if (left_load < position) { position = position - left_load - 1; remove_at_from(position, &((parent)->right)); return; } remove(parent); } static void remove(node* n); 这些函数都是 `class binary_search_tree` 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改. 找到了节点之后将会有下面 3 种情况节点是叶子节点只有一侧子树节点两侧子树健全前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点) Posted at Jan 24 2012 - 05:42:01 Permanent Link: /p/481 Load full text	Post tags: Algorithm Generic Programming Order Statistic B-tree Data Structure Template C++ Binary Search Tree
万能巧械 - 二叉检索树 [零] 堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述. 较之堆更加全能的索引数据结构非二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况. 首先还是把二叉树的架子给搭出来 template <typename T> class binary_search_tree { struct node { T t; node* left; node* right; int load; explicit node(T const& rhs) : t(rhs) , left(NULL) , right(NULL) , load(1) {} }; node* root; typedef typename T::key_type key_type; public: binary_search_tree() : root(NULL) {} public: void insert(T const& e); void remove_by(typename T::key_type const& key); void remove_at(int position); T& element_by(typename T::key_type const& key); T& element_at(int position); }; Posted at Jan 23 2012 - 05:04:23 Permanent Link: /p/479 Load full text	Post tags: C++ Generic Programming Data Structure Binary Search Tree Algorithm Order Statistic Template
日常的数据结构 - 堆的实现与第 K 最小堆在前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式. 从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如 `+---+ \| 4 \| +---+ / \ +---+ +---+ \| 5 \| \| 9 \| +---+ +---+ / \ +---+ +---+ \| 8 \| \| 5 \| +---+ +---+` 这样一棵完全二叉树可以被转换成 `.----. /--. \ +---+---+---+---+---+---+----- \| - \| 4 \| 5 \| 9 \| 8 \| 5 \| ... +---+---+---+---+---+---+----- \______/ / \________/` 其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是 `.----. /--. \ +---+---+---+---+---+---+----- \| 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| ... +---+---+---+---+---+---+----- \______/ / \________/` 这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如 `.----. /--. \ +---+---+---+---+---+---+----- \| - \| 0 \| 1 \| 2 \| 3 \| 4 \| ... +---+---+---+---+---+---+----- \______/ / \________/` 也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 `i << 1`, 2i+1 等效于 `(i << 1) \| 1`, floor(i/2) 等效于 `i >> 1`, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升). 既然堆的逻辑结构是数组, 那么可以采用 `std::vector` 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架 `template <typename _T, typename _Less> class heap { std::vector<_T> array; _Less const less; typedef typename std::vector<_T>::size_type size_type; public: heap() : array(1) /* insert a placeholder, array[0] */ , less(_Less()) {} void push(_T const& value); _T pop(); };` Posted at Oct 07 2011 - 09:23:13 Permanent Link: /p/441 Load full text	Post tags: C++ Algorithm Template Heap Order Statistic Generic Programming Data Structure
日常的算法 - 顺序统计顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 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(++) 之流在平台相关这种水深火热之中挣扎的语言, 对机器字长, 以及整数类型字长在一些情况下是极其敏感的. 所以每个大型项目建设之前, 在某个头文件里面定义一大堆 `int32` 或者是 `unsigned8_t` 之类的固定字长类型显得非常必要, 而且让工程看起来很专业的样子. 然而, 由于标准库中没有, 项目之间又互相不信任, 结果是几乎每个库都会自定一套, 比如 boost 就有 `int8_t`, `int_least8_t` 等类型, 而 Qt 更是拿出了叫做 `qulonglong` 的类型来卖萌. 虽然说是跨平台, 但是如果迁移平台时使用了错误版本的库呢? 因此有时依然需要写一个类似下面的程序来人肉验证 `int main() { std::cout << sizeof(int4_type) << " " << sizeof(int8_type) << std::endl; return 0; }` 然而, 人都是不可靠的, 如果有人对你说, 喔, 我跑了上面的程序, 结果是 "4 8", 也许你仍会强迫症一样, 自己再验证一次. 好了, 也许你已经厌烦了, 这么一点破事情, 难道不能交给机器做么? 理想的解决方案是, 只需要这样一个模板就好了 `template <int _SizeOf> struct IWantAnIntegralTypeOf; int main() { IWantAnIntegralTypeOf<4> this_is_a_4_bytes_int; IWantAnIntegralTypeOf<8> this_is_a_8_bytes_int; return 0; }` 不是吗? 这是完全可行的, 实际上, 可以把 C 支持的所有内建整数类型先拿出来, 组成一个类型链表来搜索, 像下面这样 `struct __null__ {}; struct c_char { typedef char type; typedef __null__ next; }; struct c_short { typedef short type; typedef c_char next; }; struct c_int { typedef int type; typedef c_short next; }; struct c_long { typedef long type; typedef c_int next; }; struct c_long_long { typedef long long type; typedef c_long next; }; struct __head__ { typedef c_long_long next; };` 接下来, 弄个模板来搜, 搜索当然是用模板偏特化的方法 template <typename _TypeNode, int _SizeOf, bool _SizeMatched> struct type_finder; template <typename _TypeNode, int _SizeOf> struct type_finder<_TypeNode, _SizeOf, true> { typedef typename _TypeNode::type type; }; template <typename _TypeNode, int _SizeOf> struct type_finder<_TypeNode, _SizeOf, false> { typedef typename type_finder< typename _TypeNode::next , _SizeOf , _SizeOf == sizeof(typename _TypeNode::next::type)>::type type; }; Posted at Mar 26 2011 - 09:08:36 Permanent Link: /p/217 Load full text	Post tags: Generic Programming Metaprogramming C++ Template
泛型编程中的策略类在编译期想要组合策略, 除开人肉内联不算, 有很多方式. 比如弄很多很多的 `bool` 参数 `template <bool AllowDuplicate, bool SortElements, bool CheckOutOfRange> struct just_another_container;` 这看起来就是一个参数灾难, 如果某个地方出点小的模板编译错误, 哼哼~ 当然, 另一种简单的替代方案就是把所有的 `bool` 整合在一起, 形成一个位段 `template <unsigned Policy> struct just_another_container;` 这种情况实际上缺点更多, 比如维护位域会很麻烦, 有可能在这个声明之前有这些枚举 `enum { ALLOW_DUP_MASK = 1, SORT_ELE_MASK = 2, CHECK_OUT_OF_RANGE_MASK = 4, };` 考虑这个容器有个 `insert` 函数, 它很可能需要考虑是否允许重复元素 `template <unsigned AllowDuplicate> void insert(element_type e);` 而令人郁闷的是, 在 C++ 中不允许给函数偏特化, 也就是说这样写 `template <> void insert<0>(element_type e); template <> void insert<ALLOW_DUP_MASK>(element_type e);` 是无法编译的! 要绕过这道坎, 得把 `insert` 函数放入一个模板结构体 `template <unsigned AllowDuplicate> struct insert_s; template <> struct insert_s<ALLOW_DUP_MASK> { static void insert(just_a_container& container, element_type& e); };` 这样做代价高昂, 首先, `insert` 被当作孤儿一样的抛弃, 那么类中的任何非 `public` 成员都不再对它开放, 当然, 为了这么个简单的小玩意儿声明 `friend` 也是可行的, 但是多了不觉得烦吗? 另外, 在调用策略行为进行特化时一般只针对特定的位, 那么将该策略位从组合策略中分离出来, 代码中将充斥着这样的运算 `Policy & ALLOW_DUP_MASK Policy & CHECK_OUT_OF_RANGE_MASK` 比如 `void another_member_function() { element_type ele; // wanna call insert function of policy = Policy insert_s<Policy & ALLOW_DUP_MASK>::insert(this, ele); // ... }` 这样做非常麻烦, 如果某个地方漏了 `&` 或者跟错误的掩码进行了运算, 哼哼~ 不过, 泛型程序设计有自己的方法, 那就是, 多继承! 不要吓到了, 是的, 在 C++ 远古时代, 多继承被认定为獠牙猛兽. 不过那都是跟 C++ 运行时多态相关的. 步入泛型新纪元的 C++ 又迎来了多继承第二春, 它可以显著改善上述问题. 将上面的声明编程 `template <typename Policy*> struct just_another_container;` 然后加上这些结构体声明 `struct policy_base {}; struct allow_dup : public policy_base {}; struct sort_ele : public policy_base {}; struct check_out_of_range : public policy_base {};` 组合策略, 只需要声明一个策略类型继承想要的策略, 并把它传入容器就能达到目的, 比如 Posted at Nov 22 2009 - 08:56:30 Permanent Link: /p/36 Load full text	Post tags: Generic Programming C++ Template

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