c++ - 在恒定时间内追加两个容器

Question

我正在寻找一种在恒定(或至少最小线性)时间内附加两个容器的方法。

我注意到链接的 list 合并了，但它似乎对元素进行了排序。难道没有一种容器/方法可以将一个容器重新链接到另一个容器(比如 list1.last_element.next = list2.first_element)吗？

Answer 1

您可以使用 std::list::splice方法:

std::list<int> list1;
std::list<int> list2;

list1.splice(list1.end(), list2, list2.begin(), list2.end());

此代码将 list2 的内容附加到 list1 的末尾。

正如 Dietmar Kuhl 提到的，该方法需要计算您要插入的范围内的元素:

[list2.begin(), list2.end())

所以如果你提供一个范围，复杂度是线性的。但是，如果您知道要附加一个整个列表，您可以简单地做

list1.splice(list1.end(), list2);

O(1) 时间。