Добавление целых чисел в массивы на С++?

Рассмотреть возможность:

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+1, учитывая, что numbers[] является массивом int, и вы не должны иметь возможность добавлять целое число к константе int[]?


person Krzysztof Podsiadło    schedule 28.03.2016    source источник
comment
Это код Си. Использование рекурсивной функции для вычисления суммы массива — действительно наихудший пример, который они могли выбрать. Кто пишет такие примеры? Рекурсивную функцию лучше всего использовать в обязательно рекурсивном алгоритме.   -  person tadman    schedule 28.03.2016
comment
Здесь const int numbers[] совпадает с const int* numbers: неконстантный указатель на постоянные значения.   -  person    schedule 28.03.2016
comment
@tadman по какой-то причине в некоторых компиляторах, если они обнаруживают хвостовую рекурсию, они генерируют более быстрый код, чем для цикла. Тем не менее, я согласен, что это не легкое чтение.   -  person Tom Tanner    schedule 28.03.2016
comment
@TomTanner Мне бы очень хотелось увидеть некоторые тесты для этого, потому что для меня это звучит как городская легенда.   -  person tadman    schedule 28.03.2016
comment
@TomTanner Здесь это не имеет особого значения, потому что этот пример не является хвостовой рекурсией.   -  person Random832    schedule 28.03.2016
comment
@ Random832: Хотя преобразование в хвостовую рекурсию достаточно простое, некоторые оптимизаторы делают это автоматически.   -  person Ben Voigt    schedule 28.03.2016
comment
это нетривиальное преобразование в хвостовую рекурсию, потому что оно должно учитывать, что + является ассоциативной операцией.   -  person Luka Rahne    schedule 29.03.2016


Ответы (5)


как работает «число + 1», учитывая, что числа [] являются массивом int, и вы не должны иметь возможность добавлять целое число к константе int []?

Не существует int[] константы. numbers затухает до указателя, а numbers+1 представляет собой простую арифметику указателя, применяемую к параметру, переданному рекурсивному вызову.

person πάντα ῥεῖ    schedule 28.03.2016
comment
numbers распадается на указатель. Нет, это не так. Он объявлен как указатель. Последовательность токенов const int numbers[], когда она появляется в списке формальных параметров, объявляет указатель, а не массив. - person Ben Voigt; 28.03.2016
comment
Из 8.3.5p5: Тип функции определяется по следующим правилам. Тип каждого параметра (включая пакеты параметров функции) определяется его собственным decl-specifier-seq и declarator . После определения типа каждого параметра любой параметр типа «массив T» или «функция, возвращающая T» настраивается как «указатель на T» или «указатель на функцию, возвращающую T» соответственно. - person Ben Voigt; 28.03.2016
comment
@BenVoigt Я чувствую, что πάντα ῥεῖ говорит, что numbers распадается на int*, чтобы перейти в int sum(const int numbers[], const int size). Если вы не согласны с этим, возможно, вам следует ответить отдельно, иллюстрируя разграничение. - person Jonathan Mee; 28.03.2016
comment
@JonathanMee: Возможно, первоначальный нерекурсивный вызов sum имел реальный массив, который распался, чтобы передать параметр указателя. Но numbers сам по себе не является массивом, это указатель, даже несмотря на то, что использовалась нотация объявления массива из-за процитированного мной правила настройки (оно существует для обратной совместимости с C89). - person Ben Voigt; 28.03.2016
comment
@BenVoigt прав. numbers - параметр функции - не является массивом, поэтому неявно не преобразуется (распадается) в указатель. Это всегда был указатель. - person Daniel Jour; 29.03.2016
comment
@DanielJour Итак, моя интерпретация ответа πάντα ῥεῖ заключается в том, что массив, переданный в функцию, распался до того, как он был передан в sum. Таким образом, при жизни sum numbers является int*. Все ли мы согласны с этим? - person Jonathan Mee; 29.03.2016
comment
@JonathanMee Конечно, это в std (13.1.3): Объявления параметров, которые отличаются только указателем *, и массивом [] эквивалентны. То есть объявление массива корректируется, чтобы стать объявлением указателя. В типах параметров важны только второе и последующие измерения массива - person Chris A; 29.03.2016

В качестве примечания к ответу @πάντα ῥεῖ приведем несколько пояснений по терминологии:

Ниже приведен еще один способ изобразить нотацию массива:

Фраза numbers[1] также может быть выражена как *(numbers + 1), где говорится, что оператор * разыменовывает адрес указателя numbers + 1. В этом случае разыменование можно рассматривать как чтение значения, на которое указывает.

Итак, код в вашем примере использует арифметика указателей. Фраза numbers + 1 представляет собой нотацию указателя, указывающую на второе место int указателя numbers. size - 1 — это количество байтов от ячейки памяти, начиная с numbers до конца массива.

Что касается значения decayed:
Как правило, в контексте аргументов массива C decay передает идею о том, что аргумент массива испытывает потерю информации о типе и размерности. Говорят, что ваш const int numbers[] (возможно) распадается в int *, поэтому больше не может предоставлять информацию о размере массива. (Например, использование макроса sizeof() обеспечивает не длину массива, а размер указателя.) Это также является причиной предоставления второго аргумента для передачи информации о размере.

Однако в контексте этого вопроса значение распада является академическим, как указал @Ben Voigt: последовательность токенов const int numbers[], когда он появляется в списке формальных параметров, объявляет указатель, а не массив. (Он никогда не распадался на указатель, потому что он был указателем с самого начала.)

person ryyker    schedule 28.03.2016
comment
Я собирался поднять этот вопрос, но затем нашел некоторую информацию здесь Итак, C/C++ достаточно умен, чтобы выяснить фактический адрес, учитывая тип массива? Например, если numbers находится в месте C00, то numbers+1 на самом деле не C01, а C04, потому что int имеет длину 4 байта? Я был немного удивлен, что вам не нужно было делать numbers+1*sizeof(int) или что-то в этом роде. - person Celeritas; 29.03.2016
comment
@Celeritas - LOL, угнать? мне стоит бояться? :) Значит, C/C++ достаточно умен, чтобы вычислить фактический адрес, учитывая тип массива?. Правда, когда указатель передается в качестве аргумента, прототип функции передает информацию о типе этого указателя. Относительно: тогда числа+1 на самом деле не C01, а C04. Да, если в этой реализации определено целое число, имеющее 32 бита. Часто это так, но не всегда. Адрес изменяется приращением (или уменьшением) типа переменной, с которым он связан, однако этот тип переменной определен. - person ryyker; 29.03.2016
comment
Думаю, я удивлен, что C/C++ достаточно дружелюбен/достаточно умен, чтобы делать это автоматически. - person Celeritas; 30.03.2016

Как говорит πάντα ῥεῖ 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, однако sum исчерпал место в стеке, прежде чем я смог достичь размера vector со значимой разницей, что сделало accumulate явным победителем.


Я связываю тип init аргумента accumulate с типом элементов numbers': decay_t<decltype(numbers[0])>{}. Причина этого в том, что если кто-то вернется и изменит тип numbers, а не изменит тип аргумента init accumulate, накопление будет присвоено неправильному типу.

Например, если мы используем линию накопления: cout << accumulate(cbegin(numbers), cend(numbers), 0), это нормально для int numbers[]. Проблема возникла бы, если бы мы переключились на определение: double numbers[] = {1.3, 2.3, 3.3, 4.3};, но не смогли изменить аргумент init, мы бы суммировали doubles в int. В результате получится 10, а не 11,2: http://ideone.com/A12xin.

person Jonathan Mee    schedule 28.03.2016
comment
Да, потому что decay_t<decltype(numbers[0])> супервыразителен и прост для понимания. ВОТ С++! - person Lightness Races in Orbit; 28.03.2016
comment
@BarryTheHatchet Я предполагаю, что ваш комментарий был саркастическим, потому что, на мой взгляд, распад_t‹decltype(numbers[0])› нелегко понять. И, конечно, мы могли бы использовать 0, так как мы знаем, что numbers является int[], но использование decay_t<decltype(numbers[0])>{} оставляет эту строку независимой от типа numbers, что хорошо, например, если бы она была изменена на float numbers[size], мне не пришлось бы менять эту строку. чтобы убедиться, что я добавляю floats вместо ints. - person Jonathan Mee; 28.03.2016
comment
Крайне саркастичен. С++ ужасен. - person Lightness Races in Orbit; 28.03.2016
comment
@BarryTheHatchet: Да, если вы не пытаетесь намеренно запутать свой код (что, ИМХО, является единственным обоснованием примерно 2/3 «функций» С++), используйте цикл for. - person jamesqf; 28.03.2016
comment
@BarryTheHatchet Ой, я похож на это замечание. Это был лучший известный мне способ связать тип. Я отправил вопрос, чтобы узнать, знает ли кто-нибудь лучший способ: stackoverflow.com/questions/36268132/ - person Jonathan Mee; 28.03.2016
comment
@jamesqf Я не уверен, что еще доступно в строго типизированных языках. Возможно, есть пример из другого языка, как связать тип менее запутанным способом? - person Jonathan Mee; 28.03.2016
comment
@JonathanMee Вы похожи на это замечание? Я что-то неправильно понимаю или это должно быть возмущено этим замечанием? - person James Adkison; 28.03.2016
comment
@JonathanMee: я в замешательстве; минуту назад вы, казалось, соглашались со мной. - person Lightness Races in Orbit; 28.03.2016
comment
@JamesAdkison: Это обычная, юмористическая, преднамеренная ошибка. - person Lightness Races in Orbit; 28.03.2016
comment
@JamesAdkison Как человек, чья лошадь привязана к телеге С++, я иду туда, куда он идет; таким образом: Я похож на это замечание - person Jonathan Mee; 28.03.2016
comment
@BarryTheHatchet Хорошо, тогда я не понял. Спасибо тебе за пояснение. - person James Adkison; 28.03.2016
comment
@JonathanMee Спасибо за разъяснения. - person James Adkison; 28.03.2016
comment
@BarryTheHatchet Я действительно согласен с вами. Это намного сложнее читать, чем просто ассоциировать с типом элементов number. Мой связанный вопрос надеялся на некоторую ясность. - person Jonathan Mee; 28.03.2016
comment
Почитав про decay_t у меня вопрос, а так ли он нужен в данном случае? Или это просто мера безопасности на случай, если массив не содержит простых int? Какая разница, какой распад может быть необходим? Дело в том, что С++ не будет обнулять значения lvalue? Язык может быть сложным. - person Felix Dombek; 28.03.2016
comment
@FelixDombek Я мог бы использовать remove_extent_t вместо decay_t если бы я знал, что он определен: int numbers[]. Но decay_t справится, если я работаю с константами или ссылками, а также вызову remove_extent для типа numbers. - person Jonathan Mee; 28.03.2016
comment
Разве экстент уже не удален, потому что вы делаете decltype(numbers[0]), то есть элемент в массиве, у которого нет экстента? - person Felix Dombek; 28.03.2016
comment
@FelixDombek Хорошо сказано, сэр. Оказывается, я могу забыть обо всем, что делал, за 3 часа. Да, единственная причина, по которой мне нужно использовать decay_t, заключается в том, что оператор индекса массива возвращает ссылку. - person Jonathan Mee; 28.03.2016
comment
@Jonathan Mee: Строго напечатано? Вы суммируете массив целых чисел, зачем вам ассоциировать с ним тип, кроме как объявить, что ваш массив имеет тип int? - person jamesqf; 29.03.2016
comment
Есть ли какая-то причина, по которой вы избегали accumulate( numbers, numbers + size, 0 ) в первом примере? - person M.M; 29.03.2016
comment
@M.M Да, чтобы не зависеть от типа элементов numbers. Если вы используете 0 в качестве параметра init для accumulate, вы определили аккумулятор как int. Это приведет к потенциально неправильным результатам в том случае, если numbers является числом с плавающей запятой или unsigned. Например, желаемый результат здесь должен быть 11,2, но использование аргумента 0 приводит к результату 10: ideone.com/A12xin Единственный способ сделать accumulate независимым от типа numbers — это связать тип его аккумулятора. Отсюда: decay_t<decltype(numbers[0])>{} - person Jonathan Mee; 29.03.2016
comment
@jamesqf Связывание типа аргумента init accumulate с типом numbers необходимо для получения правильного результата. Вот пример того, что произойдет, если кто-то просто заменит double numbers[], оставив аргумент accumulate вместо 0, вы бы хотели 11,2, но вы получите 10. Крайне маловероятно, что кто-то, вернувшись, чтобы изменить тип numbers, не забудет также изменить тип аккумулятора. Ассоциирование типа предотвращает такие проблемы. Отсюда: decay_t<decltype(numbers[0])>{} - person Jonathan Mee; 29.03.2016
comment
@Jonathan Mee: Но быть минимально компетентным программистом также предотвращает подобные вещи. Я имею в виду, что вместо того, чтобы возиться с накоплением или чем-то еще, вы просто выполняете простой цикл for, чтобы добавить их. - person jamesqf; 29.03.2016

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;
}

Он быстрее, компактнее и устойчив к ошибкам.

person Arif Burhan    schedule 29.03.2016
comment
@TomTanner говорит, что некоторые компиляторы, если они обнаруживают хвостовую рекурсию, генерируют более быстрый код, чем для цикла. Итак, когда вы говорите, что ваш код работает быстрее, вы засекали время? - person Jonathan Mee; 29.03.2016
comment
Я обновил свой ответ с помощью сравнительного анализа и уверен, что ваше более быстрое утверждение ложно. Я не могу достичь статистической разницы между любым из этих решений без нехватки места в стеке. Другими словами, компилятор превращает их всех в одно и то же решение. - person Jonathan Mee; 29.03.2016
comment
@Jonathan Mee: Можем ли мы сказать не медленнее, а быстрее? Я ожидаю, что хороший компилятор (во всяком случае, в архитектуре Intel) будет эффективно распараллеливать эту конструкцию с инструкциями SSE. Также помните, что если мы говорим о больших массивах, важно время чтения из памяти, и, как правило, линейное чтение выполняется быстрее. И независимо от скорости выполнения, это чертовски легче понять, чем любую альтернативу. - person jamesqf; 29.03.2016

числа - это указатель; на каждой итерации функция sum() продвигается по массиву (это то, что делает numbers+1), в то же время уменьшая размер на 1 (--size будет работать точно также).

Когда размер достигает 0, это условие выхода, и рекурсия заканчивается.

person Arif Burhan    schedule 29.03.2016
comment
Попробуйте объединить свои ответы в один ответ. - person Jonathan Mee; 29.03.2016