test.cpp

// list::begin
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <random>
#include <functional>

int main ()
{
    // First create an instance of an engine.
    std::random_device rnd_device;
    // Specify the engine and distribution.
    std::mt19937 mersenne_engine(rnd_device());
    std::uniform_int_distribution<size_t> dist(1, 1000);

    auto gen = std::bind(dist, mersenne_engine);
    
  const std::size_t numberElements = 100;
  const std::size_t numberBins = 10;
  std::vector<size_t> mylist (numberElements, 0);
  std::generate(mylist.begin(), mylist.end(), gen);
//   std::iota(mylist.begin(), mylist.end(), 0);
//   std::random_shuffle(mylist.begin(), mylist.end());
  std::vector<size_t> bins(numberBins, 0);
  std::vector<size_t> naive(numberBins, 0);
  
  std::size_t counter = 0;
  for(auto it=mylist.begin(); it != mylist.end(); ++it, ++counter)
  {
  	naive[counter/numberBins] += *it;
  }

  std::sort(mylist.begin(), mylist.end());
  bool reverse = false;
  counter = 0;
  for (auto it=mylist.begin(); it != mylist.end(); ++it, ++counter)
  {
    const std::size_t modulo = counter % numberBins;
    if(!reverse)
    {
        bins[modulo] += *it;
        if(modulo == numberBins-1)
            reverse = true;
    }
    else
    {
        const std::size_t idx = numberBins-1-modulo;
        bins[idx] += *it;
        if(idx == 0)
            reverse = false;
    }
    
  }

    std::cout << "My list\n";
    for(const auto i : mylist)
        std::cout << i << " ";
  std::cout << '\n';
  
      std::cout << "bins\n";
    for(const auto i : bins)
    {
        std::cout << i << "\n";
    }
    
    std::cout << "Naive\n";
    for(const auto i : naive)
    {
        std::cout << i << "\n";
    }
    
    double sum = std::accumulate(bins.begin(), bins.end(), 0.0);
    double mean = sum / numberBins;
    std::vector<double> diff(numberBins,0);
    std::transform(bins.begin(), bins.end(), diff.begin(), [mean](double x) { return x - mean; });
    double sq_sum = std::inner_product(diff.begin(), diff.end(), diff.begin(), 0.0);
    double variance = sq_sum / numberBins;
    std::cout << "stddev bins " << std::sqrt(variance) << std::endl;
    
    sum = std::accumulate(naive.begin(), naive.end(), 0.0);
    mean = sum / numberBins;
    std::transform(naive.begin(), naive.end(), diff.begin(), [mean](double x) { return x - mean; });
    sq_sum = std::inner_product(diff.begin(), diff.end(), diff.begin(), 0.0);
    variance = sq_sum / numberBins;
    std::cout << "stddev naive " << std::sqrt(variance) << std::endl;

  return EXIT_SUCCESS;
}