• 1

• 31.7k
• 15
• 77
• 202

(See the previous and initial iteration.)

This time, I use tag dispatching in order to make sure that non-random access iterators are not put into a std::distance, which would take \$\Theta(n)\$ time to complete, but instead, computes the distance while making the only pass over the data. See what I have now:

coderodde_sd.h

#ifndef CODERODDE_SD_H
#define CODERODDE_SD_H
#include <cmath>
#include <iterator>
#include <sstream>
#include <stdexcept>
#define DEBUG
#ifdef DEBUG
#include <iostream>
using std::cout;
#endif
namespace net {
 namespace coderodde {
 namespace stat {
 template<typename RandomAccessIter>
 double sd(RandomAccessIter begin, 
 RandomAccessIter end, 
 std::random_access_iterator_tag)
 {
 #ifdef DEBUG
 cout << "[DEBUG] RandomAccessIter version of sd is "
 "running. ";
 #endif
 auto distance = std::distance(begin, end);
 if (distance < 2)
 {
 std::stringstream ss;
 ss << "The standard deviation cannot be computed for "
 "less than two elements. The input sequence has "
 << distance 
 << (distance == 1 ? " element." : " elements.");
 throw std::runtime_error(ss.str());
 }
 double x = 0.0;
 double x_squared = 0.0;
 for (RandomAccessIter it = begin; it != end; ++it) 
 {
 x += *it;
 x_squared += (*it) * (*it);
 }
 return std::sqrt((x_squared - (x * x) / distance) / 
 (distance - 1)
 );
 }
 template<typename ForwardIter>
 double sd(ForwardIter begin, 
 ForwardIter end, 
 std::forward_iterator_tag) 
 {
 #ifdef DEBUG
 cout << "[DEBUG] ForwardIter version of sd is running. "; 
 #endif 
 double x = 0.0;
 double x_squared = 0.0;
 size_t distance = 0;
 for (ForwardIter iter = begin; iter != end; ++iter) 
 {
 x += *iter;
 x_squared += (*iter) * (*iter);
 ++distance;
 }
 if (distance < 2) 
 {
 std::stringstream ss;
 ss << "The standard deviation cannot be computed for "
 "less than two elements. The input sequence has "
 << distance
 << (distance == 1 ? " element." : " elements.");
 throw std::runtime_error(ss.str());
 }
 return std::sqrt((x_squared - (x * x) / distance) /
 (distance - 1)
 );
 }
 template<typename Iter>
 double sd(Iter begin, Iter end) 
 {
 return sd(begin,
 end, 
 typename std::iterator_traits<Iter>
 ::iterator_category());
 }
 } /* net::coderodde::stat */
 } /* net::coderodde */
} /* net */
#endif /* CODERODDE_SD_H */

main.cpp:

#include <iostream>
#include <list>
#include <vector>
#include "coderodde_sd.h"
using net::coderodde::stat::sd;
using std::cout;
using std::list;
using std::vector;
int main(int argc, char** argv) {
 double bad_array[]{1.0};
 try 
 {
 sd(bad_array, bad_array);
 }
 catch (std::runtime_error& error)
 {
 cout << "ERROR: " << error.what() << "\n";
 }
 try 
 {
 sd(bad_array, bad_array + 1);
 }
 catch (std::runtime_error& error)
 {
 cout << "ERROR: " << error.what() << "\n";
 }
 list<int> my_list = { 1, 5, 2, 4, 3 };
 vector<int> my_vector { 3, 4, 2, 5, 1 };
 int my_array[] = { 2, 4, 5, 3, 1 };
 cout << "Standard deviation (list): " 
 << sd(my_list.begin(), my_list.end())
 << "\n";
 cout << "Standard deviation (vector): "
 << sd(my_vector.begin(), my_vector.end())
 << "\n";
 cout << "Standard deviation (array): "
 << sd(my_array, my_array + sizeof(my_array) / sizeof(*my_array))
 << "\n";
 return 0;
}

Critique request

I want to improve this even more. Please tell me anything that comes to mind.