在看了NTU的AI课程之后，试着用C++来实现了A*搜索算法。它的思想就是Avoid expanding paths that are already expensive.。标准的A*搜索算法描述如下：

给出带权无向图，初始顶点，目标顶点，以及evaulation function。Evalutaion function包括

• g(n)：为到达顶点n，当前已有的花费（cost so far to reach n）
• h(n)：一个 从任意顶点 到 目标顶点 的估计花费（estimated cost to goal from n）
• f(n)：从 初始顶点 到 目标顶点 的估计花费（estimated total cost from the starting node to goal through n）

f(n) = h(n) + g(n)

例如有三个地点A, B, C，它们之间的图如下

A —— B —— C

A —— B权重为30，B —— C权重为40，

A —— C的直线距离为50，但是并没有A——C这条边（即不能直接从A开始，只经过一条边就到达C）

现在，给出初始顶点为A，目标顶点为C，h(n)如下

h(A) = 50

h(B) = 40

h(C) = 0

在一开始，我们将A放入名为froniter的优先队列中，froniter按照f(n)的值升序排序。

那么我们有f(A) = h(A) + g(A)。h(A)是由用户直接给出的，等于50。g(A)是我们为了到达C，已有的花费，在这个例子中，可以理解为已经走过的路程，因为我们是一开始就在A，还没有开始走，所以g(A)为0。于是f(A) = h(A) + g(A) = 50 + 0 = 50

froniter中的数据如下：

Continue reading Standard A* Search Algorithm in C++ →

node.js里面的EventEmitter非常好用，于是上次写完Functor之后，就顺理成章的写了这个EventEmitter，或者说，就是为了实现这个EventEmitter才写的Functor（后文会提到为什么要Functor，毕竟如果只看Functor本身的话，还不如直接用lamdba方便）。

在node.js中，使用EventEmitter非常简单，

const EventEmitter = require('events');

class MyEmitter extends EventEmitter {}

const myEmitter = new MyEmitter();
myEmitter.on('event', () => {
    console.log('an event occurred!');
});
myEmitter.emit('event');

——https://nodejs.org/api/events.html

那么现在这个C++版的EventEmitter也必须做到这样简单易用，事实上，它也的确和node.js的使用方式类似。

#include <iostream>
#include <sstream>
#include <thread>
#include <vector>
#include "EventEmitter.hpp"

using namespace std;

class emitter : public EventEmitter {
};

int main(int argc, const char * argv[]) {
    emitter emitter;
    emitter.on("event", [&emitter](int data) {
        ostringstream osstream;
        osstream << "data: " << data << '\n';
        std::cout << osstream.str();
    });

    vector<thread> threads;
    for (int i = 0; i < 10; i++) {
        threads.emplace_back([&emitter, i]() {
            emitter.emit("event", i);
        });
    }

    for (auto &t : threads) t.join();
}

Continue reading A simple EventEmitter in C++ →

最近写代码的时候，总能在不少STL的函数声明里看见可爱的std::enable_if，虽然自己偶尔用过，不过也只是直接用STL库里的std::is_arithmetic之类。

于是就去Google了std::enable_if，然后参考了如下几篇post，写了一个较为通用的Module Check。

• Introduction to Type Traits in the C++ standard library
• SFINAE and enable_if
• Tips and tricks » EnableIf<C++11>
• C++技巧： SFINAE
• C++ metafunction to determine whether a type is callable

所以还是先从一个小的问题开始讲起吧～

假设我们做了一个中间类作为接口，这个中间类有一个模版构造函数，它接受一个类实例和一个double类型的参数，并且总是调用一个固定的实例方法。

class Intermediate {
public:
    template <typename T>
    Intermediate(const T& object, double value) {
        object.method(value);
    }
};

现在我们有如下的类，

class A {
public:
    void method(double d) const {
        std::cout<<d<<'\n';
    }
};

class B {
public:
    void method(int i) const {
        std::cout<<i<<'\n';
    }
};

虽然如下代码可以编译运行，但是假如我们希望只有类A被这样调用才有效呢？

Intermediate inter_a_1(a, 2.33); // print 2.33
Intermediate inter_b_1(b, 2.33); // print 2

Continue reading Module Check——Usage of std::enable_if →