Понимание STD :: накопить

Я хочу знать почему std::accumulate (иначе уменьшить) 3-й параметр необходим. Для тех, кто не знает что 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());

Это будет работать для любой операции. Зачем вообще нужен третий параметр?

29

Решение

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

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

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

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

8

Другие решения

Вы делаете ошибочное предположение: этот тип 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's 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's 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's 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 подходит для любого времени, когда вы перебираете входной диапазон, и наращивание один единственный результат в этом диапазоне. Но результат не обязательно должен быть того же типа, что и диапазон, и вы не можете делать какие-либо предположения о том, какое начальное значение использовать — именно поэтому у вас должен быть начальный экземпляр для использования в качестве результата накопления.

21

Если бы вы хотели 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
});
3

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

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

2

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

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

0
По вопросам рекламы [email protected]