目录
- 概要
- 结构
- 重要函数
- 总结
概要
如果vector对应逻辑的array, list对应是double-link-list, 避免大obj占用连续内存, 双向可访问, 没有随机访问的特性
结构
list这块儿结构对仗比较工整, list_node作为内部成员, list_iter作为接口形式出现
list中_M_node既是头结点, 它的next指向第一个节点, 如果回环指向自己既是空list
重要函数
通过基本insert, delete符合出及其精彩的操作
//internal create node
_Node* _M_create_node(const _Tp& __x)
{
_Node* __p = _M_get_node();
__STL_TRY {
_Construct(&__p->_M_data, __x);
}
__STL_UNWIND(_M_put_node(__p));
return __p;
}
_Node* _M_create_node()
{
_Node* __p = _M_get_node();
__STL_TRY {
_Construct(&__p->_M_data);
}
__STL_UNWIND(_M_put_node(__p));
return __p;
}
iterator begin() { return (_Node*)(_M_node->_M_next);
iterator end() { return _M_node; }
//insert before __position
iterator insert(iterator __position, const _Tp& __x) {
_Node* __tmp = _M_create_node(__x);
__tmp->_M_next = __position._M_node;
__tmp->_M_prev = __position._M_node->_M_prev;
__position._M_node->_M_prev->_M_next = __tmp;
__position._M_node->_M_prev = __tmp;
return __tmp;
}
void push_front(const _Tp& __x) { insert(begin(), __x); }
list<_Tp, _Alloc>::insert(iterator __position,
const _Tp* __first, const _Tp* __last)
{
for ( ; __first != __last; ++__first)
insert(__position, *__first);
}
list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
size_type __n, const _Tp& __x)
{
for ( ; __n > 0; --__n)
insert(__position, __x);
}
//erase @__position
iterator erase(iterator __position) {
_List_node_base* __next_node = __position._M_node->_M_next;
_List_node_base* __prev_node = __position._M_node->_M_prev;
_Node* __n = (_Node*) __position._M_node;
__prev_node->_M_next = __next_node;
__next_node->_M_prev = __prev_node;
_Destroy(&__n->_M_data);
_M_put_node(__n);
return iterator((_Node*) __next_node);
}
typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
iterator __last)
{
while (__first != __last)
erase(__first++);
return __last;
}
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
{
iterator __i = begin();
size_type __len = 0;
for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
;
if (__len == __new_size)
erase(__i, end()); //original size greater
else // __i == end(), pad new elements
insert(end(), __new_size - __len, __x);
}
list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
{
if (this != &__x) {
iterator __first1 = begin();
iterator __last1 = end();
const_iterator __first2 = __x.begin();
const_iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
*__first1++ = *__first2++;
if (__first2 == __last2)
erase(__first1, __last1);
else
insert(__last1, __first2, __last2);
}
return *this;
}
template <class _InputIterator>
list(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a)
{ insert(begin(), __first, __last); }
void list<_Tp, _Alloc>::remove(const _Tp& __value)
{
iterator __first = begin();
iterator __last = end();
while (__first != __last) {
iterator __next = __first;
++__next;
if (*__first == __value) erase(__first);
__first = __next;
}
}
void list<_Tp, _Alloc>::unique()
{
iterator __first = begin();
iterator __last = end();
if (__first == __last) return;
iterator __next = __first;
while (++__next != __last) {
if (*__first == *__next)
erase(__next);
else
__first = __next;
__next = __first;
}
}
//brilliant
inline void __List_base_reverse(_List_node_base* __p)
{
_List_node_base* __tmp = __p;
do {
__STD::swap(__tmp->_M_next, __tmp->_M_prev);
__tmp = __tmp->_M_prev; // Old next node is now prev.
} while (__tmp != __p);
}
transfer, splice, merge, sort实现
splice的语义是:移动预算进入当前list
void transfer(iterator __position, iterator __first, iterator __last)语义是从__first到__last插入当前的__position
void transfer(iterator __position, iterator __first, iterator __last) {
if (__position != __last) {
// Remove [first, last) from its old position.
__last._M_node->_M_prev->_M_next = __position._M_node;//①
__first._M_node->_M_prev->_M_next = __last._M_node;//②
__position._M_node->_M_prev->_M_next = __first._M_node; //③
// Splice [first, last) into its new position.
_List_node_base* __tmp = __position._M_node->_M_prev;
__position._M_node->_M_prev = __last._M_node->_M_prev;//④
__last._M_node->_M_prev = __first._M_node->_M_prev; //⑤
__first._M_node->_M_prev = __tmp; //⑥
}
}
例如待插入list是 0<->f <-> 1<-> 2 <-> 3 <-> l <-> 4, __position(p)情况是: x <-> p <-> y
应用transfer如下:
void splice(iterator __position, list& __x) {
if (!__x.empty())
this->transfer(__position, __x.begin(), __x.end()); //all
}
void splice(iterator __position, list&, iterator __i) {
iterator __j = __i;
++__j;
if (__position == __i || __position == __j) return;
this->transfer(__position, __i, __j); // single
}
void splice(iterator __position, list&, iterator __first, iterator __last) {
if (__first != __last)
this->transfer(__position, __first, __last); // f -> l
}
//classical merge
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
{
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
if (*__first2 < *__first1) {
iterator __next = __first2;
transfer(__first1, __first2, ++__next); //merge one
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2) transfer(__last1, __first2, __last2);
}
最后还有一个list sort代码如下
void list<_Tp, _Alloc>::sort()
{
// Do nothing if the list has length 0 or 1.
if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;
while (!empty()) {
__carry.splice(__carry.begin(), *this, begin());
int __i = 0;
while(__i < __fill && !__counter[__i].empty()) {
__counter[__i].merge(__carry);
__carry.swap(__counter[__i++]);
}
__carry.swap(__counter[__i]);
if (__i == __fill) ++__fill;
}
for (int __i = 1; __i < __fill; ++__i)
__counter[__i].merge(__counter[__i-1]);
swap(__counter[__fill-1]);
}
}
最大允许长度是∑ 2^(i - 1) i = 1 -> 64, carry是每一轮中间见过, 每一次内部循环把它归并放入对应长度的counter
以一个例子看下流程:
每个小数子i的迭代次数
代码注释如下:
总结
list在iter的体系下, 通过提炼精简的如insert, erase操作, 急进美妙的组合形成了很多优美的函数, 精炼且易懂
