用 C++ 11 来实现 LINQ to Object

　　在 C# 里面 LINQ 是基于扩展方法来构建的，扩展的是 IEnumerable<T> 接口。有关扩展方法的好处在这里我就不做多的说明了，我默认看到此文章的读者都是喜欢 C# 并且理解 C# 这门语言的美妙的人~

　　在 LINQ 的扩展方法里面，返回的依旧是个 IEnumerable<T> 接口的对象，于是 LINQ 拥有了链式调用的风格。如：

List<int> list = new List<int>(){1,2,3,4,5,6,7,8,9};
var query = list
    .Where(x => x % 2 ==0)
    .Select(x => x * x)
    .Take(3);

//

　　在每一次调用中，实际上是将上一个迭代器对象重新包装（装饰）了一遍，详细请看这篇文章。这样的好处就是可以实现延迟执行（毕竟返回的对象是迭代器），当迭代的时候才真正开始运算。

基于这样的思想，我们可以用 C++ 来实现一个 LINQ：

　　由于 C++ 没有扩展方法，我们需要先将 STL 容器转换为一个 linq_enumerable 对象，里面保存着 STL 的迭代器。而在每一次的 LINQ 函数调用中，都将当前迭代器对象包装（装饰）一次，并重新返回一个 linq_enumerable 对象。

　　我们可以用 from 函数来实现转换：

    template<typename TContainer>
    auto from(const TContainer& c)->linq_enumerable<decltype(std::begin(c))>
    {
        return linq_enumerable<decltype(std::begin(c))>(std::begin(c), std::end(c));
    }

　　linq_enumerable 类如下:

 1     template<typename TIterator>
 2     class linq_enumerable
 3     {
 4     private:
 5         TIterator _begin;
 6         TIterator _end;
 7 
 8     public:
 9         linq_enumerable(const TIterator& b, const TIterator& e) :
10             _begin(b), _end(e)
11         {}
12 
13         TIterator begin()const
14         {
15             return _begin;
16         }
17 
18         TIterator end()const
19         {
20             return _end;
21         }
22     };

　　然后我们来测试一下：

 1 int main()
 2 {
 3     {
 4         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 5 
 6         for (auto x : from(v))
 7         {
 8             cout << x << endl;
 9         }
10     }
11 
12     {
13         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
14 
15         for (auto x : from(from(from(from(v)))))
16         {
17             cout << x << endl;
18         }
19     }
20     return 0;
21 }

　　好了，到这里我们已经将所有的准备工作都做好了。接下来的一个个 LINQ 函数，都是在基于这之上一点点增加的。

那么，我们就先从最简单的 select 开始吧：

　　首先，select() 是 linq_enumerable 对象的成员函数，它接收一个 lambda 函数，然后将当前 linq_enumerable 对象的迭代器对象包装为 select_iterator ，最后返回linq_enumerable 对象。

        template<typename TFunction>
        auto select(const TFunction& f)const->linq_enumerable<select_iterator<TIterator, TFunction>>
        {
            return linq_enumerable<select_iterator<TIterator, TFunction>>(
                select_iterator<TIterator,TFunction>(_begin,f),
                select_iterator<TIterator,TFunction>(_end,f)
                );
        }

　　select_iterator 对象的成员应该要有被包装的迭代器、lambda 函数对象，同时还要重载 ++ * == != 这几种操作符（自增、取值、等于、不等于）。select_iterator 类的实现如下：

 1     template<typename TIterator,typename TFunction>
 2     class select_iterator
 3     {
 4         typedef select_iterator<TIterator, TFunction> TSelf;
 5         
 6     private:
 7         TIterator iterator;
 8         TFunction f;
 9 
10     public:
11         select_iterator(const TIterator& i, const TFunction& _f) :
12             iterator(i), f(_f)
13         {}
14 
15         TSelf& operator++()
16         {
17             ++iterator;
18             return *this;
19         }
20 
21         auto operator*()const->decltype(f(*iterator))
22         {
23             return f(*iterator);
24         }
25 
26         bool operator==(const TSelf& it)const
27         {
28             return it.iterator == iterator;
29         }
30 
31         bool operator!=(const TSelf& it)const
32         {
33             return it.iterator != iterator;
34         }
35     };

　　现在我们可以再来测试一下：

 1     {
 2         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 3         auto q = from(v).select([](int x) { return x + 10; });
 4         
 5         vector<int> xs = { 11, 12, 13, 14, 15, 16, 17, 18, 19 };
 6         
 7         assert(std::equal(xs.begin(), xs.end(), q.begin()));
 8     }
 9 
10     {
11         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
12         auto q = from(v).select([](int x) { return x * x; });
13 
14         vector<int> xs = { 1, 4, 9, 16, 25, 36, 49, 64, 81 };
15 
16         assert(std::equal(xs.begin(), xs.end(), q.begin()));
17     }

　　我们看到了预期的结果，此时变量 q 的类型是类似于 linq_enumerable<select_iterator<std::vector<int>::iterator>> 这样（忽略TFunction类型），LINQ 函数的执行过程实际上只是将迭代器对象包装了一次。

那么我们再来看看 where:

　　where_iterator 对象和 select_iterator 对象很相似，稍微有点区别的地方在于自增和取值操作。当 where_iterator 自增时，它会有一个谓词条件，若没满足这个条件则会继续自增，以此过滤掉不满足条件的元素。where_iterator 的取值操作就很简单了，直接对它所包装的迭代器对象进行 * 操作即可。实现如下：

 1     template<typename TIterator,typename TFunction>
 2     class where_iterator
 3     {
 4         typedef where_iterator<TIterator, TFunction> TSelf;
 5 
 6     private:
 7         TIterator iterator;
 8         TIterator end;
 9         TFunction f;
10 
11     public:
12         where_iterator(const TIterator& i, const TIterator& e, const TFunction& _f) :
13             iterator(i), end(e), f(_f)
14         {
15             while (iterator != end && !f(*iterator))
16             {
17                 ++iterator;
18             }
19         }
20 
21         TSelf& operator++()
22         {
23             if (iterator == end) return *this;
24             ++iterator;
25             while (iterator != end && !f(*iterator))
26             {
27                 ++iterator;
28             }
29             return *this;
30         }
31 
32         iterator_type<TIterator> operator*()const
33         {
34             return *iterator;
35         }
36 
37         bool operator==(const TSelf& it)const
38         {
39             return it.iterator == iterator;
40         }
41 
42         bool operator!=(const TSelf& it)const
43         {
44             return iterator != it.iterator;
45         }
46     };

　　在取值操作中，返回值类型是迭代器所指向的元素的类型，在这里我用 iterator_type 来实现。

    template<typename TIterator>
    using iterator_type = decltype(**(TIterator*)nullptr);

　　nullptr 是 C++ 11 标准中用来表示空指针的常量值，可以将其强制转换为指向 TIterator 的指针，然后对其解引用得到一个不存在的 TIterator 对象 *(TIterator*)nullptr ，而再对迭代器对象进行解引用，即可得到迭代器所指向的元素。最后对其使用 decltype 操作，得到元素类型。对了，我们还要实现 linq_enumerable 对象的 where 函数：

        template<typename TFunction>
        auto where(const TFunction& f)const->linq_enumerable<where_iterator<TIterator,TFunction>>
        {
            return linq_enumerable<where_iterator<TIterator, TFunction>>(
                where_iterator<TIterator, TFunction>(_begin,_end,f),
                where_iterator<TIterator, TFunction>(_end,_end,f)
                );
        }

　　where 也完成了，我们赶紧来测试一下：

 1     {
 2         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 3         auto q = from(v).where([](int x) { return x % 2 == 1; });
 4 
 5         vector<int> xs = { 1, 3, 5, 7, 9 };
 6 
 7         assert(std::equal(xs.begin(), xs.end(), q.begin()));
 8     }
 9 
10     {
11         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
12         auto q = from(v).where([](int x) { return x > 5; });
13 
14         vector<int> xs = { 6, 7, 8, 9 };
15 
16         assert(std::equal(xs.begin(), xs.end(), q.begin()));
17     }
18 
19     {
20         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
21         auto q = from(v)
22             .where([](int x) { return x % 2 == 1; })
23             .select([](int x) { return x * 10; });
24 
25         vector<int> xs = { 10, 30, 50, 70, 90 };
26 
27         assert(std::equal(xs.begin(), xs.end(), q.begin()));
28     }
29 
30     {
31         vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
32         auto q = from(v)
33             .where([](int x) { return x % 2 == 1; })
34             .where([](int x) { return x > 5; })
35             .select([](int x) { return x * 10; });
36 
37         vector<int> xs = { 70, 90 };
38 
39         assert(std::equal(xs.begin(), xs.end(), q.begin()));
40     }

　　看到这样的结果，是不是觉得已经要大功告成了。简单来说，差不多是这样。LINQ 的各个函数之间是独立存在的，假如你只需要用到 LINQ 的过滤和投影的话，那么可以说我们已经完成了 LINQ to Object 的实现.....

在微软的官方文档中有 101个 LINQ 实例，要方便一点也可以看这里。这 101个例子几乎包括了所有的 LINQ 操作，我们可以据此将 LINQ 操作分为以下几类：

　　1、Restriction Operators. 如：Where

　　2、Projection Operators. 如：Select

　　3、Partitioning Operator. 如：Take

　　4、Ordering Operators. 如：OrderBy

　　5、Grouping Operators. 如：GroupBy

　　6、Set Operators. 如：Distinct

　　7、Conversion Operators. 如：ToList

　　8、Element Operators. 如：First

　　9、Generation Operators. 如：Range

　　10、Quantifiers. 如：Any

　　11、Aggregate Operators. 如：Count

　　12、Miscellaneous Operators. 如：Concat

　　13、Join Operators. 如：Cross Join 和 Group Join

　　在本文中，我会每一类给出一个实现，同一类别其他操作的实现细节大家可以看我的代码。

　　take 函数与 select 和 where 类似，也是先将迭代器包装成 take_iterator ，然后返回 linq_enumerable 对象。

        auto take(int count)const->linq_enumerable<take_iterator<TIterator>>
        {
            return linq_enumerable<take_iterator<TIterator>>(
                take_iterator<TIterator>(_begin,_end,count),
                take_iterator<TIterator>(_end,_end,count)
                );
        }

　　take_iterator 类实现如下：

 1     template<typename TIterator>
 2     class take_iterator
 3     {
 4         typedef take_iterator<TIterator> TSelf;
 5 
 6     private:
 7         TIterator iterator;
 8         TIterator end;
 9         int count;
10         int current;
11 
12     public:
13         take_iterator(const TIterator& i, const TIterator& e, int c) :
14             iterator(i), end(e), count(c), current(0)
15         {
16             if (current == count)
17             {
18                 iterator = end;
19             }
20         }
21 
22         iterator_type<TIterator> operator*()const
23         {
24             return *iterator;
25         }
26 
27         TSelf& operator++()
28         {
29             if (++current == count)
30             {
31                 iterator = end;
32             }
33             else
34             {
35                 ++iterator;
36             }
37             return *this;
38         }
39 
40         bool operator==(const TSelf& it)const
41         {
42             return iterator == it.iterator;
43         }
44 
45         bool operator!=(const TSelf& it)const
46         {
47             return iterator != it.iterator;
48         }
49     };

View Code

　　与 take 函数非常相似的还有 skip 、take_while、skip_while，所以实现细节这里我就不写了，我的代码在这里。

　　上面的几类函数具有延迟执行的特性，LINQ 当中还有一些立即执行的函数。就是 Conversion Operators 、Element Operators 和 Aggregate Operators 这几类函数，在使用这几类函数操作时，会立即执行计算出结果。

　　to_vector：

        std::vector<TElement> to_vector()const
        {
            std::vector<TElement> v;
            for (auto it = _begin; it != _end; ++it)
            {
                v.push_back(*it);
            }
            return std::move(v);
        }

　　first：

        TElement first()const
        {
            if (empty())
            {
                throw linq_exception("Failed to get a value from an empty collection");
            }
            return *_begin;
        }

　　count：

        int count()const
        {
            int counter = 0;
            for (auto it = _begin; it != _end; ++it)
            {
                ++counter;
            }
            return counter;
        }

　　TElement 类型的定义为：

        typedef typename std::remove_cv<typename std::remove_reference<iterator_type<TIterator>>::type>::type TElement;

　　这几类函数还有 to_list、to_set、to_map，first_or_default、last、last_or_default、element_at，sum、min、max、average、aggregate ，实现方式都大同小异。

　　还有几类函数的实现稍微有点难度，它们是分组、排序、连接。所以我们先放松一下，然后再集中精力往下讨论。

　　我们先从分组说起，分组函数接收一个 lambda，然后对每一个元素执行 lambda后返回的结果为分组的 key，key 相同的元素会被组合到一起为一个序列。我们用一个 pair 来保存这个 key 和序列（pari<key,linq_enumerable>），最后返回的结果是由 pair 组成的序列。虽然这种实现看起来不怎么优雅，但其实和 C# 的实现类似，只不过C#有 yield 和扩展方法，就显得很优雅了。

 1         template<typename TFunction>
 2         auto group_by(const TFunction& keySelector)const
 3             ->linq<std::pair<decltype(keySelector(*(TElement*)nullptr)), linq<TElement>>>
 4         {
 5             typedef decltype(keySelector(*(TElement*)nullptr)) TKey;
 6             typedef std::vector<TElement> TValueVector;
 7             typedef std::shared_ptr<TValueVector> TValueVectorPtr;
 8 
 9             std::map<TKey, TValueVectorPtr> map;
10             for (auto it = _begin; it != _end; ++it)
11             {
12                 auto value = *it;
13                 auto key = keySelector(value);
14                 auto it2 = map.find(key);
15                 if (it2 == map.end())
16                 {
17                     auto xs = std::make_shared<TValueVector>();
18                     xs->push_back(value);
19                     map.insert(std::make_pair(key, xs));
20                 }
21                 else
22                 {
23                     it2->second->push_back(value);
24                 }
25             }
26 
27             auto result = std::make_shared<std::vector<std::pair<TKey, linq<TElement>>>>();
28             for (auto p : map)
29             {
30                 result->push_back(std::pair<TKey, linq<TElement>>(p.first, from_values(p.second)));
31             }
32             return from_values(result);
33         }

group_by

　测试代码如下：

    {
        int xs[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        vector<int> ys = { 0, 1 };

        auto g = from(xs)
            .group_by([](int x) { return x % 2; })
            .select([](std::pair<int, linq<int>> p) { return p.first; });

        assert(std::equal(ys.begin(), ys.end(), g.begin()));

        vector<int> ys2 = { 6, 8 };
        auto g2 = from(xs)
            .group_by([](int x) { return x % 2; })
            .select([](std::pair<int, linq<int>> p) { return p.second; })
            .first()
            .where([](int x) { return x > 5; });

        assert(std::equal(ys2.begin(), ys2.end(), g2.begin()));
    }

　　相对于分组来说，其实排序的实现是最简单的，因为我在分组的实现中，使用了 map 这种数据结构作为临时变量，STL 中的 map 是用红黑树实现的，在插入数据的时候就已经保持有序了。因此排序的实现，只需要对分组的结果投影出 pair 的 second 部分，然后将其组成一个 linq_enumerable 对象就可以了。

        template<typename TFunction>
        linq<TElement> order_by(const TFunction& f)const
        {
            typedef typename std::remove_reference<decltype(f(*(TElement*)nullptr))>::type TKey;
            return group_by(f)
                .select([](const std::pair<TKey, linq<TElement>>& p) { return p.second; })
                .aggregate([](const linq<TElement>& a, const linq<TElement>& b) { return a.concat(b); });
        }

    {        
        vector<int> a = { 5, 3, 1, 4, 8, 2, 7, 6, 9 };
        vector<int> b = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        auto q = from(a).order_by([](int x) { return x; });
        
        assert(std::equal(b.begin(), b.end(), q.begin()));
    }

　　最后就是连接，我实现的是内连接。连接函数有4个参数，分别是 linq_enumerable 、keySelector1、keySelector2、resultSelector。在这里的实现我用的是非常简单的方法（没有像C#那样），C#用的是 lookup 来实现，我在这里就是直接取了笛卡尔积的子集，因此效率上会有点不足。

 1         template<typename TIterator2, typename TFunction1, typename TFunction2, typename TFunction3>
 2         auto join(const linq_enumerable<TIterator2>& e,
 3             const TFunction1& keySelector1,
 4             const TFunction2& keySelector2,
 5             const TFunction3& resultSelector)const
 6             ->linq<decltype(resultSelector(*(TElement*)nullptr, **(TIterator2*)nullptr))>
 7         {
 8             typedef decltype(resultSelector(*(TElement*)nullptr, **(TIterator2*)nullptr)) TResultValue;
 9             auto result = std::make_shared<std::vector<TResultValue>>();
10 
11             for (auto it1 = _begin; it1 != _end; ++it1)
12             {
13                 auto value1 = *it1;
14                 auto key1 = keySelector1(value1);
15                 for (auto it2 = e.begin(); it2 != e.end(); ++it2)
16                 {
17                     auto value2 = *it2;
18                     auto key2 = keySelector2(value2);
19                     if (key1 != key2) continue;
20 
21                     result->push_back(resultSelector(value1, value2));
22                 }
23             }
24             return from_values(result);
25         }

join

　　最后的最后，就是测试代码了！

 1 struct person
 2 {
 3     string name;
 4 };
 5 
 6 struct pet
 7 {
 8     string name;
 9     person owner;
10 };
11 
12     person fek = { "尔康, 福"};
13 
14     person ylc = { "良辰, 叶" };
15     person hmj = { "美景, 花" };
16     person lks = { "看山, 刘" };
17     person lat = { "傲天, 龙" };
18     person persons[] = { ylc, hmj, lks, lat };
19 
20     pet dog = { "斯派克", ylc };
21     pet cat = { "汤姆", ylc };
22     pet mouse = { "杰瑞", hmj };
23     pet bird = { "愤怒的小鸟", lks };
24     pet pig = { "风口上的猪", fek };
25     pet pets[] = { dog, cat, mouse, bird, pig };
26 
27     auto person_name = [](const person& p) { return p.name; };
28     auto pet_owner_name = [](const pet& p) { return p.owner.name; };
29     auto result = [](const person& p, const pet& pp) { return std::make_tuple(p.name, pp.name); };
30 
31     /*
32         良辰, 叶 : 斯派克   
33         良辰, 叶 : 汤姆
34         美景, 花 : 杰瑞  
35         看山, 刘 : 愤怒的小鸟
36     */
37     for (auto x : from(persons).join(from(pets), person_name, pet_owner_name, result))
38     {
39         cout << get<0>(x) << " ： " << get<1>(x) << endl;
40     }

　　文章写到这里，也就差不多要结束了。写这文章最初的目的是学习并记录，而且最好的学习方式是说出来，爱因斯坦就说了，如果你不能简单说清楚，那就是还没有完全弄明白。所以......其实我也并非完全弄明白了，但我还是试图讲清楚一部分的东西吧！

　　我是个两年多经验的野生菜鸟猿，如今在业余学习一下 C++，大家有想法可以提出来一起探讨一下，一起进步！

（完）