文章目录
STL六大组件
STL六大组件包括容器(container)、分配器(allocator)、算法(algorithm)、迭代器(iterator)、适配器(adapter)和仿函数(functor).
容器分类
STL中的容器大体分为序列容器、关联容器和无序容器.
vector:动态数组
随着元素的加入，它的内部机制会自行扩充空间以容纳新元素，并不是在原空间之后持续新空间，而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间
总结：
vector 常用来保存需要经常进行随机访问的内容，并且不需要经常对中间元素进行添加删除操作。
Deque：双端队列
list：双向链表
一般应遵循下面的原则：
1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用 vector；
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用 list；
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
set/multiset（multi是允许重复key值）
所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值(value)和键值(key)，set 元素的键值就是实值，实值就是键值，set不允许有相同的值。set 底层是通过红黑树（RB-tree）来实现的，由于红黑树是一种平衡二叉搜索树，自动排序的效果很不错
map/multimap
所有元素都会根据元素的键值自动被排序。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值。底层也是用红黑树， 是一种平衡二叉搜索树，自动排序的效果很不错
注意：multimap不可使用【】插入，只能用mp.insert(pait<int,int>(1,1))插入，multiset也只能用insert方式插入
unordered_map/unordered_set
底层都为哈希表，无序，不重复
Hash与红黑树的区别
权衡三个因素: 查找速度, 数据量, 内存使用，可扩展性，有序性。
hash查找速度会比RB树快，属于常数级别;而RB树的查找速度是log(n)级别。并不一定常数就比log(n) 小，因为hash还有hash函数的耗时。当元素达到一定数量级时，考虑hash。但若你对内存使用特别严格， 希望程序尽可能少消耗内存，而且 hash的构造速度较慢。
1.红黑树是有序的，Hash是无序的，根据需求来选择。
2.红黑树占用的内存更小（仅需要为其存在的节点分配内存），而Hash事先应该分配足够的内存存储散列表,即使有些槽可能弃用
3.红黑树查找和删除的时间复杂度都是O(logn)，Hash查找和删除的时间复杂度都是O(1)。
分配器（allocator）
负责内存的申请和释放
VC6.0的默认分配器std::allocator定义如下,可以看到VC6.0的分配器只是对::operator new和::operator delete的简单封装.
template<class _Ty>
class allocator {
public:
typedef _SIZT size_type;
typedef _PDFT difference_type;
typedef _Ty _FARQ *pointer;
typedef _Ty value_type;
pointer allocate(size_type _N, const void *) {
return (_Allocate((difference_type) _N，(pointer) 0));
}
void deallocate(void _FARQ *_P, size_type) {
operator delete(_P);
};
private:
inline _Ty _FARQ *_Allocate(_PDFT _N, _Ty _FARQ *) {
if (_N < 0) _N = 0;
return ((_Ty _FARQ *) operator new((_SIZT) _N * sizeof(_Ty)));
}
//...
};
gcc2.9中的分配器std::allocator与VC6.0的实现类似,但std::allocator并非gcc2.9的默认分配器,观察容器源码,可以看到,gcc2.9的默认分配器为std::alloc.
class alloc {
protected:
enum { _S_align = 8 };
enum { _S_max_bytes = 128 };
enum { _S_free_list_size = (size_t) _S_max_bytes / (size_t) _S_align };
union _Obj {
union _Obj *_M_free_list_link;
char _M_client_data[1]; // The client sees this.
};
// ...
}
std::alloc内部维护一个链表数组,数组中的每个链表保存某个尺寸的对象,减少了调用malloc的次数,从而减小了malloc带来的额外开销.
在gcc4.9以后,默认分配器变为std::allocator,变回了对::operator new和::operator delete的简单封装.gcc2.9中的std::alloc更名为__gnu_cxx::__pool_alloc.
STL设计模式OOP和GP
OOP(Object-Oriented Programming)和GP(Generic Programming)是STL容器设计中使用的两种设计模式.
OOP的目的是将数据和方法绑定在一起,例如对std::list容器进行排序要调用std::list::sort方法.
GP的目的是将数据和方法分离开来,例如对std::vector容器进行排序要调用std::sort方法.
这种不同是因为std::sort方法内部调用了iterator的-运算,std::list的iterator没有实现-运算符,而std::vector的iterator实现了-运算符.
模板特化
总结：泛化就是不指明类型，使用时写对应类型
特化直接指明类型，使用时就会调用对应类型
偏特化分为两个：
1.多个类型指明其中几个（个数偏特化）
2.将类型范围进行缩小或扩大（范围偏特化）
malloc分配内存的一点东西
使用malloc分配内存时，当分配大一点的空间，则内存里的额外开销（负载）就会小一点，分配小一点空间1，则内存里的额外开销（负载）就会大一点，这些负载信息都是需要的
容器
STL容器的各实现类关系如下图所示,以缩排形式表示衍生关系(主要是复合关系).
list
2.9版本
template<class T, class Alloc = alloc>
class list {
protected:
typedef __list_node<T> list_node;
public:
typedef list_node *link_type;
typedef __list_iterator<T, T &, T *> iterator;
protected:
link_type node;
};
template<class T>
struct __list_node {
typedef void *void_pointer;
void_pointer prev;
void_pointer next;
T data;
};
为实现前闭后开的特性,在环形链表末尾加入一个用以占位的空节点,并将迭代器list::end()指向该节点.
迭代器__list_iterator重载了指针的*,->,++,–等运算符
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category; // 关联类型1
typedef T value_type; // 关联类型2
typedef ptrdiff_t difference_type; // 关联类型3
typedef Ptr pointer; // 关联类型4
typedef Ref reference; // 关联类型5
typedef __list_node <T>* link_type;
link_type node; // 指向的链表节点
reference operator*() const { return (*node).data; }
pointer operator->() const { return &(operator*()); }
//前置++
self& operator++() {
node = (link_type) ((*node).next);
return *this;
}
//后置++
self operator++(int) {
self tmp = *this;//调用拷贝构造函数
++*this;//调用前置++
return tmp;
}
};
++就是获取node的next指针,–获取pre指针，可用过*或-》获取值
注意：1.重载++运算符，括号里没参数是前置++，有类型int为后置++
2.前置++返回值为引用，而后置++返回值为值类型，防止类型连续后++
int i(6);
++++i; // 被解析为 ++(++i), 能通过编译
i++++; // 被解析为 (i++)++, 不能通过编译
list<int> c;
auto ite = c.begin();
++++ite; // 被解析为 ++(++ite), 能通过编译
ite++++; // 被解析为 (ite++)++, 不能通过编译
Iterator遵循原则
必须提供了iterator_category、value_type、difference_type、pointer和pointer5个关联类型(associated types),
一般需要知道itetator的3个关联类型：category，value_type,difference_type,其它两个几乎没有用到
迭代器是泛化的指针，当迭代器不是用在类上就退化为指针了
可以使用**Iterator Traits（萃取器）**区分class iterator和non-class iterators、
在实现上,iterator_traits类使用模板的偏特化,对于一般的迭代器类型,直接取迭代器内部定义的关联类型;对于指针和常量指针进行偏特化,指定关联类型的值.
// 针对一般的迭代器类型,直接取迭代器内定义的关联类型
template<class I>
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>
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;
};
// 针对指针常量类型进行特化,指定关联类型的值
template<class T>
struct iterator_traits<const T *> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type; // value_tye被用于创建变量,为灵活起见,取 T 而非 const T 作为 value_type
typedef ptrdiff_t difference_type;
typedef const T* pointer;
typedef const T& reference;
};
vector
template<class T, class Alloc= alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
protected:
iterator start;
iterator finish;
iterator end_of_storage;
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() - begin()); }
size_type capacity() const { return size_type(end_of_storage - begin()); }
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
};
vector::push_back方法先判断内存空间是否满,若内存空间不满则直接插入;若内存空间满则调用insert_aux函数先扩容两倍再插入元素.
void push_back(const T &x) {
if (finish != end_of_storage) { // 尚有备用空间,则直接插入,并调整finish迭代器
construct(finish, x);
++finish;
} else // 已无备用空间则调用 insert_aux 先扩容再插入元素
insert_aux(end(), x);
}
nsert_aux被设计用于在容器任意位置插入元素,在容器内存空间不足会现将原有容器扩容.
template<class T, class Alloc>
void vector<T, Alloc>::insert_ux(iterator position, const T &x) {
if (finish != end_of_storage) { // 尚有备用空间,则将插入点后元素后移一位并插入元素
construct(finish, *(finish - 1)); // 以vector最后一个元素值为新节点的初值
++finish;
T x_copy = x;
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
} else {
// 已无备用空间,则先扩容,再插入
const size_type old_size = size();
const size_type len = old_size != 0 ?: 2 * old_size:1; // 扩容后长度为原长度的两倍
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
try {
new_finish = uninitialized_copy(start, position, new_start); // 拷贝插入点前的元素
construct(new_finish, x); // 插入新元素并调整水位
++new_finish;
new_finish = uninitialized_copy(position, finish, new_finish); // 拷贝插入点后的元素
}
catch (...) {
// 插入失败则回滚,释放内存并抛出错误
destroy(new_start, new_finish) :
data_allocator::deallocate(new_start, len);
throw;
}
// 释放原容器所占内存
destroy(begin(), end());
deallocate();
// 调整迭代器
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
};
其实：就是通过一个finish指针来判断是否到容器结尾，在容器内存空间不足会现将原有容器扩容为原来的两倍，先拷贝插入点前元素，然后调用拷贝构造函数插入新元素并调整finish指针，再拷贝插入点之后元素，最后调用析构函数释放原有容器内存
所以说每次插入其实都挺耗时的
deque
容器deque内部是分段连续的,对使用者表现为连续的.
template<class T, class Alloc =alloc, size_t BufSiz = 0>
class deque {
public:
typedef T value_type;
typedef _deque_iterator<T, T &, T *, BufSiz> iterator;
protected:
typedef pointer *map_pointer; // T**
protected:
iterator start;
iterator finish;
map_pointer map; // 控制中心,数组中每个元素指向一个buffer
size_type map_size;
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return finish - start; }
// ...
};
deque::map的类型为二重指针T**,称为控制中心,其中每个元素也为指针指向一个buffer.
迭代器deque::iterator的核心字段是4个指针:cur指向当前元素、first和last分别指向当前buffer的开始和末尾、node指向控制中心
deque::insert方法先判断插入元素在容器的前半部分还是后半部分,再将数据往比较短的那一半推.
iterator insert(iterator position, const value_type &x) {
if (position.cur == start.cur) { // 若插入位置是容器首部,则直接push_front
push_front(x);
return start;
} else if (position.cur == finish.cur) { // 若插入位置是容器尾部,则直接push_back
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
} else {
return insert_aux(position, x);
}
}
template<class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type &x) {
difference_type index = pos - start; // 插入点前的元素数
value_type x_copy = x;
if (index < size() / 2) { // 1. 如果插入点前的元素数较少,则将前半部分元素向前推
push_front(front()); // 1.1. 在容器首部创建元素
// ...
copy(front2, pos1, front1); // 1.2. 将前半部分元素左移
} else { // 2. 如果插入点后的元素数较少,则将后半部分元素向后推
push_back(back()); // 2.1. 在容器末尾创建元素
copy_backward(pos, back2, back1); // 2.2. 将后半部分元素右移
}
*pos = x_copy; // 3. 在插入位置上放入元素
return pos;
}
迭代器deque::iterator模拟空间的连续性.
记：当cur指针移动是否到达缓冲区边界（first或last），到达则用node回到控制中心的下一个缓冲区，如果是cur+=20，则回到控制中心看要移动几个缓冲区后，再看看移动几个位置
deque可理解为可以两端操作的动态数组
红黑树
平衡二叉查找树，查找，插入，删除时间为O（lgn），比平衡二叉树好维护
特点：
1.根节点和叶节点（null指针）为黑的
2.如果一个节点是红色的，则它的子节点必须是黑色的。
3.对于任意节点到叶节点的每条路径含相同黑节点
4.红黑树保证最长路径不超过最短路径（全黑）的二倍，因而近似平衡。
插入记忆：根节点必黑，新增是红色，只能黑连黑，不能红连红； 爸叔通红就变色，爸红叔黑就旋转，哪边黑往哪边转
插入节点一般为红，为黑的话成本太大
左旋：
y顶替x，将其左孩子成为x的右孩子
大体步骤：
1.先设置y的左孩子与x的关系
2.再设置y与x父亲的关系
3.最后设置x与y的关系
右旋：
x顶替y，将x的右孩子设为y的左孩子
大体步骤：
1.先设置x的右孩子与y的关系
2.再设置x与y父亲的关系
3.最后设置x与y的关系
插入具体步骤如下：
1.根节点为NULL，直接插入新节点并将其颜色置为黑色
2.根节点不为NULL，找到要插入新节点的位置
3.插入新节点
4.判断新插入节点对全树颜色的影响，更新调整颜色
4.1如果插入节点的父节点为黑，则不需要调整
4.2插入节点的父节点为红，则要调整，分为两种
4.2.1当父节点parent是爷爷grandfather的左节点时，此时爷爷必为黑，
如果叔叔uncle存在且为红，则将parent和uncle改为黑，grandfather改为红，将cur更新为grandfather，parent改为grandfather的父亲
如果叔叔uncle不存在或为黑，如果cur是parent的右孩子，则需要先左旋转再交换cur和parent指针，然后右旋转，将grandfather颜色改为红，parent改为黑
4.2.21当父节点parent是爷爷grandfather的右节点时，
如果叔叔uncle存在且为红，则将parent和uncle改为黑，grandfather改为红，将cur更新为grandfather，parent改为grandfather的父亲
如果叔叔uncle不存在或为黑，如果cur是parent的左孩子，则需要先右旋转再交换cur和parent指针，然后左旋转，将grandfather颜色改为红，parent改为黑
最后记得将root改为黑
面试：什么时候旋转？当叔叔uncle不存在或为黑
什么时候变色？叔叔uncle存在且为红和当叔叔uncle不存在或为黑旋转之后
源码：https://blog.csdn.net/tanrui519521/article/details/80980135
删除：
不平衡的原因：比如删除的黑色节点是左节点，导致以当前根节点的左右子树黑节点不一样
1.普通二叉树的删除
1.1找到删除节点
1.2删除节点的左节点和右节点都不为空的话
比如往左子树找最大值（最右侧），叫替代节点，将替代节点的值赋给删除节点，如果替代节点的左子树不为空，则将替代节点的父亲的right指向它
删除节点的左节点和右节点有一个为空的话，比如左节点不为空则将删除节点的父亲直接指向删除节点的left
2.修正，
2.1当删除节点为红色，不需要修正
2.当删除节点为黑色，以删除节点为左节点为例
2.1当兄弟brother为红色，则将parent跟新为红色，兄弟brother改为黑色，再将parent左旋
2.2当brother为黑色且左右节点均为黑色，将brother改为红色，将brother更新为parent，parent更新为brother的父亲继续循环
2.3.当brother为黑，且左红右黑，先交换brother和左节点颜色，再brother右旋变成2.4情况
2.4当brother为黑，且右节点为红色，将brother变为parent的颜色，然后将parent和右节点改为黑色，再parent左旋
视频：https://www.bilibili.com/video/BV1uZ4y1P7rr
源码：https://www.cnblogs.com/skywang12345/p/3245399.html
容器set和multiset
容器set和multiset以红黑树为底层容器,因此其中元素是有序的,排序的依据是key.set和multiset元素的value和key一致.
set和multiset提供迭代器iterator用以顺序遍历容器,但无法使用iterator改变元素值,因为set和multiset使用的是内部rb_tree的const_iterator.
set元素的key必須独一无二,因此其insert()调用的是内部rb_tree的insert_unique()方法;multiset元素的key可以重复,因此其insert()调用的是内部rb_tree的insert_equal()方法.
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; // 内部rb_tree容器
public:
typedef typename rep_type::const_iterator iterator;
};
容器map和multimap
容器map和multimap以rb_tree为底层容器,因此其中元素是有序的,排序的依据是key.
map和multimap提供迭代器iterator用以顺序遍历容器.无法使用iterator改变元素的key,但可以用它来改变元素的data,因为map和multimap内部自动将key的类型设为const.
map元素的key必須独一无二,因此其insert()调用的是内部rb_tree的insert_unique()方法;multimap元素的key可以重复,因此其insert()调用的是内部rb_tree的insert_equal()方法.
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;
typedef Compare key_compare;
private:
typedef rb_tree <key_type,
value_type,
select1st<value_type>,
key_compare,
Alloc> rep_type;
rep_type t; // 内部rb_tree容器
public:
typedef typename rep_type::iterator)
iterator;
};
map容器重载的[]运算符返回对应data的引用
mapped_type& operator[](key_type&& __k)
{
// 先查找key
// 若key存在,则直接返回其data的引用
iterator __i = lower_bound(__k);
// 若key不存在,则先插入key,再返回对应的引用
if (__i == end() || key_comp()(__k, (*__i).first))
__i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::tuple<>());
return (*__i).second;
}
lower_bound函数将会找到第一个大于等于该key值的位置，有则返回，没有便返回最合适的位置然后插入
set和map区别:
（1）map中的元素是pair（关键字—值）对：关键字起到索引的作用，
而Set的key跟value相等。
（2）set的迭代器是const的，不允许修改元素的值；
map允许修改value，但不允许修改key。
（3）map支持下标操作，set不支持下标操作
hashtable(哈希表)
数组+链表
当一个桶的链表元素个数大于等于桶的个数（哈希表长度）时，需要重新分配桶的个数，桶的数目扩大为最接近当前桶数两倍的质数,实际上,桶数目的增长顺序被写死在代码里:，将原来的元素重新计算哈希值搬到新的哈希表上面
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
6291469, 12582917, 25165843, 50331653, 100663319,
201326611, 402653189, 805306457, 1610612741,
3221225473ul, 4294967291ul};
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;
vector<node*, Alloc> buckets; // 保存桶的vector
size_type num_elements;
public:
size_type bucket_count() const { return buckets.size(); }
};
template<class Value>
struct __hashtable_node {
__hashtable_node *next;
Value val;
};
template<class Value, class Key, class HashFen, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
node *cur;
hashtable *ht;
};
那么hash-func如何计算出hash-code，
1.当传入为数值时，直接返回
2.而为字符串时，我们遍历我们每个字符asci数值进行计算，从而算出不同的hash-code值，值越混乱不容易发生碰撞
我们哈希表计算出数组索引（哈希函数）两步：
1.计算hash-code值
2.一般利用除留余数法算下标
迭代器的分类
迭代器的关联类型iterator_category表示迭代器类型,共5种,用类表示:input_iterator_tag、output_iterator_tag、forward_iterator_tag、bidirectional_iterator_tag和random_acess_iterator_tag.
不同容器的迭代器iterator_category值:
// 输出迭代器类型,使用函数重载以应对不同类型的迭代器
void _display_category(random_access_iterator_tag) { cout << "random_access_iterator" << endl; }
void _display_category(bidirectional_iterator_tag) { cout << "bidirectional_iterator" << endl; }
void _display_category(forward_iterator_tag) { cout << "forward_iterator" << endl; }
void _display_category(output_iterator_tag) { cout << "output_iterator" << endl; }
void _display_category(input_iterator_tag) { cout << "input_iterator" << endl; }
template<typename I>
void display_category(I itr) {
typename iterator_traits<I>::iterator_category cagy;
_display_category(cagy);
}
// 输出不同容器的迭代器类型
void test_iterator_category() {
display_category(array<int, 10>::iterator()); // random_access_iterator
display_category(vector<int>::iterator()); // random_access_iterator
display_category(list<int>::iterator()); // bidirectional_iterator
display_category(forward_list<int>::iterator()); // forward_iterator
display_category(deque<int>::iterator()); // random_access_iterator
display_category(set<int>::iterator()); // bidirectional_iterator
display_category(map<int, int>::iterator()); // bidirectional_iterator
display_category(multiset<int>::iterator()); // bidirectional_iterator
display_category(multimap<int, int>::iterator()); // bidirectional_iterator
display_category(unordered_set<int>::iterator()); // forward_iterator
display_category(unordered_map<int, int>::iterator()); // forward_iterator
display_category(unordered_multiset<int>::iterator()); // forward_iterator
display_category(unordered_multimap<int, int>::iterator()); // forward_iterator
display_category(istream_iterator<int>()); // input_iterator
display_category(ostream_iterator<int>(cout, "")); // output_iterator
}
容器array、vector、deque对使用者来说是连续空间,是可以跳跃的,其迭代器是random_access_iterator类型.
容器list是双向链表,容器set、map、multiset、multimap本身是有序的,他们的迭代器都可以双向移动,因此是bidirectional_iterator类型.
容器forward_list是单向链表,容器unordered_set、unordered_map、unordered_multiset、unordered_map哈希表中的每个桶都是单向链表.因此其迭代器只能**单向移动,**因此是forward_iterator类型.
迭代器istream_iterator和ostream_iterator本质上是迭代器,后文会提到这两个类的源码.
算法
算法accumulate
对容器指定范围做累计操作
算法accumulate的默认运算是+,但是重载版本允许自定义运算,支持所有容器,源码如下:
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
for (; first != last; ++first)
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 = binary_op(init, *first);
return init;
}
下面程序演示其使用:
#include <iostream> // std::cout
#include <functional> // std::minus
#include <numeric> // std::accumulate
// 自定义函数
int myfunc(int x, int y) { return x + 2 * y; }
// 自定义仿函数
struct myclass {
int operator()(int x, int y) { return x + 3 * y; }
} myobj;
int main() {
int init = 100;
int nums[] = {10, 20, 30};
cout << accumulate(nums, nums + 3, init); // 使用默认运算`+`,输出160
cout << accumulate(nums, nums + 3, init, minus<int>()); // 使用仿函数指定运算`-`, 输出40
cout << accumulate(nums, nums + 3, init, myfunc); // 使用自定义函数指定运算, 输出220
cout << accumulate(nums, nums + 3, init, myobj); // 使用四定义仿函数,输出280
return 0;
}
算法for_each
// 自定义函数
void myfunc(int i) { cout << ' ' << i; }
// 自定义仿函数
struct myclass {
void operator()(int i) { cout << ' ' << i; }
} myobj;
int main() {
vector<int> myvec = {10, 20, 30};
for_each(myvec.begin(), myvec.end(), myfunc); // 使用自定义函数,输出10 20 30
for_each(myvec.begin(), myvec.end(), myobj); // 使用自定义仿函数,输出10 20 30
// C++11引入的range-based for语法
for (auto &elem : myvec)//引用循环里的值变了，容器内元素也会变
elem += 5;
for (auto elem : myvec)
cout << ' ' << elem; // 输出15 25 35
return 0;
}
算法replace、replace_if、replace_copy
算法replace将范围内所有等于old_value的元素都用new_value取代.
算法replace_if将范围内所有满足pred()为true的元素都用new_value取代.
算法replace_copy将范围内所有等于old_value的元素都以new_value放入新区间,不等于old_value的元素直接放入新区间.
算法count、count_if
算法count计算范围内等于value的元素个数.
算法count_if计算范围内所有满足pred()为true的元素个数.
它们支持所有容器,但关联型容器(set、map、multiset、multimap、unordered_set、unordered_map、unordered_multiset和unordered_map)含有更高效的count成员方法,不应使用STL中的count函数.源码如下:
template<class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T &value) {
// 计算范围内等于value的元素个数
typename iterator_traits<InputIterator>::difference_type n = 0;
for (; first != last; ++first) /
if (*first == value)
++n;
return n;
}
template<class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred) {
// 计算范围内所有满足pred()为true的元素个数
typename iterator_traits<InputIterator>::difference_type n = 0;
for (; first != last; ++first)
if (pred(*first))
++n;
return n;
}
算法find、find_if
算法find查找范围内第一个等于value的元素.
算法find_if查找范围内第一个满足pred()为true的元素.
它们支持所有容器,但关联型容器(set、map、multiset、multimap、unordered_set、unordered_map、unordered_multiset和unordered_map)含有更高效的find方法,不应使用STL中的find函数.源码如下:
算法sort
算法sort暗示参数为random_access_iterator_tag类型迭代器,因此该算法只支持容器array、vector和deque.
容器list和forward_list含有sort方法.
容器set、map、multiset、multimap本身是有序的,容器unordered_set、unordered_map、unordered_multiset和unordered_map本身是无序的,不需要排序.
// 自定义函数
bool myfunc(int i, int j) { return (i < j); }
// 自定义仿函数
struct myclass {
bool operator()(int i, int j) { return (i < j); }
} myobj;
int main() {
int myints[] = {32, 71, 12, 45, 26, 80, 53, 33};
vector<int> myvec(myints, myints + 8); // myvec内元素: 32 71 12 45 26 80 53 33
sort(myvec.begin(), myvec.begin() + 4); // 使用默认`<`运算定义顺序,myvec内元素: (12 32 45 71)26 80 53 33
sort(myvec.begin() + 4, myvec.end(), myfunc); // 使用自定义函数定义顺序,myvec内元素: 12 32 45 71(26 33 53 80)
sort(myvec.begin(), myvec.end(), myobj); // 使用自定义仿函数定义顺序,myvec内元素: (12 26 32 33 45 53 71 80)
sort(myvec.rbegin(), myvec.rend()); // 使用反向迭代器逆向排序,myvec内元素: 80 71 53 45 33 32 26 12
return 0;
}
算法binary_search
算法binary_search从排好序的区间内查找元素value,支持所有可排序的容器.
算法binary_search内部调用了算法lower_bound,使用二分查找方式查询元素.
算法lower_bound和upper_bound分别返回对应元素的第一个和最后一个可插入位置.
仿函数源码分析
仿函数是struct 重载了()运算符的类,其对象可当作函数来使用,一般用于排序
STL的所有仿函数都必须继承自基类unary_function或binary_function,这两个基类定义了一系列关联类型,这些关联类型可被STL适配器使用.为了扩展性,我们自己写的仿函数也应当继承自这两个基类之一.
template<class Arg, class Result>
struct unary_function {
typedef Arg argument_type; // 关联类型1
typedef Result result_type; // 关联类型2
};
template<class Argl, class Arg2, class Result>
struct binary_function {
typedef Argl first_argument_type; // 关联类型1
typedef Arg2 second_argument_type; // 关联类型2
typedef Result result_type; // 关联类型3
};
// 算术运算类仿函数
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 minus : 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; }
};
template<class T>
struct less : public binary_function<T, T, bool> {
bool operator()(const T &x, const T &y) const { return x < y; }
}
不继承也可以，但没有继承自基类的仿函数无法与STL其他组件(尤其是函数适配器)结合起来.
仿函数自带的less()是从小到大，而greater()从大到小
适配器
容器适配器
STL中:
容器stack和queue是容器deque的适配器.
容器set、map、multiset和multimap是容器rb_tree的适配器.
容器unordered_set、unordered_multiset、unordered_map和unordered_multimap是容器hashtable的适配器.
上述源码在前文中均已分析过.
迭代器适配器
逆向迭代器reverse_iterator
容器的rbegin()和rend()方法返回逆向迭代器reverse_iterator,逆向迭代器的方向与原始迭代器相反.
逆向迭代器适配器reverse_iterator与正常迭代器的方向正好相反:逆向迭代器的尾(头)就是正向迭代器的头(尾);逆向迭代器的加(减)运算就是正向迭代器的减(加)运算.因此逆向迭代器取值时取得是迭代器前面一格元素的值.
