Crash inside 'accumulators::median' for p_square_cumulative_distribution

[Jeevaka Dassanayake <jeevaka0@…>]

Code to reproduce is below. Also I looked at the code in median.hpp and commented on the relevant lines below.

accumulator_set<double, stats<tag::p_square_cumulative_distribution, tag::median(with_p_square_cumulative_distribution)>> m_HistogramAccumulator( tag::p_square_cumulative_distribution::num_cells = 5 );

m_HistogramAccumulator( 1566 );

m_HistogramAccumulator( 1345 );

cout << accumulators::median( m_HistogramAccumulator ) << endl;

---

median.hpp line 151 – 158 (boost 1_45_0):

range_type histogram = p_square_cumulative_distribution(args);

typename range_type::iterator it = histogram.begin();

while (it->second < 0.5)

{

++it;

}

float_type over = numeric::average(it->second - 0.5, it->second - (it - 1)->second);

this->median = it->first * over + (it + 1)->first * ( 1. - over );

1) If the very first bin in the histogram has a density of 0.5 or more then the ‘while’ loop does not get executed at all and ‘it’ is still pointing to the ‘begin()’ when the code try to compute the local variable ‘over’. However this computation involves ‘(it – 1)’ and in this specific scenario it will try to decrement the iterator beyond ‘begin’ and access an element. This causes a crash.

2) Also I suspect that there is a small computation bug unrelated to the crash in the last line. It is using ‘(it+1)’ instead of ‘(it-1)’ in the last line. It seems like it should interpolate between the current element and the previous one, but it is interpolating between the current element and the next one.

[Eric Niebler]

Matthias, is (1) a case where asking for the result too soon violates this accumulator's precondition, or is this a legitimate use? Also, can you check out (2)? I don't have the expertise here to say.

[ojford@…]

Tested with the latest develop checkout and this is no longer an issue. Code now produces "1345". Ticket can be closed.