在 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()const14 {15 return _begin;16 }17 18 TIterator end()const19 {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)const27 {28 return it.iterator == iterator;29 }30 31 bool operator!=(const TSelf& it)const32 {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*()const33 {34 return *iterator;35 }36 37 bool operator==(const TSelf& it)const38 {39 return it.iterator == iterator;40 }41 42 bool operator!=(const TSelf& it)const43 {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*()const23 {24 return *iterator;25 }26 27 TSelf& operator++()28 {29 if (++current == count)30 {31 iterator = end;32 }33 else34 {35 ++iterator;36 }37 return *this;38 }39 40 bool operator==(const TSelf& it)const41 {42 return iterator == it.iterator;43 }44 45 bool operator!=(const TSelf& it)const46 {47 return iterator != it.iterator;48 }49 };
与 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 和 扩展方法,就显得很优雅了。
测试代码如下:
{ 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 }
最后的最后,就是测试代码了!
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++,大家有想法可以提出来一起探讨一下,一起进步!
(完)
联系客服