If all you care about is a windowed average you can implement the fps counter (really you keep track of seconds per frame) using an exponential moving average which has constant time and space complexity regardless of window size. The calculation you do once a frame is:

spf_avg = alpha * cur_spf + (1.0f - alpha) * spf_avg;

For alpha value you can use the formula:

alpha = 2/(n+1)

Which will give smoothing comparable to an n sample moving average. This is the same formula used for n-day exponential moving averages for stocks.

As the article points out, this is a sample based window which is not as good as a time based window, but it's also dead simple to implement. Maybe someone smarter than me knows how to derive a formula for exponential moving average for time based windows.