知识点来源：cplusplus STL list
网上很多关于list的操作很少有提及到怎么合并，要说这个合并几乎是每个数据结构课提及到的O(1)操作的必修知识点。同时还有人甚至搞不清楚什么叫Merge（归并）和合并（Union）。归并的意思同归并排序是一致的，是两个有序列合并成一个长的有序列。因此操作必定需要O(n)啊，但是这些人肯定没讨论到复杂度，并把Merge称作为合并，因此导致了极大的误导。
首先C++的list出于操作的需要，要实现迁移式操作，肯定是要破坏被操作的另一个链表，导致这个操作的是splice。
splice方法有三种情况：
void splice (iterator position, list& x);
void splice (iterator position, list& x, iterator i);
void splice (iterator position, list& x, iterator first, iterator last);
splice方法会改变x的链表结构，是完全的将x中的元素挪到操作的元素上，position是对于原操作的链表而言的，如果取y.splice(y.end(), x)就是在y的末尾添加x的所有元素，并把x清空。
对于第二种操作，相当于在y做了insert然后在x做了erase，复杂度来说肯定是O(1)，具体实现会比insert + erase快几条指令。
第三种情况其实和第二种情况的“相当于”没啥差别，就是做了稍微快点的insert + erase，因此复杂度和移动的元素数量相关。
而对于第一种情况，就是指O(1)复杂度的Union操作，即将两表合并，x的表完全移动到y的后面或者给定position的位置，x表中的元素被清空。
对于归并操作，网上其他人讲的没啥出入，理解过归并排序后，就可以理解到merge是啥。
通过splice，可以用STL实现Fib堆，具体不展开讨论。
补充一个GNU的源码：
list.cpp
// 23.2.2.4 list operations:
void
#if __cplusplus >= 201103L
splice(const_iterator __position, list&& __x) noexcept
#else
splice(iterator __position, list& __x)
#endif
{
_GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this,
_M_message(__gnu_debug::__msg_self_splice)
._M_sequence(*this, "this"));
this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
}
#if __cplusplus >= 201103L
void
splice(const_iterator __position, list& __x) noexcept
{ splice(__position, std::move(__x)); }
#endif
void
#if __cplusplus >= 201103L
splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
#else
splice(iterator __position, list& __x, iterator __i)
#endif
{
__glibcxx_check_insert(__position);
// We used to perform the splice_alloc check: not anymore, redundant
// after implementing the relevant bits of N1599.
_GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
_M_message(__gnu_debug::__msg_splice_bad)
._M_iterator(__i, "__i"));
_GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)),
_M_message(__gnu_debug::__msg_splice_other)
._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 250. splicing invalidates iterators
this->_M_transfer_from_if(__x, _Equal(__i.base()));
_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
__i.base());
}
#if __cplusplus >= 201103L
void
splice(const_iterator __position, list& __x, const_iterator __i) noexcept
{ splice(__position, std::move(__x), __i); }
#endif
void
#if __cplusplus >= 201103L
splice(const_iterator __position, list&& __x, const_iterator __first,
const_iterator __last) noexcept
#else
splice(iterator __position, list& __x, iterator __first,
iterator __last)
#endif
{
__glibcxx_check_insert(__position);
__glibcxx_check_valid_range(__first, __last);
_GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)),
_M_message(__gnu_debug::__msg_splice_other)
._M_sequence(__x, "x")
._M_iterator(__first, "first"));
// We used to perform the splice_alloc check: not anymore, redundant
// after implementing the relevant bits of N1599.
for (_Base_const_iterator __tmp = __first.base();
__tmp != __last.base(); ++__tmp)
{
_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
_M_message(__gnu_debug::__msg_valid_range)
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
_GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this
|| __tmp != __position.base(),
_M_message(__gnu_debug::__msg_splice_overlap)
._M_iterator(__tmp, "position")
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 250. splicing invalidates iterators
this->_M_transfer_from_if(__x, _Equal(__tmp));
}
_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
__first.base(), __last.base());
}
#if __cplusplus >= 201103L
void
splice(const_iterator __position, list& __x,
const_iterator __first, const_iterator __last) noexcept
{ splice(__position, std::move(__x), __first, __last); }
#endif
stl_list.h
// [23.2.2.4] list operations
/**
* @brief Insert contents of another %list.
* @param __position Iterator referencing the element to insert before.
* @param __x Source list.
*
* The elements of @a __x are inserted in constant time in front of
* the element referenced by @a __position. @a __x becomes an empty
* list.
*
* Requires this != @a __x.
*/
void
#if __cplusplus >= 201103L
splice(const_iterator __position, list&& __x) noexcept
#else
splice(iterator __position, list& __x)
#endif
{
if (!__x.empty())
{
_M_check_equal_allocators(__x);
this->_M_transfer(__position._M_const_cast(),
__x.begin(), __x.end());
this->_M_inc_size(__x._M_get_size());
__x._M_set_size(0);
}
}
#if __cplusplus >= 201103L
void
splice(const_iterator __position, list& __x) noexcept
{ splice(__position, std::move(__x)); }
#endif
#if __cplusplus >= 201103L
/**
* @brief Insert element from another %list.
* @param __position Const_iterator referencing the element to
* insert before.
* @param __x Source list.
* @param __i Const_iterator referencing the element to move.
*
* Removes the element in list @a __x referenced by @a __i and
* inserts it into the current list before @a __position.
*/
void
splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
#else
/**
* @brief Insert element from another %list.
* @param __position Iterator referencing the element to insert before.
* @param __x Source list.
* @param __i Iterator referencing the element to move.
*
* Removes the element in list @a __x referenced by @a __i and
* inserts it into the current list before @a __position.
*/
void
splice(iterator __position, list& __x, iterator __i)
#endif
{
iterator __j = __i._M_const_cast();
++__j;
if (__position == __i || __position == __j)
return;
if (this != std::__addressof(__x))
_M_check_equal_allocators(__x);
this->_M_transfer(__position._M_const_cast(),
__i._M_const_cast(), __j);
this->_M_inc_size(1);
__x._M_dec_size(1);
}
#if __cplusplus >= 201103L
/**
* @brief Insert element from another %list.
* @param __position Const_iterator referencing the element to
* insert before.
* @param __x Source list.
* @param __i Const_iterator referencing the element to move.
*
* Removes the element in list @a __x referenced by @a __i and
* inserts it into the current list before @a __position.
*/
void
splice(const_iterator __position, list& __x, const_iterator __i) noexcept
{ splice(__position, std::move(__x), __i); }
#endif
#if __cplusplus >= 201103L
/**
* @brief Insert range from another %list.
* @param __position Const_iterator referencing the element to
* insert before.
* @param __x Source list.
* @param __first Const_iterator referencing the start of range in x.
* @param __last Const_iterator referencing the end of range in x.
*
* Removes elements in the range [__first,__last) and inserts them
* before @a __position in constant time.
*
* Undefined if @a __position is in [__first,__last).
*/
void
splice(const_iterator __position, list&& __x, const_iterator __first,
const_iterator __last) noexcept
#else
/**
* @brief Insert range from another %list.
* @param __position Iterator referencing the element to insert before.
* @param __x Source list.
* @param __first Iterator referencing the start of range in x.
* @param __last Iterator referencing the end of range in x.
*
* Removes elements in the range [__first,__last) and inserts them
* before @a __position in constant time.
*
* Undefined if @a __position is in [__first,__last).
*/
void
splice(iterator __position, list& __x, iterator __first,
iterator __last)
#endif
{
if (__first != __last)
{
if (this != std::__addressof(__x))
_M_check_equal_allocators(__x);
size_t __n = _S_distance(__first, __last);
this->_M_inc_size(__n);
__x._M_dec_size(__n);
this->_M_transfer(__position._M_const_cast(),
__first._M_const_cast(),
__last._M_const_cast());
}
}
#if __cplusplus >= 201103L
/**
* @brief Insert range from another %list.
* @param __position Const_iterator referencing the element to
* insert before.
* @param __x Source list.
* @param __first Const_iterator referencing the start of range in x.
* @param __last Const_iterator referencing the end of range in x.
*
* Removes elements in the range [__first,__last) and inserts them
* before @a __position in constant time.
*
* Undefined if @a __position is in [__first,__last).
*/
void
splice(const_iterator __position, list& __x, const_iterator __first,
const_iterator __last) noexcept
{ splice(__position, std::move(__x), __first, __last); }
#endif
// Moves the elements from [first,last) before position.
void
_M_transfer(iterator __position, iterator __first, iterator __last)
{ __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
具体来讲，会存在一个问题，就是说为什么第三种情况并非O(1)呢？出自于空间的计算：
size_t __n = _S_distance(__first, __last);
this->_M_inc_size(__n);
__x._M_dec_size(__n);
也就是说，由于需要计算size的大小，会导致一个std::distance的计算，这个在list的迭代器里只有O(n)的复杂度。而迁移的transfer其实是O(1)的，注意到和第一种方法同用一个_M_transfer。而第一种方法和第三种区别在于，第一种实际上的size变更不用计算，可以直接取x的size并增加。因此，STL在内部实际上确确实实地实现了O(1)迁移。并暴露给splice使用。
而除了第一第二种方法是O(1)外，第三种方法是O(n)的，仅仅因为要记录size的大小而产生的高额复杂度。而来自<list>的还包括了对每个节点的地址规范化，姑且认为_M_transfer_from_if是做这种事的。
它的解释是：
/** Transfers all iterators @c x that reference @c from sequence,
are not singular, and for which @c __pred(x) returns @c
true. @c __pred will be invoked with the normal iterators nested
in the safe ones. */
template<typename _Predicate>
void _M_transfer_from_if(_Safe_sequence& __from, _Predicate __pred);
简单来说就是让序列在迭代器层面支持安全迁移，这是最终面向编程者的list，产生的复杂度也有O(n)。总的来说，第三种操作必然产生O(n)的复杂度。对于如何选取部分的元素做O(1)迁移操作，如果不从stl内部操作中加入直接元素数量操作和提前安全化是不可能的。安全化后采用_M_transfer就为O(1)，而操作的元素数量由编程者直接负责，不过这些操作对于一般情况来说是用不到的，而且相当于要做一些函数钩子和重载。如此麻烦，要么不用stl，要么一开始的算法就是分开维护的list。
要知道，对于一个完整的list，合并splice（y.splice(y.end(), x)）永远是O(1)。
