如何在一个集合中插入新值并同时擦除另一个值？

Question

每个集合包含指定顺序的元素.我想指定一个集合大小的界限,并自动删除最后一个元素,如果插入一个严格较小的(按顺序而言)新的元素并且已达到指定的大小.

当然,我可以做类似以下的事情:

class bounded_set
{
private:
    using set = std::set<Key, Compare, Allocator>;
    using iterator = typename set::iterator;

public:
    bounded_set(std::size_t size)
        : m_size(size)
    { }

    std::pair<iterator, bool> insert(Key const& value)
    {
        if (m_set.size() < m_size)
            return m_set.insert(value);

        auto last = std::prev(m_set.end());
        if (Compare()(value, *last))
        {
            m_set.erase(last);
            return m_set.insert(value);
        }
        return std::make_pair(last, false);
    }

private:
    set m_set;
    std::size_t m_size;
};

除了事实,这bounded_set不是最好的名字(因为有界容器在并发编程领域是众所周知的事情),我担心这个实现中的内存分配.最有可能的是,起初使用的空间last将被释放.但在此之后,需要分配新的内存value.

我真正想做的是,使用分配的内存last并将数据复制value到这个地方,同时保留订单.

Answer 1

如果我正确理解你的问题，根据底层数据结构的工作原理，如果你不必编写自定义内存分配器或使用库中的内存分配器，这不一定是可能的。例如，std::set使用红黑树作为底层数据结构。因此，节点的内存位置以及往返于这些节点的关系指针本质上依附于树的总顺序。您不能重新使用“最小”值节点的内存，并在那里放置另一个不是新的完全排序的“最小”值的值，而不重新排序指向该节点的所有指针，以便它是在树中适当的位置查找该节点的值。

如果您仍然担心内存使用情况并希望坚持使用 STL，而不是std::set，也许您应该研究固定长度优先级队列或使用基于数组的堆作为底层数据结构的类似性质的东西这样内存就不会不断地为新节点分配和重新分配。