Re: [Intrusive] Movable intrusive container elements?

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2019-09-08 21:56:24

On 08/09/2019 14:21, Phil Endecott via Boost wrote:
> Dear Experts,
> 
> Is it possible to make intrusive container elements movable?
> 
> Here's the scenario.  Say I have
> 
> struct Thing { int id, string name };
> 
> and I want a container of those indexed by both the id and the
> name.  Using Boost.Intrusive I can add two hooks to the struct
> and have two intrusive::sets, one using id as the key and the other
> using name.  All good.
> 
> But say my ids are a contiguous range of integers starting at
> zero.  It would be much better to store the Things in a vector
> (or similar), indexed by the id, and use Intrusive only for the
> name index.
> 
> Or if my ids are not contiguous, I might still prefer to keep
> the things in a vector sorted by id and do id lookup by binary
> search (i.e. a flat_set).
> 
> In both cases, the issue is that when the vector expands or is
> sorted the elements are moved, and this will invalidate the
> pointers used for the name index.
> 
> Is is possible to fix this using move constructors and move
> assignment for the hooks?  I.e. those operations could adjust
> the pointers pointing to the element's old location to point to
> its new location.  (This has some similarities to how auto-unlink
> hooks already fix pointers to remove the being-deleted item.)
> 
> Maybe there is some complication that makes this impossible.
> Or maybe this is already possible??

Hi,

Making any default behavior for hooks is always controversial, because 
different users have different needs. You must explicitly write your 
choice in the move/copy constructor/assignment of your type.

It's true that there is no explicit operation to re-link a hook to the 
position the moved-from hook comes from. But you have the "swap_nodes" 
operation on the hook. In the move/copy constructor of your type you can 
default initialize the hook and then swap_nodes. In the move/copy 
assignment you can just "swap_nodes". Could this be useful in your 
vector use case?

Best,

Ion