It makes no memory allocation, but a quicksort on every call. Other C++ implementations will probably not help. But if someone knows a trick to calculate percentiles of arbitrary arrays with no sorting, we'll gratefully implement it.
May I suggest P2 quantile estimator? It doesn't require storing whole distribution, instead needs an array with size of 5.
https://www.cse.wustl.edu/~jain/papers/ftp/psqr.pdfA blog has several posts about it, it seems to produce results closer to true quantile:
https://aakinshin.net/posts/p2-quantile-estimator/https://aakinshin.net/posts/mp2-quantile-estimator/https://aakinshin.net/tags/research-p2qe/
