如何在一个集合中插入一个新值并同时擦除另一个值？
每个集合都包含指定顺序的元素。 我想指定一个集合的大小的边界，并自动删除最后一个元素，如果插入一个严格小于（按照顺序）的新的元素并且已经达到了指定的大小。
当然，我可以做如下的事情：
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到这个地方，同时保持秩序。
如果我正确理解你的问题，根据底层数据结构的工作原理，如果你不必编写自定义的内存分配器或者使用库分配器，这不一定是可能的。 例如， std::set使用红黑树作为基础数据结构。 因此，节点的存储位置以及来自和来自那些节点的关系指针都固有地附加在树的总顺序上。 您不能重新使用来自“最小”值的节点的内存，并将不是全新排序的“最小”值的另一个值放在另一个值上，也不要重新排列指向该节点的所有指针，以便它在该节点的值的树中适当的位置。
如果你仍然关心内存使用情况，并且希望坚持使用STL而不是std::set ，那么也许你应该查看一个固定长度的优先级队列，或者使用基于数组的堆作为底层数据结构，以便内存不会不断分配并重新分配给新节点。
我看到了几种选择，标准委员会失去了一个很容易解决问题的机会。
N3586为您的问题提出了一个解决方案。
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))
{
auto temp = m_set.remove(last);
*temp = value;
return m_set.insert(temp);
}
return std::make_pair(last, false);
}
在这个假设的重写中， temp是一个node_ptr ，它允许非const访问节点的value_type 。 您可以删除节点，写入节点并重新插入节点，而无需为节点分配任何节点。
委员会礼貌地拒绝了这一提议。
std::set自定义分配器可以以不太优雅的方式来实现。 这样的分配器会简单地缓存节点，而你现有的insert将会正常工作。 这种方法的一个小缺点是，虽然自定义分配器可以让您的节点不被释放，但它不能保持您的Key不被破坏，然后在您修改Key时进行构建。 某些类型的分配效率比在销毁建设周期中效率更高。 有时候，前者可以不被noexcept而后者不能。
总之，我认为自定义分配器方法是最后的手段。 你可以让它工作。 但是它需要一些精心策划的，非直观的代码。
push_heap使用push_heap ， pop_heap 。 然而，如果你确实需要一个迭代器来返回插入的或相等的元素，那么它的使用很尴尬。 如果你可以处理一个void返回类型，它可能看起来像：
void insert(Key const& value)
{
if (m_set.size() < m_size)
{
m_set.push_back(value);
std::push_heap(m_set.begin(), m_set.end(), Compare{});
}
if (Compare()(value, m_set.front()))
{
std::pop_heap(m_set.begin(), m_set.end(), Compare{});
m_set.back() = value;
std::push_heap(m_set.begin(), m_set.end(), Compare{});
}
}
但是在堆中搜索新插入的值是很尴尬的， push_heap不提供这些信息。
还有一种选择是排序的矢量+插入排序。 你必须自己编写插入排序，但这是一个相对较小的编程任务。 你想插入排序的原因是，你总是会排序排序数组，除了最后一个元素。 插入排序对于这项工作是最佳的。
这些解决方案都不是完美的，只有N3586提供任何接近“开箱即用”的解决方案，即不需要超过几行代码的解决方案。 而N3586不存在。 如果您认为它应该存在，请联系您的C ++国家机构代表，并告诉他们。 或者亲自参与C ++委员会，并游说它。
链接地址: http://www.djcxy.com/p/81963.html上一篇: How to insert a new value to a set and erase another at the same time?