使用模板元编程实现的编译时数据结构

• 下载源代码 - 1.8 KB

1. 引言

我们已经看到了模板元编程的各种应用，例如静态数据结构[5]、算法[2][6]、设计模式[1][3]、反射[4]、表达式模板[7]和数论[8][9]。实际上，编译时数据结构在 C++ 中并不是一个新概念。更多信息可以在参考文献[1][5]中找到。在这里，我们将以链表为例研究编译时数据结构，并尝试使用模板元编程来实现它。

模板元编程起初通常很难理解，特别是对于不熟悉它的人。因此，我们将同时讨论其运行时对应部分。我们为所有运行时程序使用“List”的命名约定，以区别于编译时版本。虽然我们可以用不止一种方式实现运行时程序，但在编译时世界中，我们只能通过递归来完成所有事情，包括循环；因此，在运行时版本中，我们也打算使用递归。

2. 编译时链表

如果我们想创建一个单链表，那么我们的链表结构将是这样的

///////////////////////////////////////////////////////////
// Node of Runtime Link List
///////////////////////////////////////////////////////////
struct ListNode
{
    int value;
    ListNode* next;
};

这是该结构的编译时版本

///////////////////////////////////////////////////////////
// Termination of Link List
///////////////////////////////////////////////////////////
struct End
{
};

///////////////////////////////////////////////////////////
// Node of Static Link List
///////////////////////////////////////////////////////////
template <int iData, typename Type>
struct Node
{
    enum { value = iData };
    typedef Type Next;
};

在这里，我们需要另一个结构来指示链表的终止条件。你也可以称它为结束标记。在运行时版本中，我们不需要它，因为在这种情况下，我们只需检查节点中 next 字段的值。如果其值为 NULL，则表示它是链表的最后一个节点。

然而，在模板元编程的情况下，我们必须进行模板特化（或部分模板特化）来停止递归。我们可以对任何特定类型或任何特定值进行模板特化。在这里，我们不能对值进行模板特化，因为第二个模板参数是类型。因此，我们必须创建一个新类型来停止模板的递归实例化。结束标记的名称可以是任何名称，并且它可以存储任何你想要的东西。在我们的例子中，创建一个空结构来创建新类型作为结束标记就足够了。

现在，让我们尝试实现一些操作链表的小辅助函数。这是我们第一个插入数据到链表的函数。我们明确地使其名称与 STL list 类的成员函数相似，因为我们将实现更多 STL 算法。

这是在运行时单链表中插入项目的最简单实现。

///////////////////////////////////////////////////////////
// Insert item into Runtime Link List
///////////////////////////////////////////////////////////
void ListPushBack(ListNode** pHead, int value)
{
    if (*pHead == NULL)
    {
        *pHead = new ListNode();
        (*pHead)->value = value;
    }
    else
    {
        ListPushBack(&(*pHead)->next, value);
    }
}

链表的名称前缀为“List”，以区别于编译时版本。

有趣的是，同一函数的编译时版本不使用递归，并且实现非常简单。

///////////////////////////////////////////////////////////
// Insert item into Static Link List
///////////////////////////////////////////////////////////
template <int iData, typename Type>
struct PushBack
{
    typedef Node<iData, Type> staticList;
};

这是此函数在编译时的用法

typedef PushBack<2, End>::staticList node1;
typedef PushBack<4, node1>::staticList node2;
typedef PushBack<6, node2>::staticList node3;
typedef PushBack<8, node3>::staticList node4;
typedef PushBack<10, node4>::staticList node5;
typedef PushBack<12, node5>::staticList myList;

虽然我们可以像这样创建一个静态链表

typedef Node<-15, Node<15, Node<18, Node<13, End> > > > myList;

上面创建静态链表的方法有一些优点，当我们实现一些编译时版本的 STL 算法时，我们会看到这些优点。

现在，让我们在编译时实现更多 STL 列表算法。但首先，看看它的运行时版本，以便更好地理解模板元编程。

///////////////////////////////////////////////////////////
// Structure to calculate the length of Runtime Link List
///////////////////////////////////////////////////////////
int ListSize(ListNode* pHead)
{
    if (pHead == NULL)
        return 0;
    else
        return 1 + ListSize(pHead->next);
}

这个函数非常简单，并使用尾递归进行优化。编译器可以通过循环优化尾递归，以避免任何运行时堆栈开销。这是同一函数的编译时版本

///////////////////////////////////////////////////////////
// Structure to calculate the length of Static Link List
///////////////////////////////////////////////////////////
template <typename T>
struct Size;

template <int iData, typename Type>
struct Size<Node<iData, Type> >
{
    enum { value = 1 + Size<Type>::value };
};

template <>
struct Size<End>
{
    enum { value = 0 };
};

虽然 STL list 类没有 at() 函数，因为 list 没有随机访问迭代器，但我们正在尝试为链表实现此函数。因为我们无法随机访问链表的任何项，所以它是一个线性时间函数，而不是像 vector 的 at() 函数那样是常数时间函数。

这是在单链表上具有线性复杂度的 at() 函数的简单运行时实现

///////////////////////////////////////////////////////////
// Structure to find item from specific location from Runtime Link List
///////////////////////////////////////////////////////////
int ListAt(ListNode* pHead, int iPos)
{
    static int iIndex = 0;
    ++iIndex;

    if (iIndex == iPos)
        return pHead->value;
    else if (pHead->next == NULL)
        return -1;
    else
        return ListAt(pHead->next, iPos);
}

此处提供的代码仅是概念验证，而非生产质量代码。此函数的一个主要问题是返回码。如果输入位置大于链表长度，例如链表长度为 4，但我们试图访问第 6 个元素，则此函数返回 -1。此代码具有误导性，因为 -1 可以是给定位置链表中的数据，因此无法区分它是错误代码还是给定位置的实际数据。

这个实现比前一个要好得多

///////////////////////////////////////////////////////////
// Structure to find item from specific location from Runtime Link List
///////////////////////////////////////////////////////////
bool ListAt(ListNode* pHead, int iPos, int* iVal)
{
    static int iIndex = 0;
    ++iIndex;

    if (iIndex == iPos)
    {
        *iVal = pHead->value;
        return true;
    }
    else if (pHead->next == NULL)
    {
        return false;
    }
    else
    {
        return ListAt(pHead->next, iPos, iVal);
    }
}

此函数通过参数返回特定位置的值。如果用户传递的位置大于链表长度，它将返回 false；否则，它会将值存储在参数中并返回 true。

这是此函数的使用方法

if (pHead != NULL)
{
    int val;
    
    if (ListAt(pHead, 3, ∓val))
    {
        std::cout << val << std::endl;
    }
}

这是同一函数的编译时版本

///////////////////////////////////////////////////////////
// Structure to find item from specific location from Static Link List
///////////////////////////////////////////////////////////
template <int iIndex, typename T, int iStart = 0>
struct At;

template <int iIndex, int iData, typename Type, int iStart>
struct At<iIndex, Node<iData, Type>, iStart>
{
    enum { value = iIndex == iStart ? 
           iData : At<iIndex, Type, (iStart + 1)>::value };
};

template <int iIndex, int iData, int iStart>
struct At<iIndex, Node<iData, End>, iStart>
{
    enum { value = iIndex == iStart ? iData : -1 };
};

此程序存在相同的问题，即在找不到项目时返回 -1。在模板元编程中，我们不能像其运行时等效项那样通过参数返回一个值。解决方案是在结构中引入一个额外的 enum 变量来存储项目是否找到。这是同一程序的下一个版本

///////////////////////////////////////////////////////////
// Structure to find item from specific location from Static Link List
///////////////////////////////////////////////////////////
template <int iIndex, typename T, int iStart = 0>
struct At;

template <int iIndex, int iData, typename Type, int iStart>
struct At<iIndex, Node<iData, Type>, iStart>
{
    enum { value = iIndex == iStart ? 
           iData : At<iIndex, Type, (iStart + 1)>::value };
    enum { found = iIndex == iStart ? 1 : 
           At<iIndex, Type, (iStart + 1)>::found };
};

template <int iIndex, int iData, int iStart>
struct At<iIndex, Node<iData, End>, iStart>
{
    enum { value = iIndex == iStart ? iData : -1 };
    enum { found = iIndex == iStart ? 1 : 0 };
};

虽然当在链表中找不到项目时，value 变量仍然存储 -1，但如果我们使用另一个变量，即“found”变量，那么我们可以忽略这个值。这是此算法的使用方法

if (At<8, myList>::found == 1)
{
    std::cout << At<8, myList>::value << std::endl;
}

3. 编译时算法

在本节中，我们将研究不同的 STL 算法及其与 STL list 类的配合使用，以及如何使用模板元编程在编译时实现它们。从现在开始，我们不再创建自己的单链表并自己实现所有相关函数，而是使用 STL list 类。

3.1. Find 算法

Find 算法在给定范围内返回指定值的第一次出现。如果找不到指定的值，则返回 end 迭代器，即给定范围中最后一个元素的下一个位置。这是在 STL list 上使用 Find 算法的一个简单示例

std::list<int> lst;

lst.push_back(7);
lst.push_back(14);
lst.push_back(21);
lst.push_back(28);
lst.push_back(35);

std::list<int>::iterator iter_ = std::find(lst.begin(), lst.end(), 7);

if (iter_ != lst.end())
    std::cout << *iter_ << std::endl;
else
    std::cout << "Not found" << std::endl;

这是在模板元编程中最接近的 Find 算法实现

///////////////////////////////////////////////////////////
// Structure to find the location of specific item in Static Link List
///////////////////////////////////////////////////////////
template <typename TBegin, 
            typename TEnd, 
            int iFindData, 
            int iStart = 0>
struct Find;

template <int iData, 
            typename TBegin, 
            typename TEnd, 
            int iFindData, 
            int iStart>
struct Find<Node<iData, TBegin>, TEnd, iFindData, iStart>
{
    enum { value = iFindData == iData ? iStart : 
        Find<TBegin, TEnd, iFindData, (iStart + 1)>::value };
};

template <int iData, 
            typename TEnd, 
            int iFindData, 
            int iStart>
struct Find<Node<iData, TEnd>, TEnd, iFindData, iStart>
{
    enum { value = iFindData == iData ? iStart : -1 };
};

template <typename TEnd, int iFindData>
struct Find<TEnd, TEnd, iFindData>
{
    enum { value = -1 };
};

此实现返回指定值在单链表给定范围内的位置，如果找到；否则，返回 -1。这是上述实现的使用方法

typedef PushBack<7, End>::staticList node1;
typedef PushBack<14, node1>::staticList node2;
typedef PushBack<21, node2>::staticList node3;
typedef PushBack<28, node3>::staticList node4;
typedef PushBack<35, node4>::staticList myList;

std::cout << Find<myList, End, 7>::value << std::endl;

我们甚至可以像 STL 算法一样传递范围，以在给定范围之间查找元素。

std::cout << Find<node3, node1, 7>::value << std::endl;

这是使用静态 PushBack 实现而不是一次性创建整个静态链表的原因之一。通过使用 PushBack 实现的编译时版本，我们能够在编译时世界中获得等效的迭代器。

3.2. Count 算法

此算法返回给定范围内具有给定值的项目数。这是一个演示该算法的示例

std::list<int> lst;

lst.push_back(7);
lst.push_back(14);
lst.push_back(7);
lst.push_back(14);
lst.push_back(21);
lst.push_back(7);

std::cout << std::count(lst.begin(), lst.end(), 7) << std::endl;

此程序的输出是 3，因为在给定范围内 7 出现了三次。这是一个在编译时实现的类似算法

///////////////////////////////////////////////////////////
// Count Algorithm. Returns the number of elements in Static Link List
///////////////////////////////////////////////////////////
template <typename TBegin, 
            typename TEnd, 
            int iVal>
struct Count;

template <int iData, 
            typename TBegin, 
            typename TEnd, 
            int iVal>
struct Count<Node<iData, TBegin>, TEnd, iVal>
{
    enum { value = (iData == iVal ? 1 : 0) + 
        Count<TBegin, TEnd, iVal>::value };
};

template <int iData, typename TEnd, int iVal>
struct Count<Node<iData, TEnd>, TEnd, iVal>
{
    enum { value = iData == iVal ? 1 : 0 };
};

template <typename TEnd, int iVal>
struct Count<TEnd, TEnd, iVal>
{
    enum { value = 0 };
};

此实现与“Find”算法非常相似，其用法也与之相似。这是我们在此部分看到的，使用 STL“count”算法的代码的编译时版本的最接近实现。

typedef PushBack<7, End>::staticList node1;
typedef PushBack<14, node1>::staticList node2;
typedef PushBack<7, node2>::staticList node3;
typedef PushBack<14, node3>::staticList node4;
typedef PushBack<21, node4>::staticList node5;
typedef PushBack<7, node5>::staticList myList;

std::cout << Count<myList, End, 7>::value << std::endl;

与“Find”算法一样，我们也可以在给定范围内计算指定项目的数量，而不是搜索整个静态链表。

3.3. Find If 算法

如果我们想查找链表是否包含大于 10 但小于 20 的项，那么我们无法使用 Find 算法做到这一点。这是此问题的解决方案，Find If 算法。此算法返回链表中满足给定谓词中条件的元素的迭代器。谓词可以是简单函数，也可以是函数对象（即具有重载的 () 运算符的类），它返回 true。在该函数（或函数对象）中，我们可以检查任何我们想要的条件。在研究编译时版本之前，让我们先看看它的运行时版本，以便更好地理解它。

std::list<int> lst;

lst.push_back(7);
lst.push_back(14);
lst.push_back(7);
lst.push_back(14);
lst.push_back(21);
lst.push_back(7);

std::list<int>::iterator iter_ =  
   std::find_if(lst.begin(), lst.end(), MyPredicate());

if (iter_ != lst.end())
    std::cout << *iter_ << std::endl;
else
    std::cout << "Not found" << std::endl;

在这里，我们将 MyPridicate 作为一个函数对象传递，这是它的实现

struct MyPredicate
{
    bool operator()(int val)
    {
        return val > 10 && val < 20 ? true : false;
    }
};

实现 Find If 算法的编译时版本并不难，它看起来与 Find 算法非常相似，只是增加了一个谓词类型参数。这是 Find If 算法的编译时版本

///////////////////////////////////////////////////////////
// Find If Algorithm. 
// Locate the specific items in Static Link List that satisfy the predicate
///////////////////////////////////////////////////////////
template <typename TBegin, 
            typename TEnd, 
            template <int iData> class Predicate, 
            int iStart = 0>
struct FindIf;

template <int iData, 
            typename TBegin, 
            typename TEnd, 
            template <int iData> class Predicate, 
            int iStart>
struct FindIf<Node<iData, TBegin>, TEnd, Predicate, iStart>
{
    enum { value = Predicate<iData>::value == 1 ? iStart : 
        FindIf<TBegin, TEnd, Predicate, (iStart+1)>::value };
};

template <int iData, 
            typename TEnd,
            template <int iData> class Predicate, 
            int iStart>
struct FindIf<Node<iData, TEnd>, TEnd, Predicate, iStart>
{
    enum { value = Predicate<iData>::value == 1 ? iStart : -1 };
};

template <typename TEnd, 
    template <int iData> class Predicate>
struct FindIf<TEnd, TEnd, Predicate>
{
    enum { value = -1 };
};

在这里，我们使用模板模板参数来使其易于调用并与 STL 算法相似。这是此算法的使用方法。

typedef PushBack<7, End>::staticList node1;
typedef PushBack<14, node1>::staticList node2;
typedef PushBack<7, node2>::staticList node3;
typedef PushBack<14, node3>::staticList node4;
typedef PushBack<21, node4>::staticList node5;
typedef PushBack<7, node5>::staticList myList;

std::cout << FindIf<myList, End, MyPredicate>::value << std::endl;

在编译时世界中，谓词是结构（或类），而不是函数或函数对象。这是我们之前在本节中为运行时版本使用的相同谓词的编译时版本

template <int val>
struct MyPredicate
{
    enum { value = val > 10 && val < 20 ? 1 : 0 };
};

3.4. Count If 算法

“Count if”算法是“Find If”的近亲；唯一的区别是，它将返回链表中满足谓词中给定条件的元素的数量。让我们先看看该算法的运行时版本。

std::list<int> lst;

lst.push_back(7);
lst.push_back(14);
lst.push_back(7);
lst.push_back(14);
lst.push_back(21);
lst.push_back(7);

std::cout << std::count_if(lst.begin(), lst.end(), MyPredicate()) << std::endl;

而且，我们使用与前面相同的谓词

struct MyPredicate
{
    bool operator()(int val)
    {
        return val > 10 && val < 20 ? true : false;
    }
};

此程序的输出是 2，因为列表中有两个元素大于 10 且小于 20。现在，让我们看看同一算法的编译时版本。

///////////////////////////////////////////////////////////
// Count If Algorithm. 
// Returns the number of elements in Static Link List
// that satisfy the predicate condition
///////////////////////////////////////////////////////////
template <typename TBegin, typename TEnd, 
    template <int iData> class Predicate>
struct CountIf;

template <int iData, typename TBegin, typename TEnd, 
    template <int iData> class Predicate>
struct CountIf<Node<iData, TBegin>, TEnd, Predicate>
{
    enum { value = (Predicate<iData>::value) + 
                    CountIf<TBegin, TEnd, Predicate>::value };
};

template <int iData, typename TEnd, 
    template <int iData> class Predicate>
struct CountIf<Node<iData, TEnd>, TEnd, Predicate>
{
    enum { value = Predicate<iData>::value };
};

template <typename TEnd, 
    template <int iData> class Prediate>
struct CountIf<TEnd, TEnd, Prediate>
{
    enum { value = 0 };
};

此实现与“Find If”算法非常相似。唯一的区别是，在这里，我们实际上是在计算满足谓词中给定条件的元素的数量，而不是找到它。这是此算法的使用方法

typedef PushBack<7, End>::staticList node1;
typedef PushBack<14, node1>::staticList node2;
typedef PushBack<7, node2>::staticList node3;
typedef PushBack<14, node3>::staticList node4;
typedef PushBack<21, node4>::staticList node5;
typedef PushBack<7, node5>::staticList myList;

std::cout << CountIf<myList, End, MyPredicate>::value << std::endl;

3.5. Min, Max 算法

虽然 STL 版本的 min 和 max 算法不适用于范围，但为了保持一致性，我们以类似的方式实现了这两个算法，即，您可以查找给定范围内静态链表中的最大值或最小值。这是这两个算法的简单实现

///////////////////////////////////////////////////////////
// Structure to find the Maximum value in the Link List
///////////////////////////////////////////////////////////
template <typename TBegin, typename TEnd>
struct Max;

template <int iData, typename TBegin, typename TEnd>
struct Max<Node<iData, TBegin>, TEnd >
{
    enum { value = iData > Max<TBegin, TEnd>::value ? 
                   iData : Max<TBegin, TEnd>::value };
};

template <int iData, typename TEnd>
struct Max<Node<iData, TEnd>, TEnd>
{
    enum { value = iData };
};
///////////////////////////////////////////////////////////
// Structure to find the Minimum value in the Link List
///////////////////////////////////////////////////////////
template <typename TBegin, typename TEnd>
struct Min;

template <int iData, typename TBegin, typename TEnd>
struct Min<Node<iData, TBegin>, TEnd>
{
    enum { value = iData < Min<TBegin, TEnd>::value ? 
                   iData : Min<TBegin, TEnd>::value };
};

template <int iData, typename TEnd>
struct Min<Node<iData, TEnd>, TEnd>
{
    enum { value = iData };
};

而且，这里是这些算法的一个简单用法

std::cout << Max<myList, End>::value << std::endl;
std::cout << Min<myList, End>::value << std::endl;

如果我们使用我们在上一节中创建的相同的静态链表，那么我们将获得 21 和 7 作为静态链表中的最大值和最小值。就像其他算法一样，在这里，我们也可以指定范围来获取给定范围内的最大值或最小值，而不是整个静态链表。

3.6. For Each 算法

到目前为止，我们讨论过的所有算法都只是从链表中获取信息。上述任何算法都没有更改链表中的任何值。这是因为一旦拥有了某个值，就很难，如果不是不可能，更改我们在编译时分配的值。现在，我们将讨论一个对链表值执行某些操作的算法，但在这里，我们明确限制自己不更改链表中的任何值。让我们看看“For Each”算法的一个简单示例，用于打印链表元素

std::for_each(lst.begin(), lst.end(),PrintFunctionObject());

在这里，“PrintFunctionObject”是我们执行实际工作的函数对象。这是此谓词的一个简单实现

struct PrintFunctionObject
{
    void operator()(int val)
    {
        std::cout << val << std::endl;
    }
};

请记住，它也可以是简单函数而不是函数对象。这是同一算法的编译时等效版本

///////////////////////////////////////////////////////////
// For each algorithm. Apply some action on all items of the list
///////////////////////////////////////////////////////////
template <typename TBegin, typename TEnd, 
    template <typename T> class Function>
struct ForEach;

template <int iData, typename TBegin, typename TEnd, 
    template <typename T> class Function>
struct ForEach<Node<iData, TBegin>, TEnd, Function>
{
    void operator ()()
    {
        Function<TBegin>()(iData);
        ForEach<TBegin, TEnd, Function>()();
    }
};

template <int iData, typename TEnd, 
    template <typename T> class Function>
struct ForEach<Node<iData, TEnd>, TEnd, Function>
{
    void operator ()()
    {
        Function<TEnd>()(iData);
    }
};

template <typename TEnd, 
    template <typename T> class Function>
struct ForEach<TEnd, TEnd, Function>
{
    void operator ()()
    {
    }
};

如果您仔细查看此实现，您可能已经注意到此实现与我们之前讨论过的所有实现都有很大的不同。在此实现中，没有任何“enum”变量；相反，我们在这里重载了 () 运算符。这是因为当我们必须执行某些操作时，我们必须调用某个函数来执行实际工作。此程序实际上是运行时和编译时编程的混合。我们之前讨论过的所有程序都在编译时通过编译器完全解析，并将实际结果存储在可执行文件中。

然而，在这种情况下，尽管我们在编译过程中使用递归进行编译时计算，但实际的函数调用仍然会在程序运行时执行。这是在进行模板元编程的同时执行 IO 操作的唯一方法，即使用将在运行时执行的函数。在这里，我们不仅限于执行 IO 操作，还可以做一些更有趣的事情，比如使用 new 运算符创建一个类，或者创建一组类层次结构，如“Modern C++ Design”[1]中所述。这是“For Each”算法编译时实现的函数对象。

template <typename T>
struct PrintFunctonObject
{
    void operator ()(int iData)
    {
        std::cout << iData << std::endl;
    }
};

此算法的使用方法也略有不同。在这里，我们实际上希望在运行时执行一些代码；因此，我们必须创建一个“ForEach”结构的实例。这里有一种使用匿名对象执行此算法的可能方法

ForEach<myList, End, PrintFunctonObject>()();

4. 未来工作

在这里，我们讨论了如何实现链表及其一些相关算法。这项工作可以扩展到使用其他数据结构，并包含更多算法。我们可以进一步扩展这项工作的另一个维度是函数式编程方法，我们在这里几乎没有触及它，甚至没有提及它的名字。我们只讨论了一种在实现“For Each”算法时混合编译时和运行时执行的方法。这种技术可以用来实现一些更强大和有趣的概念。

5. 参考资料

1. Modern C++ Design Generic Programming, Andrei Alexandrescu
2. C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Byond, David Abrahams, Aleksey Gurtovoy, Addison Wesley, 2004
3. Making Patterns Explicit with Meta-programming, Daniel von Dincklage, Proceedings of the second international conference on Generative programming and component engineering (2003)
4. Reflection support by means of template Meta-programming, Guiseppe Attardi, Antonio Cisternino
5. Static Data Structure: Reconciling Template Meta-programming and Generic Programming, Michael C. Burton, William G. Griswold, Andrew D. McCulloch, Gray A. Huber
6. Loops, Metaloops & C++, Roshan Naik, August 2004 Dr Dobb Journal
7. Expression Templates, Veldhuizen, C++ Report 1995, Generative Programming – Methods, Tools and Applications
8. Template Meta Programming and Number Theory, Zeeshan Amjad
• CodeProject
• CodeGuru
9. Template Meta Programming and Number Theory: Part 2, Zeeshan Amjad
• CodeProject
• CodeGuru