Boost C++ 库

这可能是世界上最受推崇、设计最精良的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu，《C++ Coding Standards》

简单 C++11 元编程，第二部分 - Boost C++ 函数库

用于成员测试、随机访问和按键检索的高效算法

注意
 由于我算是元编程领域的后来者，因此我声明本文中的技术并非我首创。快速浏览一下 Louis Dionne 的 mpl11 和 Eric Niebler 的 meta 等实现，就会发现这些技巧大多已经为人所知。Dave Abrahams 在 2012 年 尝试过 类似的方法。多重继承技巧和 void* 参数技巧的原始发明者很可能是 Richard Smith，他在 一个 Clang 错误报告 的回复中发布了 两个 示例。

向量、集合和映射

在上篇文章中，我概述了一种对类型列表进行操作的元编程风格——可变参数类模板。

template<class... T> struct mp_list {};

经典的 Lisp 将列表作为其唯一的数据结构，但操作列表通常与其元素数量成线性关系。

除了 list，STL 还有 vector、set 和 map。vector 支持按索引进行随机访问；set 支持高效的成员测试；map 将键与值关联，并支持基于键的高效查找。

我们不引入 mp_vector、mp_set、mp_map 这样的独立数据结构，而是将数据保持为列表形式，并尝试提供高效的随机访问、成员测试和查找算法。

mp_contains

我们从集合开始。集合就是元素唯一的列表。为了从任意列表中获得一个集合，我们需要一个去除重复项的算法。我们称之为 mp_unique<L>。

// mp_if

template<bool C, class T, class E> struct mp_if_c_impl;

template<class T, class E> struct mp_if_c_impl<true, T, E>
{
    using type = T;
};

template<class T, class E> struct mp_if_c_impl<false, T, E>
{
    using type = E;
};

template<bool C, class T, class E>
    using mp_if_c = typename mp_if_c_impl<C, T, E>::type;

template<class C, class T, class E>
    using mp_if = typename mp_if_c_impl<C::value != 0, T, E>::type;

// mp_unique

template<class L> struct mp_unique_impl;

template<class L> using mp_unique = typename mp_unique_impl<L>::type;

template<template<class...> class L> struct mp_unique_impl<L<>>
{
    using type = L<>;
};

template<template<class...> class L, class T1, class... T>
    struct mp_unique_impl<L<T1, T...>>
{
    using _rest = mp_unique<L<T...>>;
    using type = mp_if<mp_contains<_rest, T1>, _rest, mp_push_front<_rest, T1>>;
};

对于成员测试，我们已经介绍了一个算法 mp_contains<L, V>，当 L 包含 V 时返回 true。mp_contains 的直接递归实现如下：

template<class L, class V> struct mp_contains_impl;

template<class L, class V> using mp_contains = typename mp_contains_impl<L, V>::type;

template<template<class...> class L, class V> struct mp_contains_impl<L<>, V>
{
    using type = std::false_type;
};

template<template<class...> class L, class... T, class V>
    struct mp_contains_impl<L<V, T...>, V>
{
    using type = std::true_type;
};

template<template<class...> class L, class T1, class... T, class V>
    struct mp_contains_impl<L<T1, T...>, V>: mp_contains_impl<L<T...>, V>
{
};

请注意，mp_unique<L> 会对 mp_contains 调用 N 次，其中 N 是列表 L 的长度。这意味着 mp_contains 需要尽可能快，而上面的实现，嗯，并不快。

以下是调用 mp_unique 处理包含 N 个（不同）元素的列表的编译时间（秒）：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，递归

2.1

DNF

clang++ 3.5.1，递归

0.9

4.5

13.2

30.2

DNF

g++ 4.9.2，递归

0.7

3.6

10.4

23.2

DNF

（测试在 Windows/Cygwin 下进行。所有编译器均为 32 位。无优化。DNF 表示“未完成”，通常意味着编译器耗尽了堆空间或崩溃了。）

显然我们需要更好的替代方案。

我在上一篇文章的结尾实现了一个依赖于 mp_count 的 mp_contains，而 mp_count 又依赖于 mp_plus。让我们看看它的表现如何：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，mp_count/mp_plus

1.1

9.8

50.5

DNF

clang++ 3.5.1，mp_count/mp_plus

0.5

1.4

3.1

6.1

DNF

g++ 4.9.2，mp_count/mp_plus

0.5

1.3

2.9

5.8

9.7

15.6

22.4

32.3

至少如果你的编译器碰巧是 g++，情况还不算太糟。尽管如此，这里仍然有改进的空间。

为了做得更好，我们必须以某种方式利用语言特性，例如包展开（pack expansion），让它们为我们做更多的工作。为了获得灵感，我们参考 C++11 标准第 14.5.3 段第 4 条，该条款解释了包展开可以在以下上下文中发生：

  • 在函数参数包（8.3.5）中；模式是省略号之前的参数声明。

  • 在模板参数包中，它是一个包展开（14.1）。

  • 在初始化列表（8.5）中；模式是初始化子句。

  • 在基类说明符列表（第 10 章）中；模式是基类说明符。

  • 在成员初始化列表（12.6.2）中；模式是成员初始化符。

  • 在模板参数列表（14.3）中；模式是模板参数。

  • 在动态异常说明（15.4）中；模式是类型标识。

  • 在属性列表（7.6.1）中；模式是属性。

  • 在对齐说明符（7.6.2）中；模式是省略号之前的对齐说明符。

  • 在捕获列表（5.1.2）中；模式是捕获。

  • 在 sizeof... 表达式（5.3.3）中；模式是标识符。

**加粗**是我添加的，用于指示可能的线索。

我们的第一个选择是将参数包展开为函数调用的参数。由于我们对在编译时发生的运算感兴趣，调用函数可能看起来没用；但 C++11 函数可以是 constexpr，而 constexpr 函数的“调用”确实发生在编译时。

回想一下我们的 mp_count：

template<class L, class V> struct mp_count_impl;

template<template<class...> class L, class... T, class V>
    struct mp_count_impl<L<T...>, V>
{
    using type = mp_plus<std::is_same<T, V>...>;
};

template<class L, class V> using mp_count = typename mp_count_impl<L, V>::type;

我们可以使用 constexpr 函数来代替模板别名 mp_plus 对 is_same 表达式进行求和：

constexpr std::size_t cx_plus()
{
    return 0;
}

template<class T1, class... T> constexpr std::size_t cx_plus(T1 t1, T... t)
{
    return t1 + cx_plus(t...);
}

// mp_size_t

template<std::size_t N> using mp_size_t = std::integral_constant<std::size_t, N>;

// mp_count

template<class L, class V> struct mp_count_impl;

template<template<class...> class L, class... T, class V>
    struct mp_count_impl<L<T...>, V>
{
    using type = mp_size_t<cx_plus(std::is_same<T, V>::value...)>;
};

template<class L, class V> using mp_count = typename mp_count_impl<L, V>::type;

结果如下：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

clang++ 3.5.1，mp_count/cx_plus

0.4

1.1

2.5

5.0

DNF

g++ 4.9.2，mp_count/cx_plus

0.4

0.9

1.7

2.9

4.7

6.7

9.2

11.8

我们改进了时间，但失去了 VC++ 2013，因为它没有实现 constexpr。

让我们尝试将包展开为初始化列表。与其将 is_same 表达式传递给函数，不如用它们构建一个常量数组，然后用 constexpr 函数对数组进行求和：

constexpr std::size_t cx_plus2(bool const * first, bool const * last)
{
    return first == last? 0: *first + cx_plus2(first + 1, last);
}

// mp_count

template<class L, class V> struct mp_count_impl;

template<template<class...> class L, class... T, class V>
    struct mp_count_impl<L<T...>, V>
{
    static constexpr bool _v[] = { std::is_same<T, V>::value... };
    using type = mp_size_t<cx_plus2(_v, _v + sizeof...(T))>;
};

template<class L, class V> using mp_count = typename mp_count_impl<L, V>::type;

这是一个巧妙的技巧，但它快吗？

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

clang++ 3.5.1，mp_count/cx_plus2

0.4

0.9

1.8

DNF

g++ 4.9.2，mp_count/cx_plus2

0.4

0.9

1.9

3.4

5.4

7.8

11.0

14.7

这有点令人失望。让我们看看如何通过将参数包展开到基类说明符列表（base-specifier-list）中来解决这个问题。我们可以定义一个派生自包中每个元素的类：

struct U: T... {};

然后我们可以使用 std::is_base_of<V, U> 来测试类型 V 是否是 U 的基类，即它是否是参数包中的一个元素。这正是我们所需要的。

void、int 或 void(int) 等任意类型不能用作基类，但我们可以将它们包装在一个空的类模板中，我们称之为 mp_identity。

template<class T> struct mp_identity
{
    using type = T;
};

template<class L, class V> struct mp_contains_impl;

template<class L, class V> using mp_contains = typename mp_contains_impl<L, V>::type;

template<template<class...> class L, class... T, class V>
    struct mp_contains_impl<L<T...>, V>
{
    struct U: mp_identity<T>... {};
    using type = std::is_base_of<mp_identity<V>, U>;
};

性能如何？

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，is_base_of

0.3

0.6

1.3

2.5

DNF

clang++ 3.5.1，is_base_of

0.3

0.4

0.6

0.8

DNF

g++ 4.9.2，is_base_of

0.3

0.4

0.6

0.9

1.3

1.7

2.3

3.0

这个实现明显是赢家。

公平地说，我们应该注意到，前四种 mp_contains 的实现不依赖于列表元素的唯一性。这使得 mp_contains 成为一个支持任意列表的算法，而不仅仅是集合。

然而，is_base_of 实现不支持包含重复项的列表，因为不能直接从同一类型继承两次。因此，它没有实现通用的 mp_contains，而是实现了一个可能应该命名为 mp_set_contains 的东西。

我们可以通过修改实现，使其通过中间基类间接继承自 mp_identity<T> 来避免“不允许重复”的要求：

// indirect_inherit

template<std::size_t I, class T> struct inherit_second: T {};

template<class L, class S> struct indirect_inherit_impl;

template<template<class...> class L, class... T, std::size_t... J>
    struct indirect_inherit_impl<L<T...>, integer_sequence<std::size_t, J...>>:
        inherit_second<J, mp_identity<T>>... {};

template<class L> using indirect_inherit =
    indirect_inherit_impl<L, make_index_sequence<mp_size<L>::value>>;

// mp_contains

template<class L, class V> struct mp_contains_impl
{
    using U = indirect_inherit<L>;
    using type = std::is_base_of<mp_identity<V>, U>;
};

template<class L, class V> using mp_contains = typename mp_contains_impl<L, V>::type;

然而，这几乎抵消了我们通过原始 is_base_of 实现观察到的惊人的性能提升：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，递归

2.1

DNF

VC++ 2013，mp_count/mp_plus

1.1

9.8

50.5

DNF

VC++ 2013，is_base_of

0.3

0.6

1.3

2.5

DNF

VC++ 2013，is_base_of/indirect

1.0

9.3

49.5

153.8

DNF
N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

clang++ 3.5.1，递归

0.9

4.5

13.2

30.2

DNF

clang++ 3.5.1，mp_count/mp_plus

0.5

1.4

3.1

6.1

DNF

clang++ 3.5.1，mp_count/cx_plus

0.4

1.1

2.5

5.0

DNF

clang++ 3.5.1，mp_count/cx_plus2

0.4

0.9

1.8

DNF

clang++ 3.5.1，is_base_of

0.3

0.4

0.6

0.8

DNF

clang++ 3.5.1，is_base_of/indirect

0.4

0.9

1.6

2.5

DNF
N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

g++ 4.9.2，递归

0.7

3.6

10.4

23.2

DNF

g++ 4.9.2，mp_count/mp_plus

0.5

1.3

2.9

5.8

9.7

15.6

22.4

32.3

g++ 4.9.2，mp_count/cx_plus

0.4

0.9

1.7

2.9

4.7

6.7

9.2

11.8

g++ 4.9.2，mp_count/cx_plus2

0.4

0.9

1.9

3.4

5.4

7.8

11.0

14.7

g++ 4.9.2，is_base_of

0.3

0.4

0.6

0.9

1.3

1.7

2.3

3.0

g++ 4.9.2，is_base_of/indirect

0.5

1.1

2.3

4.0

6.6

9.8

13.6

18.2

mp_map_find

在 STL 的意义上，映射（map）是一种将键与值关联起来的数据结构，并且可以高效地根据键检索其关联值。对我们而言，映射将是任何列表的列表，其中内部列表至少有一个元素（键）；其余元素将被视为关联值。例如，列表：

[[A, B], [C, D, E], [F], [G, H]]

是一个映射，其键为 A、C、F 和 G，关联值为 [B]、[D, E]、[] 和 [H]。出于稍后会显而易见的原因，我们将要求键是唯一的。

我将展示另外两个映射的例子，这次使用真实的 C++ 代码：

using Map = mp_list<mp_list<int, int*>, mp_list<void, void*>, mp_list<char, char*>>;
using Map2 = std::tuple<std::pair<int, int[2]>, std::pair<char, char[2]>>;

执行基于键的检索的算法的 Lisp 名称是 ASSOC，但我将其称为 mp_map_find。mp_map_find<M, K> 返回 M 中第一个元素为 K 的元素。例如，mp_map_find<Map2, int> 将返回 std::pair<int, int[2]>。如果不存在这样的键，则返回 void。

几乎没有必要实现和基准测试 mp_map_find 的递归版本——我们可以相当肯定它将表现糟糕。尽管如此：

template<class M, class K> struct mp_map_find_impl;

template<class M, class K> using mp_map_find = typename mp_map_find_impl<M, K>::type;

template<template<class...> class M, class K> struct mp_map_find_impl<M<>, K>
{
    using type = void;
};

template<template<class...> class M, class T1, class... T, class K>
    struct mp_map_find_impl<M<T1, T...>, K>
{
    using type = mp_if<std::is_same<mp_front<T1>, K>, T1, mp_map_find<M<T...>, K>>;
};

N 次查找一个大小为 N 的映射的编译时间（秒）如下：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，递归

38.2

DNF

clang++ 3.5.1，递归

2.5

13.7

DNF

g++ 4.9.2，递归

1.9

10.2

28.8

DNF

我告诉过你没有意义。

但是，我听到有人说，即使条件为真，你也在评估 else 分支，这效率非常低下！

嗯，这最多只会将性能提高大约两倍，而且仅当元素存在时才有效，但好吧，我们试试。基准测试中元素恰好存在，所以我们来看看。

// mp_eval_if

template<bool C, class T, template<class...> class E, class... A>
    struct mp_eval_if_c_impl;

template<class T, template<class...> class E, class... A>
    struct mp_eval_if_c_impl<true, T, E, A...>
{
    using type = T;
};

template<class T, template<class...> class E, class... A>
    struct mp_eval_if_c_impl<false, T, E, A...>
{
    using type = E<A...>;
};

template<bool C, class T, template<class...> class E, class... A>
    using mp_eval_if_c = typename mp_eval_if_c_impl<C, T, E, A...>::type;

template<class C, class T, template<class...> class E, class... A>
    using mp_eval_if = typename mp_eval_if_c_impl<C::value != 0, T, E, A...>::type;

// mp_map_find

template<class M, class K> struct mp_map_find_impl;

template<class M, class K> using mp_map_find = typename mp_map_find_impl<M, K>::type;

template<template<class...> class M, class K> struct mp_map_find_impl<M<>, K>
{
    using type = void;
};

template<template<class...> class M, class T1, class... T, class K>
    struct mp_map_find_impl<M<T1, T...>, K>
{
    using type = mp_eval_if<std::is_same<mp_front<T1>, K>, T1, mp_map_find, M<T...>, K>;
};

看吧：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，递归

15.6

DNF

clang++ 3.5.1，递归

1.8

9.5

DNF

g++ 4.9.2，递归

1.4

7.0

19.7

DNF

我告诉过你没有意义。

不论如何，确定递归实现效率低下与提出一个高效的实现是两回事。有两点使得 mp_contains 的技术不适用于我们当前的情况：首先，mp_contains 只需返回 true 或 false，而 mp_map_find 返回一个类型；其次，在 mp_contains 中我们知道我们正在查找的元素的精确类型，而在本例中，我们只知道它的 mp_front。

幸运的是，确实存在一个语言特性可以解决这两个问题：C++ 可以通过派生类来推导基类的模板参数。在此示例中：

struct K1 {};
struct V1 {};

struct X: std::pair<K1, V1> {};

template<class A, class B> void f(std::pair<A, B> const & p);

int main()
{
    f(X());
}

调用 f(X()) 会将 A 推导为 K1，将 B 推导为 V1。如果我们有多个 std::pair 基类，我们可以将 A 固定为 K1：

struct K1 {};
struct V1 {};

struct K2 {};
struct V2 {};

struct X: std::pair<K1, V1>, std::pair<K2, V2> {};

template<class B> void f(std::pair<K1, B> const & p);

int main()
{
    f(X());
}

而 B 将被推导为 V1。

我们可以通过返回所需的类型来检索推导结果：

template<class B> std::pair<K1, B> f(std::pair<K1, B> const & p);

然后使用 decltype(f(X())) 获取此返回类型。

如果 X 没有类型为 std::pair<K1, B> 的基类怎么办？推导将失败，我们将得到一个错误，表明 f(X()) 无法被调用。为了避免这种情况，我们可以添加一个接受任何内容并返回 void 的 f 的重载。但在这种情况下，如果 X 有两个形式与第一个 f 重载匹配的基类，例如 std::pair<K1, Y> 和 std::pair<K1, Z>，会发生什么？

推导将失败，将再次选择第二个重载，我们得到 void。这就是为什么我们要求映射具有唯一键的原因。

下面是基于此技术实现的 mp_map_find：

template<class M, class K> struct mp_map_find_impl;

template<class M, class K>
    using mp_map_find = typename mp_map_find_impl<M, K>::type;

template<template<class...> class M, class... T, class K>
    struct mp_map_find_impl<M<T...>, K>
{
    struct U: mp_identity<T>... {};

    template<template<class...> class L, class... U>
        static mp_identity<L<K, U...>>
        f( mp_identity<L<K, U...>>* );

    static mp_identity<void> f( ... );

    using V = decltype( f((U*)0) );

    using type = typename V::type;
};

及其相应的编译时间：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，推导

0.3

0.7

1.8

3.6

6.4

10.4

16.2

DNF

clang++ 3.5.1，推导

0.3

0.4

0.6

0.9

1.2

1.6

2.2

2.7

g++ 4.9.2，推导

0.3

0.5

0.9

1.6

2.3

3.4

4.7

6.3

这看起来可以发布了。

然而，该实现包含一个效率低下之处。如果我们先求值 mp_map_find<M, K1>，然后求值 mp_map_find<M, K2>，那么两个嵌套的 U 类型是相同的，因为它们仅依赖于 M，但编译器不知道这一点，并且会单独实例化每个类型。我们应该将此类型移到 mp_map_find_impl 之外，以便它能够被重用：

template<class... T> struct mp_inherit: T... {};

template<class M, class K> struct mp_map_find_impl;

template<class M, class K>
    using mp_map_find = typename mp_map_find_impl<M, K>::type;

template<template<class...> class M, class... T, class K>
    struct mp_map_find_impl<M<T...>, K>
{
    using U = mp_inherit<mp_identity<T>...>;

    template<template<class...> class L, class... U>
        static mp_identity<L<K, U...>>
        f( mp_identity<L<K, U...>>* );

    static mp_identity<void> f( ... );

    using V = decltype( f((U*)0) );

    using type = typename V::type;
};

（顺便说一句，这个优化也适用于我们基于 is_base_of 的 mp_contains 实现。）

在我们的基准测试上，编译时间的改进是可衡量的：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，deduction+mp_inherit

0.3

0.6

1.4

2.6

4.5

7.1

10.7

DNF

clang++ 3.5.1，deduction+mp_inherit

0.3

0.4

0.6

0.8

1.0

1.4

1.8

2.2

g++ 4.9.2，deduction+mp_inherit

0.3

0.4

0.6

0.9

1.3

1.8

2.3

2.9

mp_at

在涵盖了集合和映射之后，是时候处理向量了。对我们来说，向量就是列表，我们需要为其添加根据索引高效访问元素的能力。此访问器的惯用名称是 mp_at<L, I>，其中 L 是列表，I 是表示索引的 integral_constant。我们还将遵循 Boost.MPL 的约定，添加 mp_at_c<L, I>，其中 I 的类型为 size_t。

mp_at 的递归实现如下：

template<class L, std::size_t I> struct mp_at_c_impl;

template<class L, std::size_t I> using mp_at_c = typename mp_at_c_impl<L, I>::type;

template<class L, class I> using mp_at = typename mp_at_c_impl<L, I::value>::type;

template<template<class...> class L, class T1, class... T>
    struct mp_at_c_impl<L<T1, T...>, 0>
{
    using type = T1;
};

template<template<class...> class L, class T1, class... T, std::size_t I>
    struct mp_at_c_impl<L<T1, T...>, I>
{
    using type = mp_at_c<L<T...>, I-1>;
};

以下是调用 mp_at N 次（第一个参数为大小为 N 的列表）的编译时间：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，递归

3.6

DNF

clang++ 3.5.1，递归

1.0

5.1

15.3

DNF

g++ 4.9.2，递归

0.9

4.7

14.2

32.4

DNF

为了改进这个糟糕的结果，我们将再次利用包展开到函数调用中，但以一种新颖的方式。假设我们需要访问第四个元素（I = 3）。我们将生成函数签名：

template<class W> W f( void*, void*, void*, W*, ... );

然后，给定一个列表 L<T1, T2, T3, T4, T5, T6, T7>，我们将求值表达式：

decltype( f( (T1*)0, (T2*)0, (T3*)0, (T4*)0, (T5*)0, (T6*)0, (T7*)0 ) )

三个 void* 参数将处理前三个元素，W 将被推导为第四个元素，省略号将处理其余部分。

下面显示了一个基于此技术的有效实现：

// mp_repeat_c

template<std::size_t N, class... T> struct mp_repeat_c_impl
{
    using _l1 = typename mp_repeat_c_impl<N/2, T...>::type;
    using _l2 = typename mp_repeat_c_impl<N%2, T...>::type;

    using type = mp_append<_l1, _l1, _l2>;
};

template<class... T> struct mp_repeat_c_impl<0, T...>
{
    using type = mp_list<>;
};

template<class... T> struct mp_repeat_c_impl<1, T...>
{
    using type = mp_list<T...>;
};

template<std::size_t N, class... T> using mp_repeat_c =
    typename mp_repeat_c_impl<N, T...>::type;

// mp_at

template<class L, class L2> struct mp_at_c_impl;

template<template<class...> class L, class... T,
    template<class...> class L2, class... U>
    struct mp_at_c_impl<L<T...>, L2<U...>>
{
    template<class W> static W f( U*..., W*, ... );

    using R = decltype( f( (mp_identity<T>*)0 ... ) );

    using type = typename R::type;
};

template<class L, std::size_t I> using mp_at_c =
    typename mp_at_c_impl<L, mp_repeat_c<I, void>>::type;

template<class L, class I> using mp_at = mp_at_c<L, I::value>;

下表中的编译时间表明它足以满足大多数实际需求。

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，void*

0.4

1.1

2.4

4.7

DNF

clang++ 3.5.1，void*

0.4

0.7

1.2

1.9

2.7

3.8

5.0

6.6

g++ 4.9.2，void*

0.3

0.5

0.9

1.3

2.1

3.0

4.2

5.5

那么，mp_at 就算完成了吗？

让我们尝试另一种方法——将输入列表 [T1, T2, T3] 转换为映射 [[0, T1], [1, T2], [2, T3]]，然后使用 mp_map_find 进行查找：

// mp_map_from_list

template<class L, class S> struct mp_map_from_list_impl;

template<template<class...> class L, class... T, std::size_t... J>
    struct mp_map_from_list_impl<L<T...>, integer_sequence<std::size_t, J...>>
{
    using type = mp_list<mp_list<mp_size_t<J>, T>...>;
};

template<class L> using mp_map_from_list = typename mp_map_from_list_impl<L,
    make_index_sequence<mp_size<L>::value>>::type;

// mp_at

template<class L, std::size_t I> struct mp_at_c_impl
{
    using map = mp_map_from_list<L>;
    using type = mp_second<mp_map_find<map, mp_size_t<I>>>;
};

template<class L, std::size_t I> using mp_at_c = typename mp_at_c_impl<L, I>::type;

template<class L, class I> using mp_at = typename mp_at_c_impl<L, I::value>::type;

乍一看，这看起来很荒谬，但元编程有其自身的规则。我们来测量一下：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，map

0.3

0.7

1.5

2.9

5.0

7.8

11.9

DNF

clang++ 3.5.1，map

0.3

0.4

0.6

0.8

1.1

1.5

1.8

2.3

g++ 4.9.2，map

0.3

0.4

0.7

1.0

1.4

1.9

2.5

3.2

令人惊讶的是，这是最好的实现。

mp_drop

事实证明，我们并不需要 void* 技巧来处理 mp_at，但我将展示一个需要它的例子：mp_drop。mp_drop<L, N> 返回列表 L 去掉前 N 个元素；换句话说，它丢弃前 N 个元素（可能被扔进废纸篓），然后返回剩下的部分。

为了实现 mp_drop，我们只需要将上面的

template<class W> W f( void*, void*, void*, W*, ... );

修改为返回剩余的元素，而不是仅仅一个：

template<class... W> mp_list<W> f( void*, void*, void*, W*... );

添加必要的 mp_identity 调味剂，得到以下有效实现：

template<class L, class L2> struct mp_drop_c_impl;

template<template<class...> class L, class... T,
    template<class...> class L2, class... U>
    struct mp_drop_c_impl<L<T...>, L2<U...>>
{
    template<class... W> static mp_identity<L<W...>> f( U*..., mp_identity<W>*... );

    using R = decltype( f( (mp_identity<T>*)0 ... ) );

    using type = typename R::type;
};

template<class L, std::size_t N> using mp_drop_c =
    typename mp_drop_c_impl<L, mp_repeat_c<N, void>>::type;

template<class L, class N> using mp_drop = mp_drop_c<L, N::value>;

我将省略此处的递归实现和性能比较。我们可以 pretty much 知道谁将获胜，以及胜出多少。

mp_find_index

我将引起您注意的最后一个算法是 mp_find_index。mp_find_index<L, V> 返回一个类型为 size_t 的整数常量，其值为 V 在 L 中首次出现的索引。如果 V 不在 L 中，则返回值是 L 的大小。

一如既往，我们先从递归实现开始：

template<class L, class V> struct mp_find_index_impl;

template<class L, class V> using mp_find_index = typename mp_find_index_impl<L, V>::type;

template<template<class...> class L, class V> struct mp_find_index_impl<L<>, V>
{
    using type = mp_size_t<0>;
};

template<template<class...> class L, class... T, class V>
    struct mp_find_index_impl<L<V, T...>, V>
{
    using type = mp_size_t<0>;
};

template<template<class...> class L, class T1, class... T, class V>
    struct mp_find_index_impl<L<T1, T...>, V>
{
    using type = mp_size_t<1 + mp_find_index<L<T...>, V>::value>;
};

并且，一如既往，我们将继续进行调用 mp_find_index N 次（列表大小为 N）的编译时间：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，递归

3.5

DNF

clang++ 3.5.1，递归

1.1

5.5

DNF

g++ 4.9.2，递归

0.8

4.6

13.6

DNF

这里我们能做什么？

让我们回到 mp_contains，看看“mp_count/cx_plus2”实现，我们之前为了继承而否决了它。它构建了一个 constexpr 布尔数组，并在 constexpr 函数中对其求和。我们可以在这里做同样的事情，除了我们不对数组求和，而是找到第一个 true 值的索引：

template<class L, class V> struct mp_find_index_impl;

template<class L, class V> using mp_find_index = typename mp_find_index_impl<L, V>::type;

template<template<class...> class L, class V> struct mp_find_index_impl<L<>, V>
{
    using type = mp_size_t<0>;
};

constexpr std::size_t cx_find_index( bool const * first, bool const * last )
{
    return first == last || *first? 0: 1 + cx_find_index( first + 1, last );
}

template<template<class...> class L, class... T, class V>
    struct mp_find_index_impl<L<T...>, V>
{
    static constexpr bool _v[] = { std::is_same<T, V>::value... };

    using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
};

此版本的性能如下：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

clang++ 3.5.1，constexpr

0.5

1.3

2.9

DNF

g++ 4.9.2，constexpr

0.5

1.4

3.1

5.5

8.7

13.0

18.0

DNF

虽然不理想，但比我们被动挨打的递归版本要好得多。但是，如果我们的首选编译器是 VC++ 2013，我们就不能使用 constexpr。

我们可以尝试一个类似方向的实现，但是将 constexpr 函数替换为普通的元编程：

template<class L, class V> struct mp_find_index_impl;

template<class L, class V> using mp_find_index = typename mp_find_index_impl<L, V>::type;

template<template<class...> class L, class V> struct mp_find_index_impl<L<>, V>
{
    using type = mp_size_t<0>;
};

template<bool...> struct find_index_impl_;

template<> struct find_index_impl_<>
{
    static const std::size_t value = 0;
};

template<bool B1, bool... R> struct find_index_impl_<B1, R...>
{
    static const std::size_t value = B1? 0: 1 + find_index_impl_<R...>::value;
};

template<bool B1, bool B2, bool B3, bool B4, bool B5,
    bool B6, bool B7, bool B8, bool B9, bool B10, bool... R>
    struct find_index_impl_<B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, R...>
{
    static const std::size_t value = B1? 0: B2? 1: B3? 2: B4? 3: B5? 4:
        B6? 5: B7? 6: B8? 7: B9? 8: B10? 9: 10 + find_index_impl_<R...>::value;
};

template<template<class...> class L, class... T, class V>
    struct mp_find_index_impl<L<T...>, V>
{
    using type = mp_size_t<find_index_impl_<std::is_same<T, V>::value...>::value>;
};

这仍然是递归的，所以我们不期望奇迹，但测量一下也无妨：

N=100 N=200 N=300 N=400 N=500 N=600 N=700 N=800

VC++ 2013，bool…​

4.7

94.5

488.3

XFA

clang++ 3.5.1，bool…​

0.6

2.2

5.8

12.0

21.7

35.2

DNF

g++ 4.9.2，bool…​

0.6

2.4

6.5

13.2

23.8

39.1

59.0

DNF

（其中 XFA 表示“实验者睡着了”。）

这对于 VC++ 2013 和 Clang 来说是一个有趣的权衡。一方面，这个实现更慢；另一方面，它不容易导致编译器崩溃。选择哪一个取决于个人喜好以及对操作长度为 300 的类型列表需求的严肃评估。

请注意，一旦有了 mp_drop 和 mp_find_index，我们就可以通过使用 mp_drop<L, mp_find_index<L, V>> 来推导出 mp_find<L, V> 算法。该算法返回从 V 的第一个出现开始的 L 的后缀（如果存在），否则返回一个空列表。

结论

在本文中，我展示了允许我们将类型列表视为集合、映射和向量的高效算法，并在此过程中展示了各种 C++11 的实现技术。