更轻松地使用 STL 算法处理成对关联容器（map、hash_map 等）

• 下载源代码文件 - 2.09 Kb

引言

公认的 C++ 专家 Scott Meyers 曾建议避免使用循环，而是鼓励使用 STL 算法来替代，尤其是在使用 STL 容器时¹。通常情况下，这会使循环的意图更清晰，但有时将算法与某些函数对象和容器结合使用，可能会导致语句冗长且晦涩，嵌套的函数对象和模板会使语句难以阅读。

使用专门的函数适配器可以使代码显著更清晰，而不会牺牲算法的通用性。本文介绍了两个专门的函数适配器，它们可与 STL 中定义的成对关联容器一起使用。这些适配器比完全通用的算法语句有所改进，并保留了算法相对于手动编写循环的优势。

本文假设您已掌握 C++ 基础知识，并对函数对象、STL 算法和 STL 容器的使用有所经验。除非另有说明，所有类型都假定在 std 命名空间中。

STL 算法的魔力

STL 提供了所谓的算法，本质上是专门化的循环，允许使用迭代器遍历通用容器。这些专门的循环每个都根据其对容器中各个元素的操作进行命名，例如，for_each 仅调用一个函数，transform 将函数的结果输出到另一个集合，而 accumulate 将所有结果相加。容器类型，如 vector 或 list，提供迭代器来访问各个元素，而算法则对元素执行特定的操作。

每个算法至少接受一个函数参数。此函数必须定义为接受一个参数，即被遍历容器中包含的元素类型。

// highly simplified example of STL container/iterator/
// algorithm relationship
template <typename Element>
class container {
    typedef iterator<element /> iterator;
    iterator begin();
    iterator end();
    ...
};

// emulates pointer syntax
template <typename Element>
class iterator {
   typedef Element value_type;
   typedef Element* pointer;
   typedef Element& reference;

   value_type operator*()();
   reference operator*()();
   pointer operator->()();
   ...
};

template <typename Iter, typename Func>
void algorithm( Iter begin, Iter end, Func func )
{
  ...
  // every algorithm has a similar function call inside.
  func( *begin ); 
  ...
}

算法会解引用迭代器，该迭代器返回容器中元素的返回类型。这将找到接受容器中使用的元素类型的引用或值的函数重载。

这并非真正的魔法，只是库设计者所遵循的一种约定，它允许许多不同的容器和算法几乎无缝地互操作。

函数适配器

传递给算法的函数只能接受一个参数。如果您需要将更多信息传递给函数，或者要执行的操作是调用集合中对象的某个方法，该怎么办？您可以编写一个包装函数。假设您想在 vector 的 int 元素中每个都加上 2。

vector<int> my_vec;

void add2( int& number )
{
   number += 2;
}

void some_func( vector<int>& vec )
{
    for_each( vec.begin(), vec.end(), add2 );
}

现在，如果您想在向量的每个整数上加 3 怎么办？又一个包装器。即使您有一个 addn 函数引用的变量，它仍然只能用于整数。对于 doubles 加上 0.5 怎么办？又一个包装器，但又是一个变量，等等。您可能已经猜到会发生什么了。

函数适配器是函数对象，它们从语法上讲就像普通函数调用一样，但在语义上与某些其他语言结构相同，例如方法调用 (mem_fun) 或表达式 (plus)。例如，通过使用 mem_fun 函数适配器，可以轻松地在容器的每个元素上调用成员函数，如下所示：

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

class MyType {
    static int instance_count;
    int instance_id;
public:
    MyType(void) { instance_id = instance_count++; }
    void do_something(void) 
    { 
         cout <<
             "Doing something on instance " 
             << instance_id << endl;
    }
};

int MyType::instance_count = 0;

list<MyType*> my_list;

int main(void)
{
    for( int i = 0; i < 10; ++i ) 
        my_list.push_back( new MyType());

    for_each( my_list.begin(), my_list.end(), 
        mem_fun( &MyType::do_something ));

    return 0;
}

有函数适配器可以完成几乎任何任务，例如使用两个参数调用函数 (bind2nd)，以及进行函数组合 f(g()) (compose1)。

成对关联容器

成对关联容器，如 map 和 hash_map，是包含键和数据的容器。可以使用任意类型的键来引用容器内的数据。由于它们使用任意键来引用数据，因此它们需要两个强制模板参数：键类型和数据类型。

template <typename Key, typename Data>
class PairAssociativeContainer {
...
};

算法的函数参数只能接受一个参数。为了实现这一点，成对关联容器将其元素类型定义为键类型和数据类型的 pair，这意味着使用成对关联容器的算法的函数参数必须如下所示：

// the declaration for a function argument compatible with
// algorithms and pair associative containers.

template <typename A, typename B>
void some_func( std::pair<A,B> pair );

不用说，这种情况并不常见，因此大多数潜在的算法函数参数都无用。

// familiar month example used 
// mandatory contrived example to show a simple point
// compiled using MinGW gcc 3.2.3 with gcc -c -o file.o 
// file.cpp

#include <string>
#include <ext/hash_map>
#include <iostream>

using namespace std;
// some STL implementations do not put hash_map in std
using namespace __gnu_cxx; 

hash_map<const char*, int> days_in_month;

class MyClass {
    static int totalDaysInYear;
public:
    void add_days( int days ) { totalDaysInYear += days; }
    static void printTotalDaysInYear(void) 
    { 
        cout << "Total Days in a year are " 
            << totalDaysInYear << endl; 
    }
};

int MyClass::totalDaysInYear = 0;

int main(void)
{
    days_in_month["january"] = 31;
    days_in_month["february"] = 28;
    days_in_month["march"] = 31;
    days_in_month["april"] = 30;
    days_in_month["may"] = 31;
    days_in_month["june"] = 30;
    days_in_month["july"] = 31;
    days_in_month["august"] = 31;
    days_in_month["september"] = 30;
    days_in_month["october"] = 31;
    days_in_month["november"] = 30;
    days_in_month["december"] = 31;

    // ERROR: This line doesn't compile.
    accumulate( days_in_month.begin(), days_in_month.end(),
        mem_fun( &MyClass::add_days ));

    MyClass::printTotalDaysInYear();

    return 0;
}

标准 C++ 解决方案

标准 C++ 库定义了某些函数适配器，如 select1st、select2nd 和 compose1，它们可用于使用成对关联容器的键或数据元素调用单参数函数。

select1st 和 select2nd 的功能与其各自的名称几乎一致。它们分别从 pair 返回第一个或第二个参数。

compose1 允许使用函数组合，以便一个函数的返回值可以用作另一个函数的参数。compose1(f,g) 等同于 f(g(x))。

使用这些函数适配器，我们可以使用 for_each 调用我们的函数。

hash_map<string, MyType> my_map;
for_each( my_map.begin(), my_map.end(), 
          compose1( mem_fun( &MyType::do_something ), 
                    select2nd<hash_map<string, 
                    MyType>::value_type>()));

当然，这比为每个 pair 定义辅助函数要好得多，但仍然显得有些麻烦，尤其与同等的 for 循环的清晰度相比。

for( hash_map<string, MyType>::iterator i = 
         my_map.begin();
     i != my_map.end(), ++i ) {

     i->second.do_something();
}

考虑到最初使用 STL 算法的初衷是为了避免 for 循环以提高清晰度，而现在 for 循环却更加清晰简洁，这不利于算法与手动编写循环的比较。

with_data 和 with_key

with_data 和 with_key 是函数适配器，它们力求清晰，同时允许轻松地将 STL 算法与成对关联容器一起使用。它们像 mem_fun 一样被参数化。这并非什么高深的学问，但可以很快看出，它们比使用 compose1 和 select2nd 的标准函数适配器扩展要清晰得多。

使用 with_data 和 with_key，可以调用任何函数，并将 data_type 或 key_type 分别用作函数的参数。这使得 hash_map、map 以及 STL 中的任何其他成对关联容器都可以轻松地与标准算法一起使用。甚至可以将其与其他函数适配器一起使用，例如 mem_fun。

hash_map<string, IDirect3DVertexBuffer* /> my_vert_buffers;

void ReleaseBuffers(void)
{
    // release the vertex buffers created so far.
    std::for_each( my_vert_buffers.begin(), 
        my_vert_buffers.end(), 
        with_data( boost::mem_fn( 
            &IDirect3DVertexBuffer9::Release )));
}

这里使用 boost::mem_fn 而不是 mem_fun，因为它能识别 COM 使用的 __stdcall 方法，如果定义了 BOOST_MEM_FN_ENABLE_STDCALL 宏。

with_data 和 with_key 定义如下：

template <typename Result, typename Arg>
struct call_func_with_data_t {

    typedef Result (*Func)(Arg);
    Func f_;

    explicit call_func_with_data_t( Func f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const 
    {
        // to enforce the equality of the data with the 
        //argument type instantiated
        const Arg value = v.second;     

        return f_( value );
    }
};

template <typename Functor>
struct call_class_with_data_t {

    Functor f_;
    typedef typename Functor::result_type Result;
    typedef typename Functor::argument_type Arg;

    explicit call_class_with_data_t( Functor f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const 
    {
        // to enforce the equality of the data with the 
        // argument type instantiated
        const Arg value = v.second;

        return f_( value );
    }
};

template <typename Result, typename Arg>
call_func_with_data_t<Result, Arg> with_data( Result (*f)(Arg) )
{
    return call_func_with_data_t<Result, Arg>( f );
}

template <typename Functor>
call_class_with_data_t<Functor> with_data( Functor f )
{
    return call_class_with_data_t<Functor>( f );
}

template <typename Result, typename Arg>
struct call_func_with_key_t {

    typedef Result (*Func)(Arg);
    Func f_;

    explicit call_func_with_key_t( Func f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const
    {
        // to enforce the equality of the data with the 
        // argument type instantiated
        const Arg value = v.first;

        return f_( value );
    }
};

template <typename Functor>
struct call_class_with_key_t {

    Functor f_;
    typedef typename Functor::result_type Result;
    typedef typename Functor::argument_type Arg;

    explicit call_class_with_key_t( Functor f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const
    {
        // to enforce the equality of the data with the 
        // argument type instantiated
        const Arg value = v.first;

        return f_( value );
    }
};

template <typename Result, typename Arg>
call_func_with_key_t<Result, Arg> with_key( Result (*f)(Arg))
{
    return call_func_with_key_t<Result, Arg>( f );
}

template <typename Functor>
call_class_with_key_t<Functor> with_key( Functor f )
{
    return call_class_with_key_t<Functor>( f );
}

工作原理

with_key 和 with_data 之间唯一的区别在于它们在调用函数之前提取的 pair 的元素。因此，只解释 with_data。

有两个 with_data 函数，一个用于函数指针，另一个用于函数对象。编译器根据参数重载调用哪个函数。它们各自返回一个执行相同操作的特定函数对象，区别在于 operator() 函数返回的类型。函数指针版本（call_func_with_data_t）可以从模板参数中提取返回类型。函数对象版本（call_class_with_data_t）使用 unary_function 的 typedef 来确定传入函数的参数类型（unary_function::argument_type）和返回类型（unary_function::result_type）。

每个函数对象中的 operator() 方法提取第二个成员并用它来调用函数。创建临时值的那一行用于确保 B 类型与 Arg 类型兼容，因为成员函数可能无法进行部分特化。

// this is illegal. Member functions may not be 
// partially specialized.

template <typename Functor>
struct call_class_with_key_t {

    Functor f_;
    typedef typename Functor::result_type Result;
    typedef typename Functor::argument_type Arg;

    explicit call_class_with_key_t( Functor f ) : f_(f) {}
    
    // illegally specialized member function
    template <typename A>
    Result operator()<Arg>( 
        const std::pair<A,Arg>& v ) const
    {
        return f_( v.first );
    }
};

使用代码

随附的 zip 文件中包含头文件 call_with.hpp，其中定义了这两个函数适配器。代码已发布到公共领域，可随意使用。已知能在 Visual C++ 7.1、gcc 3.2.3 和 Comeau 4.3.3 上编译。

结论

with_* 函数适配器并非革命性的创新，但它们确实有助于阐明算法与成对关联容器之一的用法。它们的名称比 compose1/select2nd 组合更清楚地说明了其用途。有时，为了追求通用性，稍微具体化一些是值得的。

作者感谢 Eric Dixon、John Olsen 和 Nate Robins 的评论和更正。

参考文献

[1] Meyers, Scott. STL 算法与手动编写的循环。

历史

• 2003/12/21 - 初稿。
• 2004/1/18 - 初次发布。