container icon indicating copy to clipboard operation
container copied to clipboard

Deque should support node `extract` and `insert` a la `std::map` (since C++17)

Open justinasvd opened this issue 2 years ago • 0 comments

Let me preface this with the clarification that this is not an issue of the container code. This is more of a feature request.

Consider a motivating story:

I have one big deque<big_object, void, deque_options<block_size<256>>::type>. What I want to do with this deque, I want to partition its big_objects to, say, 2 partitions. The first partition, naturally, may be left in the original deque, and the second partition would be put in another deque.

What I would like to do, when I am adding big_objects to the second deque, is to steal the already moved from blocks from the first deque and insert them to the second deque, so that I can avoid the whole roundtrip through the memory allocator.

Without the extract and insert the above operation requires O(n) memory (O(n) to grow deque_2, so that I can later shrink deque_1 by n). With extract and insert this partitioning would require O(1), because at most I would need to allocate 1 fresh block to put the new objects to the partition, and if any more would be added, then these blocks could be stolen from the original deque.

I understand that std::deque did not get extract/insert combo like std::map, and I am not sure why. Probably lots of people want to steal tree nodes and less people want to steal deque nodes. But philosophically, both containers are "node" containers, and I don't see why this general approach to the node extraction is not applicable to deque.

justinasvd avatar Jun 14 '23 05:06 justinasvd