...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

boost::accumulators::impl::p_square_quantile_impl — Single quantile estimation with the algorithm.

template<typenameSample,typenameImpl>structp_square_quantile_impl {// typestypedefnumeric::functional::average< Sample, std::size_t >::result_type float_type;typedefarray< float_type, 5 > array_type;typedeffloat_type result_type;// construct/copy/destructtemplate<typenameArgs> p_square_quantile_impl(Argsconst&);// public member functionstemplate<typenameArgs>voidoperator()(Argsconst&) ; result_type result(dont_care)const; };

The algorithm estimates a quantile dynamically without storing samples. Instead of storing the whole sample cumulative distribution, only five points (markers) are stored. The heights of these markers are the minimum and the maximum of the samples and the current estimates of the -, - and -quantiles. Their positions are equal to the number of samples that are smaller or equal to the markers. Each time a new samples is recorded, the positions of the markers are updated and if necessary their heights are adjusted using a piecewise- parabolic formula.

For further details, see

R. Jain and I. Chlamtac, The P^2 algorithmus fordynamic calculation of quantiles and histograms without storing observations, Communications of the ACM, Volume 28 (October), Number 10, 1985, p. 1076-1085.