杂项：boost mpl 中的迭代器、算法与其它。

     题目有点大，只能尽力研究源码，尽量多写。好，目标在此，留待再议。

     给定一个数组 array[] = {3, 1, 2, 4, 0}; 这个给定的数组有目的性，即它符合 n * m 的规则，这里是 5 * 5（5个元素，5个连续且不同的值）。按我想到的一般的方法，就是使用循环来求出各种排列的可能，但这种方法不能确保每个元素只出现一次，且随着元素个数的增长，循环深度将变得很深。继续想下去，这种方法将会变得很复杂，这就要求我寻找另外一种方法。注意到每个元素并不相同，那么要使各个元素在每个位置上只出现一次，很明显的一种方法就是“彩票机读票法”。比如数据读入口在第一个元素的位置，那么依次循环这个数组，每次使后面的元素向前移动一位，各个数字不就都读到了吗，这就像在打印机中滚动的纸。具体步骤如下：

31240
12403 <—rotate

     第一位如此，那么后面的每一位也如此，也就是递归地处理后面的数字，每移动一位就以下一位为起点做相同的处理，直到所有数字循环了一遍，那排列的工作也就完成了。一个具体的实现如下：

/*
 * @param r:     需要求其排列的向量
 * @param iPos:  当前所进行到的位置
 * 程序体中的注释表示处于那个位置的向量都是一个新的且唯一的排列
*/

void rotate(vector<int>& r, int iPos) {

    if(iPos == r.size() - 1)//是否循环完毕，调用函数时 iPos 置0
        return;

    int iNextPos = iPos + 1;
    for(size_t i = iPos; i < r.size(); ++i) {
        if(i == 0) {
            //a different permutation, do something here
        }

        int t = r[iPos];
        for(size_t j = iPos; j < r.size() - 1; ++j)//循环前移
            r[j] = r[j + 1];
        r[r.size() - 1] = t;

        if(i != r.size() - 1) {
            //a different permutation, do something here
        }

        rotate(r, iNextPos);//从下一位数字开始新的位移
    }
}

   这种方法不要求数字式连续的，也不用事先规定好向量的长度。只是当向量长度到了一定的时候，运算时间会很长！其它方法未知……

   topcoder 上的练习题如下：

Problem Statement

A permutation A[0], A[1], ..., A[N-1] is a sequence containing each integer between 0 and N-1, inclusive, exactly once. Each permutation A of length N has a corresponding child array B of the same length, where B is defined as follows:
B[0] = 0
B[i] = A[B[i-1]], for every i between 1 and N-1, inclusive.
A permutation is considered perfect if its child array is also a permutation.  Below are given all permutations for N=3 with their child arrays. Note that for two of these permutations ({1, 2, 0} and {2, 0, 1}) the child array is also a permutation, so these two permutations are perfect.
Permutation        Child array
{0, 1, 2}        {0, 0, 0}
{0, 2, 1}        {0, 0, 0}
{1, 0, 2}        {0, 1, 0}
{1, 2, 0}        {0, 1, 2}
{2, 0, 1}        {0, 2, 1}
{2, 1, 0}        {0, 2, 0}
You are given a vector <int> P containing a permutation of length N. Find a perfect permutation Q of the same length such that the difference between P and Q is as small as possible, and return this difference. The difference between P and Q is the number of indices i for which P[i] and Q[i] are different.
Definition

Class:
PerfectPermutation
Method:
reorder
Parameters:
vector <int>
Returns:
int
Method signature:
int reorder(vector <int> P)
(be sure your method is public)

Constraints
-
P will contain between 1 and 50 elements, inclusive.
-
P will contain each integer between 0 and N-1, inclusive, exactly once, where N is the number of elements in P.
Examples

0)
{2, 0, 1}
Returns: 0
P is a perfect permutation, so we can use the same permutation for Q. The difference is then 0 because P and Q are the same.

1)
{2, 0, 1, 4, 3}
Returns: 2
Q might be {2, 0, 3, 4, 1}.

2)
{2, 3, 0, 1}
Returns: 2
Q might be {1, 3, 0, 2}.

3)
{0, 5, 3, 2, 1, 4}
Returns: 3

4)
{4, 2, 6, 0, 3, 5, 9, 7, 8, 1}
Returns: 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

#include <iostream>
#include <vector>
#include <cstddef>
#include <limits>
#include <cassert>

#include <boost\assign.hpp>    // for vector +=

using namespace std;

class PerfectPermutation {
public:
    int  reorder(const vector<int>& P, vector<int>& result);
    bool isPerfect(const vector<int>& P);

private:
    int  difference(const vector<int>& P, const vector<int>& Q);
    void rotate(const vector<int>& src, vector<int>& r, int level, int& nMin, vector<int>& out);
};

int PerfectPermutation::difference(const vector<int>& P, const vector<int>& Q) {

    size_t cDiff = P.size();
    assert(cDiff == Q.size());

    for(size_t i = 0; i < P.size(); ++i) {
        if(P[i] == Q[i])
            cDiff--;
    }

    return cDiff;
}

bool PerfectPermutation::isPerfect(const vector<int>& A) {

    int Bi = 0, Bi_1 = 0;
    vector<bool> vb(A.size());
    vb[0] = true;

    for(size_t i = 1; i < A.size(); ++i) {
        if(vb[Bi = A[Bi_1]])
            return false;
        else
            vb[Bi] = true;

        Bi_1 = Bi;
    }

    return true;
}

void PerfectPermutation::rotate(const vector<int>& src, vector<int>& r, int level, int& nMin, vector<int>& out) {

    if(level == r.size() - 1)
        return;

    int in = level + 1;
    for(size_t i = level; i < r.size(); ++i) {
        if(i == 0 && isPerfect(r)) {
            nMin = min(difference(src, r), nMin);
            out = r;
        }

        int t = r[level];
        for(size_t j = level; j < r.size() - 1; ++j)
            r[j] = r[j + 1];
        r[r.size() - 1] = t;

        if((i != r.size() - 1) && isPerfect(r)) {
            nMin = min(difference(src, r), nMin);
            out = r;
        }

        rotate(src, r, in, nMin, out);
    }
}

int PerfectPermutation::reorder(const vector<int>& P, vector<int>& result) {

    if(P.size() == 1 || isPerfect(P))
        return 0;

    int nMin = numeric_limits<int>::max();

    vector<int> Q(P);

    rotate(P, Q, 0, nMin, result);

    return nMin == numeric_limits<int>::max() ? -1 : nMin;
}
int main() {

    using namespace boost::assign;

    PerfectPermutation pp;

    vector<int> P;
    P += 2, 0, 1, 4, 3;
    vector<int> result(P.size());

    cout << "Is a perfect Permutation :                    " << (pp.isPerfect(P) ? "Yes" : "No") << endl;
    cout << "Difference between before reorder and after : " << pp.reorder(P, result) << endl;
    assert(pp.isPerfect(result));
    cout << "One answer might be :                         ";
    for(size_t i = 0; i < result.size(); ++i)
        cout << result[i] << " ";
    cout << endl;

    return 0;
}

      c 中的 offsetof 宏；

      《COM本质论》: "inttable.h" 中的 BASE_OFFSET ；

      和 This() (它用到了 offsetof，权且当做是一个 packaged offset 吧)。

      先定义一些辅助类：

struct IX {
    virtual void fx() = 0;
};
struct IY {
    virtual void fy() = 0;
};
class CA : public IX,
           public IY {
public:
    virtual void fx() { cout << "CA::fx()" << endl; };
    virtual void fy() { cout << "CA::fy()" << endl; };

    struct Inner {
        CA* This() { return (CA*)((char*)this - offsetof(CA, m_inner)); }
    };
    Inner m_inner;
};

      先看 offsetof ：

#define offsetof(s,m)   (size_t)&reinterpret_cast<const volatile char&>((((s *)0)->m))

    工作原理大体同下图所示，其值就是 a – 0 = a ，即 m 被映射后的地址。所以一个 –> 操作就可以搞定。

    再看 BASE_OFFSET ：

#define BASE_OFFSET(ClassName, BaseName) \
    (DWORD(static_cast<BaseName*>(reinterpret_cast<ClassName*>(0x10000000))) - 0x10000000)

    对于先前的定义，有：

DWORD disX = BASE_OFFSET(CA, IX);
DWORD disY = BASE_OFFSET(CA, IY);
cout << disX << endl    // 0
       << disY << endl;   // 4

    这个宏主要利用了派生类指针到基类指针的转换，这一切由语言内置的转换符完成。在 ATL 中相应的定义是：

#define offsetofclass(base, derived) ((DWORD_PTR)(static_cast<base*>((derived*)_ATL_PACKING))-_ATL_PACKING)

    其中 _ATL_PACKING 的值为 8 。为什么使用这两个值呢，我不知道。网上有说是为了避免 NULL 指针和负值，我暂时不能够理解。

    最后来看 This() ：

CA* This() { return (CA*)((BYTE*)this - offsetof(CA, Inner)); }

    This() 返回的即是指向 CA 的指针，如： ca.m_inner.This()->fx(); 有了上面两个 offset ，这个就不难理解了。

    整理完毕。

      Introduces a synonym for some other type. Form:

      为某种类型引入同义词。格式：

      typedef type synonym;
     

      defines synonym as another name for the type named type.

      定义 synonym 为名为 type 的类型的另一名字。

      在看《核》一书的时候，我的了解就这么一点。为什么我看不懂呢？看看《核》中的用法：

const int g_nNumRows = 256;
const int g_nNumCols = 1024;

typedef struct {
    DWORD dwValue;
    BYTE  bDummy[1020];
} CELL, *PCELL;

typedef CELL SPREADSHEET[g_nNumRows][g_nNumCols];
typedef SPREADSHEET *PSPREADSHEET;

    按照当时的想法，句子 SPREADSHEET[g_nNumRows][g_nNumCols] sh 的意思应该是 CELL sh ，不就该是这样的吗（因为它只是个别名/马甲）？但在我那个想法里 sh 可不是数组，所以我当时无法理解 sh 后来的行为。形式主义，对，形式主义影响了我，当时我就一彻底的形式主义者。我还想再一遍地重复这个词，不过那也太给它面子了。算了， Not worth to fight!(哈，最近看的一部精彩的家庭喜剧中的台词。这部剧名叫《the middle》)。《核》一书中接下来还有一个精彩的用法，为了简化代码，我把它写成这个样子：

class Base {
public:
    virtual ~Base();
    void fn();
    ...
private:
    int n;
};

class Derive : public Base {
    ...
    //no data member allow, just function here.
};

static Derive g_ssObject;
SPREADSHEET& g_ss = *(PSPREADSHEET)(PCELL)g_ssObject;

    如此一来，g_ss 就有了 Base 的 n 成员和 256 * 1024 个 CELL 结构。当向 Derive 对象使用 [] 时（它是 SPREADSHEET& 型），它的行为就跟数组一致了（n 成员不会索引到，这也是不允许派生类有数据成员的原因）。关于它的内存并没有在它声明的时候开辟，以及后来怎么开辟，那就是另一个冒险故事了。这种手法让我再一次为《核》这本书所折服。

    好了，回到 typedef 。我见得最多的用法不外乎 typedef int value_type ，“取绰号”是他的职责所在，我不能只把它理解为：当你看到 B（ value_type ） 时，它只不过是 A （ int ），还要把它理解为像上面提到的一样：SPREADSHEET 并不只是一个 CELL ，而是多个 CELL 组成的 Array 的首个元素的位置指针，不然后面的两个跟屁虫双胞胎 “[][]” 作何解释。我的这种想法让我想起了 ATL 中的 OLECHAR ，在那里我也曾是个形式主义者（又重复了一遍！）。OLECHAR 在特定的平台上有特定的意义，比如在 windows 平台并定义了 UNICODE 的情况下，它是 wchar_t 。如果保持这种理解，将无法把它当做一种特别的类型，从而在语言层面上有了障碍，也就违背了 OLECHAR 生来是为 COM 组件做“特殊”服务的本意。我们要把它当做基本类型看待，至于怎么看待以及详细的方法，另一个冒险故事…… 所以，“取绰号”专家的内涵并不单薄，我不能一厢情愿的认为他只是个爱捉弄人的讨厌鬼，它正经起来可也是一表人才滴。下面是一些 typedef 的用法（来自《c++模板元编程》中某习题的解答）：

class foo {...};

typedef int (foo::*pmd);    // pmd 解释为：指向 foo 数据成员的指针，返回值为 int
typedef int (foo::*pmf)();  // pmf 解释为：指向 foo 函数成员的指针，返回值为 int
typedef int (*pfunc)();     // pfunc 解释为：指向函数的指针，返回值为 int 且无参数（有参数的也就不难想象了）
typedef const int& refc;    // 不说这个了

using namespace boost::assign;
std::vector<int> v1;
v1 += 1, 2, 30, 40, 500;

   话不多讲，按图索骥的来分析。既然是 vector 的操作，那就找出对应的头文件来看看。第一句使用了 boost::assign 命名空间，而 STL 库中当然不会提供这样的 operator+= ，果然在 boost\assign\std\vector.hpp 中有声明：

template< class V, class A, class V2 >
inline list_inserter< assign_detail::call_push_back< std::vector<V,A> >, V > 
operator+=( std::vector<V,A>& c, V2 v ) {
    return push_back( c )( v );
}

    For the god’s sake ，它一口气抛给我这么多待查的东西，这不是打击我的求知欲么！（歇息片刻……）继续。先不管这个重载操作符的返回值，待会在函数的返回语句中自然会了解到。看到 push_back( c )( v ) 这个句子，当然是一个 operator()，继续搜索。这一次，VS 代码查看工具直接把我带到了目的地—— boost\assign\list_inserter.hpp 这块新大陆。接下来的一切都将在这里发生。首先我到了 “push_back 站”：

template< class C >
inline list_inserter< assign_detail::call_push_back<C>, 
                      BOOST_DEDUCED_TYPENAME C::value_type >
push_back( C& c ) {
    static BOOST_DEDUCED_TYPENAME C::value_type* p = 0;//static typename std::vector<int>::value_type* p = 0;
    return make_list_inserter( assign_detail::call_push_back<C>( c ), p );
}

    为了方便查看，把 make_list_inserter 和 call_push_back 也列出来：

template< class Function, class Argument >
inline list_inserter<Function,Argument>
make_list_inserter( Function fun, Argument* ) {
    return list_inserter<Function, Argument>( fun );
}

template< class C >
class call_push_back {
    C& c_;  //这里，c_ 是 vector<int>& v1
public:
    call_push_back( C& c ) : c_( c ) { }
    
    template< class T >
    void operator()( T r ) {
        c_.push_back( r );
    }
};

    过了这条流水线，现在 operator+= 中的 push_back( c ) 就被加工成了：

    list_inserter<call_push_back, p>( call_push_back<vector<int> > ) ，其私有成员 insert_ 为 call_push_back<vector<int> > 。前面提到的 operator() 就要登场了，先看 list_inserter 的部分代码：

template< class Function, class Argument = assign_detail::forward_n_arguments > 
class list_inserter {
    ...  
public:
    list_inserter( Function fun ) : insert_( fun ) {}    
    ...

    list_inserter& operator()() {    //这就是那个 operator() ! 终于找到你了
        insert_( Argument() );
        return *this;
    }
    ...    
    template< class T >
    list_inserter& operator,( const T& r ) { //它化腐朽为神奇，逗号(,)从以前的“路标”升级成了“交警”

        insert_( r  );
        return *this;
    }

    ... ...

private:   
    list_inserter& operator=( const list_inserter& );
    Function insert_;  // call_push_back

};

    到这里，第一个 v1 += 1 就是下面这个样子：

    list_inserter<call_push_back, p>( call_push_back<vector<int> > )( 1 )

    相当于 call_push_back(1)，call_push_back的 c_ 成员就是 v1 的引用，就相当于 v1.push_back(1) 。第一个元素进入了容器，鼓掌。

    看过代码后，逗号（ , ）就不足为奇了， v1 += 1, 2, 30, 40, 500; 句子中的 “,”， 功能是依次插入逗号后的元素。

    继续探索新大陆……

mpl::and_<exp1, exp2>

    它使用的是头文件中的模板:

mpl::and_<exp1, exp2, true_, true_, true_>
           1_    2_     3_    4_      5_

    然后这个模板继承自：

aux::and_impl<
              BOOST_MPL_AUX_NESTED_TYPE_WKND(exp1)::value,
              exp2, 3_, 4_, 5_
             >

    若 1_ 的 value 为 false ，它就终结于下面的主模板：

template< bool C_, typename T1, typename T2, typename T3, typename T4 >
struct and_impl
    : false_ {};

    否则，继续前进：

aux::and_impl<
              BOOST_MPL_AUX_NESTED_TYPE_WKND(exp2)::value,
              3_, 4_, 5_, true_
             >

    这又回到了上一步的分叉路口。多个参数的情况与此类似。当全部参数都成 ture/true_ 时，就有了这个特化版本：

template<>
struct and_impl<
          true
        , true_, true_, true_, true_
        >
    : true_ {};

    这样一来，当前一个参数为 false 时，后面的参数就不用触及 ::value ，也就不会被实例化，这就是 short-circuit behavior，类似于 ||, && 等操作符。 

    同理可推知 or_ 的行为。

      if_ 就是借 if_c 定义了自己 ::type 的一个元函数。之所以我会对 if_ 迷糊，是因为我想当然的认为 if_ 模板的第一个参数类型为 bool 值。这是受了 if 关键字的影响，也有错误理解 if_c 的原因。且看 if_c 的声明：

template<
      bool C          // yeah, the type here is bool, but...
    , typename T1
    , typename T2
    >
struct if_c {
    typedef T1 type;
};

template<            // 特化版本，类似这样定义元函数的例子很多
      typename T1
    , typename T2
    >
struct if_c<false,T1,T2> {
    typedef T2 type;
};

  既生 if_c ，何生 if_ ？对比二者的代码，if_ 比 if_c 多了如下句子：BOOST_MPL_AUX_LAMBDA_SUPPORT(3,if_,(T1,T2,T3))。而在 MSVC（VS2008） 编译器上这个句子没起作用。那它就是为了兼容编译器而生的，就名字来看和 lambda 表达式的支持性有关系。关于其他编译器的事情，我不知道，先搁置一边。再看 if_ 的声明：

template<
      typename BOOST_MPL_AUX_NA_PARAM(T1)
    , typename BOOST_MPL_AUX_NA_PARAM(T2)
    , typename BOOST_MPL_AUX_NA_PARAM(T3)
    >
struct if_ {
 private:
    // agurt, 02/jan/03: two-step 'type' definition for the sake of aCC 
    typedef if_c<
#if defined(BOOST_MPL_CFG_BCC_INTEGRAL_CONSTANTS)
          BOOST_MPL_AUX_VALUE_WKND(T1)::value
#else
          BOOST_MPL_AUX_STATIC_CAST(bool, BOOST_MPL_AUX_VALUE_WKND(T1)::value)
#endif
        , T2
        , T3
        > almost_type_;
 
 public:
    typedef typename almost_type_::type type;
    BOOST_MPL_AUX_LAMBDA_SUPPORT(3,if_,(T1,T2,T3))
};

    这就很明了了，先用 if_c 确定应该使用 T2 还是 T3，再来个迂回的定义，就成了 ::type 。所以就声明来看，if_ 的第一个模板参数确实是要求类型。初看时，我郁闷了，如果我喜欢用 value （有些习惯连自己也感到奇怪！），那我为什么不用 if_c 呢？哈，当然可以，如书上的例子：

template <typename T>
struct param_type 
    : mpl::if_<
               typename boost::is_scalar<T>::type,
               T,
               typename boost::add_reference<T const>::type
    > {};
typedef param_type<float>::type float_;

    完全可以改为：

template <typename T>
struct param_type 
    : mpl::if_c<
                boost::is_scalar<T>::value,
                T,
                typename boost::add_reference<T const>::type
    > {};

     对于书上面的后几个简化，也照样适用。我就更郁闷了，我前几十分钟干嘛去了？死抓着 if_ 不放，不考虑试试其它可能。我想起了昨天对书上某个例子的扩充，确实受用（这当然不是说作者坏话，他是为了使书写得清晰明了才不使用在我看来是优化的东西的。呃，有点长…），我才再一次责怪起自己的读书习惯。古人云：尽信书不如无书。这句话用到这里就是：别死跟着书走（哪里跟哪里嘛，风马牛不相及，哈哈！）。

     关于 boost ，我不了解的太多，需要一步一步来，就从简单的开始吧。现在它可是远远超出了我的理解范围，希望能赶上一点是一点。

      1. CoCreateInstance 的调用过程(这里的组件位于 DLL 中)：

      图片说明了一切。对比一下 CoCreateInstance 的声明：

WINOLEAPI CoCreateInstance(__in        REFCLSID    rclsid,
__in_opt    LPUNKNOWN   pUnkOuter,
__in        DWORD       dwClsContext,
__in        REFIID      riid,
__deref_out LPVOID FAR* ppv);

    值得一提的是 CoGetClassObject 调用了 Dll 的导出函数 DllGetClassObject ，Regsvr32 /s /u 当然是使用了对应的 DllRegisterServer / DllUnregisterServer 导出函数。如果使用 ATL，这一切繁杂的工作都省却了，但反注册还需手动操作……

    2. 获取聚合组件接口的过程：

    理解组件聚合技术是一次痛苦的经历。前后三天，苦苦思索，我终于在那个阴冷的下午获得了“安东尼达斯”的垂青。如果他早一点给我一瓶智力药水，何至如此呢！看图说话：

      其中，两个InUnk都是非代理IUnknown。

      这样一来，对于外部组件来说：

      对于内部组件来说:

      所有的 QueryInterface 动作都直接或间接的由外部组件执行。

      这让我想起了《变形金刚2》。假如我一进电影院就睡着了，等到天火和擎天柱组合之后我才醒来。那么对于我来说，擎天柱就是外部组件，IX为跑。天火为内部组件，IY为飞。此时我不知道有天火的存在。当我问擎天柱你会飞吗的时候，他知道他不会飞（没有IY接口），于是他问天火你会不会飞，天火就返回IY（飞）接口，于是擎天柱告诉我他会飞。当他飞着的时候（我想通过IY来查询IX），我问他会跑么，这句话只有天火听得见（因为我用的是IY接口），天火不会跑，他就问擎天柱，擎天柱知道自己会跑（有IX接口），于是就给我一个IX接口。整个过程中，我只知道擎天柱，并不知道天火的存在，于是擎天柱聚合了天火。

      但我怎么可能进去就睡着了呢！

      内部组件的代理接口只是简单的调用外部的QueryInterface，是个转发站，一切工作交由外部组件统筹。关于具体实现，《COM本质论》中给出的 "impunk.h" 头文件中有很好的实现。我非常喜欢其中关于接口查找表的实现，那个offset获取偏移地址的方法让我这个C语言功力薄弱的人感到十分惭愧。

      过两天再把套间线程和自由线程整理出来。

template <bool x> struct STATIC_ASSERTION_FAILURE;

template <> struct STATIC_ASSERTION_FAILURE<true> { enum { value = 1 }; };

template<int x> struct static_assert_test{};

…

使用的是显示转换

// Note that the argument to the assert is explicitly cast to bool using old-
// style casts: too many compilers currently have problems with static_cast
// when used inside integral constant expressions.

…

#elif defined(BOOST_MSVC)
#define BOOST_STATIC_ASSERT( B ) \
   typedef ::boost::static_assert_test<\
      sizeof(::boost::STATIC_ASSERTION_FAILURE< (bool)( B ) >)>\ // ***********
         BOOST_JOIN(boost_static_assert_typedef_, __COUNTER__)

关键的地方在于 sizeof() 中的句子。当 (bool)( B ) 为 false 时，因为没有这个特化版本，编译器将报错，如

《Beyond the C++ Standard Library: An Introduction to Boost》中所述：

Error: use of undefined type
  'boost::STATIC_ASSERTION_FAILURE<false>'

BOOST_JOIN(X, Y) 最终解释为 X##Y。__COUNTER__ 在 MSDN 中的描述：

Expands to an integer starting with 0 and incrementing by 1 every time it is used in a compiland.

每使用一次它就增1。