c++ - 如何使用分治法和迭代器添加所有 vector 元素？

Question

我需要编写一个函数来对 vector 的所有元素求和。规范是它必须通过递归完成，唯一的参数输入是迭代器。函数应该:将 vector 分成两半，在左手边递归，在右手边递归，返回两边的和。我写了下面的代码，但得到的答案不正确。

int sumVectorRecurse(vector<int>::iterator left, vector<int>::iterator right)
{
    if (left != right){
        int midPosition = (right - left)/2;
        vector<int>::iterator mid = left + midPosition;
        return (sumVectorRecurse(left, mid) + sumVectorRecurse(mid+1, right));
    }
    else return *left;
}

int main(){

    vector<int> v = {1,2,3,4};
    cout << endl << "THIS IS QUESTION 4:"<< endl;
    cout << sumVectorRecurse(v.begin(), v.end());

}

更新:直到 {1,2,3,4} 之前， vector 的输出是可以的，但是一旦我向它添加 5 使其成为 {1,2,3,4, 5} 输出为“32782”

Answer 1

您正在取消引用 end 迭代器，这是未定义的行为。

按照惯例，C++ 范围由一对迭代器指定，其中左侧迭代器指向第一项，右侧迭代器指向最后一项之后的一个。通过 begin == end，这允许范围为空。

你的基本情况应该是:

if (left == right) return 0;
if (left + 1 == right) return *left;

然后，将 mid 传递给递归的两半，因为它将包含在后半部分(它是左迭代器)，并在前半部分排除(它是左迭代器)结束迭代器)。

int sumVectorRecurse(vector<int>::iterator left, vector<int>::iterator right)
{
    if (left == right) return 0;
    if (left + 1 == right) return *left;
    int midPosition = (right - left)/2;
    vector<int>::iterator mid = left + midPosition;
    return sumVectorRecurse(left, mid) + sumVectorRecurse(mid, right);
}