无意间看到STL代码，忍不住读了一下，写得很简练，值得我们学习。在这里贴出来和大家分享一下。
最先看的是algorithm里的next_permutation的实现，非递归，代码很精炼，值得好好研究。
template
bool next_permutation(_BidirectionalIter first, _BidirectionalIter last)
{
// concept requirements
glibcpp_function_requires(BidirectionalIteratorConcept);
glibcpp_function_requires(LessThanComparableConcept<
typename iterator_traits::value_type>);
if (first == last)
return false;
_BidirectionalIter i = first;
++i;
if (i == last)
return false;
i = last;
—i;
for(;;) {
_BidirectionalIter ii = i;
—i;
if (*i < ii) {
_BidirectionalIter j = __last;
while (!(i < *—j))
{}
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
去重方法unique的实现：
template template
void list::unique(_BinaryPredicate binary_pred)
{
iterator first = begin();
iterator last = end();
if (first == last) return;
iterator next = first;
while (++next != last) {
if (binary_pred(__first, next))
erase(next);
else
first = next;
next = first;
}
}
看完了代码才想起来，使用unique的前提是list必须是有序的。
为了看后面的reverse方法，我们先看看它用到的transfer方法，这个一个很重要的方法，好几个方法都用到了它。transfer的作用是把[first, last)之间的元素都移动到position之前。
protected:
void transfer(iterator position, iterator first, iterator last) {
if (position != last) {
// Remove [first, last) from its old position.
((_Node*) (last._M_node->_M_prev))->_M_next = position._M_node;
((_Node*) (first._M_node->_M_prev))->_M_next = last._M_node;
((_Node*) (position._M_node->_M_prev))->_M_next = __first._M_node;
// Splice [first, last) into its new position.
_Node* __tmp = (_Node*) (__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;
}
}
然后reverse出场：
template
void list::reverse()
{
// Do nothing if the list has length 0 or 1.
if (_M_node->_M_next != _M_node &&
((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
iterator first = begin();
++first;
while (first != end()) {
iterator old = first;
++first;
transfer(begin(), old, first);
}
}
}
连接操作splice，这里看的这个splice是把list上的i移到position位置上。
void splice(iterator position, list&, iterator i) {
iterator j = i;
++j;
if (position == i || position == j) return;
transfer(position, i, j);
}
最后是sort方法，据说用了quick sort算法，不过还没看太懂……
template
void list::sort()
{
// Do nothing if the list has length 0 or 1.
if (_M_node->_M_next != _M_node &&
((_Node) (_M_node->_M_next))->_M_next != _M_node) {
list carry;
list 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]);
}
}
