cpplinq - C++ 序列的 LINQ 查询运算符。

引言

cpplinq 是一个开源的原生模板库，提供了一组类似 LINQ 的运算符，用于查询 C++11 中的集合（数组和 STL 容器）。API 由一组模板类和函数组成，兼容所有主流编译器（VC++、mingw、g++、clang++）。该库可在 Codeplex 上找到。

在开始讨论 LINQ 的一些注意事项之前，这里有一些快速示例。

求一个整数数组中所有偶数的和

int numbers[] = {1,2,3,4,5,6,7,8,9};
auto s = from_array(numbers)
      >> where([](int i) {return i%2==0;})
      >> sum(); // yields 20

按降序排序一个整数数组中的所有唯一数字，将它们转换为 string 并打印结果。

int numbers[] = {3,1,4,1,5,9,2,6};
auto result = from_array(numbers)
           >> distinct()
           >> orderby_descending([](int i) {return i;})
           >> select([](int i){std::stringstream s; s<<i; return s.str();})
           >> to_vector();
for(auto i : result)
    std::cout << i << std::endl;

关于 LINQ 的几点说明

熟悉 .NET LINQ 及其查询运算符的开发者可以跳过此段。

LINQ（Language Integrated Query，语言集成查询）是 .NET Framework 的一个组成部分，为 .NET 添加了原生的查询功能。它基本上是语言环境和数据存储之间的网关。LINQ 定义了一组标准的查询运算符，用于数据的遍历、过滤和投影。除了标准的查询运算符外，C# 和 VB.NET 语言还提供了语言扩展，以映射到这些查询运算符，使开发者能够以更具声明性、类似 SQL 的方式编写代码。

LINQ 的优点包括：

• 以声明式风格编写代码
• 使用熟悉的类似 SQL 的语法，不仅可以查询 SQL 数据库，还可以查询几乎任何数据源
• 查询的正确性在编译时确定，而不是运行时
• 通过简化和更容易编写（和阅读）的代码，提高了生产力和可维护性

如果您想阅读更多关于 LINQ 和 .NET 标准查询运算符的信息，请参阅以下文章：

• .NET 标准查询运算符
• LINQ: .NET 语言集成查询

C++ 中的 LINQ

LINQ 的实现得益于 .NET 对 lambda 表达式的支持。然而，C++11 也遵循了这一趋势，增加了对 lambda 表达式和其他功能的支持，使我们能够在 C++ 中编写类似的功能。尽管并非所有 C++11 功能都已由 C++ 编译器完全实现，但所有编译器目前都支持 lambda、auto、decltype 和其他关键功能。

已经有尝试在 C++ 中实现类似 LINQ 的查询运算符。其中一项尝试是 boolinq。它是一个模板库，允许您这样编写查询（is_prime 是一个 lambda 函数，它接受一个 int 并返回 true 表示数字是素数，否则返回 false）。

vector<int> some_primes(int src[], int howMany)
{
    return  from(src)
           .where(is_prime)
           .take(howMany)
           .toVector();
}

该库有一个重要的缺点：它基于运算符“.”，而该运算符是不可重载的。因此，不修改现有库代码，就不可能对其进行扩展。

另一方面，微软正在开发一个原生的 RX 库（参见 Reactive Extensions），该库将为 C++ 提供查询功能。该库尚未发布，但他们已经在 Channel9 上就此发布了一个 演示文稿。上面简单的示例在原生 RX 中看起来会非常相似。

vector<int> some_primes(int src[], int howMany)
{
    return  from(src)
           .where(is_prime)
           .take(howMany);
           .to_vector();
}

因此，在扩展性方面，原生 RX 可能也会遇到同样的问题（尽管现在还为时过早，无法知道该库最终会是什么样子）。

另一方面，Boost 也包含一个用于处理范围的库，名为 range。boost::range 提供了使泛型算法能够与类似标准容器、null 终止的 string、迭代器对、原始数组等一起工作的手段。该库提供的一些算法与 .NET 标准查询运算符类似，但该库的功能远不止于此。尽管该库功能强大，可用于各种容器，但它并不小。而且，我认为它和 Boost 库一样，在简洁性和可读性方面存在不足。如果您已经熟悉 .NET 并希望在 C++ 中编写类似的 C++ 代码，那么 boost::range 并不是最佳选择，我个人认为。

隆重推出 cpplinq

cpplinq 采用了另一种方法，使用运算符 >> 来管道查询运算符，这使得它在无需更改现有实现的情况下即可进行扩展。前面所示的关于素数的示例将如下所示：

vector<int> some_primes(int src[], int howMany)
{
    return    from_array(src)
           >> where(is_prime)
           >> take(howMany);
           >> to_vector();
}

该库需要 C++11 支持（支持 lambda、auto、decltype、static_assert 等），并已在所有主要编译器上进行了测试：Windows 上的 VC++ 10（来自 Visual Studio 2010）、VC++ 11（来自 Visual Studio 2012）和 mingw（v4.7.0），Linux 上的 g++（v4.7.1）和 clang++（v3.1）。

库

• 由一系列模板类和函数组成
• 所有查询运算符均在命名空间 cpplinq 下定义
• 提供单个头文件 (cpplinq.hpp)

支持的查询运算符

cpplinq 支持 .NET 大多数标准查询运算符，未来可能会实现更多运算符。下表显示了与 .NET 标准查询运算符的比较，并对每个已实现的运算符进行了简短描述。

示例

以下示例展示了该库在查询序列方面的一些功能。

第一个示例显示了素数列表，用逗号和空格分隔。首先，它生成一个从 0 到 INT_MAX 的范围，然后从该范围中过滤出素数，只取前 N 个元素并将结果投影为 string。然后，使用“, ”作为分隔符，将结果序列中的元素串联成一个 string。

using namespace cpplinq;

auto is_prime = [](int i) -> bool 
{
    if (i < 2) { return false; }
    else if (i == 2) { return true; }
    else
    {
        auto r = (int)std::ceil (std::sqrt (i));
        for (auto iter = 2; iter <= r; ++iter)
        {
            if (i % iter == 0) { return false; }
        }
        return true;
    }
};

void show_some_primes(int count)
{
    auto primes = range(0, INT_MAX)   // generate range
               >> where(is_prime)     // filter elements and keep only primes
               >> take(count)         // take first count elements
               >> select(             // project the numbers as strings
                         [](int i) {std::stringstream s; s << i; return s.str();});

    auto result = primes              // source sequence
               >> concatenate(", ");  // fold the sequence into a string

    std::cout << result << std::endl;
}

int main()
{
    show_some_primes(10); // prints 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
    return 0;
}

需要注意的是，以上所有运算符（除了 concatenate()）都不返回序列，而是返回一个代表序列“描述”的对象，从而实现惰性求值。只有当我们开始迭代它时，范围才会被生成，并且只有在执行下一次迭代时才会生成新元素。然而，这种行为因某些运算符（如集合运算符）而异。concatenate() 是迭代序列并将其折叠为字符串的运算符。

下一个示例展示了如何计算整数数组和向量的集合并集和交集。

int set1[] = {1,3,5,7,9,7,5,3,1};
std::vector<int> set2; 
set2.push_back(1);
set2.push_back(2);
set2.push_back(3);
set2.push_back(4);

auto u = from_array(set1)
      >> union_with(from(set2))
      >> to_vector(); // yields {1,2,3,4,5,7,9}
      
auto i = from_array(set1)
      >> intersect_with(from(set2))
      >> to_vector(); // yields {1,3}

下一个示例展示了如何检索序列的第一个和最后一个元素，或者在不存在此类元素时返回默认值。请注意，这些运算符有一个接受谓词的重载，因此您可以返回满足条件的第一个或最后一个元素。

struct customer
{
    std::size_t id;
    std::string first_name;
    std::string last_name;

    customer (std::size_t id = 0, std::string first_name = "", std::string last_name = "")
        :id(std::move(id)), first_name(std::move(first_name)), last_name(std::move(last_name))
    {
    }
};

customer customers[] = {
    customer (1 , "Bill"    , "Gates"   ),
    customer (2 , "Steve"   , "Jobs"    ),
    customer (4 , "Linus"   , "Torvalds"),
    customer (11, "Steve"   , "Ballmer" )
};

auto f = from_array(customers) >> first_or_default();
std::cout << f.last_name << std::endl; // prints Gates

auto l = from_array(customers) >> last_or_default();
std::cout << l.last_name << std::endl; // prints Ballmer

在下一个示例中，我们将客户序列与客户地址序列连接起来，以确定谁住在哪里。查询在客户数组和地址数组之间生成一个左连接。customer 类是前一个示例中介绍的类，而 customer_address 类显示如下：

struct customer_address
{
    std::size_t id;
    std::size_t customer_id;
    std::string country;

    customer_address(std::size_t id, std::size_t customer_id, std::string country)
        : id(std::move (id)), 
        customer_id (std::move(customer_id)), country(std::move(country))
    {
    }
};

customer customers[] = {
    customer (1 , "Bill"    , "Gates"   ),
    customer (2 , "Steve"   , "Jobs"    ),
    customer (4 , "Linus"   , "Torvalds"),
    customer (11, "Steve"   , "Ballmer" )
};

customer_address customer_addresses[] =
{
    customer_address (1, 1, "USA"       ),
    customer_address (2, 4, "Finland"   ),
    customer_address (3, 11, "USA"      ),
};

auto result = from_array(customers)                         
           >> join (
                    from_array(customer_addresses),
                    [](customer const & c) {return c.id;},
                    [](customer_address const & ca) {return ca.customer_id;},
                    [](customer const & c, customer_address const & ca) 
                                          {return std::make_pair (c, ca);});

result >> for_each([](std::pair<customer, customer_address> const & p) {
    std::cout << p.first.last_name << " lives in " << p.second.country << std::endl;
});

for_each 运算符打印的结果是：

Gates lives in USA
Torvalds lives in Finland
Ballmer lives in USA

假设我们还有一些订单（包含订单头和订单行），并且我们想打印特定 customer 的最后一个订单。假设订单头和订单行如下所示：

struct order 
{
    std::size_t id;
    std::size_t customer_id;
    time_t      date;

    order(std::size_t id, std::size_t cid, time_t date):
        id(id), customer_id(cid), date(date)
    {
    }
};

struct order_line 
{
    std::size_t id;
    std::size_t order_id;
    std::size_t article_id;
    double      quantity;

    order_line(std::size_t id, std::size_t oid, std::size_t aid, double quantity):
        id(id), order_id(oid), article_id(aid), quantity(quantity)
    {
    }
};

并且订单和行在这些数组中（忽略日期，假设它们包含真实值）：

order orders[] = 
{
    order(1, 1, time(NULL)),
    order(2, 2, time(NULL)),
    order(3, 1, time(NULL)),
};

order_line orderlines [] = 
{
    order_line(1, 1, 100, 1.0),
    order_line(2, 1, 101, 5.0),
    order_line(3, 1, 102, 2.0),
    order_line(4, 2, 400, 1.0),
    order_line(5, 3, 401, 1.0),
};

一个打印来自特定 customer 的最后一个订单的函数可能如下所示：

void print_last_order_for_customer(std::size_t custid)
{
    auto result = from_array(orders)
               >> where([=](order const & o) {return o.customer_id == custid;})
               >> orderby_descending([](order const & o) {return o.date;})
               >> take(1)
               >> join(from_array(orderlines),
                        [](order const & o) {return o.id;},
                        [](order_line const & ol) {return ol.order_id;},
                        [](order const & o, order_line const & ol) 
                          {return std::make_pair(o, ol);});

    result >> for_each([](std::pair<order, order_line> const & p){
        std::cout << "order=" << p.first.id << ", " << ctime(&(p.first.date)) 
                  << "  article=" << p.second.article_id << ", 
                     quantity=" << p.second.quantity << std::endl; 
    });
}

调用此函数来获取客户 1 的订单将打印以下文本：

order=3, Wed Oct 24 19:26:18 2012
  article=401, quantity=1

范围生成器和转换运算符

最重要和最常用的运算符是范围生成器（用于构建一个对象来表示应用查询运算符的范围）和范围转换运算符（用于将范围折叠成一个包含该范围值的容器）。该库提供了以下范围生成器：

std::vector<int> numbers; 
auto result = 
  from_iterators(numbers.begin(), numbers.end());
result >> for_each([](int i) 
  {std::cout << i << std::endl;});

std::vector<int> numbers; 
auto result = from(numbers);
result >> for_each([](int i) {std::cout << i << std::endl;});

int numbers[] = {1,2,3,4,5};  
auto result = from_array(numbers);  
result >> for_each([](int i) {std::cout << i << std::endl;});

// create a range of numbers in the interval [10, 100)
auto result = range(10, 90);

// create a range with 10 strings with the value "cpplinq"
auto result = repeat("cpplinq", 10);

// create an empty range of customers
auto result = empty<customer>();

另一方面，以下范围转换运算符（将范围折叠成 STL 或类 STL 容器）可用：

// create a vector with ten integer elements, from [1, 10]
auto result = range(1, 10) >> to_vector();

// create a vector with ten integer elements, from [1, 10]
auto result = range(1, 10) >> to_list();

// create a map where key is the customer ID, 
// and the value is the customer object
auto result = from_array (customers) 
           >> to_map ([](customer const & c){return c.id;});

customer_address customer_addresses[] =  
{  
   customer_address (2, 4, "Finland"   ),  
   customer_address (3, 4, "USA"       ),  
   customer_address (1, 1, "USA"       ),  
};  
  
auto lookup = from_array (customer_addresses)   
           >> to_lookup ([] (customer_address const & ca)
              {return ca.customer_id;});   
  
auto countries = lookup[4]   
              >> select([](customer_address const & ca) 
                 {return ca.country;})   
              >> to_vector();  // yields {"Finland", "USA"}

扩展库

由于 cpplinq 库是基于 operator>> 构建的，因此可以在不修改现有代码的情况下对其进行扩展，添加新的查询运算符。该库包含范围构建器、范围运算符和辅助方法。

范围构建器是一个将范围（序列）折叠成一个值的类。它可以是单个值，例如序列元素的总和，或者是一个值容器，例如包含序列元素的向量。

范围运算符是一个将范围转换为另一个范围的类。它可以被看作是一个范围构建器，但它返回的是另一个范围，而不是一个单一（折叠的值）。例如，select 范围可以将整数序列转换为 string 序列，而 where 范围可以过滤整数范围以仅保留偶数。每个范围运算符都有一个配套的范围构建器，其目的是生成一个新的范围。

此外，对于每个查询运算符，我们定义一个独立的辅助函数，该函数创建并返回一个构建器类的实例。

构建范围聚合器

范围聚合器有几个要求：

• 必须继承 base_builder
• 必须是可复制的
• 必须是可移动的
• 有一个名为 this_type 的成员类型，代表 builder 类的类型
• 有一个名为 build 的方法，它接受一个范围并返回聚合值

下面是 sum 范围聚合器的代码。

struct sum_builder : base_builder
{
    typedef                 sum_builder                     this_type;

    CPPLINQ_INLINEMETHOD sum_builder () throw ()
    {
    }

    CPPLINQ_INLINEMETHOD sum_builder (sum_builder const & v) throw ()
    {
    }

    CPPLINQ_INLINEMETHOD sum_builder (sum_builder && v) throw ()
    {
    }

    template<typename TRange>
    CPPLINQ_INLINEMETHOD typename TRange::value_type build (TRange range)
    {
        auto sum = typename TRange::value_type ();
        while (range.next ())
        {
            sum += range.front ();
        }
        return std::move (sum);
    }

};

build 方法通过遍历输入范围并对元素求和来完成工作。

此外，我们定义了一个辅助方法来创建并返回构建器的实例。

template<typename TSelector>
CPPLINQ_INLINEMETHOD detail::sum_selector_builder<TSelector>  sum(TSelector selector) throw()
{
    return detail::sum_selector_builder<TSelector> (std::move (selector));
}

有了这样定义的辅助方法，我们就可以用它来对序列中的元素求和。

int numbers [] = {1,2,3,4};
auto s = from_array(numbers) >> sum(); // yields 10

构建范围运算符

范围运算符有几个要求，其中一些与范围构建器相同：

• 必须继承 base_range
• 必须是可复制的
• 必须是可移动的
• 有一个名为 this_type 的成员类型，它是范围类的类型
• 有一个名为 value_type 的成员类型，它是范围中值的类型
• 有一个名为 return_type 的成员类型，它是 value_type const & 或 value_type
• 有一个名为 return_reference 的 enum 成员，根据 return_type 是否为引用类型，该成员为 0 或 1
• 有一个名为 front 的成员方法，它将当前值作为 return_type 返回
• 有一个名为 next 的成员方法，它在可用时将指针移到下一个值并返回 true，否则返回 false
• 有一个名为 operator>> 的成员方法，它接受一个范围构建器并返回一个新的范围

front 方法

• 如果在尚未调用 next 或上一个 next 返回 false 的范围上调用，则行为未定义

next 方法

• 如果在上一个 next 返回 false 的范围上调用，next 应该不执行任何操作并返回 false
• 一个 next 永远未被调用的范围应该被视为“指向”无值（与指向集合中第一个值的 begin() 不同）。

注意：没有方法可以将范围重置回第一个位置。一旦遍历完成，比赛就结束了。这样做的理由是为了支持不支持重置的范围源。实际上，对于内存中的集合，可以进行重置，但只要范围源支持正常的复制语义，就可以使用它来实现重置。

以下是 where_range 运算符的代码。

template<typename TRange, typename TPredicate>

struct where_range : base_range
{
    typedef                 where_range<TRange, TPredicate> this_type       ;
    typedef                 TRange                          range_type      ;
    typedef                 TPredicate                      predicate_type  ;

    typedef                 typename TRange::value_type     value_type      ;
    typedef                 typename TRange::return_type    return_type     ;
    enum    
    { 
        returns_reference   = TRange::returns_reference   , 
    };

    range_type              range       ;
    predicate_type          predicate   ;

    CPPLINQ_INLINEMETHOD where_range (
            range_type      range
        ,   predicate_type  predicate
        ) throw ()
        :   range       (std::move (range))
        ,   predicate   (std::move (predicate))
    {
    }

    CPPLINQ_INLINEMETHOD where_range (where_range const & v)
        :   range       (v.range)
        ,   predicate   (v.predicate)
    {
    }

    CPPLINQ_INLINEMETHOD where_range (where_range && v) throw ()
        :   range       (std::move (v.range))
        ,   predicate   (std::move (v.predicate))
    {
    }

    template<typename TRangeBuilder<
    CPPLINQ_INLINEMETHOD typename get_builtup_type<TRangeBuilder, 
            this_type<::type operator>>(TRangeBuilder range_builder) throw ()   
    {
        return range_builder.build (*this);
    }

    CPPLINQ_INLINEMETHOD return_type front () const 
    {
        return range.front ();
    }

    CPPLINQ_INLINEMETHOD bool next ()
    {
        while (range.next ())
        {
            if (predicate (range.front ()))
            {
                return true;
            }
        }

        return false;
    }
};

此外，我们还定义了一个 where_range 构建器，其目的是构建一个 where_range 运算符。

template<typename TPredicate>
struct where_builder : base_builder
{
    typedef                 where_builder<TPredicate>   this_type       ;
    typedef                 TPredicate                  predicate_type  ;

    predicate_type          predicate   ;

    CPPLINQ_INLINEMETHOD explicit where_builder (predicate_type predicate) throw ()
        :   predicate (std::move (predicate))
    {
    }

    CPPLINQ_INLINEMETHOD where_builder (where_builder const & v)
        :   predicate (v.predicate)
    {
    }

    CPPLINQ_INLINEMETHOD where_builder (where_builder && v) throw ()
        :   predicate (std::move (v.predicate))
    {
    }

    template<typename TRange>
    CPPLINQ_INLINEMETHOD where_range<TRange, TPredicate> build (TRange range) const throw ()
    {
        return where_range<TRange, TPredicate>(std::move (range), predicate);
    }

};

最后，我们还添加了一个辅助方法来实例化并返回一个 where_range 构建器。

template<typename TPredicate>
CPPLINQ_INLINEMETHOD detail::where_builder<TPredicate> where(TPredicate predicate) throw()
{
    return detail::where_builder<TPredicate> (std::move (predicate));
}

有了辅助方法，我们就可以将其投入使用。

int numbers [] = {1,2,3,4,5,6,7,8,9};
auto result = from_array(numbers)
           >> where([](int i) {return i%2==0;})
           >> to_vector(); // yields {2,4,6,8}

结论

cpplinq 模板库是为 C++11 中的对象序列提供类似 .NET 的查询运算符的一种尝试。该库实现了大多数 .NET 标准查询运算符，并可与所有主要编译器一起使用。该库围绕 operator>> 构建，使其易于扩展，无需更改现有库代码。您可以从库的 Codeplex 主页 下载该库（以及单元测试）。

历史

• 2012 年 11 月 4 日：初始版本