編寫簡單STL通用函數的問題

Question

我自學瞭如何使用迭代器創建通用函數。作爲世界您好一步，我寫了一個函數來取均值在給定的範圍和返回值：

// 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爲計數器OK，可以嗎溢出如果數據太長？

我打電話給我的功能從以下測試工具：

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不是int，以確保它不會溢出。這是std::distance返回的類型。

2. 你的編譯錯誤是因爲compilator無法確定類型T

這是因爲compilator僅在函數的聲明看起來第一。如果你只看宣言，你就不知道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?

這很好，除非你想支持超過20億項目的清單。

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可以減少舍入誤差（有許多這樣的算法，其中一些完全消除了它）。