主页 / 问题 / 1442416
Accepted
Denver Toha
Asked:2022-08-25 00:34:40 +0000 UTC2022-08-25 00:34:40 +0000 UTC

是否可以将 boost::intrusive::list 插入 boost::intrusive::list 中？

  • 772

是否可以将 boost::intrusive::list 插入 boost::intrusive::list ？我需要合并 2 个列表，没有任何逻辑和排序，显然这可以通过简单地将 list2 的第一个节点插入 list1 在 O(1) 中完成。唯一的问题是如何做到这一点，在库中我只找到了合并方法，该方法在 O(N) 中有效。是否可以将列表插入列表中？

c++

1 个回答

  1. Best Answer

    有一种方法splice。如果容器具有 trait constant_time_size<false>，它的复杂性是恒定的，否则是线性的。

    #include <boost/intrusive/list.hpp>
#include <boost/intrusive/list_hook.hpp>

struct t_Foo;

using t_FooHook = ::boost::intrusive::list_base_hook
<
    ::boost::intrusive::link_mode<::boost::intrusive::auto_unlink>
>;

using t_FooList = ::boost::intrusive::list
<
    ::t_Foo
,   ::boost::intrusive::base_hook<::t_FooHook>
,   ::boost::intrusive::constant_time_size<false>
>;

struct t_Foo: public ::t_FooHook
{
    int value{};

    explicit t_Foo(int const initial_value)
    :   ::t_FooHook{}, value{initial_value}
    {}
};

#include <cassert>

int main()
{
    ::t_Foo f0{12};
    ::t_Foo f1{34};
    ::t_Foo f2{56};
    ::t_Foo f3{78};
    ::t_FooList list1{};
    ::t_FooList list2{};
    list1.push_back(f0);
    list1.push_back(f1);
    list2.push_back(f2);
    list2.push_back(f3);
    list2.splice(++(list2.begin()), list1, list1.begin(), list1.end());
    assert(0 == list1.size());
    assert(4 == list2.size());
    return 0;
}

    在线编译器

    • 1

相关问题