STL源码之序列式容器list

前言

STL中list链表即双向链表又是循环链表

正文

一, STL源码之序列式容器list的节点和内置内存申请alloc节点的设计

1, 使用两个指针 父节点指针和下一个节点的指针

template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data; //数据 };

2, 内置的内存分配器

是链表结构 使用需要一个节点的时候就申请内存节点内存大小

template <class T, __DFL_TYPE_PARAM(Alloc,alloc) > class list { typedef list<T, Alloc> self; protected: typedef void* void_pointer; typedef __list_node<T> list_node; typedef simple_alloc<list_node, Alloc> list_node_allocator; //内置内存分配器 link_type get_node() { return list_node_allocator::allocate(); } void put_node(link_type p) { list_node_allocator::deallocate(p); } /** * * @param __false_type : check is class traits 类型萃取 */ link_type __create_node(const T& x, __false_type) { link_type p = get_node(); # ifdef __STL_USE_EXCEPTIONS try { # endif /* __STL_USE_EXCEPTIONS */ construct(&p->data, x); // return p; # ifdef __STL_USE_EXCEPTIONS } catch(...) { put_node(p); throw; } # endif /* __STL_USE_EXCEPTIONS */ return p; } link_type __create_node(const T& x, __true_type) { link_type p = get_node(); /** // int , char , long 类型是 这边为也调用 construct函数 构造函数呢！！！！！！！ 调用 new 赋值 int * ptr = (int*)malloc(sizeof(int)); new(ptr) int(5); if (ptr) { printf("ptr = %d\n", *ptr); } */ construct(&p->data, x); return p; } link_type create_node(const T& x) { typedef typename __type_traits<value_type>::is_POD_type is_POD_type; return __create_node(x, is_POD_type()); } void destroy_node(link_type p) { destroy(&p->data); put_node(p); } ... }

二, 双向链表和循环链表

在链表初始化 循环链表了

void empty_initialize() { node = get_node(); node->next = node; // 头节点的下一个节点指针和上一个指针都指向自己了 就是一个循环链表结构哈 node->prev = node; __stl_debug_do(iter_list.safe_init(node)); } void fill_initialize(size_type n, const T& value) { empty_initialize(); # ifdef __STL_USE_EXCEPTIONS try { # endif /* __STL_USE_EXCEPTIONS */ insert(begin(), n, value); # ifdef __STL_USE_EXCEPTIONS } catch(...) { clear(); put_node(node); throw; } # endif /* __STL_USE_EXCEPTIONS */ } explicit list(size_type n) { fill_initialize(n, T()); }

三, 插入和合并

插入的算法

/** *指定位置的迭代器插入一个数据的节点 的操作 * 1. 创建节点 * 2. 第一步: 创建的新的节点下一个节点指针和父节点的指针改成position节点指针的指向（新的节点下一个节点的指针指向position迭代器的节点, 新的节点的父节点指向 position上一个节点的指针） * 3. 第二步: 改position节点父节点的数据指针下一个节点的指针的指向 ， 指向新的节点 * 4. 第三步: 改position节点父节点指针的指向， 指向新的节点 * * [修改自己prev和next指针的指向， 二: 修改上一个节点的数据的下一个数据 ] * * */ iterator insert(iterator position, const T& x) { __stl_debug_check(__check_if_owner(&iter_list,position)); link_type tmp = create_node(x); tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; # if defined ( __STL_DEBUG ) return iterator(&iter_list,tmp); # else return tmp; # endif } }

有一个重要的算法 transfer是工具

/** * 将[first, last) 转移到position前面 * * * @param position * @param first * @param last */ void transfer(iterator position, iterator first, iterator last) { if (position.node != last.node) { (*(link_type((*last.node).prev))).next = position.node; (*(link_type((*first.node).prev))).next = last.node; // 原来哪个链表结构 不破坏 (*(link_type((*position.node).prev))).next = first.node; link_type tmp = link_type((*position.node).prev); (*position.node).prev = (*last.node).prev; (*last.node).prev = (*first.node).prev; // 原来哪个链表 结构 不破坏 (*first.node).prev = tmp; } } /** * 链表必须是有序的才可以去重 */ template <class T, class Alloc> void list<T, 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; } } template <class T, class Alloc> void list<T, Alloc>::merge(list<T, Alloc>& x) { iterator first1 = begin(); iterator last1 = end(); iterator first2 = x.begin(); iterator last2 = x.end(); // 需要合并的list是有序的 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); } __stl_debug_do(x.invalidate_all()); } /** * 链表 倒序 * 挺会玩的 始终在链表头插入 链表就倒序了 */ template <class T, class Alloc> void list<T, Alloc>::reverse() { if (node->next == node || link_type(node->next)->next == node) return; iterator first = begin(); ++first; while (first != end()) { iterator old = first; ++first; transfer(begin(), old, first); } __stl_debug_do(invalidate_all()); } /** * 链表不支持rand 访问 所以需要排序 * quick sort */ template <class T, class Alloc> void list<T, Alloc>::sort() { if (node->next == node || link_type(node->next)->next == node) return; list<T, Alloc> carry; list<T, 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]); __stl_debug_do(invalidate_all()); }

四, list迭代器

在list的迭代器中重要是++和–的操作

template<class T, class Ref, class Ptr> # if defined ( __STL_DEBUG ) struct __list_iterator : public __safe_base { # else struct __list_iterator { # endif typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; # if defined ( __STL_DEBUG ) link_type get_iterator() const { return node; } link_type owner_node() const { const __safe_base* ptr = owner(); return ptr ? link_type(ptr->owner_) : link_type(0); } __list_iterator(const __safe_base* root, link_type x) : __safe_base(root), node(x) {} __list_iterator() : __safe_base(0) {} __list_iterator(const iterator& x) : __safe_base(x), node(x.node) {} # else __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} # endif bool operator==(const self& x) const { __stl_debug_check(__check_same_owner(*this,x)); return node == x.node; } bool operator!=(const self& x) const { __stl_debug_check(__check_same_owner(*this,x)); return node != x.node; } reference operator*() const { __stl_verbose_assert(node!=owner_node(), __STL_MSG_NOT_DEREFERENCEABLE); return (*node).data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++() { __stl_verbose_assert(node!=owner_node(), __STL_MSG_INVALID_ADVANCE); node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); __stl_verbose_assert(node!=owner_node(), __STL_MSG_INVALID_ADVANCE); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; } };

五，排序sort (quick )

快排的算法思想: 采取分治的思想 需要在每次选择一个切分节点 作为区分两边数据分类，小于切入点的放到切入点左边，大于放到右边，然后左边和右边是"有序的",一个整个切入点选择第一个数据。

STL库中链表使用快排算法进行排序的 把链表中节点有序的放到一个临时的数组链表中然后在合并整个链表数组到最后一个链表中就是有序的

/** * 链表不支持rand 访问 所以需要排序 * quick sort * 思想 : 每一次从链表取第一个节点的数据 放到临时数组中链表中进行排序 临时每个数组链表都是有序的所以在合并的就会找到合适位置插入进入了 最后在把临时数组链表全部合并最后一个链表中 */ template <class T, class Alloc> void list<T, Alloc>::sort() { if (node->next == node || link_type(node->next)->next == node) { return; } list<T, Alloc> carry; list<T, Alloc> counter[64]; int fill = 0; while (!empty()) { //移动一个节点到carray链表中 每次拿链表第一个节点的数据作为<快排的切点> position比较节点 carry.splice(carry.begin(), *this, begin()); int i = 0; // while(i < fill && !counter[i].empty()) { //临时的数组array的合并到counter[i]中 在合并的时候就是在排序了 找到适合位置插入节点数据 counter[i].merge(carry); //把counter[i]的链表复制到carray数组中 carry.swap(counter[i++]); } //临时链表移动到counter数组中 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]); __stl_debug_do(invalidate_all()); }

结语