Does boost.multiindex provide "erase and return erased value" mechanism?

Question

Basically I'm looking for the functionality akin to std::map::extract.

TL;DR

I currently have a multi-index container with two views: insert order and sorted by an "id" member function of the contained element. The multi-index container currently operates on elements of a pointer type. However, the container fully owns the objects it contains and I'd like to change the contained elements to be unique_ptr instead.

However, it looks non-trivial to do "remove a given element preserving its value" step with unique_ptr.

Since the pointer is to an abstract base class, I can't use swap() because this would require me to construct an "empty" object of an abstract type.

Edit: Thanks to the fact that compiler explorer supports linking to 3rd party libraries, I was able to create what I think is the minimal reproducible example

#include <memory>
#include <vector>

#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/multi_index_container.hpp>



class Base {
  public:
    virtual size_t GetId() const = 0;
    virtual ~Base() = default;
};

class Derived : public Base {
  public:
    size_t GetId() const { return 42; }
};


int main(int, char**) {
    // A tag to view elements in the order of insertion.
    struct Sequenced{};
    // A tag to view elements in the order sorted by type id.
    struct Ordered{};

    using ContainerType = boost::multi_index_container<
        // Elements are pointers to Base.
        std::unique_ptr<Base>,

        boost::multi_index::indexed_by<
            boost::multi_index::sequenced<boost::multi_index::tag<Sequenced>>,
            boost::multi_index::hashed_unique<
              boost::multi_index::tag<Ordered>,
              boost::multi_index::const_mem_fun<Base, size_t,
                                                &Base::GetId>>>>;

    ContainerType container;

    // Insert an element.
    auto& ordered_view = container.get<Ordered>();
    auto new_element = std::make_unique<Derived>();
    auto insert_result = ordered_view.insert(std::move(new_element));
    if (!insert_result.second) return -1;

   // Now I just need to extract the element with GetId == 42
   // This works only starting with boost v1.74
   std::unique_ptr<Base> extracted = std::move(ordered_view.extract(42).value());
}

Starting with boost v1.74, hashed views support "extract" member function. I don't think it's possible to do what I want to do prior to that version. The swap trick mentioned in the comments won't work as it does not exist for hashed views. And furthermore, for the views it does exist (sequenced) it actually swaps the whole container, not individual elements.

Answer 1

I'd suggest upgrading. If that's not an option, I can only see a helper implementation that works if

• you have a temporary key value that you know is not in the container
• or you can use a key extractor that doesn't require the unique_ptr to be non-null

I'll demonstrate the first option using a chosen INVKEY of -1 (0xFFFFFFFF) to act as the temporary "deletion" key:

template <typename Idx, typename V = Idx::value_type> V extract(Idx& idx, size_t key) {
    auto it = idx.find(key);
    if (it == idx.end())
        return nullptr;

    BasePtr tmp = std::make_unique<Derived>(Base::INVKEY);
    idx.modify(it, [&tmp](BasePtr& element) { //
        element.swap(tmp);
    });
    idx.erase(it);
    return tmp;
}

Note that it gracefully returns nullptr when the key wasn't found. This may or may not be what you want

Demo Program

Live On Coliru

#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/multi_index_container.hpp>
#include <memory>
#include <vector>
#include <fmt/ranges.h>

struct Base {
    static constexpr size_t INVKEY = -1ul;

    virtual size_t GetId() const = 0;
    virtual ~Base()              = default;
};

using BasePtr = std::unique_ptr<Base>;

struct Derived : Base {
    Derived(size_t id) : id_(id) {}
    size_t GetId() const override { return id_; }

  private:
    size_t id_;
};

template <> struct fmt::formatter<Base, char> : fmt::formatter<size_t> {
    auto format(Base const& b, auto& ctx) const { return fmt::format_to(ctx.out(), "{}", b.GetId()); }
};

template <typename T> struct fmt::formatter<std::unique_ptr<T>, char> : fmt::formatter<std::decay_t<T>> {
    auto format(std::unique_ptr<T> const& p, auto& ctx) const {
        if (p)
            return fmt::format_to(ctx.out(), "{}", *p);
        else
            return fmt::format_to(ctx.out(), "(nullptr)");
    }
};

using ContainerType = boost::multi_index_container<
    BasePtr,
    boost::multi_index::indexed_by<
        boost::multi_index::sequenced<boost::multi_index::tag<struct Sequenced>>,
        boost::multi_index::hashed_unique<boost::multi_index::tag<struct Ordered>,
                                          boost::multi_index::const_mem_fun<Base, size_t, &Base::GetId>> //
        >>;

template <typename Idx, typename V = Idx::value_type> V extract(Idx& idx, size_t key) {
    auto it = idx.find(key);
    if (it == idx.end())
        return nullptr;

    BasePtr tmp = std::make_unique<Derived>(Base::INVKEY);
    idx.modify(it, [&tmp](BasePtr& element) { //
        element.swap(tmp);
    });
    idx.erase(it);
    return tmp;
}

int main() {
    ContainerType container;
    fmt::print("Initial: {}\n", container);

    // Insert an element.
    auto& ordered = container.get<Ordered>();
    {
        auto [it, inserted] = ordered.insert(std::make_unique<Derived>(42));
        assert(inserted);
    }
    {
        auto [it, inserted] = ordered.insert(std::make_unique<Derived>(99));
        assert(inserted);
    }
    fmt::print("Inserted: {}\n", container);

    for (size_t key : {42u, 123u, 99u}) {
        BasePtr extracted = extract(ordered, key);
        fmt::print("Extracted for key {}: {}, remain {}\n", key, extracted, container);
    }
}

Prints

Initial: {}
Inserted: {42, 99}
Extracted for key 42: 42, remain {99}
Extracted for key 123: (nullptr), remain {99}
Extracted for key 99: 99, remain {}

Comfirm Compiler Explorer Boost 1.73.0

Answer 2

An alternative to Sehe's answer is explained here. In any case, the recommended course of action is to upgrade Boost and use extract.