I'm looking for a way to efficiently maintain a set of values from a 1 minute sliding window from a given datastream (~100k values/sec).
I'm looking for solution with at most logarithmic insertion time (since basic time-ordered vector of values has o(n))
Unless I misunderstand your question, this can be done in constant time ( constant per insertion ), with a circular buffer. Allocate a buffer with is a power of 2 length larger than the maximum number of elements in your window. E.g. max 100k values per second 6 million values per minute, so allocate a buffer that is 8388608 bytes long. Keep an absolute index into this buffer, but insert into it, and remove elements from it by masking the index with 0x7FFFFF.