lcy's blog

侯捷老师STL课程笔记

2020-05-02 15:03:02

lcy

C/C++

重要网页

http://www.cplusplus.com/
https://en.cppreference.com/w/
http://gcc.gnu.org/

STL六大部件(Components)

容器(Containers) --> class template
分配器(Allocators) --> class template
算法(Algorithms) --> function template
迭代器(Iterators) --> class template
适配器(Adapters) --> class template
仿函数(Functors) --> class template

容器分类

序列容器(Sequence Containers)：array,vector,deque,list,forward_list
关联容器(Associative Containers):map/multimap,set/multiset
不定序容器(Unordered Containers，也是一种关联容器):unordered_map,unordered_set

使用array

相当于标准数组的容器类型

#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

在内存中只能向后扩展，扩展的方式是两倍扩展(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的实际容量

使用list

双向链表

#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

使用forward_list

单向链表

#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

双向链表，使用者把它当作是连续的，实际在内存中它是分段连续的(容量不足时，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最大大小

使用stack

栈，后进先出(使用deque实现，又叫做容器适配器，不提供iterator)

#include <stack>  
stack<int> s;   // 声明类型为int的栈  
s.push(1);   // 栈顶插入元素  
s.pop();   // 弹出栈顶元素  
cout << s.size();  // 栈大小  
cout << s.top();  // 栈顶元素

使用queue

队列，先进先出(使用deque实现，又叫做容器适配器，不提供iterator)

#include <queue>  
queue<int> q;  // 声明类型为int的队列  
q.push(1);  // 队尾插入元素  
q.pop();   // 弹出队首元素  
cout << q.size();  // 队列大小  
cout << q.front();  // 队首元素  
cout << q.back();  // 队尾元素

使用priority_queue

优先队列，实现了堆的结构

#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;

使用multiset

可以插入多个重复元素的集合，底层实现为红黑树

#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(),容器自身的方法效率更高

使用multimap

可以插入多个重复键值对的结构，底层实现为红黑树(高度自平衡的二叉搜索树)
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()方法用于查找指定键值的元素

使用unordered_multiset

不定序的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的载重因子

使用unordered_multimap

不定序的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; // 值

使用set

不含重复元素的集合，底层实现为红黑树

#include <set>  
set<int> s;  // 声明类型为int的set  
s.insert(1);  // 向set中插入元素  
cout << s.size();  // set中的元素个数  
cout << s.max_size();  // set的最大大小  
s.find(1);  // 查找set中的元素，返回指向该元素的指针

使用map

键值对的结构，键值唯一，底层实现为红黑树
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; // 值

使用unordered_set

不定序的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的载重因子

使用unordered_map

不定序的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：

type traits <../C++/type_traits>
iterator traits <../C++/bits/stl_iterator.h>
char traits <../C++/bits/char_traits.h>
allocator traits <../C++/bits/alloc_traits.h>
pointer traits <../C++/bits/ptr_traits.h>
array traits <../C++/array>

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;

还没有登陆？评论请先登陆或注册

还没有评论，抢个沙发吧！

侯捷老师STL课程笔记

重要网页

STL六大部件(Components)

容器分类

使用array

使用vector

使用list

使用forward_list

使用deque

使用stack

使用queue

使用priority_queue

使用multiset

使用multimap

使用unordered_multiset

使用unordered_multimap

使用set

使用map

使用unordered_set

使用unordered_map

评论

联系方式 contact me

最近评论 latest comment

侯捷老师STL课程笔记

重要网页

STL六大部件(Components)

容器分类

使用array

使用vector

使用list

使用forward_list

使用deque

使用stack

使用queue

使用priority_queue

使用multiset

使用multimap

使用unordered_multiset

使用unordered_multimap

使用set

使用map

使用unordered_set

使用unordered_map

评论

联系方式 contact me

最近评论 latest comment

友情链接 friend link