http://www.cplusplus.com/
https://en.cppreference.com/w/
http://gcc.gnu.org/
array
,vector
,deque
,list
,forward_list
map/multimap
,set/multiset
unordered_map
,unordered_set
相当于标准数组的容器类型
#include <array> array<long, ASIZE> a; // 声明类型为long大小为ASIZE的数组 cout << a.size(); // array的大小 cout << a.front(); // array的首元素 cout << a.back(); // array的尾元素 cout << a.data(); // array在内存的起始位置
在内存中只能向后扩展,扩展的方式是两倍扩展(vector容量不足时,把容量扩充为当前的2倍)
#include <vector> vector<int> v; // 声明类型为int的vector v.push_back(1); // 向vector尾部插入元素1 cout << v.size(); // vector中的元素个数 cout << v.front(); // vector第一个元素的值 cout << v.back(); // vector最后一个元素的值 cout << v.data(); // vector在内存的起始位置 cout << v.capacity(); // vector的实际容量
双向链表
#include <list> list<int> l; // 声明类型为int的list l.push_back(1); // list尾部添加一个元素 cout << l.size(); // list的元素个数 cout << l.max_size(); // list的最大大小 cout << l.front(); // list的首元素 cout << l.end(); // list的尾元素 l.sort(); // 对list进行排序 // 当容器自己有sort方法时就用容器自身的sort,而不是全局的sort // 因为::sort()只接受RandomAcessIterator
单向链表
#include <forward_list> forward_list<int> l; // 声明类型为int的forward_list l.push_front(1); // forward_list首部添加一个元素 cout << l.max_size(); // forward_list的最大大小 cout << l.front(); // forward_list的首元素 l.sort(); // 对forward_list进行排序 // forward_list没有push_back()和size()
双向链表,使用者把它当作是连续的,实际在内存中它是分段连续的(容量不足时,deque
会扩充一个buffer大小的内存,buffer内是连续的)。
#include <deque> deque<int> d; // 声明类型为int的deque d.push_back(1); // deque尾部插入元素 d.push_front(1); // deque首部插入元素 d.pop_back(); // 删除deque尾部元素 d.pop_front(); // 删除deque首部元素 cout << d.size(); // deque大小 cout << d.front(); // deque首元素 cout << d.back(); // deque尾元素 cout << d.max_size(); // deque最大大小
栈,后进先出(使用deque
实现,又叫做容器适配器,不提供iterator)
#include <stack> stack<int> s; // 声明类型为int的栈 s.push(1); // 栈顶插入元素 s.pop(); // 弹出栈顶元素 cout << s.size(); // 栈大小 cout << s.top(); // 栈顶元素
队列,先进先出(使用deque
实现,又叫做容器适配器,不提供iterator)
#include <queue> queue<int> q; // 声明类型为int的队列 q.push(1); // 队尾插入元素 q.pop(); // 弹出队首元素 cout << q.size(); // 队列大小 cout << q.front(); // 队首元素 cout << q.back(); // 队尾元素
优先队列,实现了堆的结构
#include <queue> priority_queue<int> pq; // 声明类型为int的优先队列 pq.push(1); // 向堆中插入元素1 pq.pop(); // 弹出堆顶元素 cout << pq.size(); // 堆的大小 cout << pq.top(); // 堆顶元素 // priority_queue默认为大顶堆,即堆顶元素为堆中最大元素 priority_queue<int, vector<int>, greater<int> > q; // 小顶堆 priority_queue<int, vector<int>, less<int> > q; // 大顶堆 //自定义堆结构 struct Node{ int x, y; Node(int a = 0, int b= 0):x(a), y(b) {} }; struct cmp{ bool operator() (const Node& a, const Node& b ){ if (a.x == b.x) return a.y > b.y; return a.x > b.x; // 按x从小到大排序 } }; priority_queue<Node, vector<Node>, cmp> q;
可以插入多个重复元素的集合,底层实现为红黑树
#include <set> multiset<int> ms; // 声明类型为int的multiset ms.insert(1); // 向multiset中插入元素 cout << ms.size(); // multiset中的元素个数 cout << ms.max_size(); // multiset的最大大小 ms.find(1); // 查找multiset中的元素 // 当容器有find()方法时,就不要用全局的find(),容器自身的方法效率更高
可以插入多个重复键值对的结构,底层实现为红黑树(高度自平衡的二叉搜索树)
insert
的时间复杂度为O(log n)
find
的时间复杂度也为O(log n)
#include <map> multimap<int, string> mm; // 声明键为int值为string的multimap mm.insert(pair<int, string>(1, "hi")); // 向multimap中插入元素 // multimap不可以使用[]做插入 cout << mm.size(); // multimap中的元素个数 cout << mm.max_size(); // multimap的最大大小 mm.find(1); // multimap提供find()方法用于查找指定键值的元素
不定序的multiset,底层实现为hash table
#include <unordered_set> unordered_multiset<int> um; // 声明类型为int的unordered_multiset um.insert(1); // unordered_multiset插入元素 cout << um.size(); // unordered_multiset的元素个数 cout << um.max_size(); // unordered_multiset的最大大小 cout << um.bucket_count(); // 内部hash table中的篮子数 cout << um.load_factor(); // 内部hash table的载重因子
不定序的multimap,底层实现为hash table
insert
的平均时间复杂度为O(1)
,最坏时间复杂度为O(n)
find
的平均时间复杂度为O(1)
,最坏时间复杂度为O(n)
#include <unordered_map> unordered_multimap<int, string> um; // 声明键为int值为string的unordered_multimap um.insert(pair<int, string>(1, "hi")); // 向unordered_multimap中插入元素 // unordered_multimap不可以使用[]做插入 cout << um.size(); // unordered_multimap中的元素个数 cout << um.max_size(); // unordered_multimap的最大大小 auto pItem = um.find(1); // unordered_multimap提供find()方法用于查找指定键值的元素 cout << (*pItem).first; // 键 cout << (*pItem).second; // 值
不含重复元素的集合,底层实现为红黑树
#include <set> set<int> s; // 声明类型为int的set s.insert(1); // 向set中插入元素 cout << s.size(); // set中的元素个数 cout << s.max_size(); // set的最大大小 s.find(1); // 查找set中的元素,返回指向该元素的指针
键值对的结构,键值唯一,底层实现为红黑树
insert
的时间复杂度为O(log n)
find
的时间复杂度也为O(log n)
#include <map> map<int, string> m; // 声明键为int值为string的map m.insert(pair<int, string>(1, "hi")); // 向map中插入元素 m[1] = "hello"; // map可以使用[]插入元素 cout << m.size(); // map中的元素个数 cout << m.max_size(); // map的最大大小 auto pItem = m.find(1); // map提供find()方法用于查找指定键 cout << (*pItem).first; // 键 cout << (*pItem).second; // 值
不定序的set,底层实现为hash table
#include <unordered_set> unordered_set<int> us; // 声明类型为int的unordered_set us.insert(1); // unordered_set插入元素 cout << us.size(); // unordered_set的元素个数 cout << us.max_size(); // unordered_set的最大大小 cout << us.bucket_count(); // 内部hash table中的篮子数 cout << us.load_factor(); // 内部hash table的载重因子
不定序的map,底层实现为hash table
insert
的平均时间复杂度为O(1)
,最坏时间复杂度为O(n)
find
的平均时间复杂度为O(1)
,最坏时间复杂度为O(n)
#include <unordered_map> unordered_map<int, string> um; // 声明键为int值为string的unordered_map um.insert(pair<int, string>(1, "hi")); // 向unordered_map中插入元素 um[1] = "hello"; // unordered_map可以使用[]做插入 cout << um.size(); // unordered_map中的元素个数 cout << um.max_size(); // unordered_map的最大大小 auto pItem = um.find(1); // unordered_map提供find()方法用于查找指定键值的元素 cout << (*pItem).first; // 键 cout << (*pItem).second; // 值
源码之前,了无秘密
1.分配器allocator
:VC6+/BC++/GCC的allocator
只是以::opertor new
和::operator delete
完成allocate()
和deallocate()
,::opertor new
和::operator delete
是通过malloc()
和free()
完成内存的分配与回收。
// 并不鼓励直接使用STL中的分配器,它主要用来支持容器的内存分配与回收 // 分配512 ints int *p = allocator<int>().allocate(512, (int *)0); // 使用分配器回收内存时需要指定回收的大小 allocator<int>().deallocate(p, 512);
2.GCC2.9中只是实现了allocator
的接口,但实际上并没有使用allocator
为容器分配内存, GCC2.9实际使用alloc
作为分配器,它使用了一种链表结构管理内存,减少了malloc()
的额外内存消耗(malloc()
分配的内存空间会产生头尾部的一些额外空间,用来保存这个块的大小和其他固定信息),比仅调用::opertor new
和::operator delete
的分配器更加高效。但是GCC4.9中又再次使用了allocator
作为分配器,通过::opertor new
和::operator delete
完成内存分配和回收。GCC4.9中附带了一些扩展的分配器,其中__pool_alloc
就是GCC2.9中的alloc
。
// GCC4.9中可以指定__pool_alloc作为容器的分配器 vector<string, __gnu_cxx::__pool_alloc<string> > vec;
3.Iterator必须提供的5种associated types,迭代器必须定义以回答算法的提问。
// 以GCC4.9中的_List_iterator为例 template<typename _Tp> struct _List_iterator { typedef std::bidirectional_iterator_tag iterator_category; // 迭代器的种类 typedef _Tp value_type; // 迭代器所指元素的类型 typedef _Tp* pointer; // 迭代器所指元素的指针类型 typedef _Tp& reference; // 迭代器所指元素的引用类型 typedef ptrdiff_t diffrence_type; // 两个迭代器差值的类型 ... };
4.普通的指针可以看做是退化的Iterator,可以通过 Iterator Traits 分离class iterators和non-class iterators。(解决计算机问题的尚方宝剑: 加一个中介层 )。
// GCC2.9 <stl_iterator.h> template <class I> // I是class iterator struct iterator_traits { typedef typename I::iterator_category iterator_category; typedef typename I::value_type value_type; typedef typename I::difference_type difference_type; typedef typename I::pointer pointer; typedef typename I::reference reference; }; // 为一般指针设计的两个偏特化 template <class T> // I 是指向T类的指针 struct iterator_traits<T*> { typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; }; tempalte <class T> // I是指向const T类的指针 struct iterator_traits<const T*> { typedef random_access_iterator_tag iterator_category; typedef T value_type; // 注意这里是T不是const T typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& reference; }; // 需要知道I的value type时可以用如下方式写 template<typename I,...> void algorithm(...) { typename iterator_traits<I>::value_type v1; }
除了iterator traits还有各种各样的Traits:
5.list
实现了一种双向链表的结构,在其尾部有一个空白节点,符合STL的 前闭后开区间 。
6.vector
以两倍成长的方式进行扩容。
7.像vector
和array
这种使用连续空间存储数据的容器,它们的迭代器都是使用native pointer实现的。
8.deque
采用分段连续的方式实现双向队列,它的迭代器需要处理分段边界的处理,下图中保存每个分段的map是使用vector
实现的,当分段不足时以vector
的方式扩容,不过会将当前的元素复制到新内存的中间部分。
9.deque
在执行insert()
操作时,会判断把插入点向哪一侧的元素进行移动,选择移动花费较小的一侧进行元素移动,再插入新值。
10.deque
模拟连续空间全都是deque iterators
的功劳,两个deque iterators
的距离为(两个deque iterators
间的buffers总长度 + 起始buffer的元素量 + 末尾buffer的元素量)。
// 重载操作符*,返回当前元素 reference operator*() const { return *cur; } // 重载操作符-> reference operator->() const { return &(operator*()); } // 重载操作符-,计算两个deque iterators之间的距离 // 1.两个iterators之间的buffers总长度 2. 尾部buffer元素量 3.头部buffer元素量 difference_type operator-(const self& x) const { return difference_type(buffer_size())*(node - x.node - 1) + (cur - first) + (x.last - x.cur); } // 重载操作符前++ self& operator++() { ++cur; // 切换至下一元素 if(cur == last) { // 抵达当前缓冲区尾部 set_node(node + 1); // 跳至下一节点(缓冲区) cur = first; } return *this; } // 重载操作符后++,保存结果后,调用前++ self operator++(int) { self tmp = *this; ++*this; return tmp; } // 重载操作符前-- self& operator--() { if(cur == first) { // 由于STL前闭后开,先检查是否在缓冲区头部 set_node(node - 1); // 跳至前一节点(缓冲区) cur = last; } --cur; // 往前移一元素 return *this; } // 重载操作符+= self& operator+=(difference_type n) { difference_type offset = n + (cur - first); if(offset >= 0 && offset < difference_type(buffer_size())) cur += n; // 目标位置在同一缓冲区内 else { // 目标位置不在同一缓冲区内 difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) :-difference_type((-offset - 1) / buffer_size()) - 1; // 切换至正确的缓冲区 set_node(node + node_offset); // 切换至正确的元素 cur = first + (offset - node_offset * difference_type(buffer_size())); } return *this; }
11.queue
和stack
都是包含了一个deque
,又被称作适配器,因为它们的操作都是通过调用deque
完成的。queue
和stack
都不允许遍历,也不提供iterator
。queue
和stack
也可以使用list
作为底层结构,声明时需要写为stack<int,list<int>> s
,这个底层结构一定要实现所需要的函数。
12.Red-Black tree(红黑树) 是一种高度平衡的二叉搜索树,其排列方式有利于insert()
和search()
操作。对红黑树进行中序遍历,可以获得排好序的元素。rb_tree
提供遍历操作及iterators
,按正常规则(++iter
)遍历便能得到排序状态。容器rb_tree
提供两种插入操作:insert_unique()
(节点的key在树中独一无二)和inesrt_equal()
(节点的key可重复)。
// GCC2.9中的红黑树 /* * Key表示红黑树中的键 * Value表示红黑树节点表示的值(<key | data>结合表示Value) * KeyOfValue表示从Value中获取Key的方法,可传入仿函数 * Compare表示红黑树中用于比较Key的方法,可传入仿函数 * Alloc表示分配器 */ template <class Key, class Value, class KeyOfValue, class Compare, class Alloc=alloc> class rb_tree { protected: typedef __rb_tree_node<Value> rb_tree_node; ... public: typedef rb_tree_node* link_type; ... protected: size_type node_count; // rb_tree的节点数 link_type header; // 红黑树的头节点,可以实现STL的前闭后开特性 Compare key_compare; // key的比较准则:是个function object ... }
13.set/multiset
以rb_tree
为底层结构,因此有 元素自动排序 的特性,排序的依据是key
。set/multiset
提供遍历操作及iterators
,按正常规则遍历可以获得排序状态,但是无法使用这个iterators
改变元素值。
// GCC2.9的set源码中有一个红黑树,set的所有操作都调用底层红黑树的操作,因此set也是一种container adapter template <class Key, class Compare = less<Key>, class Alloc = alloc> class set { public: typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; private: typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t; public: typedef typename rep_type::const_iterator iterator; // 不允许修改内容的迭代器 ... } // 举一个定义set的例子 set<int> iset; // 实际上使用了默认参数,具体为 set<int, less<int>, alloc> iset; // 它在底层使用了如下红黑树 template<int, int, identity<int>, less<int>, alloc> class rb_tree;
14.map/multimap
以rb_tree
做为底层结构,因此有 元素自动排序 的特性,排序的依据是key
。map/multimap
提供遍历操作及iterator
,按正常规则遍历可以获得排序状态,可以使用这个iterator
改变元素的data,但是不能改变它的key。
// GCC2.9的map源码中有一个红黑树 template <class Key, class T, class Compare = less<Key>, class Alloc alloc> class map { public: typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pair<const Key, T> value_type; // 这里的key是const类型 typedef Compare key_compare; private: typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; public: typedef typename rep_type::iterator iterator; ... } // 举一个定义map的例子 map<int, string> imap; // 实际上使用了默认参数,具体为 map<int, string, less<int>, alloc> imap; // 它在底层使用了如下红黑树 tempalte<int, pair<const int, string>, select1st<pair<const int, string>>, less<int>, alloc> class rb_tree;
15.容器map
有独特的operator[]
可以用来取元素,它返回指定键对应的data,如果键不存在,则会使用默认值创建键值为key的data,然后返回它。
// GCC4.9中[]的实现 mapped_type& operator[](const key_type& __k) { // concept requuirements __glibcxx_function_requires(_DefaultConstructibleConcept); iterator __i = lower_bound(__k); // i->first is greater than or equivalent to __k if(__i == end() || key_comp()(__k, (*__i).first)) #if __cplusplus >= 201103L __i = _M_t._M_emplace_hint_unique(...); // c++11以后使用,省略了部分 #else __i = insert(__i,value_type(__k,mapped_type())); // 没找到则插入 #endif return (*__i).second; } /* * 其中lower_bound是二分查找的一种版本,试图在sorted[first,last)中寻找元素value。 * 若可以找到,则返回指向其中第一个元素的iterator。 * 如果没有找到则返回假设改元素存在时应该出现的位置,即第一个不小于value的位置。 * 换句话说,lower_bound返回不破坏排序得以安插value的第一个适当位置。 */
16.容器hashtable
中没有使用开放地址法(发生冲突时使用线性/二次探测等方法寻找下一个空的散列表地址),而是使用了链地址法,当hash遇到冲突时把相应的数据添加到对应bucket中链表的尾部。STL实现中bucket的个数通常是质数,这些质数都是预先计算好硬编码的,当hashtable
中元素个数大于等于bucket的个数时就会进行rehashing,把bucket的个数扩充到与当前大小二倍最接近的质数,然后再次hash。虽然链表的搜索时间是线性的,但是如果链表足够小,搜索速度仍然很快。散列表的装载因子=散列表中元素个数/散列表长度
,装载因子越大,说明冲突越多。
// GCC2.9中hashtable的源码 /* * Value表示的值(<key | data>结合表示Value) * Key表示hashtable中的键 * HashFcn表示把对象(Key)映射为hash code的仿函数 * 对象在hashtable中的位置即为<hash code>%<bucket size> * ExtractKey表示指明如何从Value中取出Key的仿函数 * EqualKey表示指明Key相等条件的仿函数 * Alloc是分配器 */ template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc=alloc> class hashtable { public: typedef HashFcn hasher; typedef EqualKey key_equal; typedef size_t size_type; private: /* 三个函数对象 */ hasher hash; key_equal equals; ExtractKey get_key; typedef __hashtable_node<Value> node; // bucket中链表的节点 vector<node*, Alloc> buckets; // 保存bucket的容器 size_type num_elementsl // hashtable中的元素个数 public: size_type bucket_count() const { return bucket.size() } // bucket的大小 ... }
17.hash function
的目的就是希望根据元素值计算出一个hash code(一个可进行取模运算的值,<hash code>%<bucket size>
就是在hashtable中的位置),使得元素经hash code映射之后能够乱够随机地被置于hashtable
内,越是混乱,越不容易发生碰撞。
// GCC中提供了一些hash function // 但是如果自己设计的对象就需要自己设计hash function // 泛化版本 tempalte <class Key> struct hash {} // 特化版本 __STL_TEMPLATE_NULL struct hash<short> { size_t operator()(short x) const { return x; } } ...
18.unordered
系列的容器是C++11提出的,这些容器均是基于hashtable
实现的,它们包括unordered_set
,unordered_map
,unordered_multiset
,unordered_multimap
。
19.Algorithms 看不见 Containers ,它所需要的一切信息都必须从 Iterators 取得,而 Iterators (由 Containers 供应)必须能够回答 Algorithm 的所有提问,才能搭配该 Algorithm 的所有操作。
20.五种iterator分类:
struct input_iterator_tag {}; // istream_iterator struct output_iterator_tag {}; // ostream_iterator // 只可以单向访问(++)的iterator: Forward_list struct forward_iterator_tag: public input_iterator_tag {}; // 只可以双向访问(++, --)的itreator: List, rb_tree及以rb_tree为底层的容器 struct bidirectional_iterator_tag: public forward_iterator_tag {}; // 可随机访问的iterator:Array, Vector, Deque struct random_access_iterator_tag: public bidirectional_iterator_tag {};
21.output_iterator
是write-only的,无法像forward_iterator
那样可以读。
22.STL中的算法通常传入一些迭代器和函数,以算法accumulate()
为例介绍算法的基本使用方法。
// 传入首尾迭代器和初值 template<class InputIterator, class T> T accumulate(InputIterator first, InputIterator last, T init) { for(; first != last; ++first) // 将元素累加至初值init上 init = init + *first; return init; } // 传入首尾迭代器、初值和二元操作函数 template<class InputIterator, class T, class BinaryOperation> T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op) { for(; first != last; ++first) // 对元素累计算至初值init上 init = binary_op(init, *first); return init; } int myfunc(int x, int y) { return x+2*y; } class myclass { int operator()(int x, int y) { return x+3*y; } }; int init = 100; vector<int> v = {10, 20, 30}; cout << accumulate(v.begin(), v.end(), init); // 160(只传了迭代器和初值参数) cout << accumulate(v.begin(), v.end(), init, minus<int>()); // 40(传了迭代器和STL中的减法函数) cout << accumulate(v.begin(), v.end(), init, myfunc); // 220(传入了函数) cout << accumulate(v.begin(), v.end(), init, myclass()); // 280(传入了仿函数,即函数对象)
23.仿函数functors重载了()
运算符,它是一个对象,但行为和函数类似,可以作为参数传给算法,当作算法中的比较准则。
// 算术类仿函数 template<class T> struct plus:public binary_function<T,T,T> { T operator()(const T &x, const T &y) const { return x+y; } }; // 逻辑运算类 template<class T> struct logical_and:public binary_function<T,T,bool> { bool operator()(const T &x, const T &y) const { return x&&y; } }; // 相对关系类 template<class T> struct equal_to:public binary_function<T,T,bool> { bool operator()(const T &x, const T &y) const { return x==y; } }
24.STL规定每个可适配的仿函数都应该继承适当的父类,比如一元函数父类unary_function
和二元函数父类binary_function
,用于回答函数适配器的提问。
template<class Arg, class Result> struct unary_function { typedef Arg argument_type; typedef Result result_type; }; tempalte<class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };
25.STL中的适配器Adapter,通常分为容器适配器、迭代器适配器和仿函数适配器,用来改造已经存在的类或函数的功能。
26.stack
和queue
属于容器适配器,它们内部都拥有一个底层容器,通过调用底层容器的方法实现了它们的功能。
template<class T, class Sequence=deque<T>> class stack { protected: Sequence c; // 底层容器 ... }
27.以bind2nd
为例说明函数适配器。
count_if(v.begin(), v.end(), bind2nd(less<int>, 40));// v中小于40元素的数量 // 辅助函数,让用户方便使用binder2nd<Op>,编译器自动推导Op的类型 template<class Operation, class T> inline binder2nd<Operation> bind2nd(const Operation& op, const T& x) { typedef typename Operation::second_argument_type arg2_type; return binder2nd<Operation>(op, arg2_type(x)); } // 把某个可适配的二元函数转换为一元函数 template<class Operation> class binder2nd:public unary_function<typename Operation::first_argument_type, typename Operation::result_type> { protected: Operation op; // 内部成员,记录仿函数 typename Opeartion::second_argument_type_value; // 记录第二实参 public: // 构造函数 binder2nd(const Operation& x, const typename Operation::second_argument_type& y):op(x), value(y) {} typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const { return op(x, value); // 实际调用op并取value为第二参数 } } template<class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred) { // 定义一个初值为0的计数器 typename iterator_traits<InputIterator>::difference_type n = 0; for(; first != last; ++first) // 遍历 if(pred(*first)) // 如果元素带入pred结果为true,计数加1 ++n; return n; }
28.以reverse_iterator
介绍迭代器适配器。
reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } tempalte<class Iterator> class reverse_iterator { protected: Iterator current; // 对应正向迭代器 public: // 逆向迭代器的5种associated types都和其对应的正向迭代器相同 typedef typename iterator_traits<Iterator>::iterator_category iterator_category; typedef typename iterator_traits<Iterator>::value_type value_type; ... typedef Iterator iterator_type; // 正向迭代器 typedef reverse_iterator<Iterator> self; // 逆向迭代器 public: explicit reverse_iterator(iterator_type x):current(x) {} reverse_iterator(const self& x):current(x.current) {} iterator_type base() const { return current; } // 取对应正向迭代器 // 重载*,对逆向迭代器取值,将对应的正向迭代器退一位取值 reference operator*() const { Iterator tmp=current; return *--tmp; } pointer operator->() const { return &(operator*()); } // 前进变为后退,后退变为前进 self& operator++() { --current; return *this; } self& operator--() { ++current; reutrn *this; } self operator+(difference_type n) const { return self(current - n); } self operator-(difference_type n) const { return self(current + n); } };
29.一个万用的hash function。
#include <functional> class Customer {...}; // auxiliary generic function(using variadic templates) tempalte<typename... Types> inline size_t hash_val(const Types&... args) { size_t seed = 0; hash_val(seed, args); return seed; } template<typename T, typename... Types> inline void hash_val(size_t& seed, const T& val, const Types&... args) { hash_combine(seed, val); // 逐一取val,改变seed hash_val(seed, args...); } template<typename T> inline void hash_val(size_t& seed, const T& val) { hash_combine(seed, val); } template<typename T> inline void hash_combine(size_t& seed, const T& val) { seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } class CustomerHash { public: std::size_t operator()(const Customer& c) const { return hash_val(c.fname, c.lname, c.no); // 传入对象c的所有数据成员 } }; unordered_set<Customer, CustomerHash> custset;
a
--
123456789
更改id为3
--
test
更改id为2
--
commentor
伪造名称???
--
hhh
伪造名称???
--
yayay