c++ - 如何向集合中插入一个新值并同时删除另一个值？

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 并不是最好的名字(因为 bounded 容器在并发编程领域是众所周知的东西)，我担心此实现中的内存分配。最有可能的是，首先，last 使用的空间将被释放。但紧接着，需要为 value 分配新内存。

我真正想做的是使用为 last 分配的内存并将 value 的数据复制到这个地方，同时保留顺序。

Answer 1

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

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