проблема написания простой обобщенной функции STL - PullRequest
Новая
       36

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

1 голос
/ 22 июля 2010

Я самостоятельно изучаю, как создавать универсальные функции с использованием итераторов. В качестве шага 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> > >)’

Спасибо!

Ответы [ 3 ]

3 голосов
/ 22 июля 2010

  1. Вы можете использовать iterator_traits<It>::difference_type вместо int, чтобы быть уверенным, что оно не переполняется.Это тип, возвращаемый 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;
}
2 голосов
/ 22 июля 2010

Это должен быть комментарий, но комментарии не позволяют форматировать код. И я думаю, что это должно быть по крайней мере педагогическим. Пожалуйста, обратитесь к документации 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 может быть расширен для поддержки более сложных схем суммирования, таких как алгоритм суммирования Кахана , который уменьшает ошибку округления (существует множество таких алгоритмов, некоторые из которых полностью устраняют ее) .

2 голосов
/ 22 июля 2010

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

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

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

Специализация шаблона не может определить тип возвращаемого значения 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;
}
...