Destructive erase for associative containers

91 views
Skip to first unread message

tra...@gockelhut.com

unread,
Oct 10, 2014, 4:00:03 PM10/10/14
to

There are a number of use cases where I want to entirely consume the
contents of an associative container and re-use the memory of the keys. If
I have an expensive to copy yet cheap to move key type, there is not a
supported way of moving my key to a new object, even though I am about to
erase said key from the container. I would love an operation that allowed
me to extract and re-use the key when I am moving it to another structure.
All associative containers could benefit from such an operation. The need
for this operation isn't terrifically common, but I think it is generic
enough to warrant a discussion.

In an std::map<Key, Value>, you might have member functions like so:

std::pair<iterator, std::optional<std::pair<Key, Value>>>
destroy(const Key& position);

std::pair<iterator, std::pair<Key, Value>>
destroy(const_iterator position);

For std::set<Key>:

std::pair<iterator, std::optional<Key>>
destroy(const Key& position);

std::pair<iterator, Key>
destroy(const_iterator position);

Forgive the poor naming...I can't think of a better one. I also can't
figure out a great way to make this scale to multimap/multiset.

The concept will feel familiar if you know Rust's container removal
operations (things like std::Vec<T>::pop return an Option<T> with the value
you popped moved into the Option).


--
[ comp.std.c++ is moderated. To submit articles, try posting with your ]
[ newsreader. If that fails, use mailto:std-cpp...@vandevoorde.com ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]

Öö Tiib

unread,
Oct 15, 2014, 2:30:02 PM10/15/14
to

On Friday, 10 October 2014 23:00:03 UTC+3, tra...@gockelhut.com wrote:
> There are a number of use cases where I want to entirely consume the
> contents of an associative container and re-use the memory of the keys. If
> I have an expensive to copy yet cheap to move key type, there is not a
> supported way of moving my key to a new object, even though I am about to
> erase said key from the container. I would love an operation that allowed
> me to extract and re-use the key when I am moving it to another structure.
> All associative containers could benefit from such an operation. The need
> for this operation isn't terrifically common, but I think it is generic
> enough to warrant a discussion.

The problem is that by design of 'std::map' the "key" is const member
of element (key and value pair) and that is member of (unexposed) "node"
of RB tree. That makes the proposed "move" of "key" confusing. How can
it move from const member of member?

If you need easily extractable and reusable container elements (for
performance reasons) then you can use standard containers that use
pointers or smart pointers as elements or you can use non-standard
containers that have different design that may better fit with such
goal (for example 'boost::intrusive::set' or
'boost::intrusive::multiset').
Reply all
Reply to author
Forward
0 new messages