About
RSS

Bit Focus

std::function 基本实现

std::function 是在 C++11 中新增的一个用于统一包装可调用对象的模板类型. 所谓统一包装, 就是无论被包装的内容的实际类型, 只要符合相应的函数调用签名, 都可以装入一个 std::function 对象中使用. 比如

Code Snippet 0-0
#include <iostream>
#include <functional>

// 全局函数
int fn_ptr(int x, int y)
{
    return x + y;
}

// 包含 2 个 int 成员的函数对象类型
struct TwoInts {
    TwoInts(int m_, int n_)
        : m(m_)
        , n(n_)
    {}

    int operator()(int x, int y)
    {
        return x + y + m + n;
    }

    int m;
    int n;
};

int main()
{
    // 使用 std::function 类型包装全局函数指针
    std::function<int(int, int)> f(fn_ptr);
    std::cout << f(1, 2) << std::endl; // 输出 3

    // 使用 std::function 类型包装函数对象
    std::function<int(int, int)> g(TwoInts(10, 20));
    std::cout << g(1, 2) << std::endl; // 输出 33

    return 0;
}

上面的使用例子中, 两个 std::function 对象定义都在栈上. 按照 C++ 的常识, 两个对象一定有相同的尺寸, 即对它们求 sizeof 得出的值一定相等. 但用于构造这两个 function 对象的材料却有着不同的尺寸, 也就是说 function 可以 "捕获" 任何尺寸的可调用对象, 这正是其奇妙之处.

下面就来简单分析 std::function 的实现方法.

虽然 std::function 是在 C++11 中引入的, 但作为一个基本实现的分析, 本文将排除所有 C++11 的特性以避免不必要的解释. 当然, 这样会产生一个硬伤: 由于可变参数模板特性也是 C++11 中引入的特性, 本文的实现中将不支持任意多个模板类型参数, 而是使用返回值类型加上 2 个参数的类型共计 3 个类型作为模板的类型参数列表. 亦即, 在 C++11 中, 下面的用法是可能的

std::function<double()> f;         // 只有返回值类型 <double> 的特化
std::function<int(std::string)> g; // 有返回值类型和 1 个参数类型 <int, std::string> 的特化
std::function<void(int, float)> h; // 有返回值类型和 2 个参数类型 <void, int, float> 的特化
// 可以扩展为任意多个参数类型的特化, 这是 C++11 的新特性

而本文中要实现的只包含下面这样的形式

Code Snippet 0-1
// 默认特化没有实现
template <typename T>
class function;

// 实现有返回值类型和 2 个参数类型的偏特化
template <typename Ret, typename Arg0, typename Arg1>
class function<Ret(Arg0, Arg1)> {
    // ...
};

语法上, 类似上面的 function<int(int, int)>, class function<Ret(Arg0, Arg1)> 等类似函数签名的模板特化形式并不常见, 虽然它是 C++11 之前就一直存在的语法. 抛开语法层面的部分, function 实现中最重要的就是如何在内部维护不同类型不同尺寸的可调用对象.

Posted at Nov 25 2017 - 04:55:23

Permanent Link: /p/525 Load full text

Post tags:

 STL
 C++11
 C++

C++ Lambda 简易上手

    本文所有代码示例通过 g++ 4.6 编译.

    之前有吐槽过 C++ STL 算法中的 for_each 函数华而不实, 主要原因是受限于 C++ 的函数编写语法, 即传统上 C++ 要求函数须独立编写, 而不能嵌套在其它函数内. 不过, 欢迎来到二十一世纪的第一个 0x10 年, 现在有了 lambda.
    与其它语言一样, C++ 的 lambda 就是个匿名函数, 它的语法结构如
[ 上下文变量绑定方式 ] ( 形式参数列表 ) 可省略的返回值类型声明
{
    函数体
}
    匿名函数可以定义在任何地方, 作为一个表达式出现; 如果在匿名函数的函数体中使用了表达式所在上下文中定义的量, 则需要指定绑定方式. 如
// 定义变量 sqr 为一个匿名函数
// 这个匿名函数的上下文变量绑定方式为空, 因为它无须引入任何上下文变量
// 这个匿名函数接受一个 int 作为参数
// 返回值类型声明省略, 由编译器推倒出返回 int
auto sqr = [](int x)
           {
               return x * x;
           };

int x = 10;
// 这个匿名函数的上下文变量绑定方式为 & 即引用方式, 它引用了上文中定义的 x
// 这个匿名函数接受一个 int 作为参数
// 返回值类型声明为 bool
auto equalsToX = [&](int y) -> bool
                 {
                     return x == y;
                 };

// 这个匿名函数的上下文变量绑定方式为 = 即复制方式, 它引用了上文中定义的 x
// 这个匿名函数接受一个 int 作为参数
// 返回值类型声明省略
auto lessThanX = [=](int y)
                 {
                     return y < x;
                 };
    可见多亏了 C++ 的强制类型声明和变量定义检查, 才把一个简单的匿名函数搞得这么复杂, 解决了不少其它语言中不存在的问题.

    作为 C++ 程序员的一个特异能力便是能够在写代码时就预见到这段程序运行时内存与对象的流动. 看了上面匿名函数的各种奇葩绑定上下文的方法, 很明显它们不仅是一个函数那么简单, 如果必要匿名函数会占用一些内存空间, 可以做这样一个实验来试试.
struct Point {
    Point()
        : x(0)
        , y(0)
    {}

    double x;
    double y;
};

int main()
{
    Point p;
    auto f = [&]()
             {
                 std::cout << p.x << "," << p.y << std::endl;
             };
    auto g = [=]()
             {
                 std::cout << p.x << "," << p.y << std::endl;
             };
    std::cout << sizeof(f) << " - " << sizeof(Point*) << std::endl;
    std::cout << sizeof(g) << " - " << sizeof(Point) << std::endl;

    auto sqr = [](int x)
               {
                   return x * x;
               };
    std::cout << sizeof(sqr) << std::endl;

    return 0;
}

Posted at Mar 03 2013 - 04:58:20

Permanent Link: /p/505 Load full text

Post tags:

 Labmda
 C++
 C++11
 Nested Function

在 C++ 模板类体中将类名仍视为模板

    用 Clang++ 编译下面的源代码 (已测试 ArchLinux clang 3.2-3)
template <template <class> class T>
class A {};

template <typename T>
class B {
    A<B> member;
};

int main()
{
    B<int> b;
    return 0;
}
会得到如下错误信息
error: template argument for template template parameter must be a class template
    A<B> member;
      ^
也就是说, clang++ 会认为出现在模板类 B 的类体中的符号 B 是一个已经实例化过的类型, 不能够被传递给模板类 A 用于实例化.
    而 g++ 4.7 可以正确编译通过, 说明 g++ 肯定内置了某种脑补机制, 能灵活处理这样的情况, 它甚至可以编译如下分裂的代码
template <template <class> class T>
class A {};

template <class T>
class C {};

template <typename T>
class B {
    A<B> member;
    C<B> another;
};

int main()
{
    B<int> b;
    return 0;
}
    当然在 clang++ 下也不是没办法解决了, 方案是, 在类体中如果要将类名当作模板来使用, 则在名字前加上名字空间声明. 如上面 B 定义在全局名字空间中, 所以代码应该这样修改
template <template <class> class T>
class A {};

template <typename T>
class B {
    A< ::B> member;
};

int main()
{
    B<int> b;
    return 0;
}
    话说小于号跟双冒号之间有个空格 < ::, 这绝不是我手残了抖上去的, 而是这地方必须要一个空格. C++ 程序设计领域流行着各种都市传说, 其中有模板套模板结束时的两个大于号之间要加个空格什么的, 类似, 小于号跟冒号之间也要加个空格, 否则 <: 会被认为是 [.
    相应地, 如果 B 定义于某个有名字的名字空间 (这话说得...) 中那么上面代码应作相应修改
template <template <class> class T>
class A {};

namespace ns {
    template <typename T>
    class B {
        A<ns::B> member;
    };
}

int main()
{
    ns::B<int> b;
    return 0;
}

Posted at Jan 14 2013 - 03:26:03

Permanent Link: /p/503 Load full text

Post tags:

 C++
 Template

句读探析 - 又一个 Javascript 生成器

    前段时间博客没怎么更新, 因为不才去刷一个编译器项目了. 这项目是个 Javascript 产生器.
    起这个念头的契机是看到连 M$ 都动心思搞 JS 生成器了 (然而不得不吐槽的是, 这语言看起来跟 JS 简直一个德行). 而模仿的对象则是 CoffeeScript, 可是我又不想去分支 CoffeeScript 改点语法什么的改成 LatteScript 或 CappuccinoScript (我对 Coffee 的某些语法不很满意), 于是乎自己折腾了一个.
    不过另一方面, 这个编译器 (暂定名是 Stekinscript) 也不是完全无中生有, 而是从我的毕业项目修改过来的. 要说这样有什么不好的话, 就是 --- 这东西用 C++ 实现的 (准确地说是 C++11); 要说有什么好的话, 就是貌似这样可以直接集成 v8, 嗯 (自黑一下, 我没考察过这个, 也没有做这个事情的计划).

    下面介绍一下这个语言本身, 撇开日常的什么分支语句啦函数定义返回这些 (详情可参考文档), 先说说重点.
    首先 Stekinscript 支持缩进语法, 类似 Python 跟 CoffeeScript. 代码很重要的一点就是要看着舒服不是么?
    其次就是非强制类型, 强制类型给人的感觉呢, 就像三岁小孩子学写字旁边有个执戒尺的先生一样, 错一点就打手, 我们已经是断奶的程序员了好么, 所以什么 Dart 就先搁下不用了.
    最后是实际使用的感觉, 这一点我排斥 CoffeeScript 的 lambda 语法如 (x)-> x * x 这种. 要知道输入类似 -> 这样的符号两个字符都在右手无名指跟小指区, 还是一上一下, 而且减号不用按住 Shift 而大于号又需要, 这是有多别扭设计语言的人没知觉么? 还是说已经练成星际争霸九段这点微操不算什么?

    吐槽就到此为止, 下面贴个 Stekinscript 的例子
x: []
setTimeout(():
    if x.length = 10
        return
    x.push(document.getElementById('input').value)
, 2000)

Posted at Nov 16 2012 - 14:18:34

Permanent Link: /p/497 Load full text

Post tags:

 Compiler Construction
 Stekin
 C++

多态泛型不两全 - 面向对象中的协变与逆变

在面向对象语言中, 子类覆盖父类中的实例成员函数时, 可以酌情修改返回值类型, 使之变得更加具体. 比如在 C++ 中, 下面的代码是可行的.

Code Snippet 0-0
class base {
public:
    virtual base* copy() const
    {
        return new base;
    }
};

class inherit: public base {
    virtual inherit* copy() const
    {
        return new inherit;
    }
};

因为 inherit* 类型可以无压力转换为 base* 类型, 所以这样做并不会破坏多态机制. 这种做法称之为协变 (covariance).

然而协变一方面满足着面向对象设计的种种需求时, 另一方面与泛型的协作却非常糟糕, 比如如果尝试使用自动指针取代上述代码中的返回值类型就不正确了

Code Snippet 0-1
class base {
public:
    virtual std::unique_ptr<base> copy() const
    {
        return new base;
    }
};

class inherit: public base {
    virtual std::unique_ptr<inherit> copy() const
    {
        return new inherit;
    }
};

编译这一段代码会得到类似如下的错误

invalid covariant return type for 'virtual std::unique_ptr<inherit> inherit::copy() const'

简而言之, std::unique_ptr<base> 与 std::unique_ptr<inherit> 并无实质上的继承关系, 因此无法如此重定义子类函数的返回类型.

这并不是语言层面出现的疵漏, 如果这确实可行, 反而还会引起问题, 举个例子

Code Snippet 0-2
class fruit {};
class apple: public fruit {public: void do_something_as_apple();};
class banana: public fruit {public: void do_something_as_banana();};

int main(void)
{
    std::unique_ptr<apple> a(new apple);

    /* 如果子类的自动指针对象是可以为父类的自动指针的引用直接引用
       也就是说下面这一句合法 */
    std::unique_ptr<fruit>& f = a;

    /* 接下来利用 f 来重置内部的裸指针 */
    f.reset(new banana);

    /* 由于 f 就是 a 的引用, 因此 a 中的裸指针指向了
       与 apple 类型不兼容的 banana 的实例 */
    a->do_something_as_apple(); // 謎の結果
    return 0;
}

因此, 这种利用自动指针绕着弯子来造错误的行为是绝对不被允许的. 此外, 下面的这种赋值方式 (虽然明显看起来很怪异) 也是不被允许的

int main(void)
{
    inherit* i;
    base*& b = i; // 跪
    return 0;
}

在之前的一篇文章也有简单介绍到, 不过当时说的是父类的二级指针不能被子类二级指针所赋值.

除了指针之外, 可以想象数组, 包括 STL 容器也会纷纷中枪, 比如 std::vector<base*> 类型的引用是无法引用 std::vector<inherit*> 类型的对象的.

Posted at May 14 2012 - 15:44:54

Permanent Link: /p/490 Load full text

Post tags:

 Java
 C++
 面向对象程序设计

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

二叉检索树的查询与检索操作看这里

    从二叉检索树中删除一个元素分多个步骤:
  • 找到节点
  • 将节点移动到容易删除的位置
  • 删除节点
    找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 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

Page 0 1 2 3 4

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