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

Question

我正在寻找一种以恒定（或至少线性）时间附加两个容器的方法。

我注意到 linked lists 合并，但它似乎对元素进行了排序。是不是有一种容器/方法可以将一个容器重新链接到另一个容器（比如，像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)及时。

Answer 2

因为std::list<T>有splice()哪些可用于将节点从一个列表转移到另一个列表。可悲的是，当指定使用两个迭代器并splice()在两个std:list<T>对象之间进行 ing 的范围时，此方法被破坏为在拼接序列的长度上是线性的。进行此更改是为了进行恒定时间size()操作。

std::list<T> l1({ 1, 2, 3 });
std::list<T> l2({ 4, 5, 6 });
l1.splice(l1.end(), l2);