1.基本概念

1.1 简要介绍

STL（Standard Template Library，标准模板库）广义上分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，提供了更好的代码重用机会

1.2 优点

  • 高可重用性
  • 高性能
  • 高移植性
  • 跨平台

2.容器

2.1 容器的分类

  1. 序列式容器
    • 每个元素都有固定位置——取决于插入时机和地点，和元素值无关
    • vector、deque、list、stack、queue
  2. 关联式容器
    • 元素位置取决于特定的排序准则，和插入顺序无关
    • set、multiset、map、multimap

2.2 vector

2.2.1 vector容器简介

  • vector是将元素置于一个动态数组中加以管理的容器
  • vector可以随机存取元素
  • vector尾部添加或移出元素非常快速，但是在中部或者头部插入或移出元素比较费时

2.2.2 vector对象的默认构造

1
2
3
4
5
6
7
vector<int> VecInt;//一个存放int类型数据的vector容器
vector<double> VecDou;//一个存放double类型数据的vector容器
vector<string> VecStr;//一个存放string类型数据的vector容器
……
class CA{};
vector<CA*> VecCA;//一个存放CA对象指针的vector容器
vector<CA> VecCA;//一个存放CA对象的vector容器

2.2.3 vector对象的带参数构造

  • vector(beg,end);//构造函数将[beg,end)区间中的元素拷贝给本身（左闭右开区间）
  • vector(n,elem);//构造函数将n个elem拷贝给本身
  • vector(const vector &vec);//拷贝构造函数

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<vector>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
vector<int> v1(arr, arr + 5);
vector<int> v2(10, 1);
vector<int> v3(v1);
int main(void) {
	for (int i = 0; i < 5; ++i)
		cout << v3[i] << " ";
	//1 2 3 4 5
	cout << endl;
	return 0;
}

2.2.4 vector对象的赋值

  • vector.assign(beg,end);//将[beg,end)区间中的数据拷贝赋值给本身（左闭右开区间）
  • vector.assign(n,elem);//将n个elem拷贝赋值给本身
  • vector& operator=(const vector &vec);//重载等号操作符
  • vector.swap(vec);//将vec与本身的元素互换

注：assign方法会将原来vector对象的元素清空再拷贝

实例演示

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
26
27
28
#include<iostream>
#include<vector>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
vector<int> v1, v2, v3;
int main(void) {
	v1.assign(arr, arr + 5);
	v2.assign(3, 10);
	v3 = v2;
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 2 3 4 5
	cout << endl;
	for (int i = 0; i < v2.size(); ++i)
		cout << v2[i] << " ";
	//10 10 10
	cout << endl;
	v1.swap(v2);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//10 10 10
	cout << endl;
	for (int i = 0; i < v2.size(); ++i)
		cout << v2[i] << " ";
	//1 2 3 4 5
	cout << endl;
	return 0;
}

2.2.5 vector的大小

  • vector.size();//返回容器中元素的个数
  • vector.empty();//判断vector对象是否为空
  • vector.resize(num);//重新制定容器的长度为num：若容器变长则以默认值0填充新位置；若容器变短则末尾超出容器长度的元素将被删除
  • vector.resize(num,elem);//重新制定容器的长度为num：若容器变长则以elem值填充新位置；若容器变短则末尾超出容器长度的元素将被删除

2.2.6 vector元素的访问方式

  • vector[index]：返回索引index所指的数据（若下标越界可能会导致程序异常终止）
  • vector.at(index)：返回索引index所指的数据（若index越界则抛出out_of_range异常）

2.2.7 vector的插入删除

  • vector.insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置
  • vector.insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值
  • vector.insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值
  • vector.push_back(elem);//在vector对象末尾插入元素elem
  • vector.pop_back();//把vector对象末尾元素删除
  • vector.clear();//清空vector容器中元素
  • vector.erase(pos);//删除在pos位置的元素，返回新数据的位置
  • vector.erase(beg,end);//删除[beg,end)区间内的元素

注：pos为vector::iterator

实例演示

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
vector<int> v1;
int main(void) {
	v1.assign(arr, arr + 3);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 2 3
	cout << endl;
	v1.push_back(10);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 2 3 10
	cout << endl;
	v1.pop_back();
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 2 3
	cout << endl;
	v1.insert(v1.begin() + 1, 10);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 10 2 3
	cout << endl;
	v1.insert(v1.begin() + 1, 3, 10);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 10 10 10 10 2 3
	cout << endl;
	v1.insert(v1.begin() + 1, arr + 3, arr + 5);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 4 5 10 10 10 10 2 3
	cout << endl;
	v1.erase(v1.begin() + 3, v1.end());
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";
	//1 4 5
	cout << endl;
	v1.clear();
	cout << v1.size() << endl;//0
	return 0;
}

2.2.8 vector容器的iterator类型

  • vector< int >::iterator iter;//变量名为iter，类型为正向迭代器，反向迭代器改为reverse_iterator
  • vector容器的迭代器属于随机访问迭代器：迭代器一次可以移动多个位置
  • 成员函数：
    • begin()：返回指向容器中第一个元素的正向迭代器
    • end()：返回指向容器中最后一个元素之后一个位置的正向迭代器
    • rbegin()：返回指向最后一个元素的反向迭代器
    • rend()：返回指向第一个元素前一个位置的反向迭代器
    • cbegin()：和begin()功能类似，只不过其返回的迭代器类型是常量正向迭代器，不能用于修改元素
    • cend()：和end()功能类似，只不过其返回的迭代器类型是常量正向迭代器，不能用于修改元素
    • crbegin()：和rbegin()功能类似，只不过其返回的迭代器类型是常量反向迭代器，不能用于修改元素
    • crend()：和rend()功能类似，只不过其返回的迭代器类型是常量反向迭代器，不能用于修改元素

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<vector>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
vector<int> v1;
int main(void) {
	for (int i = 5; i < 10; ++i)
		v1.push_back(i);
	vector<int>::iterator idx = v1.begin();
	for (; idx != v1.end(); ++idx)
		cout << *idx << " ";
	//5 6 7 8 9
	cout << endl;
	for (auto it = v1.rbegin(); it!= v1.rend(); ++it)
		//it依旧是递增
		cout << *it << " ";
	//9 8 7 6 5
	cout << endl;
	return 0;
}

2.2.9 vector容器的迭代器失效

  1. 插入元素导致迭代器失效

问题演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<vector>
using namespace std;
vector<int> v1;
int main(void) {
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	vector<int>::iterator it = v1.begin() + 3;
	v1.insert(it, 8);
	cout << *it << endl;//在VS中运行无结果，返回错误代码，视不同编译器
	return 0;
}

原因

因为在insert时，vector可能需要扩容，而扩容的本质是new一块新的空间，再将数据迁移过去；而在插入后若vector扩容，则原有的数据被释放，指向原有数据的迭代器就成了野指针，所以迭代器失效了

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<vector>
using namespace std;
vector<int> v1;
int main(void) {
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	vector<int>::iterator it = v1.begin() + 3;
	it = v1.insert(it, 8);//insert会返回一个新的有效的迭代器
	cout << *it << endl;//8
	return 0;
}
  1. 删除元素导致迭代器失效

问题演示

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<vector>
using namespace std;
vector<int> v1={1,2,3,3,3,4,5};
int main(void) {
	for (auto i = v1.begin(); i != v1.end(); ++i)
		if (*i == 3)
			v1.erase(i);
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";//VS编译器无输出，返回错误代码
	cout << endl;
	return 0;
}

原因

对于序列式容器（如vector，deque），序列式容器就是数组式容器，删除当前元素的iterator会使得后面所有元素的iterator都失效。这是因为vector，deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置，所以不能使用erase(i++)的方式。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<vector>
using namespace std;
vector<int> v1={1,2,3,3,3,4,5};
int main(void) {
	vector<int>::iterator it;
	for (it = v1.begin(); it != v1.end();)
		if (*it == 3)
			it = v1.erase(it);//erase返回删除后的一个有效的迭代器
		else
			it++;
	for (int i = 0; i < v1.size(); ++i)
		cout << v1[i] << " ";//1 2 4 5
	cout << endl;
	return 0;
}

2.3 deque

2.3.1 deque容器简介

  • deque是“double-ended queue”的缩写
  • deque是双端数组（可以向两端扩容）而vector是单端的
  • deque在接口上和vector非常相似，在许多操作的地方可以直接替换
  • deque可以随机存取元素（支持索引值直接存取，用[ ]操作符或at( )方法）
  • deque头部和尾部添加或移出元素都非常快速，但是在中部安插元素或移出元素比较费时
  • deque并非连续空间存储，它是分段连续的
  • 使用需包含头文件< deque >

2.3.2 deque容器的操作

  • deque与vector在操作上几乎一样，deque多两个函数：
    • deque.push_front(elem);//在容器头部插入一个数据
    • deque.pop_front();//删除容器第一个数据

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<deque>
using namespace std;
deque<int> deq = { 1,2,3,4,5 };
int main(void) {
	deq.push_front(10);
	for (int i = 0; i < deq.size(); ++i)
		cout << deq[i] << " ";
	//10 1 2 3 4 5
	cout << endl;
	deq.pop_front();
	for (int i = 0; i < deq.size(); ++i)
		cout << deq[i] << " ";
	//1 2 3 4 5
	cout << endl;
	return 0;
}

2.4 list

2.4.1 list容器简介

  • list是一个双向链表容器，可以高效进行插入删除元素
  • list不可以随机存取元素，所以不支持at(pos)函数与[]操作符
  • list的迭代器支持自增、自减运算符，但不支持一个迭代器加上某个数字
  • 使用需要包含头文件< list >

2.4.2 list对象的默认构造

1
2
list<int> lstInt;//定义一个存放int的list容器
list<string> lstStr;//定义一个存放string的list容器

2.4.3 list头尾的添加移除操作

  • list.push_back(elem);//在容器尾部加入一个元素
  • list.pop_back();//删除容器中最后一个元素
  • list.push_front(elem);//在容器开头插入一个元素
  • list.pop_front();//从容器开头移除第一个元素

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<list>
using namespace std;
list<int> lst;
int main(void) {
	for (int i = 5; i <= 10; ++i)
		lst.push_back(i);
	lst.push_front(100);
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//100 5 6 7 8 9 10
	cout << endl;
	lst.pop_back();
	lst.pop_front();
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//5 6 7 8 9
	cout << endl;
	return 0;
}

2.4.4 list数据的存取

  • list.front();//返回list容器的第一个结点的值
  • list.back();//返回list容器的最后一个结点的值

注：可以通过list.front()=elem对第一个结点的值进行更改为elem；list.back()也同样可以

2.4.5 list与迭代器

list容器的迭代器是“双向迭代器”：双向迭代器从两个方向读写容器，除了提供前向迭代器的全部操作之外，双向迭代器还提供前置和后置的自减运算

  • list.begin();//返回容器中第一个元素的迭代器
  • list.end();//返回容器中最后一个元素之后的迭代器
  • list.rbegin();//返回容器中倒数第一个元素的迭代器
  • list.rend();//返回容器中倒数最后一个元素的后面的迭代器

2.4.6 list对象的带参数构造

  • list(n,elem);//构造函数将n个elem拷贝给本身
  • list(beg,end);//构造函数将[beg,end)区间中的元素拷贝给本身
  • list(const list& lst);//拷贝构造函数

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<vector>
#include<list>
using namespace std;
vector<int> vec = { 1,2,3,4,5 };
list<int> lst1(vec.begin(),vec.begin()+3);
list<int> lst2(5,100);
list<int> lst3(lst2);
int main(void) {
	for (auto i = lst1.begin(); i != lst1.end(); ++i)
		cout << *i << " ";
	//1 2 3
	cout << endl;
	for (auto i = lst2.begin(); i != lst2.end(); ++i)
		cout << *i << " ";
	//100 100 100 100 100
	cout << endl;
	for (auto i = lst3.begin(); i != lst3.end(); ++i)
		cout << *i << " ";
	//100 100 100 100 100
	cout << endl;
	return 0;
}

2.4.7 list对象的赋值

  • list.assign(beg,end);//将[beg,end)区间中的数据拷贝赋值给本身（左闭右开区间）
  • list.assign(n,elem);//将n个elem拷贝赋值给本身
  • list& operator=(const vector &vec);//重载等号操作符
  • list.swap(vec);//将vec与本身的元素互换

2.4.8 list对象的大小

  • list.size();//返回容器中元素的个数
  • list.empty();//判断vector对象是否为空
  • list.resize(num);//重新制定容器的长度为num：若容器变长则以默认值0填充新位置；若容器变短则末尾超出容器长度的元素将被删除
  • list.resize(num,elem);//重新制定容器的长度为num：若容器变长则以elem值填充新位置；若容器变短则末尾超出容器长度的元素将被删除

2.4.9 list容器的插入

  • list.insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置
  • list.insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值
  • list.insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值

注：list.insert不会使得迭代器失效，因为插入结点后原结点没有释放以及位置没有改变

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<vector>
#include<list>
using namespace std;
vector<int> vec = { 1,2,3,4,5 };
list<int> lst(5,100);
int main(void) {
	list<int>::iterator it = lst.begin();
	++it;
	lst.insert(it, 50);
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//100 50 100 100 100 100
	cout << endl;
	cout << *it << endl;
	//100
	lst.insert(it, 3, 10);
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//100 50 10 10 10 100 100 100 100
	cout << endl;
	return 0;
}

2.4.10 list容器的删除

  • list.clear();//移除容器中的所有元素
  • list.erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置
  • list.erase(pos);//删除pos位置的数据，返回下一个数据的位置
  • list.remove(elem);//删除容器中所有与elem值匹配的元素

实例演示

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
26
27
28
29
30
#include<iostream>
#include<list>
using namespace std;
list<int> lst{12,23,34,45,56,56,3,3,3,3,3,23};
int main(void) {
	lst.erase(lst.begin());
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//23 34 45 56 56 3 3 3 3 3 23
	cout << endl;
	list<int>::iterator it1, it2;
	it1 = it2 = lst.begin();
	++it1;//指向34
	++it2;
	++it2;
	++it2;//指向56
	//it1接受erase返回的位置
	it1 = lst.erase(it1, it2);
	cout << *it1 << endl;//56
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//23 56 56 3 3 3 3 3 23
	cout << endl;
	lst.remove(3);
	for (auto i = lst.begin(); i != lst.end(); ++i)
		cout << *i << " ";
	//23 56 56 23
	cout << endl;
	return 0;
}

2.4.11 list容器的反转

  • list.reserve();

实例演示

1
2
3
4
5
list<int> lst{ 12,23,34,45,56 };
lst.reverse();
for (auto i = lst.begin(); i != lst.end(); ++i)
	cout << *i << " ";
//56 45 34 23 12

2.4.12 list容器的迭代器失效

  • 删除结点导致迭代器失效

问题代码

1
2
3
4
5
list<int> lst{ 12,23,34,45,56 };
//报错：结点删除后，无法得到删除结点的next元素，重载后的++运算符无法进行
for (auto i = lst.begin(); i != lst.end(); ++i)
	if (*i == 34)
		lst.erase(i);

问题解决

1
2
3
4
5
6
list<int> lst{ 12,23,34,45,56 };
for (auto i = lst.begin(); i != lst.end();)
	if (*i == 34)
		i = lst.erase(i);
	else
		++i;

2.5 stack

2.5.1 stack容器简介

  • stack是堆栈容器，是一种“先进后出”的容器
  • stack没有迭代器，因为该数据结构不允许遍历
  • 使用需包含头文件< stack >

2.5.2 stack对象的默认构造

1
2
3
stack<int> stkint;//一个存放int的stack容器
stack<float> stkfloat;//一个存放float的stack容器
stack<string> stkstr;//一个存放string的stack容器

2.5.3 stack插入删除相关接口

1
2
3
4
stack.push(elem);//往栈顶添加元素
stack.pop();//从栈顶移出第一个元素，不返回值
stack.top();//访问栈顶元素并返回，可作为表达式的左值
stack.empty();//判断stack容器是否为空

实例演示

1
2
3
4
5
6
7
8
9
10
11
stack<int> stkint;
stkint.push(1);
stkint.push(3);
stkint.push(5);
stkint.push(7);
//7 5 3 1
while (!stkint.empty())
{
	cout << stkint.top() << " ";
	stkint.pop();
}

2.5.4 stack拷贝构造与赋值

  • stack(const stack& stk);//拷贝构造函数
  • stack& operator=(const stack& stk);//重载等号操作符

2.5.6 stack的大小

  • stack.empty();//判断堆栈是否为空
  • stack.size();//返回堆栈的大小

注：stack没有提供resize方法

2.6 queue

2.6.1 queue容器简介

  • queue是队列容器，是一种“先进先出”的容器
  • queue没有迭代器
  • 使用需包含< queue >头文件

2.6.2 queue对象的默认构造

1
2
queue<int> queint;//一个存放int数据的queue容器
queue<string> questr;//一个存放string数据的queue容器

2.6.3 queue插入删除相关接口

  • queue.push(elem);//往队尾添加元素
  • queue.pop();//从队头移除第一个元素
  • queue.front();//返回队头元素，可作为表达式的左值
  • queue.back();//返回队尾元素，可作为表达式的左值

实例演示

1
2
3
4
5
6
7
8
9
10
11
queue<int> q1;
q1.push(1);
q1.push(3);
q1.push(5);
q1.push(7);
//1 3 5 7
while (!q1.empty())
{
	cout << q1.front() << " ";
	q1.pop();
}

2.6.4 queue拷贝构造与赋值

  • queue(const queue& que);//拷贝构造函数
  • queue& operator=(const queue& que);//重载等号操作符

2.6.5 queue的大小

  • queue.empty();//判断队列是否为空
  • queue.size();//返回队列中元素个数

2.7 set

2.7.1 set/multiset容器简介

  • set是一个集合容器，其中所包含的元素是唯一的（去重），集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能插入指定位置
  • set采用红黑树变体的数据结构，红黑树属于平衡二叉树，在插入和删除操作上比vector快
  • set不可以直接存取元素（不可以使用at.(pos)与[]操作符）
  • multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一个值可以出现多次
  • 不可以直接修改set或multiset容器中的元素值，因为该类容器时自动排序的；如果希望修改一个元素值，必须先删除原有元素，再插入新的元素
  • 使用需包含< set >头文件

2.7.2 set/multiset对象默认构造

1
2
3
set<int> setint;//一个存放int的set容器
set<string> setstr;//一个存放string的set容器
multiset<int> mulsetint;//一个存放int的multiset容器

2.7.3 set容器的插入和迭代器

  • set.insert(elem);//在容器中插入元素
  • set.insert(beg,end);//插入范围[beg,end)内的元素
  • set.begin();//返回容器中第一个数据的迭代器
  • set.end();//返回容器中最后一个数据之后的迭代器
  • set.rbegin();//返回容器中倒数第一个元素的迭代器
  • set.rend();//返回容器中倒数最后一个元素的后面的迭代器

实例演示

1
2
3
4
5
6
7
8
9
10
11
set<int> s1;
s1.insert(3);
s1.insert(1);
s1.insert(5);
s1.insert(7);
//1 3 5 7
for (auto i = s1.begin(); i != s1.end(); ++i)
	cout << *i << " ";
//7 5 3 1
for (auto i = s1.rbegin(); i != s1.rend(); ++i)
	cout << *i << " ";

2.7.4 set容器的拷贝构造和赋值

  • set(const set& st);//拷贝构造函数
  • set& operator=(const set& st);
  • set.swap(st);//交换两个集合容器

2.7.5 set的大小

  • set.size();//返回容器中元素的个数
  • set.empty();//判断容器是否为空

2.7.6 set容器的删除

  • set.clear();//清楚所有元素
  • set.erase(pos);//删除迭代器pos（不可以为反向迭代器）所指的元素，返回下一个元素的迭代器
  • set.erase(beg,end);//删除区间[beg,end)的所有元素
  • set.erase(elem);//删除容器中值为elem的元素；元素存在返回true，否则返回false

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<int> s1;
s1.insert(3);
s1.insert(1);
s1.insert(5);
s1.insert(7);
s1.erase(s1.begin());
//3 5 7
for (auto i = s1.begin(); i != s1.end(); ++i)
	cout << *i << " ";
cout << endl;
s1.erase(5);
//3 7
for (auto i = s1.begin(); i != s1.end(); ++i)
	cout << *i << " ";

2.7.8 set容器的元素排序

实例演示

1
2
set<int,less<int>> setintA;//该容器是按照升序方式排列元素
set<int,greater<int>> setintB;//该容器是按降序方式排列元素
  • 默认情况是升序
  • less< int >与greater< int >中的int可以更改，要与set容纳的数据类型一致

2.7.9 set容器的查找

  • set.find(elem);//查找elem元素，返回指向elem元素的迭代器
  • set.count(elem);//返回容器中值为elem的元素个数：对set来说，要么是0，要么是1；对multiset来说，值可能大于1
  • set.lower_bound(elem);//返回第一个>=elem元素的迭代器
  • set.upper_bound(elem);//返回第一个>elem元素的迭代器

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
set<int> s1;
s1.insert(4);
s1.insert(12);
s1.insert(2);
s1.insert(43);
set<int>::iterator it;
if (s1.find(43) != s1.end())//找不到返回set.end()
{
	it = s1.find(43);
	cout << *it << endl;//43
}
cout << s1.count(12) << " " << s1.count(100);//1 0
cout << endl;
cout << *s1.lower_bound(12) << endl;//12
cout << *s1.upper_bound(12) << endl;//43

2.7.10 set容器set.equal_range(elem)

  • 返回容器中与elem相等的上下限的两个迭代器，上限是闭区间，下限是开区间即[beg,end)；相当于返回set.lower_bound(elem)与set.upper_bound(elem)两个迭代器
  • 函数返回的迭代器被封装到pair中
    • pair是对组，可以将两个值视为一个单元
    • pair<T1,T2>存放的两个值的类型，可以不一样，亦可以为自定义类型
    • pair.first是pair里面的第一个值，为T1类型
    • pair.second是pair里面的第二个值，为T2类型
1
pair<set<int>::iterator,set<int>::iterator> pairIt=set.equal_range(elem)

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
set<int> s1;
s1.insert(4);
s1.insert(12);
s1.insert(2);
s1.insert(43);
s1.insert(7);
s1.insert(10);
pair<set<int>::iterator, set<int>::iterator > it;
it = s1.equal_range(7);
if (it.first != s1.end() && it.second != s1.end())
	//上下限都存在的情况下
	//7 10
	cout << *(it.first) << " " << *(it.second) << endl;
else
	cout << "no find" << endl;
it = s1.equal_range(100);
if (it.first != s1.end() && it.second != s1.end())
	//上下限都存在的情况下
	cout << *(it.first) << " " << *(it.second) << endl;
else
	//no find
	cout << "no find" << endl;

2.8 map

2.8.1 map/multimap容器简介

  • map的特性是，所有的元素会根据元素的键值自动排序

  • map的所有的元素都是pair：

    • pair的第一元素被视为键值key，第二元素被视为实值value；
    • map不允许两个元素有相同的键值

  • 不能通过迭代器改变map的键值，但是可以任意修改实值

  • multimap键值可以重复

  • map和multimap都是以红黑树作为底层实现机制

2.8.2 map/multimap容器对象的默认构造

  • map/multimap采用模板类实现，默认构造形式：
    • map<T1,T2> mapTT;
    • multimap<T1,T2> multimapTT;
  • T1,T2还可以是各种指针类型或自定义类型

2.8.3 map容器的插入

  • 通过pair的方式插入对象：map.insert(pair<T1,T2>(key,value));（推荐使用）
  • 通过value_type的方式插入对象：map.insert(map<T1,T2>::value_type(key,value));（推荐使用）
  • 通过数组的形式插入值：map[key]=value;//如果key不再map内会被放在map内先获得默认值

实例演示

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
26
27
28
29
30
31
32
33
#include<iostream>
#include<map>
#include<string>
using namespace std;
class STU {
public:
	STU() {};
	STU(int id, string name) {
		this->ID = id;
		this->Name = name;
	};
	int ID;
	string Name;
};
int main(void) {
	map<int, STU> students;
	for (int i = 0; i < 3; ++i)
	{
		STU s1(i, "Lucy" + to_string(i));
		students.insert(pair<int,STU>(i, s1));
	}
	for (auto i = students.begin(); i != students.end(); ++i)
	{
		pair<int, STU> it = *i;
		cout << it.first << ": " << it.second.Name << endl;
        //不构建pair对组的方式：
        //cout << i->first << ": " << i->second.Name << endl;
	}
    //0: Lucy0
	//1: Lucy1
	//2: Lucy2
	return 0;
}

注：第三种方法存在一个性能问题：如果key存在的话就要执行修改，而修改是先删除该pair再添加新的pair

注：insert方法在key存在时不会覆盖原来的键值对，而数组的方式在key存在时会覆盖原来的键值对

2.8.4 map容器对象获取键对应的值

  • 使用[]，但是当key不存在时会将其插入，value为默认值
  • 使用find函数：成功返回对应的迭代器，失败返回map.end()（推荐使用）
  • 使用at()函数，如果键值对不存在会抛出”out_of_range”异常

实例演示

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
26
27
28
29
30
31
32
#include<iostream>
#include<map>
#include<string>
using namespace std;
class STU {
public:
	STU() {};
	STU(int id, string name) {
		this->ID = id;
		this->Name = name;
	};
	int ID;
	string Name;
};
int main(void) {
	map<int, STU> students;
	for (int i = 0; i < 3; ++i)
	{
		STU s1(i, "Lucy" + to_string(i));
		students.insert(pair<int,STU>(i, s1));
	}
	cout << students[1].Name << endl;//Lucy1
	if (students.find(2) != students.end())
	{
		auto it = students.find(2);
		cout << it->second.Name << endl;//Lucy2
	}
    else
        cout << "No Find!!" << endl;
	cout << students.at(3).Name << endl;//报错
	return 0;
}

3.算法

3.1 函数对象

重载函数调用操作符的类，其对象常称为函数对象(function object)，即它们是行为类似函数的对象，也叫仿函数(functor)，其实就是重载”()”运算符，使得类对象可以像函数那样调用

注意

  • 函数对象（仿函数）是一个类，不是一个函数
  • 函数对象（仿函数）重载了”()”操作符，使得它可以像函数一样调用

分类

  • 如果函数对象有一个参数叫：一元函数对象
  • 如果函数对象有两个参数叫：二元函数对象
  • 如果函数对象有三个参数叫：三元函数对象

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<string>
using namespace std;
class Print {
public:
	void operator()(string str) {
		cout << str << endl;
	}
};
void test() {
	//方式1
	Print op;//op为一元函数对象
	op("Hello world!");//Hello world!
	//方式2
	Print()("Hello world!");//Hello world!
}
int main(void) {
	test();
	return 0;
}

总结

  • 函数对象通常不定义构造函数和析构函数，所以在构造和析构时不会发生任何问题，避免了函数调用的运行时问题

  • 函数对象超出普通函数的概念，函数对象可以有自己的状态

  • 函数对象可内联编译，性能好，用函数指针几乎不可能

  • 模板函数对象使函数对象具有通用性

3.2 谓词

返回值为bool类型的普通函数或仿函数都叫谓词：

  • 如果谓词有一个参数叫：一元谓词
  • 如果谓词有两个参数叫：二元谓词

3.2.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
26
#include<iostream>
#include<vector>
using namespace std;
bool greaterthan30(int value) {
	return value > 30;
}
class Greaterthan30 {
public:
	bool operator()(int value) {
		return value > 30;
	}
};
vector<int> v1;
int main(void) {
	for (int i = 0; i < 5; ++i)
		v1.push_back(i * 10);
	vector<int>::iterator it;
	//find_if条件查找:find_if会将容器区间对应的“元素”传给第三个参数
	//普通函数方式
	/*it = find_if(v1.begin(), v1.end(), greaterthan30);*/
	//仿函数方式
	it = find_if(v1.begin(), v1.end(), Greaterthan30());
	if (it != v1.end())
		cout << *it << endl;//40
	return 0;
}

3.2.2 二元谓词

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Greater
{
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};
vector<int> v;
int main(void) {
	v.push_back(20);
	v.push_back(10);
	v.push_back(30);
	sort(v.begin(), v.end(), Greater());
	for (auto i = v.begin(); i != v.end(); ++i)
		cout << *i << " ";
	return 0;
}

3.3 内建函数对象

STL内建了一些函数对象，分为以下三种：算术类函数对象、关系运算符类函数对象、逻辑运算符类函数对象。这些仿函数所产生的对象用法和一般函数完全相同，当然也可以产生无名的临时对象来履行函数功能

  • 算术类函数对象，除了negate是一元运算，其他都是二元运算
1
2
3
4
5
6
template<class T> T plus<T>//加法仿函数
template<class T> T minus<T>//减法仿函数
template<class T> T multiplies<T>//乘法仿函数
template<class T> T divides<T>//除法仿函数
template<class T> T modules<T>//取模仿函数
template<class T> T negate<T>//取反仿函数
  • 关系运算类函数对象，每一种都是二元运算
1
2
3
4
5
6
template<class T>bool equal_to<T>//等于
template<class T>bool not_equal_to<T>//不等于
template<class T>bool greater<T>//大于
template<class T>bool greater_equal<T>//大于等于
template<class T>bool less<T>//小于
template<class T>bool less_equal<T>//小于等于
  • 逻辑运算类运算函数，not为一元运算，其余为二元运算
1
2
3
template<class T>bool logical_and<T>//逻辑与
template<class T>bool logical_or<T>//逻辑或
template<class T>bool logical_not<T>//逻辑非

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> v;
int main(void) {
	v.push_back(20);
	v.push_back(10);
	v.push_back(30);
	v.push_back(5);
	sort(v.begin(), v.end(), greater<int>());
	for (auto i = v.begin(); i != v.end(); ++i)
		cout << *i << " ";
	//30 20 10 5
	return 0;
}

3.4 适配器

  • 适配器为算法提供接口
  • 使用需包含头文件< functional >

3.4.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
26
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>//提供适配器
using namespace std;
vector<int> v;
//第二步：公共继承binary_function参数萃取
class PrintInt:public binary_function<int,int,void>//形参类型+返回值类型
{
public:
	//第三步：const修饰operator()
	void operator()(int val, int tmp) const{
		cout << val + tmp << " ";
	}
};
int main(void) {
	v.push_back(20);
	v.push_back(10);
	v.push_back(30);
	v.push_back(5);
	//第一步：bind2nd或bind1st绑定参数，因为for_each只有3个参数
	//bind2nd和bind1st区别主要是将100这个实参绑定到哪个形参位置
	for_each(v.begin(), v.end(), bind2nd(PrintInt(), 100));
    //120 110 130 105
	return 0;
}

3.4.2 函数指针适配器ptr_fun

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>//提供适配器
using namespace std;
vector<int> v;
void myPrintInt(int val, int temp) {
	cout << val + temp << " ";
}
int main(void) {
	v.push_back(20);
	v.push_back(10);
	v.push_back(30);
	v.push_back(5);
	for_each(v.begin(), v.end(), bind2nd(ptr_fun(myPrintInt), 100));
    //120 110 130 105
	return 0;
}

说明

  • 上述例子中for_each最后一个参数是需要传递函数入口地址，但是C++中函数名代表不了函数入口地址，在C++编译器里会通过函数名和形参类型共同决定函数入口地址，所以就要使用函数指针的宏ptr_fun让底层把ptr_fun(FunctionName)换成这个函数的入口地址
  • 使用ptr_fun同样需包含头文件< functional >
  • ptr_fun将普通函数适配为一个仿函数

3.4.3 成员函数适配器mem_fun_ref

实例演示

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>//提供适配器
using namespace std;
class Data {
private:
	int data;
public:
	Data() {};
	Data(int val) { data = val; };
	void PrintInt(int tmp) {
		cout << data + tmp << " ";
	}
};
vector<Data> v;
int main(void) {
	v.push_back(Data(10));
	v.push_back(Data(20));
	v.push_back(Data(30));
    //成员函数必须是容器存放对象的成员函数
	for_each(v.begin(), v.end(), bind2nd(mem_fun_ref(&Data::PrintInt), 100));
	//110 120 130
	return 0;
}

说明

  • mem_fun_ref是一种适配器，该函数能将类的成员函数包装成仿函数使用，于是成员函数可以搭配各种泛型算法完成所谓的多态调用

  • 使用需包含头文件< functional >

  • mem_fun_ref和mem_fun的作用和用法一样，唯一不同的就是当容器中存放的是对象实体时用mem_fun_ref，当容器中存放的时对象的指针时用mem_fun

3.4.4 取反适配器

  • 一元取反
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>//提供适配器
using namespace std;
vector<int> v;
int main(void) {
	v.push_back(10);
	v.push_back(5);
	v.push_back(30);
	v.push_back(20);
	vector<int>::iterator it;
	it = find_if(v.begin(), v.end(), not1(bind2nd(greater<int>(), 8)));
	if (it != v.end())
		cout << *it << endl;//5
	return 0;
}
  • 二元取反
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>//提供适配器
using namespace std;
vector<int> v;
int main(void) {
	v.push_back(10);
	v.push_back(5);
	v.push_back(30);
	v.push_back(20);
	for_each(v.begin(), v.end(), [=](int val) {
		cout << val << " ";
		});
	//10 5 30 20
	cout << endl;
	sort(v.begin(), v.end(), not2(greater<int>()));
	for_each(v.begin(), v.end(), [=](int val) {
		cout << val << " ";
		});
	//5 10 20 30
	return 0;
}

lambda表达式（C++11才支持）

  • [ ]：里面什么都不写，lambda不能识别外部数据
  • [=]：lambda能对外部数据进行读操作
  • [&]：lambda能对外部数据进行读写操作

3.5 常用遍历算法

3.5.1 for_each遍历算法

1
2
3
4
5
6
7
8
/*
遍历算法 遍历容器元素
@param beg 开始迭代器
@param end 结束迭代器
@param _callback 函数回调或者函数对象
@return 函数对象
*/
for_each(iterator beg, iterator end, _callback);

3.5.2 transform算法

1
2
3
4
5
6
7
8
9
10
/*
transform算法 将指定容器区间元素搬运到另一容器中
注意： transform不会给目标容器分配内存，需要提前分配好内存
@param beg1 源容器开始迭代器
@param end1 源容器结束迭代器
@param beg2 目标容器开始迭代器
@param _callback 函数回调或者函数对象
@return 返回目标容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callback);

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int myTransform(int val) {
	return val;
}
int main(void) {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(5);
	v1.push_back(30);
	v1.push_back(20);
	vector<int> v2;
	v2.resize(v1.size());
	transform(v1.begin(), v1.end(), v2.begin(),myTransform);
	for_each(v2.begin(), v2.end(), [=](int v) {
		cout << v << " ";
		});
	//10 5 30 20
	return 0;
}

3.6 常用查找算法

3.6.1 find算法

1
2
3
4
5
6
7
8
/*
find算法 查找元素
@prama beg 容器开始迭代器
@prama end 容器结束迭代器
@prama value 查找的元素
@return 返回查找元素的位置
*/
find(iterator beg, iterator end, value);

3.6.2 find_if算法

1
2
3
4
5
6
7
8
/*
find_if算法 条件查找
@prama beg 容器开始迭代器
@prama end 容器结束迭代器
@prama _callback 回调函数或谓词(返回bool类型的函数对象)
@return 返回指定位置迭代器
*/
find_if(iterator beg, iterator end, _callback);

3.6.3 adjacent_find算法

1
2
3
4
5
6
7
8
/*
adjacent_find算法 查找相邻重复元素
@prama beg 容器开始迭代器
@prama end 容器结束迭代器
@prama _callback 回调函数或谓词(返回bool类型的函数对象)一般没有就空着
@return 返回相邻元素的第一个位置的代码，无则返回end迭代器
*/
adjacent_find(iterator beg, iterator end, _callback);

3.6.4 binary_search算法

1
2
3
4
5
6
7
8
9
/*
binary_search算法 二分查找法
注意：在无序序列中不可用
@prama beg 容器开始迭代器
@prama end 容器结束迭代器
@prama value 查找的元素
@return bool 查找成功返回true否则false
*/
bool binary_search(iterator beg, iterator end, value);

3.6.5 count算法

1
2
3
4
5
6
7
8
/*
count算法 统计元素出现次数
@prama beg 容器开始迭代器
@prama end 容器结束迭代器
@prama value 查找的元素
@return 元素出现的次数
*/
count(iterator beg, iterator end, value);

3.6.6 count_if算法

1
2
3
4
5
6
7
8
/*
count_if算法 按条件统计元素出现次数
@prama beg 容器开始迭代器
@prama end 容器结束迭代器
@prama _callback 回调函数或者谓词(返回bool类型的函数对象)
@return 元素出现的次数
*/
count_if(iterator beg, iterator end, _callback);

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
int main(void) {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(5);
	v1.push_back(30);
	v1.push_back(20);
	cout << count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 15));//2
	return 0;
}

3.7 常用排序算法

3.7.1 merge算法

1
2
3
4
5
6
7
8
9
10
11
12
/*
merge算法 容器元素合并，并存储到另一容器中
注意：
* 两个源容器必须是有序的
* 不会给目标容器分配内存，需要提前分配好内存
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest 目标容器开始迭代器
*/
merge(iterator beg1, iterator end1,iterator beg2, iterator end2,iterator dest);

3.7.2 sort算法

1
2
3
4
5
6
7
/*
sort算法 容器元素排序
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param _callback 回调函数或者谓词(返回bool类型的函数对象)
*/
sort(iterator beg, iterator end, _callback);

3.7.3 random_shuffle算法

1
2
3
4
5
6
7
/*
random_shuffle算法 对指定范围内的元素随机调整次序
注意：可以使用随机数种子srand(time(NULL))保证每次随机不同
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
random_shuffle(iterator beg, iterator end);

3.7.4 reverse算法

1
2
3
4
5
6
/*
reverse算法 反转指定范围的元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
reverse(iterator beg,iterator end);

3.8 常用拷贝替换算法

3.8.1 copy算法

1
2
3
4
5
6
7
8
/*
copy算法 将容器内指定范围的元素拷贝到另一容器中
注意： copy不会给目标容器分配内存，需要提前分配好内存
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param dest 目标起始迭代器
*/
copy(iterator beg, iterator end, iterator dest);

实例演示（打印容器元素的新方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>//提供终端迭代器
using namespace std;
int main(void) {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(5);
	v1.push_back(30);
	v1.push_back(20);
	copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
	//10 5 30 20
	return 0;
}

3.8.2 replace算法

1
2
3
4
5
6
7
8
/*
replace算法 将容器内指定范围内的旧元素修改为新元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param oldval 旧元素
@param newval 新元素
*/
replace(iterator beg, iterator end, oldval, newval);

3.8.3 replace_if算法

1
2
3
4
5
6
7
8
/*
replace_if算法 将容器内指定范围内的满足条件的元素修改为新元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param _callback 函数回调或者谓词(返回bool类型的函数对象)
@param newval 新元素
*/
replace_if(iterator beg, iterator end, _callback, newval);

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>//提供终端迭代器
#include<functional>
using namespace std;
bool LessThan15(int val) {
	return val <= 15;
}
int main(void) {
	vector<int> v1;
	v1.push_back(30);
	v1.push_back(5);
	v1.push_back(10);
	v1.push_back(20);
	replace_if(v1.begin(), v1.end(), LessThan15, 15);
	replace_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 15), 100);
	copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
	//100 15 15 100
	return 0;
}

3.8.4 swap算法

1
2
3
4
5
6
/*
swap算法 互换两个容器的元素
@param c1 容器1
@param c2 容器2
*/
swap(container c1,container c2);

3.9 常用算术生成算法

3.9.1 accumulate算法

1
2
3
4
5
6
7
8
/*
accmulate算法 计算容器累计总和
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 累加值
@return 最终返回值是总和加上value
*/
accmulate(iterator beg,iterator end,value);

3.9.2 fill算法

1
2
3
4
5
6
/*fill算法 对容器某个区间进行填充
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 填充值
*/
fill(iterator beg,iterator end,value);

3.10 常用集合算法

3.10.1 set_intersection算法

1
2
3
4
5
6
7
8
9
10
11
/*
set_intersection算法 求两个集合的交集
注意：两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest 目标容器开始迭代器
@return 目标容器的最后一个元素之后的迭代器地址
*/
set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>//提供终端迭代器
#include<functional>
using namespace std;
int main(void) {
	vector<int> v1{ 12,23,34,45,56 };
	vector<int> v2{ 23,34,78,90 };
	vector<int> v;//存交集
	v.resize(min(v1.size(), v2.size()));
	vector<int>::iterator it;
	it = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin());
	copy(v.begin(), it, ostream_iterator<int>(cout, " "));
	//23 34
	return 0;
}

3.10.2 set_union算法

1
2
3
4
5
6
7
8
9
10
11
/*
set_union算法 求两个集合的并集
注意：两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest 目标容器开始迭代器
@return 目标容器的最后一个元素之后的迭代器地址
*/
set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>//提供终端迭代器
#include<functional>
using namespace std;
int main(void) {
	vector<int> v1{ 12,23,34,45,56 };
	vector<int> v2{ 23,34,78,90 };
	vector<int> v;//存并集
	v.resize(v1.size() + v2.size());
	vector<int>::iterator it;
	it = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin());
	copy(v.begin(), it, ostream_iterator<int>(cout, " "));
	//12 23 34 45 56 78 90
	return 0;
}

3.10.3 set_difference算法

1
2
3
4
5
6
7
8
9
10
11
/*
set_difference算法 求两个集合的差集(某个集合和交集相差的部分)
注意：两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest 目标容器开始迭代器
@return 目标容器的最后一个元素之后的迭代器地址
*/
set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

实例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>//提供终端迭代器
#include<functional>
using namespace std;
int main(void) {
	vector<int> v1{ 12,23,34,45,56 };
	vector<int> v2{ 23,34,78,90 };
	vector<int> v;//存v1对v2的差集
	v.resize(v1.size());
	vector<int>::iterator it;
	it = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin());
	copy(v.begin(), it, ostream_iterator<int>(cout, " "));
	//12 45 56
	return 0;
}