在C++中将整数添加到数组中？

Question

考虑：

int sum(const int numbers[], const int size){
    if (size == 0)
        return 0;
    else
        return numbers[0] + sum(numbers+1, size-1);
}

这是MIT 6.096课程中一个简单的递归函数，用于对任意数量的整数进行求和，并且它可以正常运行。

我不理解的是最后一行：

鉴于numbers[]是一个int数组，您不应该能够将整数添加到int[]常量中，那么numbers+1是如何工作的呢？

- Krzysztof Podsiadło

---

这是C代码。使用递归函数来计算数组的总和真的是他们可能选择的最糟糕的示例。谁会写这样的例子呢？递归函数最好用在必要的递归算法上。 - tadman

这里，“const int numbers[]”与“const int* numbers”相同：指向常量值的非常量指针。 - user2249683

@tadman出于某些原因，在一些编译器上，如果它们发现尾递归，它们会生成比循环更快的代码。但是，我同意这不容易阅读。 - Tom Tanner

@TomTanner，我真的很想看到一些基准测试数据，因为对我来说听起来像是一个城市传说。 - tadman

这里并不重要，因为这个例子并不是尾递归的。 - Random832

Answer 1

“numbers+1” 如何工作？给定 numbers [] 是一个 int 数组，你不应该能够将整数添加到 int[] 常量中？

没有 int[] 常量。numbers 衰变为指针，并且 numbers+1 是应用于递归调用传递的参数的简单指针算术。

- πάντα ῥεῖ

---

“numbers”已经退化为指针。不是这样的。它被声明为指针。当令牌序列“const int numbers[]”出现在形式参数列表中时，它声明的是一个指针而不是数组。 - Ben Voigt

从8.3.5p5：函数的类型是根据以下规则确定的。每个参数的类型（包括函数参数包）都是从其自己的decl-specifier-seq和declarator中确定的。确定了每个参数的类型之后，任何类型为“T数组”或“返回T的函数”的参数都将分别调整为“指向T的指针”或“指向返回T的函数的指针”。 - Ben Voigt

@BenVoigt，我觉得πάντα ῥεῖ的意思是numbers会衰减为一个int*，然后传递到int sum(const int numbers[], const int size)中。如果你不同意这一点，也许你应该单独回答并说明界限。 - Jonathan Mee

@BenVoigt 是正确的。numbers - 这个函数参数 - 不是一个数组，因此它不会被隐式转换成指针（"衰减"）。它一直都是一个指针。 - Daniel Jour

@JonathanMee 当然可以，它在std（13.1.3）中：仅在指针*与数组[]之间不同的参数声明是等效的。也就是说，数组声明被调整为成为指针声明。只有第二个及其后续的数组维度在参数类型中是重要的。 - Chris A

Answer 2

作为对 @πάντα ῥεῖ 的回答的补充，这里有一些术语解释:

以下是另一种表示数组符号的方式:

表达式 numbers[1] 还可以表示为 *(numbers + 1)。其中 * 操作符被称为 解引用 偏移量为 numbers + 1 的指针地址。在这种情况下， 解引用 可以理解为 读取指向的值。

因此，您示例中的代码在使用指针算术。表达式 numbers + 1 是指针符号，指向指针 numbers 的第二个 int 位置。size - 1 是从内存位置numbers开始到数组末尾的字节数计数。

至于 "退化" 的含义：
通常，在 C 数组参数 上下文中，decay 表示数组参数丢失了类型和维度信息的概念。您的 const int numbers[] 被认为（有争议地）退化为一个int *，因此不再能提供数组大小信息。 （例如，使用sizeof() 宏不提供数组长度，而是指针的大小。）这也是提供第二个参数的原因，以传达大小信息。

然而，在这个问题的背景下，@Ben Voigt 指出的decay的含义是学术性质的：当 const int numbers[] 这个标记序列出现在形式参数列表中时，它声明了一个指针而非数组。（它从未衰减成指针，因为它一开始就是一个指针。）

- ryyker

---

我本来想抢答这个问题，但后来在这里找到了一些信息（http://www.tutorialspoint.com/cprogramming/c_pointer_arithmetic.htm）。所以C/C++足够聪明，可以根据数组类型找出实际地址？例如，如果“numbers”位于位置“C00”，那么“numbers+1”实际上不是“C01”，而是“C04”，因为一个“int”占4个字节？我有点惊讶，你不需要做“numbers+1*sizeof(int)”之类的事情。 - Celeritas

@Celeritas - 哈哈，劫持？我应该害怕吗？ :) 所以 C/C++ 足够聪明，可以根据数组类型找到实际地址？ 是的，当指针作为参数传递时，函数原型传达了该指针的类型信息。关于：_那么 numbers+1 实际上不是 C01 而是 C04_。是的，如果在该实现中定义了一个具有 32 位的 int。这通常是正确的，但并非总是如此。地址通过与其相关联的 变量类型 的增量（或减量）进行更改，无论该变量类型如何定义。 - ryyker

我想我很惊讶C/C++足够友好/聪明，可以自动完成这个。 - Celeritas

Answer 3

如πάντα ῥεῖ所说，int[]会衰减为int*。

但这个sum函数是穷人的解决方案，你应该更喜欢使用accumulate：

cout << accumulate(numbers, next(numbers, size), decay_t<decltype(numbers[0])>{});

实时例子

如果您拥有C++17和静态分配的数组，例如int numbers[size]，您可以利用cbegin和cend：

cout << accumulate(cbegin(numbers), cend(numbers), decay_t<decltype(numbers[0])>{});

我尝试对递归的sum和accumulate进行基准测试，然而在我能够达到有意义差异的vector大小之前，sum会耗尽堆栈空间，使accumulate成为明显的获胜者。

---

我将accumulate的init参数的类型与numbers的元素类型相关联：decay_t<decltype(numbers[0])>{}。原因是如果有人回来更改numbers的类型，但没有更改accumulate的init参数的类型，则累加会分配给错误的类型。

例如，如果我们使用累加行：cout << accumulate(cbegin(numbers), cend(numbers), 0)，这对于int numbers[]是可以的。如果我们切换到定义：double numbers[] = {1.3, 2.3, 3.3, 4.3};，但我们未能更改init参数，则我们会将double加总为int。这将导致结果为10而不是11.2：http://ideone.com/A12xin。

- Jonathan Mee

---

没问题，decay_t<decltype(numbers[0])>非常具有表现力并且易于理解。C++做得好！ - Lightness Races in Orbit

非常挖苦。C++很糟糕。 - Lightness Races in Orbit

@BarryTheHatchet：是的，除非你有意试图混淆你的代码（在我看来这是C++“特性”的三分之二的唯一理由），否则请使用for循环。 - jamesqf

@JamesAdkison：这是一个常见的、幽默的、故意犯错。 - Lightness Races in Orbit

@FelixDombek 先生说得好。显然我可以在3小时内忘记我所做的一切。是的，我需要使用decay_t的唯一原因是因为数组下标运算符返回一个引用。 - Jonathan Mee

Answer 4

int sum(int *num,int size)
{
int total=0;
                                   /* function to sum integer array */
if (size <= 0) return(ERROR);
while(size--) total+= *num++;
return total;
}

更快、更紧凑且容错性更强。

- Arif Burhan

---

@TomTanner说：“一些编译器，如果它们发现尾递归，会生成比循环更快的代码。”所以当你说你的代码“更快”时，你有计时吗？ - Jonathan Mee

我已经更新了我的答案，添加了基准测试，我确信你的“更快”声明是错误的。我无法在不耗尽堆栈空间的情况下得出这些解决方案之间的任何统计差异。换句话说，编译器将它们全部转化为完全相同的解决方案。 - Jonathan Mee

@Jonathan Mee：我们可以说“不要更慢”而不是“更快”吗？我期望一个好的编译器（在英特尔架构中）能够有效地使用SSE指令并行化该结构。另外请记住，如果我们谈论大数组，则从内存读取时间很重要，并且通常线性读取速度更快。无论执行速度如何，这比任何其他替代方案都容易理解得多。 - jamesqf

Answer 5

numbers是一个指针；在每次迭代中，函数sum()通过数组前进（这就是numbers+1的作用），同时将大小减少1（--size同样有效）。

当大小达到0时，这是退出条件，递归结束。

- Arif Burhan

---

考虑将您的答案合并为一个答案。 - Jonathan Mee