Move Element from Boost Multi_Index Array

Move element from boost multi_index array

Adding to @sehe's answer, the following shows how to modify the code in case your moveable type is not default constructible:

Edited: changed code to properly deal with destruction of *extracted.

Edited: added alternative with std::unique_ptr.

Edited: added a second altrnative by sehe.

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <iostream>
#include <type_traits>

struct moveonly {
    int x;
    moveonly(int x) noexcept : x(x) {}
    moveonly(moveonly&& o) noexcept : x(o.x) { o = {-1}; }
    moveonly& operator=(moveonly o) noexcept { using std::swap; swap(x, o.x); return *this; }
};

static_assert(not std::is_copy_constructible<moveonly>{}, "moveonly");

namespace bmi = boost::multi_index;
using Table   = bmi::multi_index_container<moveonly,
    bmi::indexed_by<
        bmi::random_access<bmi::tag<struct _ra> >
    > >;

template <typename Container>
void dump(std::ostream& os, Container const& c) { 
    for (auto& r: c) os << r.x << " ";
    os << "\n";
}

moveonly pop_front(Table& table) {
    std::aligned_storage<sizeof(moveonly), alignof(moveonly)>::type buffer;
    moveonly* extracted = reinterpret_cast<moveonly*>(&buffer);

    auto it = table.begin();
    if (it == table.end())
        throw std::logic_error("pop_front");

    if (table.modify(it, [&](moveonly& v) { new (extracted) moveonly{std::move(v)}; })) {
        table.erase(it);
    }

    try {
        moveonly ret = std::move(*extracted);
        extracted->~moveonly();
        return ret;
    } catch(...) {
        extracted->~moveonly();
        throw;
    }
}

int main() {
    Table table;

    table.push_back({1});
    table.push_back({2});
    table.push_back({3});

    dump(std::cout << "table before: ", table);

    std::cout << "Extracted: " << pop_front(table).x << "\n";

    dump(std::cout << "table after: ", table);
}

Same thing using std::unique_ptr for cleanup:

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <iostream>
#include <memory>
#include <type_traits>

struct moveonly {
    int x;
    moveonly(int x) noexcept : x(x) {}
    moveonly(moveonly&& o) noexcept : x(o.x) { o = {-1}; }
    moveonly& operator=(moveonly o) noexcept { using std::swap; swap(x, o.x); return *this; }
};

static_assert(not std::is_copy_constructible<moveonly>{}, "moveonly");

namespace bmi = boost::multi_index;
using Table   = bmi::multi_index_container<moveonly,
    bmi::indexed_by<
        bmi::random_access<bmi::tag<struct _ra> >
    > >;

template <typename Container>
void dump(std::ostream& os, Container const& c) { 
    for (auto& r: c) os << r.x << " ";
    os << "\n";
}

moveonly pop_front(Table& table) {
    std::aligned_storage<sizeof(moveonly), alignof(moveonly)>::type buffer;
    moveonly* extracted = reinterpret_cast<moveonly*>(&buffer);

    auto it = table.begin();
    if (it == table.end())
        throw std::logic_error("pop_front");

    if (table.modify(it, [&](moveonly& v) { new (extracted) moveonly{std::move(v)}; })) {
        table.erase(it);
    }

    std::unique_ptr<moveonly,void(*)(moveonly*)> ptr = {
        extracted,
        [](moveonly* p){ p->~moveonly(); }
    };

    return std::move(*extracted);
}

int main() {
    Table table;

    table.push_back({1});
    table.push_back({2});
    table.push_back({3});

    dump(std::cout << "table before: ", table);

    std::cout << "Extracted: " << pop_front(table).x << "\n";

    dump(std::cout << "table after: ", table);
}

Sehe provides yet another alternative based on boost::optional which is the most elegant of all:

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/optional.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <iostream>
#include <memory>
#include <type_traits>

struct moveonly {
    int x;
    moveonly(int x) noexcept : x(x) {}
    moveonly(moveonly&& o) noexcept : x(o.x) { o = {-1}; }
    moveonly& operator=(moveonly o) noexcept { using std::swap; swap(x, o.x); return *this; }
};

static_assert(not std::is_copy_constructible<moveonly>{}, "moveonly");

namespace bmi = boost::multi_index;
using Table   = bmi::multi_index_container<moveonly,
    bmi::indexed_by<
        bmi::random_access<bmi::tag<struct _ra> >
    > >;

template <typename Container>
void dump(std::ostream& os, Container const& c) { 
    for (auto& r: c) os << r.x << " ";
    os << "\n";
}

moveonly pop_front(Table& table) {
    boost::optional<moveonly> extracted;

    auto it = table.begin();
    if (it == table.end())
        throw std::logic_error("pop_front");

    if (table.modify(it, [&](moveonly& v) { extracted = std::move(v); })) {
        table.erase(it);
    }

    return std::move(*extracted);
}

int main() {
    Table table;

    table.push_back({1});
    table.push_back({2});
    table.push_back({3});

    dump(std::cout << "table before: ", table);

    std::cout << "Extracted: " << pop_front(table).x << "\n";

    dump(std::cout << "table after: ", table);
}

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

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

How to move an element without removing and re-inserting it into a boost::multi_index_container?

Use relocate:

http://www.boost.org/libs/multi_index/doc/reference/rnd_indices.html#rearrange_operations

Filter and modify elements in boost::multi_index from an equal_range query

Some comments to your proposed solution:

  • BMIter is not special as you seem to imply, but merely the iterator associated to the first index of the container. Note that this will be the same as myIter when myView happens to be this first index.
  • Nevertheless, iterators of hashed indices are not invalidated by insertions or modifications, so you're safe. In fact, you could have defined iters as a vector<myIter> and store the iterators directly without any further conversion --you're still achieving the intended effect of not being affected by potential reorderings after modification.
  • Even though what you're doing is perfectly fine, if you're into squeezing some additional performance note that modification of elements in a hashed index does not change the underlying ordering when the key remains equivalent, so the only way a reordering can possibly affect you when traversing a range of equivalent keys is when a modified element jumps directly after the range (i.e, just before iterRange.second). With this mind, you can spare the iters trick as follows:

 

for (myIter iter = iterRange.first; iter != iterRange.second; ) {
    auto nextIter = std::next(iter);
    if (filter(*iter)) {
        myView.modify(iter, modifier);
        if (nextIter != iterRange.second && std::next(iter) == iterRange.second)
            iterRange.second = iter;
    }
    iter = nextIter;
}

Consistency when removing items from boost multi-index using an iterator

The paragraph you linked only applies to hashed (unordered) indices. It states that when inserting new elements, hashed index iterators remain valid.

When erasing, for ordered indices you can always guarantee complete iteration by using the return value from erase:

for (; it != index.get<0>().end(); ) {
    if (...) it = index.erase(it);
    else ++it;
}

This will also work for hashed (unordered) indices, as the iteration order is stable over erasing elements.

Erasing and modifying elements in Boost MultiIndex Container

shared_ptr will remove actual Host object in its destructor (if there is no other instances of shared_ptr). All objects in MultiIndex are considered constant. To modify the object you should use method modify of MultiIndex. In that case indexes will be updates if necessary.

You could use the following functor to change age field:

  struct change_age
  {
    change_age(int age) : age_(age) {}    
    void operator()(boost::shared_ptr<Host> h) // shared_ptr !!!
    {
      h->age = age_;
    }

  private:
    int age_;
  };

Then use it as follows:

  testHosts.modify( it, Host::change_age( 22 ) ); // set age to 22

get the rank of an element of a boost::multi_index container

@sehe's answer is perfectly valid but runs in linear time. If you want better performance, consider defining your index #0 as random_access and #1 as ranked_non_unique (index #2 is redundant):

typedef multi_index_container <
    int
  , indexed_by<
        random_access<>
      , ranked_non_unique<identity<int>>
    >
> Ints;

so that you can write:

std::cout
    << "rank of next by sequence is "
    << ints.project<0>(it)-sequence.begin()+1 // O(1)
    << std::endl
;
std::cout
    << "rank of next by order is "
    << order.rank(it)+1 // O(log n)
    << std::endl
;

Related Topics

Is There Any Danger in Calling Free() or Delete Instead of Delete[]

How to Compare Char Variables (C-Strings)

Why Does Std::Vector Work with Incomplete Types in Class Definitions

How Do C++ Progs Get Their Return Value, When a Return Is Not Specified in the Function

Receiving Only Necessary Data with C++ Socket

Initializing a Vector of Vectors Having a Fixed Size with Boost Assign

What Is the Most Efficient Thread-Safe C++ Logger

Get List of Static Libraries Used in an Executable

Const to Non-Const Conversion in C++

How Is Llvm Isa<> Implemented

Static Member Variable in a Class

How to Use Gpu::Stream in Opencv

Emacs C++-Mode Incorrect Indentation

Is Lambdification of a Concept an Improvement or Bad Practice

Getting Input from User Using Cin

C++11 Memory Pool Design Pattern

What Does "-Wall" in "G++ -Wall Test.Cpp -O Test" Do

What's the Difference Between Sockaddr, Sockaddr_In, and Sockaddr_In6


Leave a reply



Submit