devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

STL list合并_c++中如何将三个std::list的别名合并到一个std::list中

作者：菜鸟追梦旅行 | 2024-04-17 13:22:07

赞

踩

c++中如何将三个std::list的别名合并到一个std::list中

知识点来源：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); 

  • 1
  • 2
  • 3

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

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); }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170

具体来讲，会存在一个问题，就是说为什么第三种情况并非O(1)呢？出自于空间的计算：

size_t __n = _S_distance(__first, __last);
this->_M_inc_size(__n);
__x._M_dec_size(__n);

  • 1
  • 2
  • 3

也就是说，由于需要计算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);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

简单来说就是让序列在迭代器层面支持安全迁移，这是最终面向编程者的list，产生的复杂度也有O(n)。总的来说，第三种操作必然产生O(n)的复杂度。对于如何选取部分的元素做O(1)迁移操作，如果不从stl内部操作中加入直接元素数量操作和提前安全化是不可能的。安全化后采用_M_transfer就为O(1)，而操作的元素数量由编程者直接负责，不过这些操作对于一般情况来说是用不到的，而且相当于要做一些函数钩子和重载。如此麻烦，要么不用stl，要么一开始的算法就是分开维护的list。

要知道，对于一个完整的list，合并splice（y.splice(y.end(), x)）永远是O(1)。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/440434
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号