STL101 C 部分 - Functors

Christian Graus

3.52/5 (16投票s)

2002 年 2 月 25 日

6分钟阅读

190249

这第三篇文章介绍了如何编写函数适配器，以实现对 STL 函数的自定义。

引言

希望你现在已经熟悉我的写作格式了——我将再次提供你可以直接复制粘贴到空控制台应用程序中的代码，而不是使用 zip 文件。我们稍后再见……

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>

using std::binary_function;
using std::unary_function;
using std::accumulate;
using std::cout;
using std::string;
using std::vector;
using std::for_each;
using std::ostream_iterator;
using std::copy;
using std::endl;
using std::sort;
using std::mem_fun_ref;

struct Member
{
   string Surname;
   string Name;
   int    VideosOut;
   int DaysOverdue;

   Member::Member(string surname, string name, int videosOut = 0, 
      int daysOverdue = 0) : Surname(surname),
      Name(name), VideosOut(videosOut), DaysOverdue(daysOverdue) {};

   int Print()
   {
      cout << "Name: " << Surname <<", " << Name;

      if (VideosOut > 0) cout << "  Videos Out = " << VideosOut;

      if (DaysOverdue > 0) cout << "  Days overdue = " << DaysOverdue;

      cout << endl;

      return 0;
   }
};

void PrintItem(const Member & m)
{
   cout << "Name: " << m.Surname <<", " << m.Name;

   if (m.VideosOut > 0) cout << "  Videos Out = " << m.VideosOut;

   if (m.DaysOverdue > 0) cout << "  Days overdue = " << m.DaysOverdue;

   cout << endl; 
}

struct CountOverdueDays : public unary_function<int, int>
{
   CountOverdueDays(int nDayLimit) : m_nDayLimit(nDayLimit) { }
   int operator()(int nOverdueSoFar, const Member& m)  
   {  
      return m.DaysOverdue >= m_nDayLimit ? 
                   nOverdueSoFar + m.VideosOut : nOverdueSoFar;
   }
private:  
   const int m_nDayLimit;
};

struct SortByVideosOut : public binary_function<Member, Member, bool>
{
   bool operator() (const Member & m1, const Member & m2)
   {
      return (m1.VideosOut < m2.VideosOut);
   }
};

bool SortMember(const Member m1, const Member m2)
{
   if (m1.Surname < m2.Surname)
      return true;
   else if (m1.Surname > m2.Surname)
      return false;

   return (m1.Name < m2.Name);
}

struct CountIntSort : public binary_function<int, int, bool>
{
public:
   static int nCount;

   bool operator() (const int n1, const int n2)
   {
      ++ nCount;
      return (n1 < n2);
   }
};

int CountIntSort::nCount = 0;

struct CountIntSort2 : public binary_function<int, int, bool>
{
public:
   int nCount;

   CountIntSort2() : nCount(0){};

   bool operator() (const int n1, const int n2)
   {
      ++ nCount;
      return (n1 < n2);
   }
};

struct CountIntSort3 : public binary_function<int, int, bool>
{
public:
   int nCount;
   CountIntSort3 * pParent;
   int nCopies;

   CountIntSort3() : nCount(0), nCopies(0), pParent(0) {};

   CountIntSort3(CountIntSort3 & c) : nCount(0), nCopies(1)
   {
      pParent = &c;
   }

   ~CountIntSort3()
   {
      pParent->nCount += nCount;
      pParent->nCopies += nCopies;
   }

   bool operator() (const int n1, const int n2)
   {
      ++ nCount;
      return (n1 < n2);
   }
};

int _tmain(int argc, _TCHAR* argv[])
{
   vector<Member> vecMem;

   vecMem.push_back(Member("Zaphir", "Jill"));
   vecMem.push_back(Member("Smith", "John", 5, 0));
   vecMem.push_back(Member("Smith", "Phil", 1, 3));
   vecMem.push_back(Member("Jones", "Susan"));
   vecMem.push_back(Member("Kaputnik", "Joe", 10, 5));
   vecMem.push_back(Member("Jones", "Bill", 3, 7));

   for_each(vecMem.begin(), vecMem.end(), PrintItem);

   cout << endl;

   sort(vecMem.begin(), vecMem.end(), SortMember);

   cout << "Now the same list sorted\n\n";

   for_each(vecMem.begin(), vecMem.end(), mem_fun_ref(&Member::Print));

   cout << endl;

   int nOverdue = accumulate(vecMem.begin(), vecMem.end(),
      0 /* initval = identity of addition */, 
      CountOverdueDays(5));

   cout << "Number of videos overdue by five or more days: " << nOverdue;

   cout << "\n\nSorted by number of videos out:\n\n";

   SortByVideosOut v;

   sort (vecMem.begin(), vecMem.end(), v);

   for_each(vecMem.begin(), vecMem.end(), mem_fun_ref(&Member::Print));

   cout << endl;

   vector<int> vecInt;
   
   for (int i = 0; i < 10000; ++i)
      vecInt.push_back(rand()% 10000);

   CountIntSort::nCount = 0;

   CountIntSort c;

   // Use a copy so it always requires the same number of iterations

   vector<int> vecInt2 = vecInt; 

       sort(vecInt2.begin(), vecInt2.end(), c);

   cout << "Sorting a vector of 10000 ints took " 
        << CountIntSort::nCount << " calls to the sort function" 
        << endl;

   CountIntSort2 c2;

   vecInt2 = vecInt;

   sort(vecInt2.begin(), vecInt2.end(), c2);

   cout << "Sorting a vector of 10000 ints second try took " 
        << c2.nCount << " calls to the sort function" << endl;

   CountIntSort3 c3;

   vecInt2 = vecInt;

   sort(vecInt2.begin(), vecInt2.end(), c3);

   cout << "Sorting a vector of 10000 ints second try took " 
       << c3.nCount 
       << " calls to the sort function, and the predicate was copied " 
       << c3.nCopies << " times." << endl;

   string s;
   std::cin >> s;

   return 0;
}

这第三部分涉及一个虚构的影像库程序，其中保存客户数据的一部分 struct 可能是这样的：

struct Member
{
    string Surname;
    string Name;
    int    VideosOut;
    int DaysOverdue;

    Member::Member(string surname, string name, int videosOut = 0, 
              daysOverdue = 0) : Surname(surname),
              Name(name), VideosOut(videosOut), DaysOverdue(daysOverdue) {};
}

创建了这个 struct 之后，我们可以像这样构建一个虚构客户的 vector：

    vector<Member> vecMem;

    vecMem.push_back(Member("Zaphir", "Jill"));
    vecMem.push_back(Member("Smith", "John", 5, 0));
    vecMem.push_back(Member("Smith", "Phil", 1, 3));
    vecMem.push_back(Member("Jones", "Susan"));
    vecMem.push_back(Member("Kaputnik", "Joe", 10, 5));
    vecMem.push_back(Member("Jones", "Bill", 3, 7));

通常，如果我在控制台上创建这样一个 struct，我会为它创建一个流插入/提取对，这样我就可以直接对每个项调用 cout，但我并不想展示如何做到这一点。相反，我将创建自己的函数，并用 for_each 来调用它。这个函数通常比手写的循环更受欢迎，原因有很多，这些都在 Scott Meyers 的《Effective STL》一书中有详细介绍。如果你对我的文章有足够的兴趣并已经读到了第三篇，那么你需要这本书。现在就去 Fatbrain 或 Amazon 订购吧。别担心，我会等你……

你回来了吗？很好。现在，它的工作原理是这样的。像 for_each 这样的函数需要一个一元函数，也就是一个只接受一个参数的函数。所以我们像这样编写一个打印函数：

void PrintItem(const Member & m)
{
    cout << "Name: " << m.Surname <<", " << m.Name;

    if (m.VideosOut > 0) cout << "  Videos Out = " << m.VideosOut;

    if (m.DaysOverdue > 0) cout << "  Days overdue = " << m.DaysOverdue;

    cout << endl; 
}

然后在 main 函数中像这样调用它：

for_each(vecMem.begin(), vecMem.end(), PrintItem);

很简单，对吧？像 sort 这样的比较函数需要一个二元函数——它需要两个对象来进行比较。让我们编写一个按姓名排序的函数——对于一个结构体，需要这样的函数来告诉我们按什么排序。此外，在这种情况下，我们将按姓氏排序，并在相同姓氏的组内按名字排序。

bool SortMember(const Member & m1, const Member & m2)
{
    if (m1.Surname < m2.Surname)
        return true;
    else if (m1.Surname > m2.Surname)
        return false;

    return (m1.Name < m2.Name);
}

然后，只需要使用这个函数进行排序，如下所示：

    sort(vecMem.begin(), vecMem.end(), SortMember);

当然，所有这些全局函数都会变得有些杂乱，更不用说它们根本不是面向对象的，因此我们提供了一些适配器来帮助我们，即 mem_fun 和 mem_fun_ref。这两者都允许我们传入一个作为容器中存储的类的成员函数。mem_fun 假设我们存储的是对象的指针，而 mem_fun_ref 则假设我们按值存储它们。因此，如果我们将以下代码添加到我们的 Member struct 中：

    int Print()
    {
        cout << "Name: " << Surname <<", " << Name;  

        if (VideosOut > 0) cout << "  Videos Out = " << VideosOut;

        if (DaysOverdue > 0) cout << "  Days overdue = " << DaysOverdue;

        cout << endl;

        return 0;
    }

那么我们就可以这样做：

for_each(vecMem.begin(), vecMem.end(), mem_fun_ref(&Member::Print));

我们还有 mem_fun1 和 mem_fun1_ref，它们允许我们指定接受一个参数的函数。遗憾的是，没有 mem_fun2_ref，这意味着我们不能将谓词放入类中（谓词是一个接受两个参数并返回 bool 的函数）。

然而，我们可以超越这些全局函数，通过创建一个重载了 () 操作符的 struct 或类来实现。这样的函数在 STL 领域被称为仿函数（functor），而其中 operator() 返回 bool 的仿函数则被称为谓词（predicate）。

在讨论其效果之前，让我首先感谢 Jörgen Sigvardsson，他是众多指出我原始文章中关于这部分缺陷的第一人。他也是接下来 CoutOverdueDays 函数的作者。

经过几次错误的尝试，我想我已经弄清了仿函数带有状态的问题。Meyers 解释说，如果 operator() 修改了仿函数的状态，我们就会遇到问题，因为我们无法确切知道它将被调用多少次。然而，我们可以在仿函数中引入状态，这也是使用它的一个好理由。Chris Losinger 在这里的文章中提供了一个很好的例子。Jörgen 的 CountOverdueDays 仿函数如下所示：

struct CountOverdueDays
{
   CountOverdueDays(int nDayLimit) : m_nDayLimit(nDayLimit) { }

   int operator()(int nOverdueSoFar, const Member& m)    
   { 
       return m.DaysOverdue >= 
                m_nDayLimit ? nOverdueSoFar + m.VideosOut : nOverdueSoFar;
   }
private: 
   const int m_nDayLimit;
};

在 Jörgen 的帮助下，以下改进后的代码演示了如何统计有多少视频逾期五天或更长时间：

int nOverdue = accumulate(vecMem.begin(), vecMem.end(),
   0 /* initval = identity of addition */, 
   CountOverdueDays(5));

cout << "Number of videos overdue by five or more days: " << nOverdue;

为了让你能轻松看出这是正确的，我提供了另一种排序方式，即按借出视频的数量排序。

struct SortByVideosOut : public 
     binary_function<MEMBER bool Member Member Member,> 
{
    bool operator() (const Member & m1, const Member & m2)
    {
        return (m1.VideosOut < m2.VideosOut);
    }
};

无论如何，现在我们可以通过执行以下操作，按借出视频的数量输出列表：

SortByVideosOut v;

sort (vecMem.begin(), vecMem.end(), v);

for_each(vecMem.begin(), vecMem.end(), mem_fun_ref(&Member::Print));

使用仿函数而不是全局函数的一个好理由是，一旦它们作为参数传入，就不会有函数调用的开销。另一个理由，正如 Jörgen 也指出的，是它允许你使用像 binder1st 和 unary_negate 这样的函数适配器，只要你让它们派生自 unary_function 或 binary_function。这两个类可以在头文件 <functional> 中找到。

讲到这里，我决定做一个练习，添加代码来计算一个常用函数（即 sort）调用 operator() 的次数。以下代码创建了一个二元谓词，它执行正常的排序，但同时使用一个静态变量来计算操作符被调用的频率。

struct CountIntSort : public 
     binary_function<int, int, bool><int int bool int int,,>
{
public:
   static int nCount;

   bool operator() (const int n1, const int n2)
   {
      ++ nCount;
      return (n1 < n2);
   }
};

int CountIntSort::nCount = 0;

以及在 main() 中：

vector<int> vecInt;

for (int i = 0; i < 10000; ++i)
   vecInt.push_back(rand()% 10000);

CountIntSort::nCount = 0;

CountIntSort c;

// Use a copy so it always requires the same number of iterations

vector<int> vecInt2 = vecInt; 

sort(vecInt2.begin(), vecInt2.end(), c);

cout << "Sorting a vector of 10000 ints took " 
     << CountIntSort::nCount << " calls to the sort function" << endl;

在我的机器上，排序 10,000 个 int 需要调用 operator () 205,832 次。不过那个静态变量有点难看，所以我们用一个类级别的成员变量来替换它。

struct CountIntSort2 : public binary_function<int, int, bool>
{
public:
   int nCount;

   CountIntSort2() : nCount(0){};

   bool operator() (const int n1, const int n2)
   {
      ++ nCount;
      return (n1 < n2);
   }
};

创建同一个 vector 的另一个副本并调用它，返回的迭代次数为 0。这和我在写原始文章时遇到的问题一样，是 Joaquín M López Muñoz 在下面的讨论中提供了解决方案。

谓词是按值传递的，而不是按引用传递。因此，计数器在 STL 内部正常运转，但你传入的谓词实例却不受影响。Joaquín 在下面题为“我明白了”（I got it）的消息中，以及在“我还是不明白为什么谓词应该是无状态的”（I still don't get why predicates should be stateless）的讨论串中给出了完整的解释。简单来说，这种方法行不通。那么我们如何摆脱静态变量呢？我们需要重载我们的拷贝构造函数和析构函数，以便为每个副本维护一个计数，并将其传回，直到它返回到我们最初的谓词。顺便，我们再来计算一下在拷贝操作期间谓词被复制了多少次。

struct CountIntSort3 : public binary_function<int, int, bool>
{
public:
   int nCount;
   CountIntSort3 * pParent;
   int nCopies;

   CountIntSort3() : nCount(0), nCopies(0), pParent(0) {};

   CountIntSort3(CountIntSort3 & c) : nCount(0), nCopies(1)
   {
      pParent = &c;
   }

   ~CountIntSort3()
   {
      pParent->nCount += nCount;
      pParent->nCopies += nCopies;
   }

   bool operator() (const int n1, const int n2)
   {
      ++ nCount;
      return (n1 < n2);
   }
};

使用这段代码，我们再次得到 205,832 次对 operator () 的调用，并且谓词在操作期间被复制了 3,315 次。

正如之前评论我第一篇文章的其他人所指出的，Boost 库为 STL 提供了很多扩展，但我没有使用它们，仅仅是因为让公司的每个人都安装 STLPort 就已经够费劲了，而且我认为学习那些让我不太可能知道在各种情况下都能使用的变通方法的东西没什么意义。当我写一篇关于 VC6 STL 中没有但很有用的东西的文章时，我会安装 Boost，尽管那篇文章主要会涵盖 STLPort 中的内容。我再次提到这一点，是因为如果可以的话，我真的很想把这些谓词函数添加到类本身中。

如你所见，STL 不仅内置了许多强大的函数（未来的文章将讨论具体有多少，现在我只是在每篇文章中介绍几个），for_each 还为我们提供了一种编写自己函数的简单方法，而提供我们自己的代码作为策略的通用机制意味着我们可以根据自己的需求来调整通用算法。接下来，我将写一篇关于关联容器的文章，即 map 和 set。我发现，set 是 map 的一个子集，如果你想保持数据排序，或者想在向 vector 插入的高成本和搜索 list 的高成本之间寻求一个折中方案，这两者都是非常有用的替代方案。