为什么std :: list :: splice不是自由函数？

Question

Splice是一个成员函数，它将链接列表的一部分放在另一个链接列表中。

为什么需要成为会员功能？我希望我可以将迭代器拼接到列表中，并在列表上设置句柄。除了开始和结束迭代器之外，为什么拼接列表需要成为参数？

为了测试，我制作了三个列表并混合了容器和迭代器。在下面的拼接中看到容器（空）与迭代器（test0和test1）不匹配的位置：

list<int> test0;
list<int> test1;
list<int> empty;
test0.push_back(1);
test0.push_back(2);
test0.push_back(3);
test1.push_back(4);
test1.push_back(5);
test1.push_back(6);
empty.splice(test0.end(), empty, test1.begin(), test1.end());
printf("empty size: %ld\n", empty.size());
printf("test0 size: %ld\n", test0.size());
printf("test1 size: %ld\n", test1.size());
for (const auto& i : test0) {
  printf("%d\n", i);
}

令人惊讶的是，这一切都很好，甚至大小！

empty size: 0
test0 size: 6
test1 size: 0
1
2
3
4
5
6

我可以在某种程度上理解迭代的工作原理，因为它只运行直到next为null，而不考虑容器的前/后指针。但它是如何得到正确的尺寸？也许大小是动态计算的？

编辑：基于大小的this explanation，在线性时间内动态计算列表的大小。所以容器实际上只是一个虚拟参数。也许只有在添加新元素时才需要它，因为它有用于在列表中创建新节点的分配器？

Answer 1

std::list::splice修改容器的大小。您不能使用容器的迭代器来修改它的大小。您会注意到标准库中没有可以仅使用迭代器将新元素插入范围的自由函数。他们最多可以重新安排它们。

例如，std::remove将要移除的元素移除到容器的末尾，并返回一个迭代器，用于标识需要删除的元素范围。它无法真正从范围本身中删除元素。

有一些解决方法，例如使用std::back_inserter，但通过模拟未绑定范围起作用。

Answer 2

前几天我正在查看std :: list :: splice实现。通常，迭代器将指向列表节点私有实现的指针抽象化。列表节点包含指向其邻居节点的_M_prev和_M_next指针 - 这完全取决于实现。对于空列表，该列表包含一个sentinal节点，该节点用作head和tail（再次依赖于实现）。

所以我想我会尝试仅使用列表节点来实现拼接：

void splice(const_iterator pos, list& other,
            const_iterator first, const_iterator last)
{
    // Hook up last.
    last->_M_next = pos->_M_next;
    pos->_M_next->_M_prev = last;

    // Hook up first.
    pos->_M_next = first;
    first->_M_prev = pos;
}

我认为这看起来是正确的，但我可能是错的。

因此，基于该实现，如果动态计算大小，那么这将按照您的说法工作。

然而正如FrançoisAndrieux指出的那样，动态计算尺寸会浪费，因此需要涉及容器，以便保持内部尺寸计数。