用C++11来实现LINQtoObject

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　在 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)

鲜花

握手

雷人

路过

鸡蛋

该文章已有0人参与评论

请发表评论

全部评论

专题导读

More+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

c#将字符串和ASCII码数组互相转换发布时间：2022-07-14

C++mutex&&RWlock发布时间：2022-07-14

剪的笔顺,诠释剪的笔画,认识剪的部首

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19131|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：9972|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8317|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8686|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8627|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9643|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8611|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：7991|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8642|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7527|2022-11-06

客服电话

电子邮件

用C++11来实现LINQtoObject

请发表评论

全部评论

上一篇：

下一篇：

bradtraversy/iweather: Ionic 3 mobile we

joaomh/curso-de-matlab

断牙刷新位置时间（断牙属性及刷新位置介绍

MATLAB 常用操作命令和快捷键 - 躬耕南阳

rugk/mastodon-simplified-federation: Sim

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053