Подтвердить что ты не робот

Понимание std:: accumulate

Я хочу знать, почему нужен std::accumulate (aka reduce) третий параметр. Для тех, кто не знает, что такое accumulate, он используется так:

vector<int> V{1,2,3};  
int sum = accumulate(V.begin(), V.end(), 0);
// sum == 6

Вызов accumulate эквивалентен:

sum = 0;  // 0 - value of 3rd param
for (auto x : V)  sum += x;

Существует также необязательный 4-й параметр, который позволяет заменить дополнение любой другой операцией.

Обоснование, которое я слышал, состоит в том, что если вам нужно позволить сказать, что не складывать, а умножать элементы вектора, нам нужно другое (ненулевое) начальное значение:

vector<int> V{1,2,3};
int product = accumulate(V.begin(), V.end(), 1, multiplies<int>());

Но почему бы не сделать Python - установить начальное значение для V.begin() и использовать диапазон, начинающийся с V.begin()+1. Что-то вроде этого:

int sum = accumulate(V.begin()+1, V.end(), V.begin());

Это будет работать для любого op. Почему необходим третий параметр?

4b9b3361

ОТВЕТЫ

Ответ 1

Как бы то ни было, это раздражает код, который наверняка знает, что диапазон не пуст и хочет начать накапливаться с первого элемента диапазона. В зависимости от операции, которая используется для накопления, не всегда очевидно, что использовать значение "нуль".

Если, с другой стороны, вы предоставляете только версию, которая требует непустых диапазонов, это раздражает для абонентов, которые не знают точно, что их диапазоны не пусты. На них налагается дополнительное бремя.

Одна из перспектив заключается в том, что лучшее из обоих миров, конечно же, обеспечивает обе функции. В качестве примера, Haskell предоставляет как foldl1, так и foldr1 (которые требуют непустых списков) вместе с foldl и foldr (которые отражают std::transform).

Другая перспектива заключается в том, что, поскольку один может быть реализован в терминах другого с тривиальным преобразованием (как вы продемонстрировали: std::transform(std::next(b), e, *b, f) - std::next - это С++ 11, но точка все еще стоит), это предпочтительнее сделать интерфейс минимальным, поскольку он может быть без реальной потери выразительной мощности.

Ответ 2

Вы делаете ошибочное предположение: этот тип T того же типа, что и InputIterator.

Но std::accumulate является общим и допускает все виды творческих накоплений и сокращений.

Пример № 1: накапливать зарплату среди сотрудников

Вот простой пример: класс Employee со многими полями данных.

class Employee {
/** All kinds of data: name, ID number, phone, email address... */
public:
 int monthlyPay() const;
};

Вы не можете осмысленно "накапливать" набор сотрудников. Это не имеет смысла; это не определено. Но вы можете определить накопление в отношении сотрудников. Допустим, мы хотим подвести итоги всех месячных заработных плат всех сотрудников. std::accumulate может сделать это:

/** Simple class defining how to add a single Employee's
 *  monthly pay to our existing tally */
auto accumulate_func = [](int accumulator, const Employee& emp) {
   return accumulator + emp.monthlyPay();
 };

// And here how you call the actual calculation:
int TotalMonthlyPayrollCost(const vector<Employee>& V)
{
 return std::accumulate(V.begin(), V.end(), 0, accumulate_func);
}

Итак, в этом примере мы накапливаем значение int в коллекции объектов Employee. Здесь сумма накопления - это не та переменная, с которой мы на самом деле суммируем.

Пример № 2: накопление среднего

Вы можете использовать accumulate и для более сложных типов накоплений - возможно, захотите добавить значения к вектору; возможно у вас есть какая-то непонятная статистика, которую вы отслеживаете на входе; и т.д. То, что вы накапливаете, не должно быть просто числом; это может быть что-то более сложное.

Например, вот простой пример использования accumulate для вычисления среднего вектора целых чисел:

// This time our accumulator isn't an int -- it a structure that lets us
// accumulate an average.
struct average_accumulate_t
{
    int sum;
    size_t n;
    double GetAverage() const { return ((double)sum)/n; }
};

// Here HOW we add a value to the average:
auto func_accumulate_average = 
    [](average_accumulate_t accAverage, int value) {
        return average_accumulate_t(
            {accAverage.sum+value, // value is added to the total sum
            accAverage.n+1});      // increment number of values seen
    };

double CalculateAverage(const vector<int>& V)
{
    average_accumulate_t res =
        std::accumulate(V.begin(), V.end(), average_accumulate_t({0,0}), func_accumulate_average)
    return res.GetAverage();
}

Пример № 3: накопление скользящего среднего

Еще одна причина, по которой вам нужно начальное значение, заключается в том, что это значение не всегда является значением по умолчанию/нейтральным для вычислений, которые вы делаете.

Давайте построим на среднем примере, который мы уже видели. Но теперь нам нужен класс, который может содержать скользящее среднее, то есть мы можем продолжать вводить новые значения и проверять среднее значение по нескольким вызовам.

class RunningAverage
{
    average_accumulate_t _avg;
public:
    RunningAverage():_avg({0,0}){} // initialize to empty average

    double AverageSoFar() const { return _avg.GetAverage(); }

    void AddValues(const vector<int>& v)
    {
        _avg = std::accumulate(v.begin(), v.end(), 
            _avg, // NOT the default initial {0,0}!
            func_accumulate_average);
    }

};

int main()
{
    RunningAverage r;
    r.AddValues(vector<int>({1,1,1}));
    std::cout << "Running Average: " << r.AverageSoFar() << std::endl; // 1.0
    r.AddValues(vector<int>({-1,-1,-1}));
    std::cout << "Running Average: " << r.AverageSoFar() << std::endl; // 0.0
}

Это тот случай, когда мы абсолютно уверены в возможности установить это начальное значение для std::accumulate - нам нужно иметь возможность инициализировать накопление из разных начальных точек.

Таким образом, std::accumulate подходит для всех случаев, когда вы выполняете итерации по входному диапазону и строите один единственный результат в этом диапазоне. Но результат не обязательно должен быть того же типа, что и диапазон, и вы не можете делать какие-либо предположения о том, какое начальное значение использовать - именно поэтому у вас должен быть начальный экземпляр для использования в качестве результата накопления.

Ответ 3

Если вы хотели accumulate(V.begin()+1, V.end(), V.begin()), вы могли бы просто написать это. Но что, если вы думаете, что v.begin() может быть v.end() (т.е. V пуст)? Что делать, если v.begin() + 1 не реализовано (потому что v только реализует ++, а не генерирует добавление)? Что, если тип аккумулятора не является типом элементов? Например.

std::accumulate(v.begin(), v.end(), 0, [](long count, char c){
   return isalpha(c) ? count + 1 : count
});

Ответ 4

Поскольку стандартные библиотечные алгоритмы должны работать для произвольных диапазонов (совместимых) итераторов. Таким образом, первый аргумент accumulate не должен быть begin(), он может быть любым итератором между begin() и одним перед end(). Он также может использовать обратные итераторы.

Вся идея состоит в том, чтобы отделить алгоритмы от данных. Ваше предложение, если я его правильно понимаю, требует определенной структуры в данных.

Ответ 5

Это действительно не нужно. Наша кодовая база имеет перегрузки с двумя и тремя аргументами, которые используют значение T{}.

Тем не менее, std::accumulate довольно стар; это происходит от оригинального STL. Наша кодовая база имеет причудливую логику std::enable_if, чтобы различать "2 итератора и начальное значение" и "2 итератора и оператор редукции". Это требует С++ 11. Наш код также использует конечный тип возврата (auto accumulate(...) -> ...) для вычисления типа возврата, еще одна особенность С++ 11.