時間戳組織的容器

以下是我對一些代碼的摘錄。時間戳組織的容器

的HPP：

class message_receiver 
{ 
    struct Chunk 
    { 
     // inits timestamp and other data memebers 
     Chunk(); 
     boost::uint64_t m_timeStamp; 
     bool last; 
     std::vector<std::string> m_message; 
     ... 
    }; 

    struct Compare 
    { 
     bool operator()(const boost::shared_ptr<Chunk> p_left, const 
      boost::shared_ptr<Chunk> p_right) const 
     { 
      return p_left.m_timeStamp > p_right.m_timeStamp; 
     } 
    }; 

    std::vector< boost::shared_ptr<Chunk> > m_chunks; 
    void setTimeStamp(const boost::shared_ptr<Chunk>& p_ca, bool isNew) 
    //other stuff 

};

的CPP：

void message_receiver::setTimeStamp(const boost::shared_ptr<Chunk>& p_ca, bool isNew) 
{ 
    p_ca->m_timeStamp = boost::chrono::duration_cast<boost::chrono::microseconds>(
    boost::chrono::high_resolution_clock::now().time_since_epoch()).count(); 

    if (isNew) 
    { 
     m_chunks.push_back(p_ca); 
     std::push_heap(m_chunks.begin(), m_chunks.end(), Compare()); 
    } 
    else 
    { 
     std::make_heap(m_chunks.begin(), m_chunks.end(), Compare()); 
    } 
}

最終，設置時間戳在一個循環中完成。所以這個函數會被調用很多次，它應該保持所有的時間戳以最小堆的順序排列。

我想保持郵票的最小堆順序，所以最老的時間戳可以在我的向量的前面獲得以獲得。這是用std :: pop_heap完成的（未顯示）。這是與我需要順序訪問的想法完成的。

所以我的第一個問題是在else語句中的std :: make heap調用。應該這樣做嗎？我搜索了一段時間的文檔，除非使用了std :: pop_heap或push堆，否則我沒有看到任何其他方式去修改堆順序，但在一種情況下，我所做的只是更新對象。當我這樣做時，我認爲堆順序可能不會維持？更新後有沒有更好的方法來恢復堆屬性？其次，我意識到，每次更新具有O（n）複雜度的算法的時間戳時，該代碼都會調用min-heapify。這對我的需求來說有點慢。我着眼於使用提升斐波那契堆，但經過一些研究後，似乎只會在縮小尺寸時效率更高，並且最終不會提供較大的性能提升。經過大量研究，我無法找到有效滿足我需求的容器，因此您是否知道可能在此處更好地工作的任何其他容器？

來源

2015-10-09 joshu

我不相信這堆是你最好的選擇。

有幾個自組織樹具有您似乎在之後的屬性。

我建議使用這樣的樹（treap），只是重新插入被修改的元素。

問：大量的研究後，我一直沒能找到一個容器，有效五星級我的需求，讓你知道任何其他容器能夠工作更好地在這裏的？

我會看看Boost Intrusive中的各種樹形容器。

例如， http://www.boost.org/doc/libs/1_59_0/doc/html/intrusive/treap_set_multiset.html#intrusive.treap_set_multiset.treap_set_multiset_containers

升壓侵入是使用有點特殊，但它看起來非常像它正是你想在這裏反正做什麼（因爲介入式容器從未自己它們所包含的元素）。

來源

2015-10-09 20:42:21 sehe

優秀的答案！ +1 – Columbo

時間戳組織的容器

回答

相關問題