可移植的静态线程局部存储修饰符

主流 C、C++ 编译器在主流平台下通常都通过语言扩展来支持静态线程局部存储，用户可以通过在静态变量前简单地添加一个修饰符使其被静态地添加到 TLS 索引中。然而，不同的编译器支持不同的修饰方式，有时为了可移植性，就需要类似下面这样的预编译指令，根据当前使用的编译器来决定如何定义修饰符。

#if defined(__GNUC__) || defined(__SUNPRO_C) || defined(__xlc__)
# define THREAD_LOCAL __thread
#elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
# define THREAD_LOCAL __declspec(thread)
#elif defined(__INTEL_COMPILER)
# ifdef _WIN32
#   define THREAD_LOCAL __declspec(thread)
# else
#   define THREAD_LOCAL __thread
# endif
#else
# error "Unsupported compiler."
#endif

之后用 static THREAD_LOCAL 修饰变量即可。

方法分派

Ruby 和大部分 OO 语言一样，都是在语言、语法层仅支持单一方法分派的语言。单一分派（single dispatch）是在通过迟（动态）绑定实现多态时的一种思路，它依靠接收者的运行时类型动态地分派应该调用的方法。

Smalltalk、Python 以及 Ruby 使用的都是一种实现方式，那就是通过方法分派函数（dispatch function）和分派表（dispatch table）进行消息到方法的映射。每个类型在定义时就内置了这样的分派函数和分派表，后者是一个消息（符号）到实际方法的映射表，而前者接受一个输入符号，然后通过分派表映射到正确的方法（其间包含处理派生类继承的方法和模块 mixin 后的方法等比较复杂的过程）。当我们在 Ruby 中以 obj.method 的形式调用一个方法时，按照 Smalltalk 的程序语言概念，就是向 obj 这个对象发送了一个消息，传递了一个 :method 符号，而作为接收者的 obj 会通过分派函数在分派表中找到对应的方法。这整个过程就是所谓的动态方法分派（dynamic method dispatch）。

比如：基类和派生类有同名方法，但在实际调用时，随着接收者的不同，实际调用的方法也不同，当接收者是基类实例时调用基类实例方法，当接收者是派生类实例时调用派生类实力方法。关于这个的更多信息，还可以参考本主题早期的一篇关于迟绑定的回帖。

既然 Ruby 使用的分派模式唤作单一分派，那自然还有多重分派（multiple dispatch）。Common Lisp 是一个众所周知的最早支持多重分派的语言。多重分派通常是指在动态判断接收者类型的同时也判断方法参数的动态类型的分派模式。更有甚者，会判断参数的值，返回类型，或返回值。

要注意这里是方法参数的动态类型（运行时类型），而不是静态类型，这是关键。对于支持静态类型的语言来说，由于方法参数的类型可以在编译时决定，所以他完全可以做静态分派，也就是静态绑定（早绑定）。静态类型语言中的方法重载就是这样的一个概念——静态类型的参数在编译时就可以确定，所以方法的分派也是静态的。

比如，C++ 的方法重载，就是通过不同的静态类型的参数实现的，这个过程不属于动态分派，自然也就不能称之为多重分派。实际上，大多数 C++ 编译器都会给重载的方法/函数进行一个所谓的方法名/函数名装饰（function name decoration）的处理，所以在链接的时候，实际参与链接使用的正式函数名并不是你在源代码中敲下的函数名，而会有一些别的奇怪的符号，这个想必自己写过 C++ 共享库的朋友都深有体会。动态多重分派的严格定义，是指方法名不变，根据接收者和参数类型（甚至参数值、返回类型、返回值）判断应该调用的方法的一种多态。当然，由于 C++ 本身有虚函数的机制，所以还是支持动态分派的，只不过不支持多重分派罢了。

像后来的 Java 这样的静态类型语言，看起来也是支持方法重载，实际上也和 C++ 一样，只是单一分派罢了。C# 是个怪胎，C# 4.0 同时支持静态类型和动态类型，这使得多重分派在 4.0 中得到了支持。Python、Ruby 都是没有静态类型的语言，所以不可能像 C++ 那样去根据静态类型在编译时做函数名装饰，也就不可能有静态分派。因此，传统意义上的方法重载在这样的纯动态类型语言中是不存在的。由于不能重载，相同名称的方法就只有一个定义，所以在语言层、语法层是不能实现多重分派的。要想在仅支持单一分派的语言中使用多重分派，只能在高层模拟进行，比如 Ruby 可以通过 Object#class 去判断对象的运行时类（型），然后根据类型的不同分别处理。很多第三方的扩展库就是这么做的。

def foo(bar)
  case bar
  when String
    p 'bar'
  when Symbol
    p :bar
  end
end

foo :foo
foo 'foo'

输出：

:bar
"bar"

二叉堆

一个最小二叉堆的 C++ 实现，底层采用了数组形式的 Vector 结构存放二叉树。add 添加元素到堆，shift 从堆顶部删除元素，peek 获取堆顶部元素。其中最重要的算法是 bubble-down，它把堆中放置位置过高的“重”（如果是最大堆，自然就是“轻”）物推到了合适位置。二叉堆再抽象一层，就可以用来实现优先队列。

#ifndef _BINARY_HEAP_H_
#define _BINARY_HEAP_H_

#include <vector>

template <typename T>
class BinaryHeap
{
public:
    BinaryHeap()
    {
    }

    BinaryHeap(const T& elem)
    {
        heap_.push_back(elem);
    }

    BinaryHeap(const std::vector<T>& elems)
    {
        heap_= elems;
        for (int i = (heap_.size() - 1) / 2; i >= 0; --i)
            bubbleDown(i);
    }

    virtual void insert(const T& elem)
    {
        int i = heap_.size();
        heap_.resize(i + 1);
        do {
            /* Check heap_[i]'s parent. */
            int j = (i - 1) / 2;
            if (i <= 0 || elem >= heap_[j])
                break;
            heap_[i] = heap_[j];
            i = j;
        } while (true);
        heap_[i] = elem;
    }

    virtual T shift(unsigned idx = 0)
    {
        if (heap_.size() <= idx)
            throw "Heap is empty";
        T ret = heap_[idx];
        heap_[idx] = heap_.back();
        heap_.pop_back();
        bubbleDown(idx);
        return ret;
    }

    virtual const T& peek() const
    {
        return heap_.front();
    }

    virtual BinaryHeap<T>& operator << (const T& elem)
    {
        insert(elem);
        return *this;
    }

    virtual BinaryHeap<T>& operator >> (T& receiver)
    {
        receiver = shift();
        return *this;
    }

protected:
    void bubbleDown(unsigned idx)
    {
        unsigned int max = idx;
        do {
            unsigned int i, j;
            i = idx * 2 + 1;
            j = i + 1;
            /* Pick heap_[i]'s largest child. */
            if (j < heap_.size() && heap_[j] < heap_[max])
                max = j;
            if (i < heap_.size() && heap_[i] < heap_[max])
                max = i;
            if (max == idx)
                break;
            /* Exchange heap_[i] and heap_[max_idx]. */
            T tmp = heap_[idx];
            heap_[idx] = heap_[max];
            heap_[max] = tmp;
            idx = max;
        } while (true);
    }

protected:
    std::vector<T> heap_;
};

#endif /* _BINARY_HEAP_H_ */

同样的算法也用 Ruby 写了一份，但执行效率是有巨大差别的，特别是 Ruby 1.8。不过使用 Ruby 的好处是通过闭包可以方便地传递匿名比较函数，而在 C++ 中则需要传递函数指针，这个过程往往缺乏爱且伴随着痛苦。

class BinaryHeap
  def initialize(*args, &cmptr)
    @cmptr = cmptr
    @heap = args.clone
    i = (@heap.size - 1) >> 1
    while i >= 0
      bubble_down(i)
      i -= 1
    end
  end
  def insert(elem)
    i = @heap.size
    loop do
      j = (i - 1) >> 1
      if j < 0 || @cmptr.call(elem, @heap[j]) <= 0
        @heap[i] = elem
        break
      else
        @heap[i] = @heap[j]
        i = j
      end
    end
    self
  end
  def shift(idx = 0)
    ret = @heap[idx]
    len = @heap.size
    if len > 1
      @heap[idx] = @heap.pop
      bubble_down(idx)
    elsif 1 == len
      @heap.clear
    end
    ret
  end
  def bubble_down(idx)
    len = @heap.size
    loop do
      i = (idx << 1) + 1
      j = i + 1
      max = idx
      max = j if j < len && @cmptr.call(@heap[j], @heap[max]) > 0
      max = i if i < len && @cmptr.call(@heap[i], @heap[max]) > 0
      if max != idx
        @heap[idx],@heap[max] = @heap[max],@heap[idx]
        idx = max
      else
        break
      end
    end
  end
  def to_s(indent = 8)
    helper = lambda do |idx, acc|
      if idx >= @heap.size then ''
      else
        child_base = idx << 1
        helper.call(child_base + 2, acc + 1) +
        ' '*indent*acc + @heap[idx].to_s + "\n" +
        helper.call(child_base + 1, acc + 1)
      end
    end
    helper.call(0, 0)
  end
  def <<(elem)
    add(elem)
  end
end

DATA = 10
data = Array.new(DATA)
DATA.times do |i|
  data[i] = rand(DATA<<1)
end

bh = BinaryHeap.new(*data) { |a, b| a <=> b }
print bh
bh << 1 << 3 << 0 << -3 << 0
print bh
bh.shift
print bh
bh.shift
print bh

绑定

　　在计算机科学中，“绑定”（Binding）一词是指一个更复杂、更大型的物件的引用的创建。例如当我们编写了一个函数，这个函数名就绑定了该函数本体，我们可以通过函数名来引用并调用该函数，这被称为名称绑定；又如当 Ruby 通过 API 去调用了 C 语言写的库函数时，这就是一个语言绑定；再如面向对象语言中的方法调度 obj.method，这也是一个名称绑定，它会根据接收者 obj 具体的对象类型来确定应该引用哪个对象类型的 method 方法，而如果 obj 在编译时就能确定，那便可称之为静态绑定（早绑定），早期的静态类型语言（如 C）使用的是早绑定；如果 obj 在运行时才能确定，那便可称为动态绑定（迟绑定），动态类型语言（如 Ruby）使用的是迟绑定，而有些语言则同时支持早绑定和迟绑定，如 C++ 的虚函数使用迟绑定，普通函数则使用早绑定。

　　在 Ruby 中，Kernel 有一个方法 binding，它返回一个 Binding 类型的对象。这个 Binding 对象就是我们这里说的绑定，它封装了当前执行上下文中的所有绑定（变量、方法、语句块、self 的名称绑定），而这些绑定直接决定了面向对象语言中的执行环境。比如，当我们调用 p 时，实际上是进行了 self 和 p 的绑定，而 p 具体是哪个方法，是由 self 的类型来决定的，如果我们在顶层，而 Kernel#p 又没有被重写，那 p 就是一个用来显示对象细节的方法。可以说有了一个绑定的列表，我们就有了一个完整的面向对象上下文的拷贝，就好比上帝在 12 分 37 秒复制了一份世界，而这个世界与原本世界的环境一模一样，既有这朵花，又有那株草。Ruby 的 Binding 对象的概念和 Continuation 有共通之处，但 Continuation 主要用于实际堆、栈内存的环境跳转，而 Binding 则比较高层。

　　这个 Binding 对象有什么用？主要是用于 eval 这个函数。eval 的第一个参数是需要 eval 的一段脚本字符串，而第二个可选参数则接受一个 Binding 对象。当指定了 Binding 时，eval 会在传递给它的 Binding 所封装的执行环境里执行脚本，否则是在调用者的执行环境里执行。我们可以通过这个机制来进行一些不同上下文之间的通信，或者是在一个上下文即将被销毁之前保存该上下文环境以留他用，如：

def foo
  bar = 'baz'
  return binding
end

eval('p bar', foo)

　　这里我们通过 foo 返回的 Binding 获取到了局部上下文销毁前的局部变量 bar 的值，而在不使用 binding 的情况下，局部变量 bar 在 foo 外层是不可见的。

　　最后，Ruby 有一个预定义的常量：TOPLEVEL_BINDING，它指向一个封装了顶层绑定的对象，通过它我们可以在其它上下文中通过 eval 在顶层上下文环境中执行脚本。

双向循环链表

双向循环链表，即每个节点都拥有一前一后两个指针且头尾互链的链表。各种链表的简单区别如下：

• 单向链表：基本链表；
• 单向循环链表：不同于单向链表以 NULL 判断链表的尾部，单向循环链表的尾部链接到表头，因此当迭代操作到表头前即是尾部；
• 双向链表：比单向链表多出指向前一个节点的指针，但实际上使用双向链表时很少使用不循环的；
• 双向循环链表：相对于单向循环链表，双向循环链表可从头部反向迭代，这在链表长度很大且需要获取、插入或删除靠近链表尾部元素的时候十分高效。单向循环列表只能从表头正向迭代，执行的时间大于从反向迭代。

node.h:

/*
 * 节点类型。三个成员分别是：指向前一个节点的指针，元素本身，指向后一个节点的指针。
 */
class Node {
public:
    int element;
    Node *next;
    Node *previous;
    Node(int element, Node *next, Node *previous) {
        this->element = element;
        this->next = next;
        this->previous = previous;
    }
};

linkedlist.h:

#include "node.h"

struct LinkedList {
    LinkedList();
    void addFirst(int);
    void addLast(int);
    void add(int index, int element);
    int getFirst();
    int getLast();
    int get(int);
    int removeFirst();
    int removeLast();
    int remove(int);
    void iterate();

private:
    Node *header;
    int size;
};

linkedlist.cpp:

#include "linkedlist.h"
#include <iostream>
using std::cout;

/*
 * 构造方法。
 * 生成一个空的节点介于表头和表尾之间，初始前后指针都指向自己。
 */
LinkedList::LinkedList() {
    header = new Node(NULL, NULL, NULL);
    header->next = header;
    header->previous = header;
    size = 0;
}

/*
 * 在链表头部添加一个元素。
 * 生成一个新的节点，向前指向空节点，向后指向原来空节点的下一个节点，即原来的第一个节点。
 * 空节点向后指向此节点，原来的第一个节点向前指向此节点。
 */
void LinkedList::addFirst(int i) {
    header->next = new Node(i, header->next, header);
    header->next->next->previous = header->next;
    ++size;
}

/*
 * 在链表最后添加一个元素。
 * 生成一个新的节点，向前指向原来空节点的前一个节点，即原来的最后一个节点，向后指向空节点。
 * 原来的最后一个节点向后指向此节点，空节点向前指向此节点。
 */
void LinkedList::addLast(int i) {
    header->previous = new Node(i, header, header->previous);
    header->previous->previous->next = header->previous;
    ++size;
}

/*
 * 在指定的索引前插入一个元素。0 <= 索引 <= 链表长度。
 * 如果索引值小于链表长度的一半，向后（正向）迭代获取索引值位置的节点，反之则向前（反向）。
 * 生成一个新的节点，向前指向原来这个位置的节点的前一个节点，向后指向原来这个位置的节点。
 * 原来这个位置的节点的前一个节点向后指向此节点，原来这个位置的节点向前指向此节点。
 * （在指定的索引删除一个元素实现方法类似）
 */
void LinkedList::add(int index, int i) {
    if(index > size || index < 0) {
        cout << "Exception in add(): Index out of bound." << '\n';
    return;
    }
    Node *entry;
    if(index < size / 2) {
        entry = header->next;
        for(int i = 0; i < index; ++i)
            entry = entry->next;
    }
    else {
        entry = header;
        for(int i = size; i > index; --i)
            entry = entry->previous;
    }
    entry->previous->next = new Node(i, entry, entry->previous);
    entry->previous = entry->previous->next;
    ++size;
}

/*
 * 获取链表第一个元素。
 * 空节点向后指向的节点即是第一个元素。
 */
int LinkedList::getFirst() {
    if(!size)
        cout << "Exception in getFirst(): List is empty." << '\n';
    return header->next->element;
}

/*
 * 获取链表最后一个元素。
 * 空节点向前指向的节点即是最后一个元素。
 */
int LinkedList::getLast() {
    if(!size)
        cout << "Exception in getLast(): List is empty." << '\n';
    return header->previous->element;
}

/*
 * 删除并返回链表第一个元素。
 * 链表第二个节点向前指向空节点，空节点向后指向第二个节点。
 */
int LinkedList::removeFirst() {
    int remove = header->next->element;
    header->next->next->previous = header;
    header->next = header->next->next;
    --size;
    return remove;
}

/*
 * 删除并返回链表最后一个元素。
 * 链表倒数第二个节点向后指向空节点，空节点向前指向倒数第二个节点。
 */
int LinkedList::removeLast() {
    int remove = header->previous->element;
    header->previous->previous->next = header;
    header->previous = header->previous->previous;
    --size;
    return remove;
}

/*
 * 用来输出所有元素的迭代方法。
 */
void LinkedList::iterate() {
    if(!size) {
        cout << "Exception in iterate(): List is empty." << '\n';
        return;
    }
    for(Node *entry = header->next; entry != header; entry = entry->next)
        cout << entry->element << " ";
    cout << '\n';
}