Re: [Intrusive] Movable intrusive container elements?

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2019-09-09 15:37:08

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";
}