时间戳组织的容器

Question

以下是我的一些代码的摘录。

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

};

菲律宾共产党：

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堆调用。应该这样做吗？我搜索了一段时间的文档，但没有看到任何其他方法来实际修改堆顺序，除非使用 std::pop_heap 或推送堆，但在一种情况下，我所做的就是更新对象。我认为当我这样做时可能不会维护堆顺序？有没有更好的方法在更新后恢复堆属性？

其次，我意识到每次更新时间戳时这段代码都会调用 min-heapify，这是一种复杂度为 O(n) 的算法。这对我的需求来说有点慢。我研究过使用 boost Fibonacci 堆，但经过一些研究后，它似乎只会在减小大小时更有效率并且最终不会提供较大的性能提升。经过大量研究后，我一直未能找到能够有效满足我需求的容器，所以您是否知道任何其他可能在这里工作得更好的容器？

Answer 1

我不认为堆是您在这里的最佳选择。

有几种自组织树具有您想要的属性。

我建议使用这样的树 (treap) 并重新插入修改过的元素。

Q. After much research I haven't been able to find a container that efficiently suites my needs so are you aware of any other containers that could possibly work better here?

我会查看 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

Boost Intrusive 在用法上有些特殊，但它看起来非常像您在这里想要做的事情（因为 Intrusive 容器从不拥有它们包含的元素）。

时间戳组织的容器

Container for time stamp organization

c++

algorithm

heap

boost