[Intrusive] Movable intrusive container elements?
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?? Any thoughts anyone? Regards, Phil.
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
Hi Ion, thanks for your reply. Ion Gazta?aga wrote:
On 08/09/2019 14:21, Phil Endecott via Boost wrote:
Is it possible to make intrusive container elements movable?
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?
Yes, that's exactly what is needed. Thanks for the hint!
Here's a demo, just in case anyone else ever needs to do this.
#include
participants (2)
-
Ion Gaztañaga -
Phil Endecott