sgi stl 的list實(shí)際上是一個(gè)雙向環(huán)形鏈表

下面是代碼

#ifndef C_LIST_H #define C_LIST_H #include "cconstruct.h" #include "cvector.h"template <class T> struct list_node {typedef list_node<T>* point;point prev;point next;T data; };template <class T, class Ref, class Ptr> struct list_iterator {typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, Ref, Ptr> self;typedef bidirectional_iterator_tag iterator_category;typedef ptrdiff_t distance_type;typedef T value_type;typedef Ref reference;typedef Ptr pointer;typedef list_node<T>* link_type;//指向list_node的指針，所謂list_iterator也指向list_node的指針link_type node;list_iterator(){}list_iterator(link_type x):node(x) {}list_iterator(iterator& x):node(x.node) {}bool operator==(const self& x) const { return node == x.node; }bool operator!=(const self& x) const { return node != x.node; }reference operator*() const {return (*node).data;}//list_iterator表示指針，*point 表示取得這個(gè)指針?biāo)钢?指向的不是list_node而是datapointer operator->() const { return &(operator*()); }//++iself& operator++() {node = node->next;return *this;}//i++self operator++(int) {self tmp = *this;++(*this);return tmp;}//--iself& operator--() {node = node->prev;return *this;}//i--self operator--(int) {self tmp = *this;--(*this);return tmp;} };template <class T, class Alloc = alloc> class clist { protected:typedef T vale_type;typedef T* pointer;typedef T& reference;typedef list_node<T> list_node;typedef list_node* link_type;typedef simple_alloc<list_node, Alloc> list_node_allocator;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;public:iterator begin() { return node->next; }const_iterator begin() const{ return node->next; }iterator end() {return node;}const_iterator end() const{ return node; }bool empty() const { return node->next == node; }size_t size() const{size_t len = 0;const_iterator it;for (it = begin(); it != end(); ++it)++len;return len;}reference front() { return *begin(); }reference back() { return *(--end()); }protected://獲得一塊結(jié)點(diǎn)的內(nèi)存link_type get_node() { return list_node_allocator::allocate(); }//釋放一個(gè)節(jié)點(diǎn)的內(nèi)存void put_node(link_type p) { list_node_allocator::deallocate(p); }//構(gòu)造一個(gè)節(jié)點(diǎn)link_type create_node(const T& x) {link_type p = get_node();construct(&p->data, x);return p;}void destroy_node(link_type p) {destroy(&p->data);put_node(p);}void empty_initialize() {node = get_node();node->next = node;node->prev = node;} public:clist() { empty_initialize(); }~clist() {clear();destroy_node(node);}iterator insert(iterator position, const T& x) {link_type tmp = create_node(x);tmp->next = position.node;tmp->prev = position.node->prev;position.node->prev->next = tmp;position.node->prev = tmp;return tmp;}void push_back(const T& x) { insert(end(), x); }void pop_back() {erase(--end());}void pop_front() {erase(begin());}void push_front(const T& x) { insert(begin(), x); }iterator erase(iterator position) {position.node->prev->next = position.node->next;position.node->next->prev = position.node->prev;destroy_node(position.node);return position.node->next;}void clear() {iterator currNode = begin();while ( currNode != end()) {destroy_node((currNode++).node);}node->next = node;node->prev = node;}void remove(const T& x) {iterator first = begin();iterator last = end();while (first != last) {if (*first == x)erase(first++);else++first;}}//這個(gè)算法的思路很清晰void unique() {iterator first = begin();iterator last = end();if (first == last) return ;iterator next = first;while (++next != last ) {if (*first == *next)erase(next);elsefirst = next;next = first;}}void splice(iterator position, clist&, iterator i) {iterator j = i;++j;if (j == position || i == position) return;transfer(position, i, j);}//將[first, last) 放入position之前,[first, last) 可以和position在同一鏈表或不同鏈表，但是區(qū)間和position不能重疊void transfer(iterator position, iterator first, iterator last) {if (position != last) {first.node->prev->next = last.node;position.node->prev->next = first.node;last.node->prev->next = position.node;link_type tmp = position.node->prev;position.node->prev = last.node->prev;last.node->prev = first.node->prev;first.node->prev = tmp;}}void merge(clist<T, 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);first2 = next;}else {++first1;}}if (first2 != last2) transfer(last1, first2, last2);}void reverse() {if (node->next == node || node->next->next == node) return;iterator first = begin();++first;while(first != end()) {iterator old = first;++first;transfer(begin(),old, first);}}void swap(clist<T, Alloc>& x) {std::swap(node, x.node);}void sort() {if (node->next == node || node->next->next == node) return;clist<T, Alloc> carry;clist<T, Alloc> counter[64];int fill = 0;while ( !empty()) {carry.splice(carry.begin(), *this, begin());//carry = 1;可以認(rèn)為是carry每次都賦值為1，counter是一個(gè)大數(shù)，能夠表示2^64進(jìn)制的數(shù)。while的過程就是counter加1的過程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]);}protected:link_type node;//用此指針指向環(huán)狀鏈表 };#endif

其中比較難理解的list中快速排序的實(shí)現(xiàn)，其實(shí)更像是歸并排序

就是用counter[64]表示一個(gè)進(jìn)制為2^64的大數(shù)，同樣，這個(gè)算法可以排序的最大結(jié)點(diǎn)數(shù)是2^64 - 1

while(i < fill && !counter[i].empty())

可以看做是一個(gè)加1操作，從低位開始進(jìn)位

總結(jié)

以上是生活随笔為你收集整理的sgi stl 之list的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。