std :: deque內存使用

Question

我已經實現了一個簡單的統計引擎來使用deque返回滾動均值和方差來提供數據隊列。

該deque構造的條目數量等於滾動數值。

當新值到達時，最早的值被彈出前面，新的值被推到後面。

我需要確定這不會在內存中增長，因爲它預計會長時間作爲後臺任務運行。

Deque是否在堆中分配使用？ 有沒有可以用來修復尺寸的標誌？

我上RHEL 5.3

Answer 1

基本上採用G ++ 4.1.2，任何動態大小的容器中從堆中分配內存。另一個問題提供了一個overview over the implementation of the deque。

但在您的特定情況下，隊列始終具有相同的大小。如果遇到問題，可以使用固定大小的陣列上的circular buffer實現簡單的固定大小隊列。這個實現應該具有更好的內存行爲（因爲它永遠不需要重新分配）。如果沒有分析數據，它的優勢是否值得實施的麻煩很難評估。

Answer 2

該規範將實施細節留給供應商。但是，由於兩端的插入是有效的，所以它很可能作爲堆上的鏈接結構來實現。這就是說，當你從堆中彈出某些東西時，它應該被解構，所以你的總內存使用量不應該增加。

Answer 3

就像一個提示，如果你不需要跟蹤值，那麼這個非常輕量級的算法是非常重要的（我甚至在8位微型計算機上使用它）並且是準確的。

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; 
}; 

這種算法是由B. P.維爾福德創建，並在計算機程序設計，第2卷，第232頁，第3版的高德納的藝術呈現。

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