0x00.前言

STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。其中本文包含stackqueuelistset/multisetmap/multimap 五种容器的相关知识。

0x01.stack

stack基础概念

概念:stack是一种先进后出(First In Last Out)的数据结构,它只要一个出口

栈只能对栈顶操作,因此无遍历操作

栈中进入元素称为 — 入栈push

栈中弹出元素称为 — 出栈pop

stack基本接口

功能描述:栈容器常用的对外接口

构造函数:

  • stack<T> stk; stack采用模板类实现,此为默认构造形式
  • stack(const stack& stk); 拷贝构造函数

赋值操作:

  • stack& operator=(const stack& stk); 重载等号运算符

数据存取:

  • push(elem); 向栈顶添加元素
  • pop(); 从栈顶移除第一个元素
  • top(); 返回栈顶元素

大小操作:

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

代码块:

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
#include <iostream>
#include <stack>
using namespace std;

void test()
{
stack<int>s;

//入栈
s.push(10);
s.push(20);
s.push(30);
s.push(40);

//只要栈不为空,查看栈顶,并执行出栈
while (!s.empty())
{
cout << "栈顶元素为" << s.top() << endl;
s.pop();
}

cout << "栈的大小为" << s.size() << endl;
}

int main() {
test();
return 0;
}

/*
栈顶元素为40
栈顶元素为30
栈顶元素为20
栈顶元素为10
栈的大小为0
*/

0x02.queue

queue基本概念

概念:queue是一种先进先出(first in frist out)的数据机构,它有两个出口

队首只能出队pop,队尾只能入队push

queue基本接口

构造函数:

  • queue<T> que; 默认构造
  • queue(const queue& que); 拷贝构造

赋值操作:

  • queue& operator=(const queue& que); 重载等号

数据存取:

  • push(elem); 往队尾添加元素
  • pop(); 从队首移除第一个元素
  • back(); 返回最后一个元素
  • front(); 返回第一个元素

大小操作:

  • empty(); 判断是否为空
  • size(); 换回栈的大小

代码块:

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
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <queue>
using namespace std;

void test()
{
queue<int>q;

//入队
q.push(10);
q.push(20);
q.push(30);
q.push(40);

int i = 0;
//只要队不为空,查看队首与队尾,并执行出队
while (!q.empty())
{
cout << " " << i << endl;
i++;
cout << "队首元素为" << q.front() << endl;
cout << "队尾元素为" << q.back() << endl;
q.pop();
cout << endl;
}
cout << endl;
cout << "队的大小为" << q.size() << endl;
}

int main() {
test();
return 0;
}

/*
0
队首元素为10
队尾元素为40

1
队首元素为20
队尾元素为40

2
队首元素为30
队尾元素为40

3
队首元素为40
队尾元素为40


队的大小为0

*/

0x03.list

list基本概念

功能:将数据进行链式存储

list即链表,是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的

链表由结点组成,结点由数据域与指针域组成,其中STL中的链表是一个双向循环链表

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

list优点:

  • 采用动态存储分配,不会造成内存浪费和溢出
  • 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素

list缺点:

  • 空间与时间额外耗费较大

List插入操作与删除操作都不会造成原有list迭代器的失效,这在vector是不成立的。

总结:STL中list和vector是两个最常用的容器,各有优缺点

list构造函数

函数原型:

  • list<T> lst; 默认构造函数
  • list(beg,end); 将区间中的元素拷贝给本身
  • list(n,elem); 将n个elem拷贝给本身
  • 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <list>
using namespace std;

void printList(const list<int>& l)
{
for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
}

void test()
{
//默认构造
list<int> l1;

l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);

printList(l1);

//用区间构造
list<int>l2(l1.begin(), l1.end());
printList(l2);

//拷贝构造
list<int>l3(l2);
printList(l3);

//n个elem
list<int>l4(4, 888);
printList(l4);
}

int main() {
test();
return 0;
}

/*
10 20 30 40
10 20 30 40
10 20 30 40
888 888 888 888
*/

list赋值和交换

函数原型:

  • assign(beg,end); 给区间中的数据拷贝赋值给本身
  • assign(n,elem); 将n个elem拷贝赋值给本身
  • list& operator=(const list& lst); 重载等号操作符
  • swap(lst); 将lst与本身的元素互换

示例:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <list>
using namespace std;

void printList(const list<int>& l)
{
for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
}

void test()
{

list<int> l1;

l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);

printList(l1);

list<int>l2;
l2 = l1;
printList(l2);

list<int>l3;
l3.assign(l2.begin(), l2.end());
printList(l3);

list<int>l4;
l4.assign(4,88);
printList(l4);


}

//交换
void test02()
{
list<int> l1;

l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);

list<int>l2;
l2.assign(5, 88);

cout << " before" << endl;
printList(l1);
printList(l2);

l1.swap(l2);

cout << " after" << endl;
printList(l1);
printList(l2);
}

int main() {
//test();
test02();
return 0;
}

/*
before
10 20 30 40
88 88 88 88 88
after
88 88 88 88 88
10 20 30 40
*/

list大小操作

函数原型:

  • size();
  • empty();
  • resize(num);
  • resize(num,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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <list>
using namespace std;

void printList(const list<int>& l)
{
for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
}

void test()
{

list<int> l1;

l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);

printList(l1);

if (l1.empty())
{
cout << "empty " << endl;
}
else
{
cout << "not empty" << endl;
cout << "size = " << l1.size() << endl;
}

//重新指定大小
l1.resize(10, 88);
printList(l1);

l1.resize(2);
printList(l1);
}

int main() {
test();
return 0;
}

/*
10 20 30 40
not empty
size = 4
10 20 30 40 88 88 88 88 88 88
10 20
*/

list插入与删除

函数原型:

头尾插入删除一个元素:

  • push_back(elem);
  • pop_back();
  • push_front(elem);
  • pop_front();

指定位置插入:

  • insert(pos,elem); pos均为迭代器
  • insert(pos,n,elem);
  • insert(pos,beg,end);

指定删除:

  • clear()
  • erase(beg,end);
  • erase(pos);
  • 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <list>
using namespace std;

void printList(const list<int>& l)
{
for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
}

void test()
{

list<int> l1;

//尾插
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);

//头插
l1.push_front(100);
l1.push_front(200);
l1.push_front(300);

printList(l1);

//尾删
cout << " 尾删" << endl;
l1.pop_back();
printList(l1);
//头删
cout << " 头删" << endl;
l1.pop_front();
printList(l1);

//insert插入
cout << " insert插入" << endl;
list<int>::iterator it = l1.begin();
it++;
l1.insert(it, 1000);
printList(l1);

//删除
cout << " 删除" << endl;
it = l1.begin();
l1.erase(++it);
printList(l1);

//移除
it = l1.begin();
l1.insert(++it, 4, 88);
cout << " 移除前" << endl;
printList(l1);

l1.remove(88);
cout << " 移除后" << endl;
printList(l1);

//清空
l1.clear();
printList(l1);
}

int main() {
test();
return 0;
}

/*
300 200 100 10 20 30
尾删
300 200 100 10 20
头删
200 100 10 20
insert插入
200 1000 100 10 20
删除
200 100 10 20
移除前
200 88 88 88 88 100 10 20
移除后
200 100 10 20
*/

list数据存取

函数原型:

  • front(); 返回第一个元素
  • back(); 返回最后一个元素

代码块:

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 <list>
using namespace std;


void test()
{

list<int> l1;

l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);

cout << "首元素为:" << l1.front() << endl;
cout << "尾元素为:" << l1.back() << endl;
}

int main() {
test();
return 0;
}

/*
首元素为:10
尾元素为:40
*/

list翻转与排序

函数原型:

  • reverse(); 反转链表
  • sort(); 链表排序

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <list>
using namespace std;

void printList(const list<int>& l)
{
for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
}

bool myCompare(int a, int b)
{
//想升序 a < b
//想降序 a > b
return a > b;
}

void test()
{

list<int> l1;

l1.push_back(25);
l1.push_back(20);
l1.push_back(30);
l1.push_back(49);

cout << "反转前:" << endl;
printList(l1);

//反转
l1.reverse();

cout << "反转后:" << endl;
printList(l1);

cout << "排序前:" << endl;
printList(l1);

/*
不能使用 sort(l1.begin(),l1.end())
所有不支持随机访问迭代器的容器,不可以使用标准算法
但是不支持随机访问迭代器的容器会自带对应的算法
*/
//排序
l1.sort();
cout << "升序排序后:" << endl;
printList(l1);


l1.sort(myCompare);
cout << "降序排序后:" << endl;
printList(l1);

}

int main() {
test();
return 0;
}

/*
反转前:
25 20 30 49
反转后:
49 30 20 25
排序前:
49 30 20 25
升序排序后:
20 25 30 49
降序排序后:
49 30 25 20
*/

排序案例

案例描述:将Person自定义数据类型进行排序,Person中属性有姓名、年龄、升高

排序规则:按照年龄进行升序,如果年龄相同,按照升高进行降序

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <list>
#include <string>
using namespace std;

class Person
{
public:
Person(string name, int age, int height)
{
this->m_Name = name;
this->m_Age = age;
this->m_Height = height;
}


string m_Name;
int m_Age;
int m_Height;
};

void printList(const list<Person>& l)
{
for (list<Person>::const_iterator it = l.begin(); it != l.end(); it++)
{
cout << it->m_Name << " " << it->m_Age << " " << it->m_Height << endl;
}
cout << endl;
}

bool comparePerson(Person& p1,Person& p2)
{
if (p1.m_Age == p2.m_Age)
return p1.m_Height > p2.m_Height;
else
return p1.m_Age < p2.m_Age;
}

void test()
{

list<Person> l1;

Person p1("唐僧",28,175);
Person p2("悟空", 888, 165);
Person p3("八戒", 444, 170);
Person p4("沙僧", 444, 175);

l1.push_back(p1);
l1.push_back(p2);
l1.push_back(p3);
l1.push_back(p4);

cout << "排序前:" << endl;
printList(l1);
cout << "-------------------" << endl;
l1.sort(comparePerson);
cout << "排序后:" << endl;
printList(l1);


}

int main() {
test();
return 0;
}

/*

排序前:
唐僧 28 175
悟空 888 165
八戒 444 170
沙僧 444 175

-------------------
排序后:
唐僧 28 175
沙僧 444 175
八戒 444 170
悟空 888 165

*/

小结:

  • 对于自定义数据类型,必须要制定排序规则
  • 高级排序只是在排序规则上再进行一次逻辑规则制定

0x04.set/multiset

set基本概念

简介:

  • 所有的元素都会在插入时自动被排序

本质:

  • set/multiset属于关联式容器,底层结构是用二叉树实现。

set与multiset区别:

  • set不允许容器中有重复的元素
  • multiset允许容器中有重复的元素

set构造和赋值

构造:

  • set<T> st; 默认构造
  • set(const set &st); 拷贝构造

赋值:

  • set& operator=(const set &st); 重载等号操作符

代码块:

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
#include <iostream>
#include <set>
using namespace std;

void printSet(set<int>&s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

void test()
{

set<int> s1;

s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(30);

//遍历容器
//set容器特点:所有元素插入时候会被自动排序,且不允许重复值
printSet(s1);

set<int>s2(s1);
printSet(s2);

set<int>s3;
s3 = s2;
printSet(s3);
}

int main() {
test();
return 0;
}

小结:插入数据是使用insert,无push

set大小与交换

函数原型:

  • size(); 返回容器中的数目
  • empty(); 判断容器是否为空
  • swap(); 交换两个集合容器

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <set>
using namespace std;

void printSet(set<int>& s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

void test()
{

set<int> s1;

s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(30);


if (s1.empty())
{
cout << "s1's empty" << endl;
}
else
{
cout << "s1's not empty" << endl;
printSet(s1);
}

set<int>s2;
cout << "s1的大小为 " << s1.size() << endl;

s2.insert(999);

cout << "----交换前----" << endl;
cout << "s1 : ";
printSet(s1);

cout << "s2 : ";
printSet(s2);

s1.swap(s2);

cout << "----交换后----" << endl;
cout << "s1 : ";
printSet(s1);

cout << "s2 : ";
printSet(s2);
}

int main() {
test();
return 0;
}

/*
s1's not empty
10 20 30
s1的大小为 3
----交换前----
s1 : 10 20 30
s2 : 999
----交换后----
s1 : 999
s2 : 10 20 30
*/

小结:不支持resize

set插入与删除

函数原型:

  • insert(elem); 在容器中插入元素
  • clear(); 清除所有元素
  • erase(pos); 删除pos迭代器所指的元素,返回下一个元素的迭代器
  • erase(beg, end); 删除区间内的元素,返回下一个元素的迭代器
  • erase(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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <set>
using namespace std;

void printSet(set<int>& s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

void test()
{

set<int> s1;

s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);


printSet(s1);

//删除
s1.erase(s1.begin());
printSet(s1);

//指定删除
s1.erase(40);
printSet(s1);

//清空
//s1.erase(s1.begin(), s1.end());
s1.clear();
printSet(s1);
}

int main() {
test();
return 0;
}

/*
10 20 30 40
20 30 40
20 30

*/

set查找与统计

函数原型:

  • find(key); 查找key是否存在,返回该键的元素迭代器;若不存在返回set.end()
  • count(key); 统计key的元素个数

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <set>
using namespace std;

void printSet(set<int>& s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

void test()
{

set<int> s1;

s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);

set<int>::iterator pos = s1.find(30);
//set<int>::iterator pos = s1.find(300);

if (pos != s1.end())
{
cout << "找到元素" << endl;
}
else
{
cout << "未找到元素" << endl;
}

}

void test02()
{

set<int> s1;

s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
s1.insert(40);
s1.insert(40);

int num = s1.count(40);
cout << "num = " << num << endl;

num = s1.count(60);
cout << "num = " << num << endl;

//对于set而言count只返回0或1,multiset返回值可以大于1
}

int main() {
test();
test02();
return 0;
}

set和multiset区别

区别:

  • set不可以插入重复数据,二multiset可以
  • set插入数据的同时会返回结果,表示插入是否成功
  • multiset不会检测数据,因此可以插入重复数据

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <set>
using namespace std;

void printSet(set<int>& s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

void test()
{

set<int> s;

pair<set<int>::iterator, bool> ret = s.insert(10);

if (ret.second)
{
cout << "第一次插入成功" << endl;
}
else
{
cout << "第一次插入失败" << endl;
}

ret = s.insert(10);
if (ret.second)
{
cout << "第二次插入成功" << endl;
}
else
{
cout << "第二次插入失败" << endl;
}

cout << "\n以下为multiset测试" << endl;
multiset<int>ms;
//可以插入重复值
ms.insert(10); //返回值是iterator而不是pair
ms.insert(10);

for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}

int main() {
test();
return 0;
}

/*
第一次插入成功
第二次插入失败

以下为multiset测试
10 10
*/

小结:

  • 如果不允许插入重复的数据,可以使用set
  • 如果需要插入重复的数据,那么使用multiset

pair对组创建

功能:

  • 成对出现的数据,利用对组可以返回两个数据

创建方式:

  • pair<type,type>p(value1,value2);
  • pair<type,type>p=make_pair(value1,value2);

代码块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
using namespace std;


void test()
{
//第一种方式
pair<string, int>p("Tom", 20);

cout << "姓名" << p.first << " 年龄: " << p.second << endl;

//第二种方式
pair<string, int>p2 = make_pair("Jerry", 18);
cout << "姓名" << p2.first << " 年龄: " << p2.second << endl;
}

int main() {
test();
return 0;
}

set容器排序

学习目标:

  • set容器默认排序规则是从小到大,掌握如何改变排序规则

主要技术点:

  • 利用仿函数,可以改变排序规则

示例一: set存放内置数据类型

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
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <set>
using namespace std;


class MyCompare
{
public:
//仿函数 vs2019需要加上const
bool operator()(int v1,int v2) const
{
return v1 > v2;
}
};

void test()
{

set<int> s1;

s1.insert(50);
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);


for (set<int>::iterator it = s1.begin(); it != s1.end(); it++)
{
cout << *it << " ";
}
cout << endl;

//指定排序规则为从大到小
set<int, MyCompare> s2;

s2.insert(50);
s2.insert(10);
s2.insert(20);
s2.insert(40);
s2.insert(30);

for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++)
{
cout << (*it) << " ";
}
cout << endl;
}

int main() {
test();
return 0;
}

/*
10 20 30 40 50
50 40 30 20 10
*/

小结:利用仿函数可以指定set容器的排序规则

示例二:: set存放自定义数据类型

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <set>
#include <string>
using namespace std;

class Person
{
public:
Person(string name,int age)
{
this->m_Age = age;
this->m_Name = name;
}

string m_Name;
int m_Age;
};

class ComparePerson
{
public:
bool operator()(const Person&p1, const Person&p2) const
{
//按照年龄降序
return p1.m_Age > p2.m_Age;
}
};

void test()
{
//自定义的数据类型 都会指定排序规则
set<Person, ComparePerson> s;

Person p3("张飞", 25);
Person p4("赵云", 21);
Person p1("刘备", 28);
Person p2("关羽", 26);

s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);

for (set<Person, ComparePerson>::iterator it = s.begin(); it != s.end(); it++)
{
cout << "姓名: " << it->m_Name << " 年龄: " << it->m_Age << endl;
}
}

int main() {
test();
return 0;
}

/*
姓名: 刘备 年龄: 28
姓名: 关羽 年龄: 26
姓名: 张飞 年龄: 25
姓名: 赵云 年龄: 21
*/

小结:自定义数据类型,set必须指定排序规则才可以插入数据

0x05 map/multimap

map基本概念

简介:

  • map中所有的元素都是pair
  • pair中第一个元素为key,起到索引作用,第二个元素为value
  • 所有的元素都会根据元素的键值自动排序

本质:

  • map/multimap属于关联式容器,底层结构用二叉树实现

优点:

  • 可以根据key值快速的找到value值

map与multimap区别:

  • map不允许容器中有重复key值远古三
  • multimap允许容器中有重复key值元素

map构造和赋值

函数原型:

构造

  • map<T1,T2> mp;
  • map(const map& mp);

赋值

  • map& operator=(const map& mp);

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <map>
using namespace std;

void printMap(map<int, int>&m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}

void test()
{
map<int, int> m;

//按照key来排序
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(4, 40));
m.insert(pair<int, int>(5, 50));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));

printMap(m);

map<int, int> m2(m);
printMap(m2);

map<int, int> m3;
m3 = m2;
printMap(m3);
}

int main() {
test();
return 0;
}

/*
key = 1 value = 10
key = 2 value = 20
key = 3 value = 30
key = 4 value = 40
key = 5 value = 50

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30
key = 4 value = 40
key = 5 value = 50

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30
key = 4 value = 40
key = 5 value = 50
*/

小结:map中所有的元素都是成对出现,插入数据时候要使用对组

map大小和交换

函数原型:

  • size();
  • empty();
  • swap(st);

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <map>
using namespace std;

void printMap(map<int, int>& m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}

void test()
{
map<int, int> m;

//按照key来排序
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(4, 40));
m.insert(pair<int, int>(5, 50));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));

printMap(m);

if (m.empty())
{
cout << "empty" << endl;
cout << "size = " << m.size() << endl;
}
else
{
cout << "not empty" << endl;
cout << "size = " << m.size() << endl;
}


}

void test02()
{
map<int, int>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));

map<int, int>m2;
m2.insert(pair<int, int>(4, 40));
m2.insert(pair<int, int>(5, 50));
m2.insert(pair<int, int>(6, 60));

cout << " before swap " << endl;
printMap(m);
printMap(m2);

m.swap(m2);

cout << " after swap " << endl;
printMap(m);
printMap(m2);
}

int main() {
test();
test02();
return 0;
}

/*
key = 1 value = 10
key = 2 value = 20
key = 3 value = 30
key = 4 value = 40
key = 5 value = 50

not empty
size = 5
before swap
key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

key = 4 value = 40
key = 5 value = 50
key = 6 value = 60

after swap
key = 4 value = 40
key = 5 value = 50
key = 6 value = 60

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

*/

map插入和删除

函数原型:

  • insert(elem);
  • clear();
  • erase(pos);
  • erase(beg,end);
  • erase(key);

代码块:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <map>
using namespace std;

void printMap(map<int, int>& m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}

void test()
{
map<int, int> m;

//插入
//第一种
m.insert(pair<int, int>(1, 10));

//第二组
m.insert(make_pair(2, 20));

//第三种
m.insert(map<int, int>::value_type(3, 30));

//第四种 可能会意外的创建不想要的数据 如30行
m[4] = 40;
//cout << m[5] << endl; 若没有第五个元素会创建一个key=5 value=0的pair

printMap(m);

//删除
m.erase(m.begin());
printMap(m);

m.erase(3); //按照 key 删除
printMap(m);

//两种清空
m.erase(m.begin(), m.end());
printMap(m);
m.clear();
printMap(m);
}


int main() {
test();
return 0;
}

/*
key = 1 value = 10
key = 2 value = 20
key = 3 value = 30
key = 4 value = 40

key = 2 value = 20
key = 3 value = 30
key = 4 value = 40

key = 2 value = 20
key = 4 value = 40



*/

map查找与统计

函数原型:

  • find(key); 查找key是否存在,若存在则返回该键的迭代器,不存在则返回map.end();
  • count(key); 统计key的元素个数

代码:

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
46
47
#include <iostream>
#include <map>
using namespace std;

void printMap(const map<int, int>& m)
{
for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}

void test()
{
//查找
map<int, int>m;
m.insert(make_pair(1, 10));
m.insert(make_pair(2, 20));
m.insert(make_pair(3, 30));

map<int, int>::iterator pos = m.find(3);

if (pos != m.end())
{
cout << "查找到了元素 key = " << pos->first << " value = " << pos->second << endl;
}
else
{
cout << "未找到元素" << endl;
}

//统计 map中无重复key,但是在multimap可以有重复key
//所以map的count()返回值只有0 1,但是multimap的count()返回值可以是>1
int num = m.count(3);
cout << "num = " << num << endl;
}

int main() {
test();
return 0;
}

/*
查找到了元素 key = 3 value = 30
num = 1
*/

map排序

学习目标:

  • map容器默认的排序规则为按照key值 从小到大排序,需掌握如何改变排序规则

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

内置数据类型排序:

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
#include <iostream>
#include <map>
using namespace std;

class Compare
{
public:
bool operator()(int v1,int v2) const
{
return v1 > v2;
}
};

void printMap(const map<int, int, Compare>& m)
{
for (map<int, int, Compare>::const_iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}

void test()
{

map<int, int , Compare>m;
m.insert(make_pair(1, 10));
m.insert(make_pair(6, 60));
m.insert(make_pair(2, 20));
m.insert(make_pair(5, 50));
m.insert(make_pair(3, 30));
m.insert(make_pair(4, 40));

printMap(m);
}

int main() {
test();
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <map>
#include <string>
using namespace std;

class Person
{
public:

Person(string name, int age)
{
this->m_Name = name;
this->m_Age = age;
}

string m_Name;
int m_Age;

};

class Compare
{
public:
bool operator()(const Person& v1, const Person& v2) const
{
return v1.m_Age < v2.m_Age;
}
};


void test()
{
Person p1("张飞", 25);
Person p2("赵云", 21);
Person p3("刘备", 28);
Person p4("关羽", 26);


map<Person, int , Compare>m;
m.insert(make_pair(p1, 10));
m.insert(make_pair(p2, 20));
m.insert(make_pair(p3, 30));
m.insert(make_pair(p4, 40));

cout << "按照key中年龄升序排列:" << endl;
for (map<Person, int, Compare>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = ( 姓名:" << (it->first).m_Name
<< " 年龄:" << (it->first).m_Age << " ) "
<< "value = " << it->second << endl;
}
}

int main() {
test();
return 0;
}

/*
按照key中年龄升序排列:
key = ( 姓名:赵云 年龄:21 ) value = 20
key = ( 姓名:张飞 年龄:25 ) value = 10
key = ( 姓名:关羽 年龄:26 ) value = 40
key = ( 姓名:刘备 年龄:28 ) value = 30
*/
  • 对于自定义数据类型,map必须要指定排序规则,同set

0x06.案例-员工分组

案例描述

  • 公司招聘了10个员工(ABCDEFGHIJ),10名员工进入公司之后,需要指派员工在那个部门工作
  • 员工信息:姓名 工作组成;部门信息:策划,美术,研发
  • 随机给10名员工分配部门和工资
  • 通过multimap进行信息的插入 key(部门编号) value(员工)
  • 分部门展示员工信息

实现步骤

1.创建10名员工,放在vector中
2.遍历vector容器,取出每个员工,进行随机分组
3.分组后将部门编号最为key,员工最为value,放入multimap中
4.分部门显示员工信息

代码实现

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <ctime>
using namespace std;

#define CEHUA 0
#define MEISHU 1
#define YANFA 2

class Worker
{
public:
Worker(string name,int salary)
{
this->m_Name = name;
this->m_Salary = salary;
}
Worker() {}
string m_Name;
int m_Salary;
};

void createWorker(vector<Worker>&v)
{
string nameSeed = "ABCDEFGHIJ";
for (int i = 0; i < 10; i++)
{
Worker worker;
worker.m_Name = "员工";
worker.m_Name += nameSeed[i];

worker.m_Salary = rand() % 10000 + 10000;

v.push_back(worker);
}
}

void setGroup(vector<Worker>& v, multimap<int, Worker>&m)
{

for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
{
//产生随机部门编号
int depId = rand() % 3;

//将员工插入到分组中
m.insert(make_pair(depId, *it));

}
}

void showWorkerByGroup(multimap<int, Worker>&m)
{

cout << "-------------" << endl;
cout << " 策划部门 " << endl;
multimap<int, Worker>::iterator pos = m.find(CEHUA);
int count = m.count(CEHUA);
int index = 0;
for (; pos != m.end() && index < count; pos++, index++)
{
cout << "姓名: " << pos->second.m_Name
<< " 工资: " << pos->second.m_Salary << endl;
}

cout << "-------------" << endl;
cout << " 美术部门 " << endl;
pos = m.find(MEISHU);
count = m.count(MEISHU);
index = 0;
for (; pos != m.end() && index < count; pos++, index++)
{
cout << "姓名: " << pos->second.m_Name
<< " 工资: " << pos->second.m_Salary << endl;
}

cout << "-------------" << endl;
cout << " 研发部门 " << endl;
pos = m.find(YANFA);
count = m.count(YANFA);
index = 0;
for (; pos != m.end() && index < count; pos++, index++)
{
cout << "姓名: " << pos->second.m_Name
<< " 工资: " << pos->second.m_Salary << endl;
}
cout << "-------------" << endl;
}

int main() {

srand((unsigned int)time(NULL));

//创建员工
vector<Worker> vWorker;
createWorker(vWorker);

//员工分组
multimap<int, Worker>mWorker;
setGroup(vWorker, mWorker);

//分组显示员工
showWorkerByGroup(mWorker);
return 0;
}

/*
某一次结果:
-------------
策划部门
姓名: 员工E 工资: 15622
姓名: 员工H 工资: 11675
-------------
美术部门
姓名: 员工B 工资: 11266
姓名: 员工C 工资: 12042
姓名: 员工D 工资: 17050
姓名: 员工G 工资: 11886
姓名: 员工I 工资: 11899
姓名: 员工J 工资: 18774
-------------
研发部门
姓名: 员工A 工资: 16322
姓名: 员工F 工资: 19324
-------------
*/

0x07.后记

在之后的学习中,还将学习到STL中的函数对象STL中的常用算法相关的知识。



生活不是等待风暴过去,而是学会在雨中翩翩起舞。