How to use boost::intrusive_ptr with boost::intrusive::list?

Question

I want to allocate an object exact one time and push it to few lists. How can I do this with boost::intrusive_ptr and boost::intrusive::list? Or should I use another container and reference counter?

Answer 1

Intrusive lists and intrusive_ptr are not related.

• One is from the "Boost Intrusive" library
• The other is a smart pointer from "Boost SmartPtr" library

You can use either. Intrusive containers have more management features but require a dedicated hook per container.

intrusive_ptr is more flexible in that it can support unbounded containers by using reference counting.

Also, keep in mind if you just want several indexes to the same underlying data, often you can use Boost MultiIndex and get the best of both worlds.

Intrusive List

Simplest demo: Live On Compiler Explorer

#include <string>
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/list_hook.hpp>

// for debug output
#include <fmt/ranges.h>

namespace bi = boost::intrusive;

using BaseHook = bi::list_base_hook<>;
using MemberHook = bi::list_member_hook<>;

struct Item : BaseHook {
    std::string data;
    Item(std::string data) : data(std::move(data)) {}

    MemberHook _secondary, _secondary2;

    bool operator<(Item const& rhs) const { return data < rhs.data; }
};

template <> struct fmt::formatter<Item> : fmt::formatter<std::string> {
    template <typename Ctx>
    auto format(Item const&val, Ctx &ctx) { return fmt::format_to(ctx.out(), "'{}'", val.data); }
};

// primary container uses the base hook
using Items     = bi::list<Item>;
using Secondary = bi::list<Item, bi::member_hook<Item, MemberHook, &Item::_secondary >>;
using Third     = bi::list<Item, bi::member_hook<Item, MemberHook, &Item::_secondary2 >>;

int main() {
    Item elements[] { {"one"}, {"two"},  {"three"} };

    Items primary(std::begin(elements), std::end(elements));

    Secondary idx1(primary.begin(), primary.end());
    Third     idx2(primary.begin(), primary.end());

    idx1.sort();
    idx2.reverse();

    fmt::print("primary: {}\n", primary);
    fmt::print("idx1: {}\n", idx1);
    fmt::print("idx2: {}\n", idx2);
}

Prints

primary: {'one', 'two', 'three'}
idx1: {'one', 'three', 'two'}
idx2: {'three', 'two', 'one'}

Using intrusive_ptr

Note how this is more dynamic, but costs more as a consequence. Also note that since the container elements are no longer "direct values", all operations become more complicated because of indirection:

• insertion needs dynamic allocation (new)
• sort requires a predicate lest you would be sorting on the pointers
• printing needs indirection

I used various other Boost helpers to save time here, but note that this kind of complexity might reduce your development speeds more depending on whether you know these helper bits

Live On Compiler Explorer

#include <string>
#include <boost/intrusive_ptr.hpp>
#include <boost/smart_ptr/intrusive_ref_counter.hpp>
#include <list>

// helpers to make handling containers of intrusive pointers easier
#include <boost/range/adaptor/indirected.hpp>
#include <boost/ptr_container/indirect_fun.hpp>
#include <memory>

// for debug output
#include <fmt/ranges.h>

struct Item : boost::intrusive_ref_counter<Item> {
    std::string data;
    Item(std::string data) : data(std::move(data)) {}

    bool operator<(Item const& rhs) const { return data < rhs.data; }
};

template <> struct fmt::formatter<Item> : fmt::formatter<std::string> {
    template <typename Ctx>
    auto format(Item const&val, Ctx &ctx) { return fmt::format_to(ctx.out(), "'{}'", val.data); }
};

int main() {
    using List = std::list<boost::intrusive_ptr<Item> >;

    List primary;
    for (auto name : {"one","two","three"}) {
        primary.emplace_back(new Item(name));
    }

    List idx1(primary.begin(), primary.end());
    List idx2(primary.begin(), primary.end());

    idx1.sort(boost::make_indirect_fun(std::less<Item>{}));
    idx2.reverse();

    fmt::print("primary: {}\n", primary | boost::adaptors::indirected);
    fmt::print("idx1: {}\n", idx1 | boost::adaptors::indirected);
    fmt::print("idx2: {}\n", idx2 | boost::adaptors::indirected);
}

Prints

primary: {'one', 'two', 'three'}
idx1: {'one', 'three', 'two'}
idx2: {'three', 'two', 'one'}

Bonus: Multi Index Container

You didn't ask for this, but it seems a logical solution given the sample (I realize the sample might not represent your problem, of course):

Live On Compiler Explorer

#include <string>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>

// for debug output
#include <fmt/ranges.h>

struct Item {
    std::string data;
    bool operator<(Item const& rhs) const { return data < rhs.data; }
};

template <> struct fmt::formatter<Item> : fmt::formatter<std::string> {
    template <typename Ctx>
    auto format(Item const&val, Ctx &ctx) { return fmt::format_to(ctx.out(), "'{}'", val.data); }
};

namespace bmi = boost::multi_index;
using Table = bmi::multi_index_container<Item,
      bmi::indexed_by<
        bmi::sequenced<>, // primary
        bmi::sequenced<bmi::tag<struct Index1> >,
        bmi::sequenced<bmi::tag<struct Index2> >
      > >;

int main() {
    Table primary{ {"one"},{"two"},{"three"} };
    
    auto& idx1 = primary.get<Index1>();
    auto& idx2 = primary.get<Index2>();

    idx1.sort();
    idx2.reverse();

    fmt::print("primary: {}\n", primary);
    fmt::print("idx1: {}\n", idx1);
    fmt::print("idx2: {}\n", idx2);
}

Prints

primary: {'one', 'two', 'three'}
idx1: {'one', 'three', 'two'}
idx2: {'three', 'two', 'one'}

The latter has - by far - the most flexibility and highest-level semantics (e.g. removing elements applies to all indices). You can have associative indexes, ordered, compound keys etc. In such cases they will automatically be maintained on replace or modify.

Of course, if your use case is not like indexing of a fixed collection, then you will probably want one of the first options.