проблема с написанием простой общей функции STL

Question

Я самонаучаю, как создавать общие функции с помощью итераторов. В качестве шага Hello World, я написал функцию, чтобы взять среднее значение в заданном диапазоне и возвращает значение:

// It is the iterator to access the data, T is the type of the data. 
template <class It, class T> 
T mean(It begin, It end) 
{ 
    if (begin == end) { 
     throw domain_error("mean called with empty array"); 
    } 

    T sum = 0; 
    int count = 0; 
    while (begin != end) { 
     sum += *begin; 
     ++begin; 
     ++count; 
    } 
    return sum/count; 
} 

Мой первый вопрос: является ли с помощью int для счетчика ОК, может это переполнение, если данные слишком долго?

Звоню функцию из следующего жгута испытания:

template <class It, class T> T mean(It begin, It end); 

int main() { 
    vector<int> v_int; 
    v_int.push_back(1); 
    v_int.push_back(2); 
    v_int.push_back(3); 
    v_int.push_back(4); 

    cout << "int mean = " << mean(v_int.begin(), v_int.begin()) << endl;; 

    return 0; 
} 

Когда я компилирую это я получаю ошибку:

error: no matching function for call to ‘mean(__gnu_cxx::__normal_iterator<int*,  
std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, 
std::vector<int, std::allocator<int> > >)’ 

Спасибо!

Answer 1

1. Вы можете использовать iterator_traits<It>::difference_type вместо междунар, чтобы быть уверенным, что он не переполнение. Это тип, возвращаемый std::distance.

2. Ваша ошибка компиляции, потому что составитель не может определить тип T

Это происходит потому, что составитель смотрит только на описание функции первого. И если вы посмотрите только на объявление, вы не можете знать, что такое T. Как и в первом вопросе, вы можете использовать iterator_traits.

Вы можете, что вы хотите, как это:

template <class It> 
typename std::iterator_traits<It>::value_type mean(It begin, It end) 
{ 
    if (begin == end) { 
     throw domain_error("mean called with empty array"); 
    } 

    typename std::iterator_traits<It>::value_type sum = 0; 
    typename std::iterator_traits<It>::difference_type count = 0; 
    while (begin != end) { 
     sum += *begin; 
     ++begin; 
     ++count; 
    } 
    return sum/count; 
} 

Answer 2

My first question is: Is using int for the counter OK, can it overflow if the data is too long?

Это нормально, если вы не хотите поддерживать список из более чем 2 миллиардов предметов.

When I compile this I get the error:

Специализация шаблона неспособна вывести тип возврата T. Вы должны называть его всеми параметрами шаблона.

mean<vector<int>::const_iterator, double>(v_int.begin(), v_int.begin()) 

---

Кстати, в STL, то accumulate() и distance() функции могут уже вычислить сумму и считать.

#include <numeric> 
#include <iterator> 

template <class It, class T> 
T mean (It begin, It end) { 
    if (begin == end) 
    throw domain_error("mean called with empty array"); 

    T zero = 0; 
    T sum = std::accumulate(begin, end, zero); 
    typename iterator_traits<It>::difference_type count; 
    count = std::distance(begin, end); 
    return sum/count; 
} 

Answer 3

Это должно быть в качестве комментария, но комментарии не позволяют форматирования кода. И я думаю, что это должно быть хотя бы педагогическим. Пожалуйста, обратитесь к документации for_each и unary_function.

Я бы написал так:

#include <algorithm> 
#include <functional> 
#include <iterator> 

template <typename T> 
struct accum : std::unary_function<T, void> 
{ 
    void operator()(T const& x) 
    { count++; acc += x; } 

    // Edited to take care of case count == 0 
    T mean() const 
    { 
     if (count) return acc/count; 
     else throw "Division by zero"; 
    } 

private: 
    size_t count; 
    T acc; 
}; 


template <template Iter> 
typename std::iterator_traits<Iter>::value_type 
mean(Iter begin, Iter end) 
{ 
    typedef typename std::iterator_traits<Iter>::value_type T; 
    return std::for_each(begin, end, accum<T>()).mean(); 
} 

Использование: mean(v.begin(), v.end()).

Это работает, потому что for_each возвращает функтор, который был применен ко всем элементам в последовательности. В нашем случае функтор накапливал результаты, и мы можем получить среднее значение.

Обратите внимание, что функтор accum может быть усилен для поддержки более сложных схем суммирования, таких как Kahan summation algorithm, что уменьшает погрешность округления (существует множество таких алгоритмов, некоторые из которых полностью исключают его).