从 boost multi_index 数组中移动元素

Question

假设我有可移动且不可复制的对象，并且我有带 random_access 索引的 boost 多索引数组。我需要将我的对象移出数组前端，但我找不到任何方法，可以在 documentation 中给我 rvalue/lvalue 引用。我只能看到 front() 给了我持续的参考和 pop_front() 擦除元素，但没有 return 任何东西。那么有没有办法将元素移出boost multi-index？

Answer 1

不支持非常量元素操作，因为它们可能会使元素处于一种状态，这会破坏各种索引放置在它们上面的不变量。

您可以做的最接近的事情是使用 modify:

moveonly pop_front(Table& table) {
    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 extracted;
}

请注意 modify 确实会产生检查所有索引的成本，并且可能会失败。还好，如果确实失败了，效果就是iterator被抹掉了：

Effects: Calls mod(e) where e is the element pointed to by position and rearranges *position into all the indices of the multi_index_container. Rearrangement on sequenced indices does not change the position of the element with respect to the index; rearrangement on other indices may or might not succeed. If the rearrangement fails, the element is erased.

Postconditions: Validity of position is preserved if the operation succeeds.

这是一个现场演示：

Live On Coliru

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

struct moveonly {
    int x;
    moveonly(int x = -1) noexcept : x(x) {}
    moveonly(moveonly&& o) noexcept : x(o.x) { o = {}; }
    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) {
    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 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);
}

打印：

table before: 1 2 3 
Extracted: 1
table after: 2 3

Answer 2

添加到@sehe 的回答中，下面显示了在您的可移动类型不可默认构造的情况下如何修改代码：

编辑： 更改代码以正确处理 *extracted.
的破坏 已编辑： 添加了替代 std::unique_ptr。
已编辑： 添加了 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);
}

同样使用 std::unique_ptr 进行清理：

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 提供了另一种基于 boost::optional 的替代方案，这是所有方案中最优雅的：

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

从 boost multi_index 数组中移动元素

Move element from boost multi_index array

c++

boost

move-semantics

boost-multi-index