一、容器概览
上图为 GI STL 2.9的各种容器。图中以内缩方式来表达基层与衍生层的关系。所谓的衍生,并非继承(inheritance)关系,而是内含(containment)关系。例如 heap 内含一个 vector,priority-queue 内含一个 heap,stack 和 queue 都含一个 deque,set/map/multiset/multimap 都内含一个 RB-tree,hast_x都内含一个 hashtable.
二、序列式容器(sequential containers)
所谓序列式容器,其中的元素都可序(ordered),但排序(sorted)。C++ 语 言本身提供了一个序列式容器array,STL另外再提供vector,list,deque, stack,queue,priority-queue等等序列式容器。其中stack和queue由于 只是将deque改头换面而成,技术上被归类为一种适配(adapter)。
list 容器
文件依赖结构图
list概览
list 内实现了其迭代器(G2.9)
注意操作符++重载
虽然iterator也重载operator*(), 但是这里面的*this并没有使用这个重载;例如self tmp = *this, return *this;这两次*this已经被解释为拷贝构造的参数了 ++*this也没有使用重载的operator*();也是已经把*this解释成了operator++()的参数了
简化修改代码
1 #include <iostream> 2 #include <cstdio> 3 namespace sk 4 { 5 template <class T> 6 struct __list_node { 7 typedef void* void_pointer; 8 void_pointer next; 9 void_pointer prev; 10 T data; 11 }; 12 13 template<class T, class Ref, class Ptr> 14 struct __list_iterator { 15 typedef __list_iterator<T, T&, T*> iterator; 16 typedef __list_iterator<T, const T&, const T*> const_iterator; 17 typedef __list_iterator<T, Ref, Ptr> self; 18 19 typedef T value_type; 20 typedef Ptr pointer; 21 typedef Ref reference; 22 typedef __list_node<T>* link_type; 23 typedef size_t size_type; 24 25 link_type node; 26 27 __list_iterator(link_type x) : node(x) { printf("__list_iterator(link_type x) "); } 28 __list_iterator() { printf("__list_iterator() "); } 29 __list_iterator(const iterator& x) : node(x.node) {printf("__list_iterator(const link_type x) ");} 30 31 bool operator==(const self& x) const { return node == x.node; } 32 bool operator!=(const self& x) const { return node != x.node; } 33 reference operator*() const { printf(" operator*() ");return (*node).data; } 34 35 #ifndef __SGI_STL_NO_ARROW_OPERATOR 36 pointer operator->() const { return &(operator*()); } 37 #endif /* __SGI_STL_NO_ARROW_OPERATOR */ 38 39 self& operator++() { 40 printf("prev ++ "); 41 node = (link_type)((*node).next); 42 return *this; 43 } 44 self operator++(int) { 45 printf("post ++ "); 46 self tmp = *this; 47 ++*this; 48 return tmp; 49 } 50 self& operator--() { 51 node = (link_type)((*node).prev); 52 return *this; 53 } 54 self operator--(int) { 55 self tmp = *this; 56 --*this; 57 return tmp; 58 } 59 60 void operator=(const self &test) 61 { 62 printf("operator= "); 63 64 } 65 }; 66 67 } 68 69 typedef sk::__list_iterator<int,int&,int*> 70 list_iterator_int; 71 list_iterator_int 72 testassign(list_iterator_int t) 73 { 74 return t; 75 } 76 77 int main() 78 { 79 sk::__list_node<int> node1; 80 sk::__list_node<int> node2; 81 sk::__list_node<int> node3; 82 sk::__list_node<int> node4; 83 sk::__list_node<int> node5; 84 node1.next = &node2; 85 node2.next = &node3; 86 node3.next = &node4; 87 node4.next = &node5; 88 89 node2.prev = &node1; 90 node3.prev = &node2; 91 node4.prev = &node3; 92 node5.prev = &node4; 93 94 sk::__list_iterator<int,int&,int*> iter1; 95 iter1.node = &node2; 96 printf("-------------------iter1++---------------------- "); 97 iter1++; 98 printf("-------------------++iter1---------------------- "); 99 ++iter1; 100 printf(" "); 101 printf("-------------------1---------------------- "); 102 list_iterator_int iter_test; 103 printf("-------------------2---------------------- "); 104 iter_test = iter1; 105 printf("-------------------3---------------------- "); 106 list_iterator_int iter2 = iter1; 107 printf("-------------------4---------------------- "); 108 iter_test = testassign(iter1); 109 printf("-------------------5---------------------- "); 110 testassign(iter1); 111 printf("------------------------------------------ "); 112 113 return 0; 114 }
测试结果
- 传参的过程中,要调用一次复制构造函数: iter1入栈时会调用复制构造函数创建一个临时对象,与函数内的局部变量具有相同的作用域.
- 函数返回值时,也会构造一个临时对象;调用重载赋值操作符赋值给iter_test.
内容参考整理:侯捷STL课程