[Intrusive] Movable intrusive container elements?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[Intrusive] Movable intrusive container elements?

Boost - Dev mailing list
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.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Intrusive] Movable intrusive container elements?

Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Intrusive] Movable intrusive container elements?

Boost - Dev mailing list
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 <boost/intrusive/set.hpp>

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

namespace bi = boost::intrusive;


struct Thing
{
  int id;
  std::string name;

  bi::set_member_hook<> name_hook;

  Thing() = default;
  Thing(int id_, std::string name_): id(id_), name(name_) {}
  Thing(const Thing& other) = delete;
  Thing(Thing&& other):
    id(other.id),
    name(std::move(other.name)),
    name_hook()
  {
    name_hook.swap_nodes(other.name_hook);
  }
  Thing& operator=(const Thing&) = delete;
  Thing& operator=(Thing&& other)
  {
    id = other.id;
    name = std::move(other.name);
    name_hook.swap_nodes(other.name_hook);
    return *this;
  }
};


class Things
{
  std::vector<Thing> data;

  struct name_compare_t {
    bool operator()(const Thing& a, const Thing& b) const { return a.name < b.name; }
  };

  using thing_name_option = bi::member_hook< Thing, bi::set_member_hook<>, &Thing::name_hook >;
  using compare_name_option = bi::compare< name_compare_t >;  // Can I use a lambda here?
  bi::set< Thing, thing_name_option, compare_name_option, bi::link_mode<bi::auto_unlink> > name_index;

public:
  // Add, then sort, then lookup.

  void add(Thing&& t)
  {
    data.push_back(std::move(t));
    name_index.insert(data.back());
  }

  void sort()
  {
    std::sort(data.begin(), data.end(),
              [](auto& a, auto& b) { return a.id < b.id; });
  }

  Thing& lookup_by_id(int id)
  {
    auto i = std::lower_bound(data.begin(), data.end(), id,
              [](auto& a, int b) { return a.id < b; });
    assert( i != data.end() );
    return *i;
  }

  Thing& lookup_by_name(std::string name)
  {
    Thing key{ 0, name };  // Can I avoid this?
    auto i = name_index.find(key);
    assert( i != name_index.end() );
    return *i;
  }
};


int main()
{
  Things things;

  things.add({1,   "Hello"});
  things.add({2,   "World"});
  things.add({42,  "Foo"});
  things.add({420, "Blah"});
  things.add({17,  "Goodbye"});

  things.sort();

  auto& t1 = things.lookup_by_id(42);  std::cout << t1.id << " = " << t1.name << "\n";
  auto& t2 = things.lookup_by_id(17);  std::cout << t2.id << " = " << t2.name << "\n";

  auto& t3 = things.lookup_by_name("Hello"); std::cout << t3.name << " = " << t3.id << "\n";
  auto& t4 = things.lookup_by_name("Blah");  std::cout << t4.name << " = " << t4.id << "\n";
}





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost