c++ - 拆分 STL 列表？

Question

我有一个循环链表，看起来像这样:

4 -> 3 -> 2 -> 5 -> 0 -> 1 -> 开始

我想把这个列表分成两段，反转其中一段，然后重新加入列表。像这样:

拆分，一个 O(1) 操作 4 ** 3 -> 2 -> 5 ** 0 -> 1 -> 开头

反向，一个O(n)的操作 0 ** 3 -> 2 -> 5 ** 4 -> 1 -> 开始

重新加入，O(1) 操作 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> 开头

STL 似乎没有循环链表，但我希望我可以将列表表示为(正向)列表。这需要: * 一种将列表拆分为子列表的方法 * 一种将列表合并在一起的方法

将子列表合并在一起应该很容易使用 std::list::splice ，它应该是一个 O(1) 操作。耶!

但是，我找不到一个好的 O(1) 方法来将列表拆分为子列表。 One approach是使用迭代器，但我不认为这适用于我的情况，因为子列表离开列表的末尾并在列表的开头恢复。

是否有使用 STL 实现此算法的有效方法？还是我应该放弃并编写自己的循环链表库？

谢谢!

Answer 1

我不确定这有多大帮助，但在这里:

template<typename I>
void inner(I b, I e)
{
    std::reverse(b, e);  // l = {4 5 2 3 0 1}
}

template<typename L, typename I>
void outer(L& l, I b, I e)
{
    l.splice(l.begin(), l, e, l.end());  // l = {0 1 4 3 2 5}
    std::reverse(l.begin(), b);          // l = {4 1 0 3 2 5}
}

int main ()
{
    std::list<int> t, l{4, 3, 2, 5, 0, 1};
    std::cout << l << std::endl;

    auto b = l.begin(), e = l.begin();
    std::advance(b, 1);
    std::advance(e, 4);
    bool in = true;

    in ? inner(b, e) : outer(l, b, e);
    std::cout << l << std::endl;
}

有两种选择:

• 反转列表的内部部分(3 2 5)
• 反转外部部分(0 1 -> 4)

并且您可能想要反转较短的那个，但您必须考虑到这一点，这是线性时间。我为这两个任务编写了两个单独的函数 inner,outer。

inner 非常简单(只是一个包装器)并且按预期工作。但是，outer 使列表处于等同于预期模数旋转(循环移位)的状态。如果您正在为循环列表建模，这应该没问题。但是，如果您希望输出与您的示例完全相同，则必须再次计数，以找到正确的旋转点。我会避免这种情况，因为它是线性时间。

请注意，实际上不需要拆分，因为就地进行了反转。还有，操作

l.splice(l.begin(), l, e, l.end());

是常数时间。

检查 live example .