# C++ STL demon
参考:C++ STL 教程_w3cschool
在前面的章节中,我们已经进修了 C++ 模板的概念。C++ STL(尺度模板库)是一套功用强大的 C++ 模板类,供给了通用的模板类和函数,那些模板类和函数能够实现多种流行和常用的算法和数据构造,如向量、链表、队列、栈。
C++ 尺度模板库的核心包罗以下三个组件:
![image](https://note.youdao.com/yws/res/12911/0C536BE852234634838D27BB63EA5D8D)
那三个组件都带有丰硕的预定义函数,帮忙我们通过简单的体例处置复杂的使命。
下面的法式演示了向量容器(一个 C++ 尺度的模板),它与数组非常类似,独一差别的是,向量在需要扩展大小的时候,会主动处置它本身的存储需求:
```
#include <iostream>
#include <vector>
using namespace std ;
int main()
{
// 创建一个向量存储 int
vector<int> vec ;
int i ;
// 显示 vec 的原始大小
cout<<"vec的原始大小"<< vec.size()<<endl ;
// 推入 5 个值到向量中
for(i = 0 ; i < 5 ; i++)
{
vec.push_back(i);
}
// 显示 vec 扩展后的大小
cout<<"vec 扩展后的大小"<<vec.size()<<endl;
// 拜候向量中的 5 个值
for(int j = 0; j<5; j++)
{
cout<<"vec["<<j<<"]的值:"<<vec[j]<<endl;
}
// 利用迭代器 iterator 拜候值
vector<int>::iterator v = vec.begin();
while(v!= vec.end())
{
cout<<"value of v = "<< *v <<endl ;
v++;
}
return 0 ;
}
```
当上面的代码被编译和施行时,它会产生下列成果:
```
vector size = 0
extended vector size = 5
value of vec [0] = 0
value of vec [1] = 1
value of vec [2] = 2
value of vec [3] = 3
value of vec [4] = 4
value of v = 0
value of v = 1
value of v = 2
value of v = 3
value of v = 4
```
关于上面实例中所利用的各类函数,有几点要留意:
* push_back( ) 成员函数在向量的末尾插入值,若是有需要会扩展向量的大小。
* size( ) 函数显示向量的大小。
* begin( ) 函数返回一个指向向量开头的迭代器。
* end( ) 函数返回一个指向向量末尾的迭代器。
# STL 讲解
参考:C++中STL用法超详细总结_一只大笨猫的博客-CSDN博客_c++ stl
STL容器之vector容器巧用swap收缩空间 - BZ易风 - 博客园
c++---vector的利用_boke_fengwei-CSDN博客_vector随机拜候
C++ STL deque容器(详解版)
## STL是什么
STL(Standard Template Library),即尺度模板库,是一个具有工业强度的,高效的C++ 法式库。该库包罗了诸多在计算机科学范畴里所常用的**根本数据构造和根本算法**。为广阔C++ 法式员们供给了一个可扩展的应用框架,高度表现了**软件的可复用性**。
1. **STL的一个重要特点是数据构造和算法的别离**。egg: 因为STL的sort()函数是完全通用的,你能够用它来操做几乎任何数据 *** ,包罗链表,容器和数组。
2. STL另一个重要特征是它不是面向对象的。为了具有足够通用性,STL次要依赖于模板而不是封拆,继承和虚函数(多态性)——OOP的三个要素。你在STL中找不到任何明显的类继承关系。那仿佛是一种倒退,但那正好是使得STL的组件具有普遍通用性的底层特征。别的,因为STL是基于模板,内联函数的利用使得生成的代码短小高效。
## STL的内容
STL是由六大组件构成的:容器,迭代器,算法,仿函数,适配器,分配器。
### 容器
容器(Container),是一种数据构造,如list,vector,和deques ,以模板类的办法供给。为了拜候容器中的数据,能够利用由容器类输出的迭代器。
STL中的容器有队列容器和联系关系容器,容器适配器(congtainer adapters:stack,queue,priority queue),位集(bit_set),串包(string_package)等等。
#### 序列式容器(Sequence containers)
每个元素都有固定位置--取决于插入时机和地点,和元素值无关,**vector、deque、list**;
##### vector
vector是一个动态数组,能够随机存取元素(用索引间接存取), 数组尾部添加或移除元素十分快速。但是在中部或头部安插元素比力费时.
1. 特点:
* (1) 一个动态分配的数组(当数组空间内存不敷时,城市施行:分配新空间-复造元素-释放原空间);
* (2) 当删除元素时,不会释放限造的空间,所以向量容器的容量(capacity)大于向量容器的大小(size);
* (3) 关于删除或插入操做,施行效率不高,越靠后插入或删除施行效率越高;
* (4) 高效的随机拜候的容器。
2. vector的常用操做
* vector构造函数
```
vector<T> v; //接纳模板实现类实现,默认构造函数
vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给自己。
vector(n, elem);//构造函数将n个elem拷贝给自己。
vector(const vector &vec);//拷贝构造函数。
```
常用:egg vector<int> vec ; //vec即为int类型的动态数组
* vector大小操做:
```
size();//返回容器中元素的个数
empty();//判断容器能否为空
resize(int num);//从头指定容器的长度为num,若容器变长,则以默认值填充新位置。若是容器变短,则末尾超出容器长度的元素被删除。改动的是vector的size。
resize(int num, elem);//从头指定容器的长度为num,若容器变长,则以elem值填充新位置。若是容器变短,则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度,预留位置不初始化,元素不成拜候。改动的是capacity
```
* vector数据存取操做
```
at(int idx); //返回索引idx所指的数据,若是idx越界,抛出out_of_range异常。
operator[];//返回索引idx所指的数据,越界时,运行间接报错
front();//返回容器中之一个数据元素
back();//返回容器中最初一个数据元素
```
* vector插入和删除操做
```
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最初一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素 迭代器就是指针
clear();//删除容器中所有元素
//逆序遍历的迭代器:reverse_iterator rbegin(末尾的位置) rend(起头位置的前一个)
```
3. 巧用swap,收缩删除内存空间
```
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
//巧用swap收缩空间
void test01()
{
vector<int> v;
for (int i = 0; i < 100000; i++)
{
v.push_back(i);
}
cout << "v的容量:" << v.capacity() << endl; //13W+
cout << "v的大小:" << v.size() << endl; //10W
v.resize(3); //从头分配大小 大小变了 空间仍是13W+
cout << "v的容量:" << v.capacity() << endl; //13W+
cout << "v的大小:" << v.size() << endl; //3
//用swap收缩空间
vector<int>(v).swap(v); //匿名对象 拷贝构造一个临时对象 其分配了v.size()个元素的内存空间,即capacity为v.size()
//然后与v交换数据, 匿名对象销毁
cout << "v的容量:" << v.capacity() << endl; //3
cout << "v的大小:" << v.size() << endl; //3
//用swap肃清内存空间
vector<int>().swap(v); // 能够肃清v的内存空间
cout << "v的容量:" << v.capacity() << endl; //0
cout << "v的大小:" << v.size() << endl; //0
}
int main()
{
test01();
system("Pause");
return 0;
}
```
运行成果:
![image](https://note.youdao.com/yws/res/13020/8FD8C0B52AF44669B03E92DC86DEAC0C)
> vector<int>(v).swap(v); 拷贝构造一个临时对象 其分配了v.size()个元素的内存空间,即capacity为v.size()
> vector<int>().swap(v); // 能够肃清v的内存空间
4. 关于vector的size和capacity的区别:
关于笼统的问题,只要我们把它们同我们的生活现实相连系,将问题具象化,天然就会很好的理解。
就拿我们的办公室举例,假设,我们部分的办公地点位于公司大楼的六楼。在我们的办公室里面,放置了100套办公桌椅(工位),公司说根据一个萝卜一个坑来算,你们部分最多只能招那么多人,那么,那时我们能够说,我们部分的容量(即capacity)就是100人,若是我们部分是公司刚成立的部分,正处于开展强大的阶段,目前只要40为员工,也就是说,办公室里只坐了40小我,别的60个工位是空着的,那么,我们能够说,我们部分当前的大小(即size)是40人。那现实上就是size和capacity的区别。类比到vector,size和capacity的概念天然就很清晰了。
##### deque容器
1. 概述:
deque 是 double-ended queue的缩写,又称双端队列容器。前面末节中,我们已经系统进修了 vector 容器,值得一提的是,deque 容器和 vecotr 容器有良多类似之处,好比:
* deque 容器也擅长在序列尾部添加或删除元素(时间复杂度为O(1)),而不擅长在序列中间添加或删除元素。
* deque 容器也能够按照需要修改本身的容量和大小。
和 vector 差别的是:
* deque 还擅长在序列头部添加或删除元素,所消耗的时间复杂度也为常数阶O(1)。
* **而且更重要的一点是,deque 容器中存储元素其实不能包管所有元素都存储到持续的内存空间中**。
> 当需要向序列两头频繁的添加或删除元素时,应首选 deque 容器。
利用deque 容器,代码中需要包罗下面两行代码:
```
#include <deque>
using namespace std;
```
2. 创建deque容器的几种体例:
创建 deque 容器,按照差别的现实场景,可选择利用如下几种体例。
* deque<int> d; //创建一个没有任何元素的空 deque 容器。
* deque<int> d(10); //deque<int> d(10);
* deque<int> d(10, 5); //创建一个具有 10 个元素的 deque 容器,并为每个元素都指定初始值5。
* 在已有 deque 容器的情况下,能够通过拷贝该容器创建一个新的 deque 容器,例如:
```
deque<int> d1(5);
deque<int> d2(d1);
```
留意,接纳此体例,必需包管新旧容器存储的元素类型一致。
* 通过拷贝其他类型容器中指定区域内的元素(也能够是通俗数组),能够创建一个新容器,例如:
```
//拷贝通俗数组,创建deque容器
int a[] = { 1,2,3,4,5 };
deque<int>d(a, a + 5);
//适用于所有类型的容器
array<int, 5>arr{ 11,12,13,14,15 };
deque<int>d(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}
```
|函数成员 | 函数功用|
|:--|:--|:--|
|begin()|返回指向容器中之一个元素的迭代器。|
|end()| 返回指向容器最初一个元素所在位置后一个位置的迭代器,凡是和 begin() 连系利用|
|size() |返回现实元素个数|
|max_size()|返回容器所能包容元素个数的更大值。那凡是是一个很大的值,我们很少会用到那个函数。|
|resize()|改动现实元素的个数|
|empty()|判断容器中能否有元素,若无元素,则返回 true;反之,返回 false。|
|shrink _to_fit()|将内存削减到等于当前元素现实所利用的大小。|
|at()|利用颠末鸿沟查抄的索引拜候元素。|
|front()|返回之一个元素的引用。|
|back()|返回最初一个元素的引用。|
|push_back()|在序列的尾部添加一个元素。|
|push_front()|在序列的头部添加一个元素。|
|pop_back()|移除容器尾部的元素。|
|pop_front()|移除容器头部的元素。|
|swap()|交换两个容器的所有元素。|
> 和 vector 比拟,额外增加了实如今容器头部添加和删除元素的成员函数,同时删除了 capacity()、reserve() 和 data() 成员函数。
##### List
双向链表,不供给随机存取(按挨次走到需存取的元素,O(n)),在任何位置上施行插入或删除动做都十分敏捷,内部只需调整一下指针。
1. list构造函数
```
list<int> L0; // 空链表
list<int> L1(9); // 建一个含个默认值0是的9元素的链表
//链表内容0.0.0.0.0.0.0.0.0.0
list<int> L2(5, 1); // 建一个含个5元素的链表,值都是1
//链表内容1.1.1.1.1
list<int> L3(L2); // 建一个L2的copy链表
//链表内容1.1.1.1.1
list<int> L4(L0.begin(), L0.end());//建一个含L0一个区域的元素
//链表内容0.0.0.0.0.0.0.0.0.0
```
轮回输出链表所有值:
```
void showlist(list<int> a)
{
for (list<int>::iterator i = a.begin(); i!=a.end();i++ )
{
cout<< *i <<"_";
}
cout <<endl;
}
```
2. assign()分配值,有两个重载
```
L1.assign(4,3); // L1(3,3,3,3)
```
3. front()返回之一个元素的引用
```
int nRet = list1.front() // nRet = 1
```
4. back()返回最初一元素的引用
```
int nRet = list1.back() // nRet = 3
```
5. begin()返回之一个元素的指针(iterator)
```
it = list1.begin(); // *it = 1
```
6. end()返回最初一个元素的下一位置的指针(list为空时end()=begin())
```
it = list1.end();
--it; // *it = 3
```
7. push_back()增加一元素到链表尾
```
list1.push_back(4) // list1(1,2,3,4)
```
8. push_front()增加一元素到链表头
```
list1.push_front(4) // list1(4,1,2,3)
```
9. pop_back()删除链表尾的一个元素
```
list1.pop_back() // list1(1,2)
```
10. pop_front()删除链表头的一元素
```
list1.pop_front() // list1(2,3)
```
11. empty()判断能否链表为空
```
bool bRet = L1.empty(); //若L1为空,bRet = true,不然bRet = false。
```
12. size()返回链表中元素个数
```
list<int>::size_type nRet = list1.size(); // nRet = 3
```
#### 联系关系式容器(Associated containers)
概述: 元素位置取决于特定的排序原则,和插入挨次无关,set、multiset、map、multimap等。map/multimap,set/multiset都为c++中的尺度容器,它们的底层都是用红黑树实现的,因而在停止查询,修改,删除等操做上具有很高的效率,能够到达O(logN)。
##### Set/Multiset
###### 概述
1. 内部的元素根据其值主动排序,Set内的不异数值的元素只能呈现一次,Multisets内可包罗多个数值不异的元素,内部由二叉树实现,便于查找。
和所有的尺度联系关系容器类似,sets和multisets凡是以平衡二叉树完成。
![image](https://note.youdao.com/yws/res/13224/3BD034F4088D49ACA3E37EF2F472AD8A)
主动排序的次要长处在于使二叉树搜索元素具有优良的性能,在其搜刮函数算法具有对数复杂度。但是主动排序也形成了一个限造,不克不及间接改动元素值,因为如许会打乱原有的挨次,要改动元素的值,必需先删除旧元素,再插入新元素。所以sets和multisets具有以下特点:
* 不供给间接用来存取元素的任何操做元素
* 通过迭代器停止元素的存取。
2. set demon:
```
#include <iostream>
#include <set>
using namespace std ;
typedef set<int,greater<int> > Intset ; //从大到小排序
int main()
{
Intset coll1 ;
//随机插入元素
coll1.insert(4);
coll1.insert(3);
coll1.insert(5);
coll1.insert(1);
coll1.insert(6);
coll1.insert(2);
coll1.insert(5);
Intset ::iterator p = coll1.begin();
int i = 0 ;
for(p; p!= coll1.end();p++)
{
i++ ;
cout<<"coll1的第"<<i <<"个元素"<<*p<<endl;
}
return 0 ;
}
```
3. multiset demon
```
#include <iostream>
#include <set>
using namespace std;
int main()
{
/*type of the collection:
*-duplicates allowed
*-elements are integral values
*-descending order
*/
typedef multiset<int,greater<int> > IntSet;
IntSet coll1, // empty multiset container
//insert elements in random order
coll1.insert(4);
coll1.insert(3);
coll1.insert(5);
coll1.insert(l);
coll1.insert(6);
coll1.insert(2);
coll1.insert(5);
//iterate over all elements and print them
IntSet::iterator pos;
for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
cout << *pos << ;
}
cout << endl;
//insert 4 again and process return value
IntSet::iterator ipos = coll1.insert(4);
cout << "4 inserted as element "
<< distance (coll1.begin(),ipos) + 1
<< endl;
//assign elements to another multiset with ascending order
multiset<int> coll2(coll1.begin(),
coll1.end());
//print all elements of the copy
copy (coll2.begin(), coll2.end(),
ostream_iterator<int>(cout," "));
cout << endl;
//remove all elements up to element with value 3
coll2.erase (coll2.begin(), coll2.find(3));
//remove all elements with value 5
int num;
num = coll2.erase (5);
cout << num << " element(s) removed" << endl;
//print all elements
copy (coll2.begin(), coll2.end(),
ostream_iterator<int>(cout," "));
cout << endl;
}
```
###### 操做函数
1. 构造
函数 | 功用
---|---
set c |产生一个空的set/multiset,不含任何元素
set c(op)| 以op为排序原则,产生一个空的set/multiset
set<Elem>|产生一个set,以(operator <)为排序原则
set<Elem,0p>|产生一个set,以op为排序原则
2. 拷贝
函数 | 功用
---|---
set c1(c2) |产生某个set/multiset的副本,所有元素都被拷贝
set c(beg,end)|以区间[beg,end)内的所有元素产生一个set/multiset
set c(beg,end,op)|以op为排序原则,区间[beg,end)内的元素产生一个set/multiset
3. 销毁
c.~set(): 销毁所有元素,释放内存
4. 非变更性操做
函数|功用
---|---
c.size()|返回当前的元素数量
c.max_size()|返回能包容的元素更大数量
c.empty ()|判断大小能否为零,等同于0 == size(),效率更高
c1 == c2|判断c1能否等于c2
c1 != c2|判断c1能否不等于c2(等同于!(c1==c2))
5. 该数据构造自带的特殊的搜刮函数
函数|功用
---|---
count (elem)|返回元素值为elem的个数
find(elem)|返回元素值为elem的之一个元素,若是没有返回end()
lower _bound(elem) | 返回元素值为elem的之一个可安插位置,也就是元素值 >= elem的之一个元素位置
upper _bound (elem) |返回元素值为elem的最初一个可安插位置,也就是元素值 > elem 的之一个元素位置
equal_range (elem)| 返回elem可安插的之一个位置和最初一个位置,也就是元素值==elem的区间
6. 赋值
函数 | 功用
---|---
c1 = c2|将c2的元素全数给c1
c1.swap(c2) |将c1和c2 的元素互换
swap(c1,c2)|同上,全局函数
7. 迭代器相关函数
sets和multisets的迭代器是双向迭代器,对迭代器操做而言,所有的元素都被视为常数,能够确保你不会报酬改动元素值,从而打乱既定挨次,所以无法挪用变更性算法,如remove()。
函数|功用
---|---
c.begin() | 返回一个随机存取迭代器,指向之一个元素
c.end() | 返回一个随机存取迭代器,指向最初一个元素的下一个位置
8. 安插和删除元素
必需包管参数有效,迭代器必需指向有效位置,序列起点不克不及位于起点之后,不克不及从空容器删除元素。
函数|功用
---|---
c.insert(elem)|插入一个elem副本,返回新元素位置,无论插入胜利与否。
c.insert(pos,elem)|安插一个elem元素副本,返回新元素位置,pos为收索起点,提拔插入速度。
c.insert(beg,end)|将区间[beg,end)所有的元素安插到c,无返回值。
c.erase(elem)|删除与elem相等的所有元素,返回被移除的元素个数。
c.erase(pos)|移除迭代器pos所指位置元素,无返回值。
c.erase(beg,end)|移除区间[beg,end)所有元素,无返回值。
c.clear()|移除所有元素,将容器清空
##### Map/Multimap
Map的元素是成对的键值/实值,内部的元素根据其值主动排序,Map内的不异数值的元素只能呈现一次,Multimap内可包罗多个数值不异的元素,内部由二叉树实现,便于查找。Map不允许key值反复,而Multimap允许。
**demon**
```
#pragma once
#include<map>
#include<set>
#include<string>
#include<iostream>
using namespace std;
//map与set都是c++里面的尺度容器,它们底层的实现都是通过红黑树完成的,而map与set的区别在与map为kay-value构造,而set为key构造
//因为是红黑树,所以它里面不允许有不异kay值存在,所以若反复插入,成果稳定。
void myTest()
{
multimap<string, string> myMap;
myMap.insert(make_pair("right", "右边"));
myMap.insert(make_pair("hello", "你好"));
myMap.insert(make_pair("where", "哪里"));
myMap.insert(make_pair("fjt","华南理工大学计算机学院电子信息计算机手艺全日造专业硕士"));
myMap.insert(make_pair("fjt","香港科技大学全日造博士")); //multimap允许key反复,能够插入
//myMap["1112"] = "无语de today";
map<string, string>::iterator it = myMap.begin();
for (; it != myMap.end(); it++)
{
cout << (*it).first<<" "<<(*it).second<<endl;
}
}
void myTest2()
{
map<string, string> Map;
Map.insert(make_pair("right", "右边"));
Map.insert(make_pair("hello", "你好"));
Map.insert(make_pair("fjt", "香港科技大学计算机科学全奖博士"));
Map.insert(make_pair("fjt", "SCUT")); //查找key能否存在,若是已存在,则插入失败
map<string,string>::iterator p = Map.begin();
while(p != Map.end())
{
cout<<(*p).first<<" "<<(*p).second<<endl;
cout<<"------"<<endl;
p++;
}
// return ;
}
int main()
{
cout<<"myTest()运行"<<endl ;
myTest();
cout<<"----------------------------"<<endl;
cout<<"myTest2()运行"<<endl;
myTest2();
cout<<"-----------------------------"<<endl ;
return 0 ;
}
```
它的make_pair(k,v)办法即是用来生成pair类型的变量的。
Map.insert(make_pair("fjt", "香港科技大学计算机科学全奖博士"));。
若是间接利用Map.insert("fjt","香港科技大学计算机科学全奖博士")法式无法通过编译。
### STL迭代器
Iterator(迭代器)形式又称Cursor(游标)形式。Iterator形式是运用于聚合对象的一种形式,通过运用该形式,使得我们能够在不晓得对象内部暗示的情况下,根据必然挨次(由iterator供给的办法)拜候聚合对象中的各个元素。
迭代器的感化:可以让迭代器与算法不干扰的彼此开展,最初又能无间隙的粘合起来,重载了*,++,==,!=,=运算符。用以操做复杂的数据构造,容器供给迭代器,算法利用迭代器;常见的一些迭代器类型:==iterator、const_iterator、reverse_iterator和const_reverse_iterator==.
迭代器利用办法:
```
容器::iterator iter;
for(iter= 容器.begin();iter!=容器.end();iter++){undefined
cout<<*iter或者是 iter->first等等之类的 //迭代器就是那么个套路
}
```
### 算法
函数库对数据类型的选择对其可重用性起着至关重要的感化。举例来说,一个求方根的函数,在利用浮点数做为其参数类型的情况下的可重用性必定比利用整型做为它的参数类性要高。而C++通过模板的机造允许推延对某些类型的选择,**曲到实正想利用模板或者说对模板停止特化的时候**,STL就操纵了那一点供给了相当多的有用算法。**它是在一个有效的框架中完成那些算法的——你能够将所有的类型划分为少数的几类,然后就能够在模版的参数中利用一品种型替代掉统一品种中的其他类型。**
STL供给了大约100个实现算法的模版函数,好比算法for_each将为指定序列中的每一个元素挪用指定的函数,stable_sort以你所指定的规则对序列停止不变性排序等等。只要我们熟悉了STL之后,许多代码能够被大大的化简,只需要通过挪用一两个算法模板,就能够完成所需要的功用并大大地提拔效率。
算法部门次要由头文件<algorithm>,<numeric>和<functional>构成。
1. <algorithm>是所有STL头文件中更大的一个(虽然它很好理解),它是由一大堆模版函数构成的,能够认为每个函数在很大水平上都是独立的,此中常用到的功用范畴涉及到比力、交换、查找、遍历操做、复造、修改、移除、反转、排序、合并等等。
2. <numeric>体积很小,只包罗几个在序列上面停止简单数学运算的模板函数,包罗加法和乘法在序列上的一些操做。
3. <functional>中则定义了一些模板类,用以声明函数对象。
**STL中算法大致分为四类:**
* 非可变序列算法:指不间接修改其所操做的容器内容的算法。
* 可变序列算法:指能够修改它们所操做的容器内容的算法。
* 排序算法:对序列停止排序和合并的算法、搜刮算法以及有序序列上的 *** 操做。
* 数值算法:对容器内容停止数值计算。
#### 查找算法:判断容器中能否包罗某个值
1. adjacent_find:在iterator对标识元素范畴内,查找一对相邻反复元素,找到则返回指向那对元素的之一个元素的Forward Iterator。不然返回last。重载版本利用输入的二元操做符取代相等的判断。
2. binary_search: 在有序序列中查找value,找到返回true。
3. count: 操纵等于操做符,把标记范畴内的元素与输入值比力,返回相等元素个数。
4. count_if: 操纵输入的操做符,对标记范畴内的元素停止操做,返回成果为true的个数。
5. equal_range: 功用类似equal,返回一对iterator,之一个暗示lower_bound,第二个暗示upper_bound。
6. find: 操纵底层元素的等于操做符,对指定范畴内的元素与输入值停止比力。当婚配时,完毕搜刮,返回该元素的一个InputIterator。
7. search: 给出两个范畴,返回一个ForwardIterator,查找胜利指向之一个范畴内之一次呈现子序列(第二个范畴)的位 置,查找失败指向last1。重载版本利用自定义的比力操做。
8. search_n: 在指定范畴内查找val呈现n次的子序列。重载版本
利用自定义的比力操做。
#### 排序和通用算法:供给元素排序战略
1. inplace_merge: 合并两个有序序列,成果序列笼盖两头范畴
2. merge: 合并两个有序序列,存放到另一个序列。重载版本利用自定义的比力。
3. nth_element: 将范畴内的序列从头排序,使所有小于第n个元素的元素都呈现在它前面,而大于它的都呈现在后面。重载版本利用自定义的比力操做。
4. partial_sort: 对序列做部门排序,被排序元素个数正好能够被放到范畴内。重载版本利用自定义的比力操做。
5. partial_sort_copy: 与partial_sort类似,不外将颠末排序的序列复造到另一个容器。
6. partition: 对指定范畴内元素从头排序,利用输入的函数,把成果为true的元素放在成果为false的元素之前。
7. random_shuffle: 对指定范畴内的元素随机调整次序。重载版本输入一个随机数产生操做。
8. reverse: 将指定范畴内元素从头反序排序。
9. reverse_copy: 与reverse类似,不外将成果写入另一个容器。
10. rotate: 将指定范畴内元素移到容器末尾,由middle指向的元素成为容器之一个元素。
11. rotate_copy: 与rotate类似,不外将成果写入另一个容器。
12. sort: 以升序从头摆列指定范畴内的元素。重载版本利用自定义的比力操做。
13. stable_sort: 与sort类似,不外保留相等元素之间的挨次关系。
14. stable_partition: 与partition类似,不外不包管保留容器中的相对挨次。
#### 删除和替代算法
1. copy: 复造序列
2. copy_backward: 与copy不异,不外元素是以相反挨次被拷贝。
3. iter_swap: 交换两个ForwardIterator的值。
4. remove: 删除指定范畴内所有等于指定元素的元素。留意,该函数不是实正删除函数。内置函数不合适利用remove和 remove_if函数:
6. remove_copy: 将所有不婚配元素复造到一个造定容器,返回Output Iterator指向被拷贝的末元素的下一个位置。
7. remove_if: 删除指定范畴内输入操做成果为true的所有元素。
8. remove_copy_if: 将所有不婚配元素拷贝到一个指定容器。
9. replace: 将指定范畴内所有等于vold的元素都用vnew取代。
10. replace_copy: 与replace类似,不外将成果写入另一个容器。
11. replace_if: 将指定范畴内所有操做成果为true的元素用新值取代。
12. replace_copy_if: 与replace_if,不外将成果写入另一个容器。
swap: 交换存储在两个对象中的值。
13. swap_range: 将指定范畴内的元素与另一个序列元素值停止交换。
14. unique: 肃清序列中反复元素,和remove类似,它也不克不及实正删除元素。重载版本利用自定义比力操做。
15. unique_copy: 与unique类似,不外把成果输出到另一个容器。
#### 摆列组合算法:供给计算给定 *** 按必然挨次的所有可能摆列组合
1. next_permutation: 取出当前范畴内的摆列,并从头排序为下一个摆列。重载版本利用自定义的比力操做。
2. prev_permutation: 取出指定范畴内的序列并将它从头排序为上一个序列。若是不存在上一个序列则返回false。重载版本利用自定义的比力操做。
#### 算术算法(4个)
1. accumulate:iterator对标识的序列段元素之和,加到一个由val指定的初始值上。重载版本不再做加法,而是传进来的二元操做符被应用到元素上。
2. partial_sum:创建一个新序列,此中每个元素值代表指定范畴内该位置前所有元素之和。重载版本利用自定义操做取代加法。
3. inner_product: 对两个序列做内积(对应元素相乘,再乞降)并将内积加到一个输入的初始值上。重载版本利用用户定义的操做。
4. adjacent_difference:创建一个新序列,新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操做计算相邻元素的差。
#### 生成和异变算法(6个)
![image](https://note.youdao.com/yws/res/13520/59817C98C7664822A2E8EDF4F83EF801)
#### 关系算法(8个)
![image](https://note.youdao.com/yws/res/13523/73F2031CFC144EB1AD0B755F23F2E231)
#### *** 算法(4个)
![image](https://note.youdao.com/yws/res/13528/4D074C7B6423477CB832616CE6D7A1FC)
#### 堆算法(4个)
![image](https://note.youdao.com/yws/res/13531/657B26620D284699969ABFC5EB66A58C)
### 仿函数
#### 概述:
仿函数(functor),就是使一个类的利用看上去象一个函数。其实现就是类中实现一个operator(),那个类就有了类似函数的行为,就是一个仿函数类了。有些功用的的代码,会在差别的成员函数顶用到,想复用那些代码。
* 公共的函数: 那是一个处理办法,不外函数用到的一些变量,就可能成为公共的全局变量,再说为了复用那么一片代码,就要单立出一个函数,也不是很好维护。
* 仿函数:写一个简单类,除了那些维护一个类的成员函数外,就只是实现一个operator(),在类实例化时,就将要用的,非参数的元素传入类中。求–函数指针无法和STL其他组件搭配,产生更灵敏变革。
#### 自定义仿函数:
```
#include <iostream>
#include <functional>
using namespace std ;
struct MyPlus{
int operator()(const int &a , const int &b) const{
return a + b;
}
};
int main()
{
MyPlus a;
cout << MyPlus()(1,2) << endl;//1、通过产生临时对象挪用重载运算符
cout << a.operator()(1,2) << endl;//2、通过对象显示挪用重载运算符
cout << a(1,2) << endl;//3、通过对象类似函数挪用 隐示地挪用重载运算符
return 0;
}
```
#### STL内建的仿函数
要利用STL内建的仿函数,必需包罗<functional>头文件。而头文件中包罗的仿函数分类包罗:算术类仿函数、关系运算类仿函数、逻辑运算仿函数。
##### 算术类仿函数
![image](https://note.youdao.com/yws/res/13568/11E9FD7082264EB886916683F9CB0912)
```
#include <iostream>
#include <numeric>
#include <vector>
#include <functional>
using namespace std;
int main()
{
int ia[] = { 1,2,3,4,5 };
vector<int> iv(ia, ia + 5);
//120
cout << accumulate(iv.begin(), iv.end(), 1, multiplies<int>()) << endl;
//15
cout << multiplies<int>()(3, 5) << endl;
modulus<int> modulusObj;
cout << modulusObj(3, 5) << endl; // 3
system("pause");
return 0;
}
```
##### 关系运算类仿函数
![image](https://note.youdao.com/yws/res/13573/B782FA46AC784C92881CA16FE5C9007D)
从大到小排序:
```
#include <iostream>
#include <algorithm>
#include<functional>
#include <vector>
using namespace std;
template <class T>
class display
{
public:
void operator()(const T &x)
{
cout << x << " ";
}
};
int main()
{
int ia[] = { 1,5,4,3,2 };
vector<int> iv(ia, ia + 5);
sort(iv.begin(), iv.end(), greater<int>());
for_each(iv.begin(), iv.end(), display<int>());
system("pause");
return 0;
}
```
##### 逻辑运算仿函数
![image](https://note.youdao.com/yws/res/13579/6DF16FB2B04B45E18C0892F1C33FC1FB)