代码之家 › 专栏 › 技术社区 › Andy Venikov

boost.multiindex是否提供“擦除并返回擦除值”机制?

boost-multi-index boost c++

0

Andy Venikov · 技术社区 · 2 年前

基本上,我在寻找类似的功能 std::map::extract .

TL;博士

我目前有一个多索引容器,它有两个视图:插入顺序和按所包含元素的“id”成员函数排序。多索引容器当前对指针类型的元素进行操作。但是,容器完全拥有它所包含的对象,我想将所包含的元素更改为unique_ptr。

然而,使用unique_ptr执行“删除给定元素并保留其值”步骤似乎并不简单。

由于指针指向抽象基类,我不能使用swap(),因为这需要我构造一个抽象类型的“空”对象。

编辑: 由于编译器资源管理器支持链接到第三方库,我能够创建我认为最小的可重复性 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());
}

从boost v1.74开始,哈希视图支持“提取”成员函数。我认为在那个版本之前不可能做我想做的事情。评论中提到的交换技巧不起作用,因为它不适用于哈希视图。此外,对于它确实存在(按顺序排列)的视图,它实际上交换了整个容器,而不是单个元素。

0 回复 | 直到 2 年前

1

2

sehe 2 年前

我建议升级。如果这不是一个选项,我只能看到一个在以下情况下有效的助手实现

您有一个临时键值,但您知道它不在容器中
或者,您可以使用不需要密钥提取器的密钥提取器 unique_ptr 非空

我将使用选定的INVKEY演示第一个选项 -1 (0xFFFFFFFF)作为临时“删除”键:

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

请注意,它优雅地返回 nullptr 当钥匙找不到的时候。这可能是也可能不是你想要的

演示程序

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

印刷品

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

确认 Compiler Explorer Boost 1.73.0

2

Joaquín M López Muñoz 2 年前

解释了Sehe答案的另一种选择 here 。无论如何,建议的行动方案是升级Boost并使用 extract .