Daily C/C++ Learn By Discovering ——— 探究partial_sum
今天这个文章可能会比较长,因为这里我想整理一下我在学习新东西的过程,如果在这个过程中能够总结一些相关的方法论,或者能够给他人带来启发就更好了。
学习这个东西,我个人还是感觉要有兴趣,有探索的欲望,这样才能不断的向深处挖掘。就像是树盘跟一样,一边向深处挖掘,一边去学习和总结在过程中遇到的一些小的点,这样不断积累,如果有一天,我们有幸读到了一些较为系统性的书,帮助我们整理之前的知识,就可以将这些知识系统化,从而获得比较大的突破,即便是将来的某一天忘掉了一些东西,或者遇到新的东西,也可以根据已有的体系快速的学习。
这篇文章就是来记录,我是如何去探索新的东西,并在这个过程中学习和整理遇到的一切问题。这条根
的主线就是去探究partial_sum
的问题,具体的我会在文后进行总结。
首先是引入,我为什么会遇到这个问题?
源于今天的leetcode每日一题,题目链接
是一个相当常规的题目,我最开始的代码如下
int chalkReplacer(vector<int>& chalk, int k) {
vector<long> sum;
partial_sum(chalk.begin(), chalk.end(), back_inserter(sum), plus<long>{});
k %= sum.back();
return upper_bound(sum.begin(), sum.end(), k) - sum.begin();
}
计算前缀和,然后二分
这里很巧的是我今天就恰好想试一试STL中的partial_sum
,因为之前一直听说,这里就想着也用一下,来简化一下代码
可以看到,虽然原始数组的类型是int,但是我仍然使用了long进行计算和储存
乍一看没什么毛病的代码,但是结果却总是出错。而出错的原因就是在计算partial_sum
的过程中溢出了
我很纳闷,我还特意用了long来储存,为什么会溢出呢?
我去看了cppreference,检查了对应的参数,我还尝试自己定义了函数对象,用于匹配正确的类型计算。
最后我将问题锁定在了中间变量中
在以往的前缀和实现,我们都是这样做的
sum[0] = val[0];
for (i = 1; i < n; i++)
sum[i] = sum[i - 1] + val[i];
但是看了cppreference中的可能的实现,我发现他是这样的
typename std::iterator_traits<InputIt>::value_type sum = *first;
*d_first = sum;
while (++first != last) {
sum = std::move(sum) + *first; // std::move since C++20
*++d_first = sum;
}
他使用了中间变量来储存结果,而这里我们会发现,中间变量这个sum的类型,是iterator_traits<InputIt>::value_type
当然我们可以猜出来,这里的类型就是InputIt
这个迭代器储存的值类型
为了以防万一,我们也可以去看一下具体的定义。当然不出所料,他和我们想的一样,也就是说,对于之前的代码,他的sum的类型是int
但是这里大家也可以想到,他这个是可能的实现,不代表真正的实现吧。于是我就去是libstdc++
中找到了这个代码
template<typename _IIter,
typename _OutputIterator,
typename _BinaryOperation>
_OutputIterator
__parallel_partial_sum_basecase(_IIter __begin, _IIter __end,
_OutputIterator __result,
_BinaryOperation __bin_op,
typename std::iterator_traits <_IIter>::value_type __value)
{
if (__begin == __end)
return __result;
while (__begin != __end)
{
__value = __bin_op(__value, *__begin);
*__result = __value;
++__result;
++__begin;
}
return __result;
}
可以看到,他确实是使用了_IIter的value_type来定义value
那么我们的问题也就可以明确了,中间变量的类型不对导致的溢出
你可能会想,为什么他不用我们刚才展示的第一种方法呢?那样做肯定没错的。
但是注意,我们能够使用下标来访问的前提是随机访问迭代器,而我们在传入参数的时候却是有可能传入普通的前向迭代器的,所以第一种实现要求的条件比较强
然后回过头来看,我们知道了partial_sum不能处理溢出的情况,在探索的过程中我们学习了iterator_traits
嗯,本文结束
但是到这里如果就结束,就显得比较被动了。我们会想到,对于这样的问题,如果我会发现,其他人不会发现吗?如果其他人发现了,那么为什么不去修复呢?
标准库这样实现肯定有他的理由,我们要去探究一下到底为什么他是这样的
其实我是想在stackoverflow上提问的,但是我有幸找到了一个相关的提问,链接
然后在这里,我们有幸看到了前人在修正和实现cpp的过程中的讨论,讨论链接
在这里,我们可以看到前面的部分就是在讨论这个中间变量类型的问题,有的人也认为我们可以显式的指定中间变量的类型,从而得到正确的表现
比如这里Consequently, it appears legitimate to expect that intermediate result being used throughout the accumulation, because it is the natural type of the result.
再比如I agree the paragraph should probably make it explicit what type is being used. I think there's another subtle error in the Effects clause, since dereferencing an input iterator invalidates previous copies, and order of evaluation is unspecified.
但是另一个人提出了他的见解
I'm not personally 100% sure that this should be "fixed", I've used partial_sum where I've assumed this
behaviour, and adding the things in the "output type" would have broken...
I've attached the work-around I personally use to this kind of problem, which is wrapping the iterator in
another iterator which changes the value_type. Feel free to use this code if you like.
他使用了一个wrapper来包装迭代器,从而让partial_sum可以正确使用中间变量的类型
在查阅了这些人在讨论过程中给出的链接后,我最终将问题的解决点锁定到了这里
这里有对C++standard的修正,以及对相关问题的讨论
搜索partial_sum就可以看到
然后我们可以看到对我们的问题的相关的声明
图片貌似有点小,大家可以自己去这个网页看一下
主要的意思就是这里谈到了我们需要使用哪个类型,inputType
或者resultType
他们都有各自的要求,而最终决议的结果是使用了inputType
的原因我认为是语义,因为partial_sum
的意思就是求部分和,他并不像是accumulate那样可以用作归约。所以可以在cppreference中看到这样的话
The type Type1 must be such that an object of type iterator_traits
即便我们是使用不同类型的二元函数在计算,但是这里也要求了输入类型是可以转化到返回类型的
即如果我们在使用之前说的类似第一种方法的实现,函数就更像是一个部分归约,而不是部分和了
同时也可以看到等价的运算是这样的
*(d_first) = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
而非
*(d_first) = *first;
*(d_first+1) = op(*first, *(first+1));
*(d_first+2) = op(op(*first, *(first+1)), *(first+2)));
在加上我们是可以通过传入自定义的迭代器来拓展输出类型的,所以最终选择了用输入类型做中间类型
c++标准中的含义也是类似的,这里最终要求了输出的类型需要转化到输入类型,对应的就是我们在使用中间变量储存。而输入类型转化到输出类型则是储存的要求
从这里也可以看到,各有利弊,inputType只是语义上更有优势
那么这里我们就剩下最后的一个问题了,我们要怎么修正partial_sum
呢
这个是stackoverflow上的代码
template< class Base, class Wider >
struct widen_iter : iterator< input_iterator_tag, Wider > {
Base b;
widen_iter( Base const &inb = Base() ) : b( inb ) {}
Wider operator*() const { return Wider( *b ); }
Wider const *operator->() const { Wider t( *b ), *ta = &t; return ta; }
widen_iter &operator++() { ++ b; return *this; }
widen_iter operator++(int) { widen_iter t = *this; ++ b; return t; }
bool operator==( widen_iter const &r ) const { return b == r.b; }
bool operator!=( widen_iter const &r ) const { return b != r.b; }
};
template< class Wider, class Base >
widen_iter< Base, Wider >
widener( Base b ) { return widen_iter< Base, Wider >( b ); }
可以看到,我们可以自己定义一个输入迭代器,然后我们手动模拟在原始的input类型上的迭代
但是将value_type
设置成宽类型,用来指导中间变量的类型
那么下面就是如何看懂这个代码了
第一步当然就是查看cppreference
幸运的是,里面有我们想要的一切东西,cppreference已经告诉我们怎么去定义一个迭代器了
在这里我们只需要显式的制定Category
和T
,也就是迭代器类别和值类型
这时候就又有一个问题,什么是迭代器类别?
跟着链接点进去就可以发现,就是用来指示我们当前迭代器的种类,比如是输入迭代器,或者输出迭代器等
这里我们是自定义的输入迭代器,所以就用input_iterator_tag
然后我们自己模拟Base类型的迭代器,在我们原本的例子中,Base就是一个数组指针了,或者是一个vector的迭代器
这样在使用iterator_traits
的时候,我们就可以得到宽类型,进而定义一个宽类型的中间变量,就解决了溢出的问题
至此,这个问题也就画上了一个句号,基于已有的知识来产生更多新的知识,便是如此
最后我们总结一下,我们以探究partial_sum
的问题为根向外延伸,在这个过程中,我们学会了iterator_traits
,迭代器类别,如何实现自定义迭代器,看了partial_sum
的源码,浏览了一部分的cpp standard,浏览了cpp演化过程中前人的讨论以及对语义和代码的修正,以及初步的了解了cpp standard相关的一些设计理念,STL设计时候的目的和他想表达的语义。
当然更重要的是这个过程为我们打开了以后探索相关问题的大门,即再有相关类似的问题,我们也可以很快的解决,并在探究问题的过程中学习。
所以如果你已经有了自己的体系,希望这篇文章能够给你一个新的解决问题的思路或方向。如果你还没有形成自己的体系,希望这篇文章可以启发你。
文章评论