Is there any way to move an element from ordered_index ed multi_index?

Question

Since C++17, std::set has extract() member function that support moving the node from the container. Here is an example code:

#include <iostream>
#include <cassert>
#include <set>

struct trace {
    trace() {
        std::cout << this << ":" << " construct" << std::endl;
    }
    ~trace() {
        std::cout << this << ":" << " destruct" << std::endl;
    }
    trace(trace& other) {
        std::cout << this << ":" << " copy construct from " << &other << std::endl;
    }
    trace(trace&& other) {
        std::cout << this << ":" << " move construct from " << &other << std::endl;
    }
    trace& operator=(trace const& other) {
        std::cout << this << ":" << " copy assign from    " << &other << std::endl;
        return *this;
    }
    trace& operator=(trace&& other) {
        std::cout << this << ":" << " move assign from    " << &other << std::endl;
        return *this;
    }
};

inline bool operator<(trace const& lhs, trace const& rhs) {
    std::cout << &lhs << " < " << &rhs << std::endl;
    return &lhs < &rhs;
}

int main () {
    std::set<trace> s;
    s.insert(trace());
    s.insert(trace());
    s.insert(trace());
    auto it = s.begin();
    ++it;

    assert(s.size() == 3);
    std::cout << "[[extract]]" << std::endl;
    trace t = std::move(s.extract(it).value());
    assert(s.size() == 2);
}

Running demo: https://wandbox.org/permlink/ZZHkZV1DUZpM3YrU

I got the following result:

0x7ffd30bbfbd0: construct
0x55edd361d2a0: move construct from 0x7ffd30bbfbd0
0x7ffd30bbfbd0: destruct
0x7ffd30bbfbc8: construct
0x7ffd30bbfbc8 < 0x55edd361d2a0
0x55edd361d2a0 < 0x7ffd30bbfbc8
0x7ffd30bbfbc8 < 0x55edd361d2a0
0x55edd361d2d0: move construct from 0x7ffd30bbfbc8
0x7ffd30bbfbc8: destruct
0x7ffd30bbfbc0: construct
0x7ffd30bbfbc0 < 0x55edd361d2a0
0x7ffd30bbfbc0 < 0x55edd361d2d0
0x55edd361d2d0 < 0x7ffd30bbfbc0
0x7ffd30bbfbc0 < 0x55edd361d2d0
0x55edd361d300: move construct from 0x7ffd30bbfbc0
0x7ffd30bbfbc0: destruct
[[extract]]
0x7ffd30bbfbb0: move construct from 0x55edd361d2d0
0x55edd361d2d0: destruct
0x7ffd30bbfbb0: destruct
0x55edd361d300: destruct
0x55edd361d2a0: destruct

After [[extract]], the container doesn't access to the move from object. It is fine.

I'm looking for a way to do the same thing on boost::multi_index.

I tried the same way as the following Q&A: Move element from boost multi_index array

I tried the same approach:

namespace mi = boost::multi_index;

using mi_trace = mi::multi_index_container<
    trace,
    mi::indexed_by<
        mi::ordered_unique<
            mi::identity<trace>
        >
    >
>;

int main () {
    mi_trace mi;

    mi.insert(trace());
    mi.insert(trace());
    mi.insert(trace());

    auto it = mi.begin();
    ++it;

    assert(mi.size() == 3);
    std::optional<trace> target;
    std::cout << "[[modify]]" << std::endl;
    if (mi.modify(
            it,
            [&](auto& e) {
                target.emplace(std::move(e));
            }
        )
    ) {
        std::cout << "[[erase]]" << std::endl;
        mi.erase(it);
        assert(mi.size() == 2);
    }
}

Running demo: https://wandbox.org/permlink/eKpGDpMBbx5aRz9O

And got the following output:

[[modify]]
0x7fffe1f77c66: move construct from 0x55fdda3272e0
0x55fdda3272b0 < 0x55fdda3272e0
0x55fdda3272e0 < 0x55fdda327310
[[erase]]
0x55fdda3272e0: destruct
0x7fffe1f77c66: destruct
0x55fdda3272b0: destruct
0x55fdda327310: destruct

multi_index container accesses moved from object (0x55fdda3272e0) after modify lambda returned. I think that it is for reordering. modify() doesn't know that I use modify() with erase(). For random_access_index, it works well because the container doesn't need to reorder but it doesn't work for ordered_index.

Is there any way to move an element from ordered_indexed multi_index ?

It's pretty hard to understand your question. Let's take the first part - output looks fine to me. What output do you expect? — Michael Nastenko, Aug 03 '19 at 10:53
The first part output is fine. The last output is bad, because 0x55fdda3272e0 is accessed after moved. — Takatoshi Kondo, Aug 03 '19 at 10:56
I want to do the same thing as `std::set::extract` using `boost::muti_index` ordered index. — Takatoshi Kondo, Aug 03 '19 at 10:57
I'm still not sure what do you try to achieve. You have iterator `it` that point to the element you need, if you what to move from it - just move and erase it from the container. What is wrong with this? — Michael Nastenko, Aug 03 '19 at 11:20
Do you mean this https://wandbox.org/permlink/WSHwdvNvFtp5CMPJ ? `multi_index` returns `const_iterator` so I can't move from the iterator. — Takatoshi Kondo, Aug 03 '19 at 11:24
See https://wandbox.org/permlink/pxEdj9Dq1fOoU6Uk . The type of `*it` is `trace const&`. So `std::move(*it)` is fallbacked to copy. — Takatoshi Kondo, Aug 03 '19 at 11:43
Oh, right... Well, in your second part you do pretty much the right thing, but when you move out data it reorders container ('cos you moved out only data, elements still there) I can see any way to pop this element out the same way `extract()` does. — Michael Nastenko, Aug 03 '19 at 11:44
I start thinking that we can implement `extract()` for `multi_index`, but it doesn't exist so far. `std::set::extract()` returns `node_type`(node-handle?). See https://en.cppreference.com/w/cpp/container/set/extract and https://en.cppreference.com/w/cpp/container/node_handle. I'm not sure the internal node structure of `multi_index`. I think that I should create the issue as the feature request for `extract()` on https://github.com/boostorg/multi_index. — Takatoshi Kondo, Aug 03 '19 at 11:52
I created an issue. https://github.com/boostorg/multi_index/issues/27 — Takatoshi Kondo, Aug 03 '19 at 12:14
Note that the reason why boost::multi_index has iterators that point to constant reference is in large part motivated by the container invariants that boost::multi_index provides. If you have a multi-index container, and you 'move from' one of the items in the container, the resulting `valid-but-unspecified` object that you moved from will not necessarily hold the invariants of the container. Boost::multi_index provides a modify_index function which allows the user to modify the data held by the container, and if the invariants are violated, a roll-back function is executed to fix it. — jonesmz, Sep 02 '19 at 20:14

score 1 · Accepted Answer · answered Aug 05 '19 at 07:45

You can use the following to extract a value from a multi_index_container while making sure the element is erased right after value extraction:

struct extract_value_exception{};

template<typename MultiIndexContainerIndex>
auto extract_value(
    MultiIndexContainerIndex& i,
    typename MultiIndexContainerIndex::iterator it)
{
    using value_type = typename MultiIndexContainerIndex::value_type;

    std::optional<value_type> o;
    try{
        i.modify(it, [&](value_type& x){
            o.emplace(std::move(x));
            throw extract_value_exception{};
        });
    }
    catch(const extract_value_exception&){}
    return std::move(*o);
}

Complete example follows.

Live On Wandbox

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <cassert>
#include <iostream>
#include <optional>

struct trace {
    trace() {
        std::cout << this << ":" << " construct" << std::endl;
    }
    ~trace() {
        std::cout << this << ":" << " destruct" << std::endl;
    }
    trace(trace& other) {
        std::cout << this << ":" << " copy construct from " << &other << std::endl;
    }
    trace(trace&& other) {
        std::cout << this << ":" << " move construct from " << &other << std::endl;
    }
    trace& operator=(trace const& other) {
        std::cout << this << ":" << " copy assign from    " << &other << std::endl;
        return *this;
    }
    trace& operator=(trace&& other) {
        std::cout << this << ":" << " move assign from    " << &other << std::endl;
        return *this;
    }
};

inline bool operator<(trace const& lhs, trace const& rhs) {
    std::cout << &lhs << " < " << &rhs << std::endl;
    return &lhs < &rhs;
}

struct extract_value_exception{};

template<typename MultiIndexContainerIndex>
auto extract_value(
    MultiIndexContainerIndex& i,
    typename MultiIndexContainerIndex::iterator it)
{
    using value_type = typename MultiIndexContainerIndex::value_type;

    std::optional<value_type> o;
    try{
        i.modify(it, [&](value_type& x){
            o.emplace(std::move(x));
            throw extract_value_exception{};
        });
    }
    catch(const extract_value_exception&){}
    return std::move(*o);
}

int main () {
    boost::multi_index_container<trace> s;
    s.insert(trace());
    s.insert(trace());
    s.insert(trace());
    auto it = s.begin();
    ++it;

    assert(s.size() == 3);
    std::cout << "[[extract]]" << std::endl;
    trace t = extract_value(s, it);
    assert(s.size() == 2);
}

Output

0x7ffd5feed89d: construct
0x21f7190: move construct from 0x7ffd5feed89d
0x7ffd5feed89d: destruct
0x7ffd5feed89e: construct
0x7ffd5feed89e < 0x21f7190
0x21f7190 < 0x7ffd5feed89e
0x21f71c0: move construct from 0x7ffd5feed89e
0x7ffd5feed89e: destruct
0x7ffd5feed89f: construct
0x7ffd5feed89f < 0x21f7190
0x7ffd5feed89f < 0x21f71c0
0x21f71c0 < 0x7ffd5feed89f
0x21f71f0: move construct from 0x7ffd5feed89f
0x7ffd5feed89f: destruct
[[extract]]
0x7ffd5feed836: move construct from 0x21f71c0
0x21f71c0: destruct
0x7ffd5feed867: move construct from 0x7ffd5feed836
0x7ffd5feed836: destruct
0x7ffd5feed867: destruct
0x21f7190: destruct
0x21f71f0: destruct

Thank you! It perfectly works. If someone worries about performance, see https://github.com/boostorg/multi_index/issues/27. We could have `extract()` for `multi_index` in the future. — Takatoshi Kondo, Aug 05 '19 at 09:15

Is there any way to move an element from ordered_index ed multi_index?

1 Answers1