找出std::vector中所有元素的和的好方法是什么?
假设我有一个向量std::vector<int> vector,其中有几个元素。现在我要求所有元素的和。同样的东西有什么不同的表达方式?
找出std::vector中所有元素的和的好方法是什么?
假设我有一个向量std::vector<int> vector,其中有几个元素。现在我要求所有元素的和。同样的东西有什么不同的表达方式?
当前回答
prason已经提供了许多不同的(而且很好的)方法来做到这一点,这里没有一个需要重复。不过,我想建议另一种提高速度的方法。
如果你要经常这样做,你可能想要考虑“子类化”你的vector,这样元素的和就被分开维护(实际上不是子类化vector,因为缺少虚析构函数而存在问题——我说的更多的是一个包含和和和的类,has-a而不是is-a,并提供类似vector的方法)。
对于空向量,和设为零。每次插入向量时,将插入的元素加到和中。在每次删除时,减去它。基本上,任何可能改变底层向量的东西都会被拦截,以确保总和保持一致。
这样,您就有了一个非常有效的O(1)方法来“计算”任何时间点的和(只返回当前计算的和)。插入和删除将花费稍长的时间来调整总数,您应该考虑到这种性能影响。
如果向量的和比向量的改变更频繁,那么这些向量可能会从这个方案中受益,因为计算和的成本会在所有访问中摊销。显然,如果你只需要每小时求和,而向量每秒变化3000次,这是不合适的。
这样就足够了:
class UberVector:
private Vector<int> vec
private int sum
public UberVector():
vec = new Vector<int>()
sum = 0
public getSum():
return sum
public add (int val):
rc = vec.add (val)
if rc == OK:
sum = sum + val
return rc
public delindex (int idx):
val = 0
if idx >= 0 and idx < vec.size:
val = vec[idx]
rc = vec.delindex (idx)
if rc == OK:
sum = sum - val
return rc
显然,这是伪代码,您可能希望有更多的功能,但它显示了基本概念。
其他回答
prason已经提供了许多不同的(而且很好的)方法来做到这一点,这里没有一个需要重复。不过,我想建议另一种提高速度的方法。
如果你要经常这样做,你可能想要考虑“子类化”你的vector,这样元素的和就被分开维护(实际上不是子类化vector,因为缺少虚析构函数而存在问题——我说的更多的是一个包含和和和的类,has-a而不是is-a,并提供类似vector的方法)。
对于空向量,和设为零。每次插入向量时,将插入的元素加到和中。在每次删除时,减去它。基本上,任何可能改变底层向量的东西都会被拦截,以确保总和保持一致。
这样,您就有了一个非常有效的O(1)方法来“计算”任何时间点的和(只返回当前计算的和)。插入和删除将花费稍长的时间来调整总数,您应该考虑到这种性能影响。
如果向量的和比向量的改变更频繁,那么这些向量可能会从这个方案中受益,因为计算和的成本会在所有访问中摊销。显然,如果你只需要每小时求和,而向量每秒变化3000次,这是不合适的。
这样就足够了:
class UberVector:
private Vector<int> vec
private int sum
public UberVector():
vec = new Vector<int>()
sum = 0
public getSum():
return sum
public add (int val):
rc = vec.add (val)
if rc == OK:
sum = sum + val
return rc
public delindex (int idx):
val = 0
if idx >= 0 and idx < vec.size:
val = vec[idx]
rc = vec.delindex (idx)
if rc == OK:
sum = sum - val
return rc
显然,这是伪代码,您可能希望有更多的功能,但它显示了基本概念。
这很简单。c++ 11提供了一种简单的方法来对一个向量的元素求和。
sum = 0;
vector<int> vec = {1,2,3,4,5,....}
for(auto i:vec)
sum+=i;
cout<<" The sum is :: "<<sum<<endl;
我是一个Perl用户,我们有一个游戏是找到各种不同的方法来增加一个变量…这里没有什么不同。在c++中,有多少种方法可以求出一个向量元素的和,答案可能是无穷大……
我的观点是:
使用BOOST_FOREACH,摆脱丑陋的迭代器语法:
sum = 0;
BOOST_FOREACH(int & x, myvector){
sum += x;
}
在索引上迭代(非常容易阅读)。
int i, sum = 0;
for (i=0; i<myvector.size(); i++){
sum += myvector[i];
}
另一个是破坏性的,像访问堆栈一样访问vector:
while (!myvector.empty()){
sum+=myvector.back();
myvector.pop_back();
}
#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main() {
vector<int> v = {2,7,6,10};
cout<<"Sum of all the elements are:"<<endl;
cout<<accumulate(v.begin(),v.end(),0);
}
使用inclinclve_scan (c++ 17及以上):
这样做的好处是可以得到一个向量中前“N”个元素的和。下面是代码。在评论中解释。
要使用inclinclve_scan,需要包含“numeric”标头。
//INPUT VECTOR
std::vector<int> data{ 3, 1, 4, 1, 5, 9, 2, 6 };
//OUTPUT VECTOR WITH SUMS
//FIRST ELEMENT - 3
//SECOND ELEMENT - 3 + 1
//THIRD ELEMENT - 3 + 1 + 4
//FOURTH ELEMENT - 3 + 1 + 4 + 1
// ..
// ..
//LAST ELEMENT - 3 + 1 + 4 + 1 + 5 + 9 + 2 + 6
std::vector<int> sums(data.size());
//SUM ALL NUMBERS IN A GIVEN VECTOR.
inclusive_scan(data.begin(), data.end(),
sums.begin());
//SUM OF FIRST 5 ELEMENTS.
std::cout << "Sum of first 5 elements :: " << sums[4] << std::endl;
//SUM OF ALL ELEMENTS
std::cout << "Sum of all elements :: " << sums[data.size() - 1] << std::endl;
还有一种重载,可以指定执行策略。顺序执行或并行执行。需要包括“执行”头。
//SUM ALL NUMBERS IN A GIVEN VECTOR.
inclusive_scan(std::execution::par,data.begin(), data.end(),
sums.begin());
使用reduce:
我在答案中没有注意到的另一个选项是使用c++17中引入的std::reduce。
但是你可能会注意到很多编译器不支持它(GCC 10以上可能就不错了)。但最终支持会来的。
使用std::reduce,优势在于使用执行策略。指定执行策略可选。当指定执行策略为std::execution::par时,算法可能会使用硬件并行处理能力。当使用大尺寸向量时,增益可能会更明显。
例子:
//SAMPLE
std::vector<int> vec = {2,4,6,8,10,12,14,16,18};
//WITHOUT EXECUTION POLICY
int sum = std::reduce(vec.begin(),vec.end());
//TAKING THE ADVANTAGE OF EXECUTION POLICIES
int sum2 = std::reduce(std::execution::par,vec.begin(),vec.end());
std::cout << "Without execution policy " << sum << std::endl;
std::cout << "With execution policy " << sum2 << std::endl;
std::reduce需要<numeric>报头。 和'<execution>'用于执行策略。