How to insert a new value into a set and delete another at the same time?

Question

Each set contains items in that order. I want to specify the binding according to the size of the set and automatically delete the last element if a new, strictly smaller (in terms of order) is inserted and the specified size has already been reached.

Of course, I could do something like the following:

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; }; 

Besides the fact that bounded_set not the best name (since limited containers are a well-known thing in the parallel programming world), I am worried about memory allocation in this implementation. Most likely, the space used by last will be freed first. But immediately after that it is necessary to allocate a new memory for value .

What I really would like to do is use the memory allocated for last and copy the data for value to this place, while preserving the order.

Answer 1

If I understand your questions correctly, depending on how the basic data structure works, it will not necessarily be possible without writing a specialized memory allocator or using it from a library. For example, std::set uses a red-black tree as the underlying data structure. Thus, the memory location of nodes and relational pointers to and from these nodes is internally tied to the general order of the tree. You cannot reuse memory from a node, which is the "smallest" value, and put there another value that is not a new fully ordered "least" value, without re-sorting all the pointers to that node so that it is in the right place in the tree for the value of this node.

If you are still worried about memory usage and want to stick to STL rather than std::set , you might want to look at a fixed-priority priority queue or something like that that uses a massive heap as the underlying data structure, so memory not constantly distributed and reallocated for new nodes.

Answer 2

I see a couple of options for you and a missed opportunity on the part of the standards committee that would easily solve your problem.

N3586 suggested a solution to your problem.

 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); } 

In this hypothetical rewrite, temp is node_ptr , which allows non-constant access to node value_type . You can remove the node, write to it and reinsert it, all without any allocation for the nodes.

The committee politely declined the offer.

A custom allocator for std::set can do the trick in a less elegant way. Such a allocator will simply cache nodes, and your existing insert will work. One of the minor drawbacks of this approach is that while a custom allocator does not free your node from freeing it, it cannot destroy your Key and then is constructed when you change it. Some types are more effective in the appointment than in the cycle of destruction. And sometimes the former may be noexcept , while the latter cannot be.

In general, I see the custom allocator approach as a last resort. You can make it work. But this requires carefully planned and non-intuitive code.

The use of push_heap , pop_heap . However, using it is inconvenient if you really need an iterator for an inserted or equal element. If you can deal with the void return type, it might look like this:

 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{}); } } 

But it is inconvenient to look for a heap for the newly inserted value, and push_heap does not provide this information.

Another option is a sorted vector + insertion sort. You will have to write the insertion sort yourself, but this is a relatively small programming task. The reason you want to sort the inserts is because you will always sort the sorted array, except for the last element. And insertion sorting is optimal for this job.

None of these solutions are ideal, and no one but N3586 offers anything that comes close to an out of the box solution, i.e. Doesn't require more than a few lines of code. And N3586 does not exist. If you think it should exist, contact your C ++ national authority representative and tell them about it. Or take care of the C ++ committee itself and be nice.