Возможно ли вставить boost::intrusive::list в boost::intrusive::list?

Question

Возможно ли вставить boost::intrusive::list в boost::intrusive::list ? У меня возникла потребность объединить 2 списка, без всякой логики и сортировок, очевидно это можно сделать за O(1) просто вставив первую ноду списка2 в список1. Вопрос только как это сделать, в библиотеке я нашел только метод merge, который работает за O(N). Есть ли возможность вставить список в список?

Answer 1

Для этого есть метод splice. Сложность у него константная, если контейнер имеет трейт 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;
}

online compiler

БЛОГ НА HUSL

Возможно ли вставить boost::intrusive::list в boost::intrusive::list?

Ответы (1 шт):