1 STL初识

1.1 STL基本概念

STL（Standard Template Library）标准模板库

STL从广义上分为：容器(container) 算法(algorithm) 迭代器(iterator)

容器和算法之间通过迭代器进行无缝连接

1.2 STL六大组件

容器、算法、迭代器、仿函数、适配器、空间配置器

  • 容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据
  • 算法：各种常用算法，如sort、find、copy、for_each等
  • 迭代器：扮演了容器与算法之间的胶合剂
  • 仿函数：行嘞类似函数，可作为算法的某种策略
  • 适配器：用来修饰容器或仿函数或迭代器接口的东西。
  • 空间配置器：负责空间配置和管理

1.3 算法和迭代器

1.3.1 算法

  • 质变算法：运算过程会更改区间内的元素内容，如拷贝、替换、删除等
  • 非质变算法：运算过程不会改变区间内的元素内容，如查找，计数，遍历等

1.3.2 迭代器

每一个容器都有属于自己的迭代器（迭代器与指针非常类似）

image-20240308164731980

常用的容器迭代器类型为双向迭代器和随机访问迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <algorithm>
void myPrint(int val){
    cout << val;
}
void main(){
    vector<int> a;
    a.push_back(10);
    vector<int>::iterator itBegin = v.begin();
    vector<int>::iterator itEnd = v.end();
    //第一种遍历方式
    while(itBegin!=itEnd){
        cout<<*itBegin<<endl;
        itBegin++;
    }
    //第二种遍历方式
    for(vector<int>::iterator it = v.begin(); it!=v.end(); it++){
        cout<<*it<<endl;
    }
    //第三种遍历方式
    for_each(v.begin(), v.end(), myPrint);
}

2 STL常用容器

2.1 string容器

string本质上是一个类，是C++风格的字符串

**string 和 char *的区别**

  • char *是一个指针
  • string是一个类，类的内部封装了char *，管理这个字符串

2.1.1 string的构造函数

  • string(); //创建一个空字符串
  • string(const char* s); //使用字符串s初始化
  • string(const string& str);//使用string对象初始化
  • string(int n, char c); //使用n个字符c初始化
1
2
3
4
5
6
7
8
9
10
11
12
//括号法
string s1;
string s2("vicczyq");
string s3(s2);
string s4(10,'1');

//显示法
string s1 = string("vicczyq");

//隐式转换法
string s1 = "vicczyq";
string s2 = s1;

2.1.2 string赋值操作

1
2
3
4
5
6
7
string &operator=(const char *s);
string &operator=(const string &s);
string &operator=(char c);//把一个字符赋值给string
string &assign(const char *s);
string &assign(const char *s, int n);//把前n个字符赋值给string
string &assign(const string &s);
string &assign(int n,char c);
1
2
3
4
5
6
7
8
string s1,s2,s3;
s1 = "vicczyq";
s2 = s1;
s3 = 'a';
s1.assign("vicczyq");
s1.assign("vicczyq",2);
s1.assign(s2);
s1.assgin(10,'a');

2.1.3 string拼接

1
2
3
4
5
6
7
8
string &operator+=(const char *s);
string &operator+=(const char c);
string &operator+=(const string &s);
string &append(const char *s);
string &append(const char c);
string &append(const string &s);
string &append(const string &s, int pos, int n);
//字符串s中从pos开始的n个字符连接到末尾

2.1.4 string查找和替换

1
2
3
4
5
6
7
8
9
10
int find(const string &str, int pos = 0) const;

//查找s的前n个字符第一次出现的位置
int find(const char* s,int pos=0, int n)const;

//查找str最后出现的位置
int rfind(const string &str, int pos = npos)const;

//从pos开始查找s的前n个字符最后一次出现的位置
int rfind(const char* s,int pos, int n)const;
1
2
string &replace(int pos, int n, const string &str);
//从pos开始n个字符替换为str

巧记：“字符串在前为查找，在后为替换，所以是查找和替换”

2.1.5 stirng字符串比较

根据字符串ASCII码值进行比较

等于返回0，大于返回1，小于返回-1

函数原型：

  • int compare(const string &s)const;
  • int compare(const char *s);
1
2
string s1 = "vicczyq", s2="vicczyq";
if(s1.compare(s2)==0)cout<<"yes!"<<endl;

也可以用运算符重载

1
if(s1==s2)cout<<"yes"<<endl;

2.1.6 string字符存取

有两种方式：

  • char &operator[](int n)
  • char &at(int n)

取：

1
2
3
string s1="vicczyq";
cout<<s1[0]<<endl;
cout<<s1.at(0)<<endl;

存：

1
2
s1[0]='V';
s1.at(0)='v';

2.1.7 string插入和删除

  • string& insert(int pos, const char* s) //插入字符串
  • string& inster(int pos, const string &str)
  • string& insert(int pos, int n, char c) //在指定位置插入n个c
  • string& erase(int pos, int n=npos) //删除从pos开始的n个字符

2.1.8 string子串获取

string substr(int pos=0, int n=npos)const;

//从pos开始，多少个字符作为子串，返回

2.1.9 string迭代器

1
2
3
4
5
6
7
string str = "vicczyq";
for(string::iterator it = str.begin(); it != str.end(); it++){
	cout << *it << endl;//vicczyq
}
for (string::reverse_iterator it = str.rbegin(); it != str.rend(); it++){
	cout << *it << endl;//qyzcciv
}

2.2 vector容器

vector数据结构和数组非常相似，也成为单端数组

普通数组用的是静态空间，而vector采用动态扩展

2.2.0 动态扩展

动态扩展并不是在元空间的基础上续接新空间，而是找到更大的内存空间，将原数据拷贝到新空间，并释放原空间。

可能会多扩展一些，具体是STL内部算法实现。

2.2.1 基本结构

采用模板类实现的。

image-20240309123617832 
1
2
3
4
vector<T> v;	//默认构造
vector<T> v1(v.begin(),v.end());//区间拷贝构造
vector<T> v2(n, elem);//将n个elem拷贝给本身
vector<T> v3(const vector &vec);//拷贝构造

2.2.2 赋值操作

1
2
3
vector &operator=(const vector &vec);//重载等号赋值
assign(beg, end); //将[beg,end)之间的数据拷贝赋值给自身
assign(n, elem);//将n个elem赋值给本身
1
2
3
4
vector<int> v1(10,100),v2;
v2 = v1;
v2.assign(v1.begin(),v1.end());
v2.assign(10,100);

2.2.3 容量和大小

1
2
3
4
5
empty();					//判断是否为空
capacity()					//容器容量
size()						//容器中元素个数
resize(int num);		//重新指定容器的长度为num，若容器变短，末尾超出的元素会被删除，若变长则以默认值填充
resize(int num, elem);	//重新指定容器的长度为num，若容器变短，末尾超出的元素会被删除，若变长则以elem填充新位置

2.2.4 插入和删除

1
2
3
4
5
6
7
push_back(elem);					//尾部插入elem
pop_back();							//删除最后一个元素
insert(const_iterator pos, elem);			//向迭代器指向的pos位置插入elem
insert(const_iterator pos, int n, elem);	//向迭代器指向的位置插入n个elem
erase(const_iterator pos);					//删除迭代器指向的元素
erase(const_iterator start, const_iterator end);//删除区间内的元素
clear();									//删除容器内所有元素

2.2.5 数据存取

1
2
3
4
at(int idx);	//返回索引idx所指的数据
operator[];		
front();		//返回第一个数据元素
back();			//返回最后一个数据元素

2.2.6 vector互换容器

1
swap(vec);		//将vec与本身的元素进行互换

实际用途：巧用swap可以收缩内存空间

解释：

1
2
3
4
5
for(int i=0; i<100000; i++){
	v.push_back(i);
}
cout << "v的容量："<< v.capacity() << endl;
cout << "v的大小："<< v.size() << endl;
image-20240309131309430

虽然只存入了10000个数据，但是vector会多扩展一些内存空间

1
2
3
4
//此时使用
v.resize(3);
cout << "v的容量："<< v.capacity() << endl;
cout << "v的大小："<< v.size() << endl;
image-20240309131553262

容量并不会变小，这样会导致空间过于浪费

1
vector<int>(v).swap(v);
image-20240309132257980

vector<int>(v1)为匿名对象，通过拷贝构造创建，创建时会按照v的元素个数进行设置容量，再和v进行交换。

如果新创建一个普通对象来交换会存在更大的空间浪费，但是匿名对象就可以解决

匿名对象：当前行执行完成，系统会自动进行回收

2.2.7 vector预留空间

1
reserve(int len);//容器预留len个元素长度，预留位置不会初始化，元素不可访问

可以减少内存重新分配的次数

1
2
3
4
5
6
7
8
9
10
11
vector<int> v;
int num = 0;
int* p = NULL;
for (int i = 0; i < 1e6; i++) {
	v.push_back(i);
	if (p != &v[0]) {
		num++;
		p = &v[0];
	}
}
cout << num << endl;//此时需要多次动态扩展
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> v;
v.reserve(1e6);//进行空间预留操作
int num = 0;
int* p = NULL;
for (int i = 0; i < 1e6; i++) {
	v.push_back(i);
	if (p != &v[0]) {
		num++;
		p = &v[0];
	}
}
cout << num << endl;//此时只需要1次内存分配

2.3 deque容器

双端数组，可以对头端和尾端进行插入和删除

与vector的区别：

  • vector对于头部插入效率低，deque对头部的插入和删除速度快
  • vector访问元素的速度比deque快（与各自的实现原理有关）
image-20240309152351353

实现原理：

image-20240309152642579

中空气维护每个缓冲区的地址，使得deque像一片连续的内存空间

缓冲区中存放真实的数据。

2.3.1 构造函数

1
2
3
4
deque<T> deq0;
deque<T> deq1(deq0.begin(),deq0.end());
deque<T> deq2(n, elem);
deque<T> deq3(const deque &deq);

2.3.2 赋值操作

1
2
3
deque &operator(const deque &deq);
assign(beg,end);
assign(n, elem);

2.3.3 容量和大小

1
2
3
4
empty();
size();
resize(int num);
resize(int num, elem);

deque不像vector有capacity

2.3.4 插入和删除

两端插入删除操作：

1
2
3
4
push_back(elem);
push_front(elem);
pop_back(elem);
push_front(elem);

指定位置的操作

1
2
3
4
5
6
insert(const_iterator pos, elem);//返回新数据的位置
insert(const_iterator pos, n, elem);//无返回值
insert(const_iterator pos, const_iterator begin, const_iterator end);//插入[begin,end)之间的数据，无返回值
clear();
erase(const_iterator pos);
erase(const_iterator beg,const_iterator end);

2.3.5 数据存取

1
2
3
4
at(int idx);
operator[];
front();
back();
1
2
3
4
5
6
7
deque<int> deq;
deq.push_front(100);
deq.push_back(200);
deq.front()=0;
deq[0]=0;
deq.at(0)=0;
cout<<deq[0]<<deq.at(0)<<deq.front()<<deq.back();

2.4 stack 容器

先进后出（FILO）数据结构——栈

只有栈顶元素才可以被外界使用，因此栈不允许被遍历

image-20240309161606134 
1
2
3
4
5
6
7
8
9
10
11
12
构造函数：
    stack<T> stk;//默认构造
	stack<T> stk(const stack &stk);//拷贝构造
赋值操作：
    stack& operator=(const stack &stk);
数据存取：
    push(elem);
	pop();
	top();
空间和大小：
    empty();
	size();

2.5 queue 容器

先进先出FIFIO数据结构——队列

image-20240309162359585

只有队头和队尾才能被外界使用，不能遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
构造函数：
    queue<T> que;
	queue<T> que(const queue &que);
赋值操作：
    queue& operator=(const queue &que);
数据存取：
    push(elem);		//入队
	pop();			//出队
	back();			//返回最后一个元素
	front();		//返回第一个元素
大小操作：
    empty();
	size();

2.6 list容器

将数据进行链式存储，链表

链表是由一系列的结点组成的，结点=数据域+指针域

STL中的链表是一个双向循环链表

image-20240309224548260

链表的存储方式并不是连续的内存空间，因此链表的迭代器只支持前移和后移，属于双向迭代器

list的优点：

  • 采用动态的内存分配，不会造成内存的浪费和溢出
  • 链表插入和删除十分方便，不需要移动大量元素

list的缺点：

  • 空间和时间耗费较大

List有一个重要的性质，插入和删除操作不会造成原有的list迭代器失效，vector会造成失效

（由于vector插入的时候如果capacity大小不够的话就会重新申请一个空间，并将数据拷贝到新空间，而原本的迭代器任指向原空间地址）

2.6.1 list构造函数

1
2
3
4
list<T> lst;							//默认构造
list<T> lst1(lst.begin(), lst.end());	//将lst[begin,end)区间的元素拷贝
list<T> lst2(n, elem);					//将n个elem拷贝给lst2
list<T> lst3(const list &lst);			//拷贝构造函数

2.6.2 list赋值和交换

1
2
3
4
assign(lst.begin(),lst.end());
assign(n , elem);
list &operator=(const list &lst);
swap(lst);							//将lst与本身元素进行交换

2.6.3 list空间和大小

1
2
3
4
size();
empty();
resize(num);
resize(num, elem);

2.6.4 list插入和删除

1
2
3
4
5
6
7
8
9
10
11
push_back(elem);
pop_back();
push_front(elem);
pop_front();
insert(const_operator pos, elem);
insert(const_operator pos, n, elem);
insert(const_operator pos, const_operator beg, const_operator end);
clear();
erase(const_operator beg, const_operator end);
erase(const_operator pos);
remove(elem);//删除容器中所有与elem值匹配的元素

2.6.5 数据存取

1
2
front();	//返回第一个元素
back();		//返回最后一个元素

2.6.6 list反转和排序

1
reverse();
1
2
3
lst.sort();
//lst不支持随机访问迭代器，不可以用标准的排序算法
//但是一般内部都会有提供

2.7 set/multiset/unordered_set容器

所有元素都会在插入时候自动排序

本质：

set、multiset属于关联式容器，底层结构都是二叉树实现

set不允许容器内有重复的元素，multiset允许容器内有重复元素，unordered_set不排序要去重

2.7.1 set的构造和赋值

1
2
set<T> st;
set<T> st1(st);
1
set& operator=(const set &st);

2.7.2 set大小和交换

1
2
3
size();
empty();
swap(st);	//交换两个集合容器

不允许重新指定大小resize

2.7.3 set插入和删除

1
2
3
4
5
insert(elem);
erase(iterator pos);
erase(iterator begin, iterator end);
erase(elem);	//删除值为elem的元素
clear();

2.7.4 set查找和统计

1
2
find(key);	//检查key是否存在，若存在则返回元素迭代器，不存在则返回st.end();
count(key);	//统计key元素的个数

2.7.5 set容器排序

默认排序规则为从小到大，

利用仿函数改变排序规则。

1.内置数据类型：

1
2
3
4
5
6
7
8
9
10
11
12
class MyCompare{
public:
    bool operator()(int v1, int v2){//采用仿函数
        return v1 > v2;
    } 
}
void main(){
    set<int,MyCompare> s;
    for(set<int,MyCompare>::iterator it=s.begin();it!=s.end();it++){
        cout<<*it<<endl;
    }
}

2.自定义数据类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Person{
public:
   Person(string name,int age){
       m_Name = name;
       m_Age = age;
   }
   string m_Name;
   int m_Age;
}
class comparePerson{
public:
    bool operator()(const Person &p1, const Person &p2){
        return p1.m_Age>p2.m_Age;
    }
}
void main(){
    set<Person,comparePerson> s;
    s.insert(Person("vicczyq",18));
    
}

2.8 map/multimap容器

  • map中全部元素都是pair对组
  • pair第一个元素为key(键值)，起到索引作用，第二个为value(实值)
  • 所有元素都会根据元素的键(key)自动排序

map、multimap属于关联式容器，底层是用二叉树实现。

map不允许重复key值，multimap可以有重复key

2.8.1 map构造和赋值

1
2
map<string,int> mp;
map<string,int> mp1(mp);
1
map<string,int>& operator=(const map &mp);

2.8.2 map的大小和交换

1
2
3
size();
empty();
swap(st);

2.8.3 map的插入和删除

1
2
3
4
5
insert(pair);	//如下代码段，有几种方法
clear();
erase(iterator pos);
erase(iterator beg, iterator end);
erase(key);
1
2
3
m.insert(pair<int,int>(1,10));	//第一种
m.insert(make_pair(1,10));		//第二种
m[1]=10;						//第三种：key为4,value为10

不建议采用第三种，但可以利用key访问value

原因：如果没有赋值value，直接用m[1]，这样他会默认创建一个m[1]=0

2.8.4 map的查找和统计

1
2
find(key);	//查找，返回元素迭代器，如果没查到返回mp.end();
count(key); //统计key元素个数

2.8.5 map的排序

利用仿函数改变排序规则

1
2
3
4
5
6
7
8
class myCompare{
public:
	bool operator()(int v1, int v2){
		return v1>v2;
	}
}

map<int,myCompare> mp;

3 函数对象

在algorithm算法库中有许多函数，如sort、for_each、find_if等

都需要传入一个函数指针

1
2
3
4
5
6
7
bool Find(const int &x){
	return x==3;
}
int main(){
	int a[10]={1,2,3,4,5,6,7,8,9,10};
	cout << *(find_if(a,a+10,Find));
}

这里查找的固定值是3，但是如果不固定呢，就需要把他当做一个变量

解决方法：

  • 给函数再加一个形参：但是这里传的是函数指针，形参赋值不了
  • 作为局部变量：不能在调用的时候传入，扩展性不强
  • 作为全局变量：维护起来不方便
  • 成员变量：可以在构造里传参，将参数保护到成员变量，易于维护
1
2
3
4
5
6
7
8
9
10
template<typename T> class Find{
public:
    T num;
    Find(const T& n){
        num = n;
    }
    bool operator()(const T& x){
        return x==num;
    }
}

3.1 函数对象概念

  • 重载函数调用操作符的类，其对象称为函数对象
  • 函数对象使用重载的()时，行为类似于函数调用，也叫仿函数

本质：

函数对象是一个类，不是一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//函数对象在使用时，可以像普通函数那样调用，可以有参数和返回值
class myAdd{
public:
	int operator()(int v1, int v2){
		return v1+v2;
	}
}

myAdd myadd;
cout << myadd(10,10) << endl;

//函数对象超出了普通函数的概念，可以拥有自己的状态
class myPrint{
public:
    myPrint(){
        this->count=0;
    }
    void operator()(string &a){
        cout << a << endl;
        count++;
    }
 	int count = 0;//自己内部状态
}

//函数对象可以作为参数进行传递

3.2 谓词

返回bool类型的仿函数称为谓词

一元谓词：operator接受的是一个参数

二元谓词：operator接受的是两个参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class myPrint{//一元谓词
public:
	bool operator()(string &a){
		//
	}
}

class myCompare{//二元谓词
public:
    bool operator()(int &a,int &b){
        return a>b;
    }
}

void main(){
    vector<int> a;
	//一系列的插入操作   
    sort(a.begin(),a.end(),myCompare());
}

3.3 内建函数对象

分类：

  • 算数仿函数
  • 关系仿函数
  • 逻辑仿函数

使用内建函数对象的会后，需要引入头文件#include <functional>

3.3.1 算数仿函数

1
2
3
4
5
6
template<typename T> T plus<T>			//加法仿函数
template<typename T> T minus<T>			//减法仿函数
template<typename T> T multiplies<T>	//乘加仿函数
template<typename T> T divides<T>		//除法仿函数
template<typename T> T modulus<T>		//取模仿函数
template<typename T> T negate<T>		//取反仿函数（一元）
1
2
3
4
5
6
7
#include <functional>
void main(){
    nagate<int> n1;
    n1(50);//取反
    plus<int> n2;
    n2(10,20);//相加
}

3.3.2 关系仿函数

1
2
3
4
5
6
template<typename T> bool equal_to<T>		//等于
template<typename T> bool not_equal_to<T>	//不等于
template<typename T> bool greater<T>		//大于
template<typename T> bool greater_equal<T>	//大于等于
template<typename T> bool less<T>			//小于
template<typename T> bool less_equal<T>		//小于等于
1
2
3
4
#include <functional>
void main(){
    sort(a, a+10, greater<int>());
}

3.3.3 逻辑仿函数

1
2
3
template<typename T> bool logical_and<T>	//与
template<typename T> bool logical_or<T>		//或
template<typename T> bool logical_not<T>	//非

4 算法

主要由algorithm、functional、numeric组成

  • <algorihtm>：STL中最大的一个，涉及到比较、交换、查找、遍历、复制、修改等
  • <functional>：定义了一些模板类，用于声明函数对象
  • <numeric>：体积很小，只包括几个序列上面进行简单数学算数运算的模板函数

4.1 遍历算法

  • for_each：遍历容器
  • transform：搬运容器到另外一个容器中

4.1.1 for_each

1
for_each(iterator beg, iterator end, _func);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <vector>
using namespace std;
//普通函数方式
void print01(int &val){
    cout<<val<<endl;
}
//仿函数
class print02{
public:
    void operator()(int &val){
        cout<<val<<endl;
    }
}

void main(){
    vector<int> vec;
    for(int i=0;i<10;i++){
    	vec.push_back(i);
    }
    for_each(vec.begin(),vec.end(), print01);//普通函数方式
    for_each(vec.begin(),vec.end(), print02());//仿函数方式(函数对象方式)
}

4.1.2 transform

搬运容器到另外一个容器中

1
transform(iterator beg1, iterator end1, iterator beg2, _func);

_func可以实现在搬运过程中对数据进行处理，可以用普通函数或函数对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <vector>
using namespace std;
class Transform{
public:
    int operator()(int v){
        return v;
    }
}

void main(){
    vector<int> vec;
    for(int i=0;i<10;i++)vec.push_back(i);
    
    vector<int> vTarget;
    vTarget.resize(10);
    transform(vec.begin(),vec.end(),vTarget.begin(),Transform());
}

4.2 查找算法

  • find：查找元素
  • find_if：按条件查找
  • adjacent_find：查找相邻重复元素
  • binary_search：二分查找法
  • count：统计元素个数
  • count_if：按条件统计元素个数

4.2.1 find

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器.end()

1
find(iterator beg, iterator end, value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Person{
public:
    string m_Name;
    int m_Age;
    Person(string &name, int &age){
        m_Name=name;
        m_Age=age;
    }
    bool operator==(const Person &p){
        if(m_Name==p.m_name && m_Age==p.m_Age){
            return true;
        }
    }
}
void main(){
    //。。。
    vector<int>::iterator it =find(vec.begin(),vec.end(),Person("bbb",18));
    //。。。
}

4.2.2 find_if

1
find_if(iterator beg, iterator end, _Pred);

查找元素，有过存在返回迭代器，不存在返回end()

1
2
3
4
5
6
7
8
9
10
11
12
#include <functional>
#include <algorithm>
#include <vector>
using namespace std;
class GreaterFive{
public:
    bool operator()(int val){
        return val>5;
    }
}
find_if(vec.begin(),vec.end(),GreaterFive());
//此时不能用内置的greater，因为greater是二元

4.2.3 adjacent_find

查找相邻的重复元素

1
iterator &adjacent_find(iterator beg, iterator end,);

返回相邻元素的第一个位置的迭代器

二分查找，返回值为bool，查找指定元素是否存在

1
bool binary_search(iterator beg, iterator end, value);

4.2.5 count

统计元素个数，返回值为整数型

1
count(iterator beg, iterator end, value);

4.2.6 count_if

按条件统计元素个数

1
count(iterator beg, iterator end, _Pred);

_Pred为谓词

1
2
3
4
5
6
7
8
9
10
11
class MyCount{
public:
	bool operator()(int val){
		return val>5;
	}
}

vector<int> vec;
for(int i=0;i<10;i++)vec.push_back(i);
int c = count(vec.begin(), vec.end(), myCount());
cout << "vec中大于5的元素个数:" << c <<endl;

4.3 排序算法

4.3.1 sort

1
sort(iterator beg, iterator end, _Pred);

_Pred选填，谓词，默认为升序排序

1
2
3
4
5
6
7
8
9
10
class mySort{
public:
    bool operator()(int &a, int &b){
        return a>b;
    }
}
vector<int> vec;
for(int i=0;i<10;i++)vec.push_back(i);
sort(vec.begin(),vec.end(),greater<int>());//内置仿函数
sort(vec.begin(),vec.end(),mySort());//自定义仿函数

4.3.2 random_shuffle

洗牌，指定范围元素随机调整次序

1
2
3
#include <ctime>
srand((unsigned int)time(NULL));//随机数种子
random_shuffle(iterator beg, iterator end);

4.3.3 merge

将两个容器合并，并存储到另外一个容器

1
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest_beg);

注意：两个容器必须是有序的

1
2
3
4
5
6
7
vector<int> v1,v2,vTarget;
for(int i=0; i<10;i++){
	v1.push_back(i);
	v2.push_back(i+1);
}
vTarget.resize(20);
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vTarget.begin());

输出：0,1,1,2,2,3,3,4,4,5.......

4.3.4 reverse

反转

1
reverse(iterator beg, iterator end);

4.4 拷贝和替换

4.4.1 copy

1
copy(iterator beg, iterator end, iterator dest_beg);

4.4.2 replace

1
replace(iterator beg, iterator end, old_value, new_value);

4.4.3 replace_if

1
replace_if(iterator beg, iterator end, _Pred, new_value);

4.4.4 swap

1
swap(container c1, container c2);

注意：容器必须为同种类型

4.5算数生成算法

头文件#include <numeric>

4.5.1 accumulate

1
2
accumulate(iterator beg, iterator end, value);
//value为起始值
1
2
3
4
vector<int> vec;
for(int i =0;i<10;i++)vec.push_back(i);
int n = accumulate(vec.begin(),vec.end(),0);
cout << n << endl;

4.5.2 fill

向容器内填充指定的容器

1
fill(iterator beg, iterator end, value);

4.6 集合算法

容器必须有序

4.6.1 set_intersection

求两个容器的交集

1
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator Target_beg);
1
2
3
4
5
6
7
8
vector<int> v1,v2,vTarget;
for(int i=0;i<10;i++){
    v1.push_back(i);
    v2.push_back(i+5);
}
vTarget.resize(min(v1.size(),v2.size()));
vector<int>::iterator it = set_intersection(v1.begin(),v1.end(),v2.begin(,v2.end(),vTarget.begin());//返回的是交集最后一个元素的位置
for_each(vTarget.begin(), it, myPrint);

4.6.2 set_union

求两个容器的并集，必须是有序序列！

1
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator Target_beg);

4.6.3 set_difference

求两个容器的差集

1
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator Target_beg);