std::deque memory use

Question

I have implemented a simple statistical engine to return rolling mean and variance using a deque to provide a data queue.

The deque is constructed with a number of entries equal to the rolling number of values.

When a new value arrives the oldest value is popped of the front and the new one pushed onto the back.

I need to be sure that this is not going to grow in memory as it is expected to run as a background task for a long time.

Does deque allocate on the heap in use? Are there flags that I can use to fix its size?

I am using G++ 4.1.2 on RHEL 5.3

Answer 1

Essentially, any dynamically sized container allocates memory from the heap. Another question provides an overview over the implementation of the deque.

But in your particular case, the queue always has the same size. If you hit problems with the deque, it might be beneficial to implement a simple fixed-size queue using a circular buffer on a fixed-sized array. This implementation should have fundamentally better memory behaviour (since it never requires reallocation). Whether its advantage is worth the trouble of implementing is hard to assess without profiling data.

Answer 2

Just as a tip, if you don't need to keep track of the values there is this great algorithm that is very lightweight (I even use it on 8bit micros) and is accurate.

 class RunningStat
{
public:
    RunningStat() : m_n(0) {}

    void Clear()
    {
        m_n = 0;
    }

    void Push(double x)
    {
        m_n++;

        // See Knuth TAOCP vol 2, 3rd edition, page 232
        if (m_n == 1)
        {
            m_oldM = m_newM = x;
            m_oldS = 0.0;
        }
        else
        {
            m_newM = m_oldM + (x - m_oldM)/m_n;
            m_newS = m_oldS + (x - m_oldM)*(x - m_newM);

            // set up for next iteration
            m_oldM = m_newM; 
            m_oldS = m_newS;
        }
    }

    int NumDataValues() const
    {
        return m_n;
    }

    double Mean() const
    {
        return (m_n > 0) ? m_newM : 0.0;
    }

    double Variance() const
    {
        return ( (m_n > 1) ? m_newS/(m_n - 1) : 0.0 );
    }

    double StandardDeviation() const
    {
        return sqrt( Variance() );
    }

private:
    int m_n;
    double m_oldM, m_newM, m_oldS, m_newS;
};

This algorithm was created by B. P. Welford and is presented in Donald Knuth's Art of Computer Programming, Vol 2, page 232, 3rd edition.

http://www.johndcook.com/standard_deviation.html