• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

用C++11来实现LINQtoObject

原作者: [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人参与评论

请发表评论

全部评论

专题导读
上一篇:
c#将字符串和ASCII码数组互相转换发布时间:2022-07-14
下一篇:
C++mutex&amp;&amp;RWlock发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap