Re: [boost] Median in Boost.Accumulators

Subject: Re: [boost] Median in Boost.Accumulators
From: Bjorn Reese (breese_at_[hidden])
Date: 2018-09-23 14:29:04

On 09/23/18 04:21, Lakshay Garg via Boost wrote:

> I rolled up my custom implementation of the algorithm and
> used it for my project. I wanted to check if people on
> this list might be interested in such an implementation
> for Boost.Accumulators in which case I can try to adapt my
> implementation and send a PR.

Boost.Accumulators does not seem to be actively maintained.

> Performance characteristics: For a stream of n numbers, the
> memory required is O(n). Median can be queried at any point
> of time in O(1) and adding all the elements costs O(nlog(n))

Sounds like you keep two ordered lists (e.g. std::set) of equal size.
Then the median is the first element in the second list.