Learn from proposal for new forloop

 

最近阅读 Bjarne Stroustrup 的论文 Evolution a language in and for the real world: C++ 1991-2006 [1]。这篇长达59的论文是自 D&E [2] 之后，Stroustrup 对C++语言的发展历史最系统、最详细的回顾与展望，对于C++程序员和程序设计语言的研究者具备很高的参考价值。

这篇论文最令我感兴趣的部分是对下一代语言标准C++0x的展望。其中，Stroustrup 提到了一个新的for-loop语句的提案 [3]。我曾经阅读过Neric Niebler关于BOOST_FOREACH的实作 [4]，因此很想知道这份提案的技术细节。于是，通过搜索关键字"WG21"(C++0x的ISO编号) 和"Proposal for new for-loop"获得了提案的在线文档。这是一份很短的文档，但却是一个展示语言进化的极好的例子：简单、清晰、展示了语言细节改进带来的整体增益。本文将按照提案的结构，介绍相关技术细节和我的感想。这不是一份提案的译稿，想深入细节的朋友请阅读原文。

1 动机 

Java、C#、Python等现代程序设计语言都提供了foreach关键字。这是一个非常便利的语言设施，可以实现对一个区间(range)的访问。然而，在C++98中却没有相应的语言设施。虽然std::for_each()提供了遍历区间的框架算法，但是编写和使用仿函数(functor, function object)并不是一件轻松、愉快的任务，特别是和手工编写的for语言相比。

新的for-loop语句将带来两个好处：

• 可用性：C++程序员可以快速地编写出正确、清晰、易读、易维护的区间遍历代码。
• 性能：对于新的for-loop，区间的起点和终点是固定的(参见下文)，这有利于编译器实施并行优化。这也符合C++语言在多核时代的发展方向。

2 例子

新的for-loop语句将基于迭代子区间 [begin, end)，可以作用在数组、STL容器、用户自定义类型上。这和BOOST_FOREACH非常相像：BOOST_FOREACH可以作用于任何支持Boost.Range [5]的对象上，而Boost.Range适用于数组、STL容器和用户自定义类型。值得注意的是，这份提案的作者恰恰是Boost.Range的作者Thorsten Ottosen。

以下是一些样例代码。

// STL container: readonly
vector<int> vec = ...;
for( int i : vec )
    std::cout << i; 

// STL container: writable
vector<int> vec = ...;
for( int& i : vec );
    i = 42;

// builtin arrays
const int[] integers = { 1, 2, 3, 4, 5, 6 };
for( int i : integers )
    std::cout << c;

// pairs of iterators
typedef vector<int>::iterator iter;
std::pair<iter,iter> p = std::make_pair(vec.begin(), vec.end());
for( int i : p )
    std::cout << i;

新的for-loop语句的最大优点在于，它使用了较高层次的、定义更佳的抽象操作("处理此区间")代替了底层的、无语义的循环 [6]。

3 参考实现

和BOOST_FOREACH的思路接近，新for-loop语句会被转换成传统的for-loop语句。一个可能的实现策略是，将语句

for( int i : vec )
    std::cout << i; 

转换成：

using std::begin; // enable ADL
using std::end;   // ditto
for( auto __begin = begin(vec),  // (1)
          __end   = end(vec);    // (2)
     __begin != __end; ++__begin )
{
    int i = *__begin;
    std::cout << i;
}  

值得注意的是迭代子__end只被赋值一次，这避免了不必要的开销，也有利于并行优化。

为了使代码通过编译，程序员需要include头文件<iterator>。在此头文件中有默认版本的begin()和end()。

namespace std
{
    template< class T >
    auto begin( T&& t ) -> decltype( t.begin() ) // (3)
    {
        return t.begin(); // (4)
    }

    template< class T >
    auto end( T&& t ) -> decltype( t.end() )
    {
        return t.end();
    }
}

以上代码对于一些C++程序员而言有些陌生，因为它使用到了一些C++98的高级特性和C++0x的新特性。我看到注释"enable ADL" 时也皱了一下眉头，但看到begin()和end()的定义时却兴奋得站了起来。因为，这一小段代码很好的展现了C++0x的弹性和力量，而这种能力来自于多个小的语言特性的累积作用(cumulative effect)。让我们逐一检阅它们。

区间(Range) 是一个类似于STL容器的概念(concept)，它提供了迭代子用于访问区间[first, one_past_last)中的元素。区间提供了一种看待聚集元素的更高层的抽象，它能够涵盖内建数组、STL容器和用户自定义类型。具体而言，语句(1)中begin(vec) 获取区间的first元素，语句(2)中end(vec)于获取区间的one_past_last元素。更详细的说明请参考 Boost.Range[5]。

ADL 参数相关查找(argument-dependent-lookup)，也称Koenig lookup (以其提案人Andrew Koenig命名) 是C++98的一条重要的名字查找规则。它很难用只言片语描述清楚，好在Effective C++ 3e的条款25对ADL有通俗易懂的解释 [7]。在这里，ADL(using std::begin)的作用是，

• 如果用户为vec的类型定义了非成员函数begin()，那么调用用户定义的begin()。
• 如果用户没有为vec定义begin()，那么调用std::begin()。

auto 是C++0x的新关键字，提供了一种基于初始化表达式的类型来推导被初始化变量类型的能力。它的引入将极大地简化泛型代码的编写。具体而言，在语句(1)处，编译器将根据函数begin()的返回值类型来推导变量__begin的类型。值得一提的是，C#3.0也引入了一个类似的变量类型推导机制 (基于关键字var)。

右值引用(Rvalue Reference) 也是C++0x的新特性，是一种不需要const修饰(const qualified) 就可以绑定到右值(rvalue)上的引用。在语句(3)处，T&& t就是一个右值引用，它提供了这样的能力：

• 如果实参是左值，T&&就会被推导为non-const左值引用(non-const lvalue reference)，即T& 。因此，语句(4)中 t.begin()调用的是non-const成员函数begin()。
• 如果实参是右值，T&&就会被推导为带有“右值”语义。因此，语句(4) 中t.begin()调用的是const成员函数begin()。
• 以上的参数推导能力是，C++98中的T& (non-const左值引用) 和const T& (const左值引用) 所不具备的。实际上，右值引用在这里解决了"The Forwarding Problem"。更详细的解释可以参考在线文档 [8]。

decltype 是C++0x的新关键字，用于推导表达式的类型。auto begin( T&& t ) -> decltype( t.begin() ) 是新的函数声明语法，其语义是函数begin(T&&)的返回值类型是decltype( t.begin() )，即表达式t.begin()的类型。

总之，如果vec是vector<int>，那么代码会被翻译为：

for( vector<int>::iterator __begin = vec.begin(),  
                           __end   = vec. end();   
     __begin != __end; ++__begin )
{
    int i = *__begin;
    std::cout << i;
}

如果vec是int vec[6]，那么代码会被翻译为：

for( int* __beging = vec,  
          __end   = vec + 6;   
     __begin != __end; ++__begin )
{
    int i = *__begin;
    std::cout << i;
}  

这时，需要在std名空间中再增加两个函数：

namespace std
{
    template< typename T, size_t N >
    T* begin( T (&&a) [N] )
    {
        return a;
    }

    template< typename T, size_t N >
    T* end( T (&&a) [N] )
    {
        return a + N;
    }
}

4 使用户自定义类型适用于新的for-loop

在以上语言设施的“助力”下，使用户自定义类型(UDT, User-Defined Type) 和for-loop协同工作是非常容易的。

方法1：非成员、非友员函数 (non-member, non-friend function)

// UDT
class MyContainer
{
    char*  data_;
    size_t size_;
    
 public:
    char* Begin() const { return data_; } 
    char* End() const { return data_ + size; } 
};

// for-loop requirements
std::if_< std::is_const<MyContainer>, const char*, char* >::type // (5)
begin( MyContainer&& c )
{
    return c.Begin();
}   

std::if_< std::is_const<MyContainer>, const char*, char* >::type 
end( MyContainer&& c )
{
    return c.End();
}  

以上代码用到了两个标准库的扩展：

Type traits in TR1 在语句(5)，std::is_const<MyContainer> 判断类型MyContainer是否被const修饰(const-qualified)。该模板类是C++0x Library TR1的Type traits库的一部分，相关的Boost实现可以参考Boost.TypeTraits [9]。具体而言，std::is_const<T>内含一个类型为bool的静态数据成员value，

• 如果T是const-qualified，则std::is_const<T>::value == true；
• 否则std::is_const<T>::value == false。

Template Metaprogramming Library 模板元编程是一个相当高阶的技术，但是std::if_的实作却很直观(一个示例性的实现如下)。有关MPL (Meta-Programming Library)的Boost实作可以参考Boost.MPL [10]。

namespace std
{
    template< class Predicate, class X, class Y >
    struct if_
    {
         typedef detail::if_impl_< Predicate::value, X, Y > type;
    }

    namespace detail
    {	
        template< bool b, class X, class Y >
        struct if_impl_ 
        {
            typedef X type;  // use X if b is true
        };
 
        template< class X, class Y >
        struct if_impl_ < false, X, Y > 
        {
            typedef Y type;  // use Y if b is false
        };
    }
}

于是，语句(5)的语义是，

• 如果MyContainer是const-qualified，那么函数begin(MyContainer&&)的返回值是const char*；
• 否则，函数begin(MyContainer&&)的返回值是char*。

值得指出的是，虽然类MyContainer的定义不是const-correct的：MyContainer::Begin()作为const成员函数却返回char*，但是语句(5)的begin(MyContainer&&)的函数界面(interface)是const-correct的。

方法2：使用Adapter模式 [11]

class my_range_adapter
{
    MyContainer& c;
public:
    my_range_adapter( MyContainer& r ) : c(r)
    { }

    char* begin()
    {
        return c.Begin();
    }   

    const char* begin() const
    {
        return c.Begin();
    }   

    char* end()
    {
        return c.End();
    }   

    const char* end() const
    {
        return c.End();
    }   
};

// usage
MyContainer m = ...;
for( char c : my_range_adapter(m) )
    ...;

方法3：利用标准库的实用工具

for( char c : std::make_iterator_range(m.Begin(),m.End()) )
    ...

5 小结

很遗憾，本文比原提案文档要长一些。这是因为新for-loop语句涉及一些C++98/0x的特性，而这些特性对于C++初学者而言不是不言自明的。幸运的是，恰恰是因为有了这些高阶特性，我们才能拥有如此简单、优雅、高效、可扩展的for-loop语句。

6 参考文献

[1] Bjarne Stroustrup: Evolving a language in and for the real world: C++ 1991-2006. To appear HOPL-III. June 2007.

[2] Bjarne Stroustrup: The Design and Evolution of C++, Addison-Wesley, 1994.

[3] Thorsten Ottosen: Proposal for new for-loop. ISO SC22 WG21 TR N1796==05-0056.

[4] Eric Niebler: Boost.Foreach, http://www.boost.org/regression-logs/cs-win32_metacomm/doc/html/foreach.html

[5] Thorsten Ottosen: Boost.Range, http://www.boost.org/libs/range/index.html

[6] Herb Sutter, Andrei Alexanderscu: C++ Coding Standards, Addison-Wesley, 2005.

[7] Scott Meyers: Effective C++ 3e, Addison-Wesley, 2005.

[8] Danny Kalev: The rvalue Reference Proposal, http://www.informit.com/guides/content.asp?g=cplusplus&seqNum=310

[9] Boost.org: Boost.TypeTraits, http://www.boost.org/doc/html/boost_typetraits.html

[10] Aleksey Gurtovoy, David Abrahams: Boost.MPL, http://www.boost.org/libs/mpl/doc/index.html

[11] Erich Gamma, Richrad Helm, Ralph Johnson, and John Vlissides, Design Patterns - Elements of Reusable Object-Oriented Software, Addison Wesley/Pearson, 1995.