数据结构 -- C++ STL中的数据结构与算法[2]
接前一篇
本篇主要讲 Priority_queue、Set、Map、MutilSet、MutilMap 容器
Priority_queue(优先队列)
优先队列是一种极其特殊的队列，他与标准的队列使用线性结构进行计算不同，优先队列的底层是以散列的状态（非线性）表现的，他与标准的队列有如下的区别，标准的队列遵从严格的先进先出，优先队列并不遵从标准的先进先出，而是对每一个数据赋予一个权值，根据当前队列权值的状态进行排序，永远使得权值最大（或最小）的排在队列的最前面。
2. 相关文件
由于其属于队列的一种，因此可以直接使用队列的头文件#include<queue>
3. 初始化
priority_queue<T, Container, Compare>
priority_queue<T> //直接输入元素则使用默认容器和比较函数
与往常的初始化不同，优先队列的初始化涉及到一组而外的变量，这里解释一下初始化：
a) T就是Type为数据类型
b) Container是容器类型，（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
c) Compare是比较方法，类似于sort第三个参数那样的比较方式，对于自定义类型，需要我们手动进行比较运算符的重载。与sort直接Bool一个函数来进行比较的简单方法不同，Compare需要使用结构体的运算符重载完成，直接bool cmp(int a,int b){ return a>b; } 这么写是无法通过编译的。
4.Demo
#include <queue>
#include <iostream>
using namespace std;
struct compare
{
//这个比较要用结构体表示
bool operator()(float &a, float &b) const
{
return a > b;
}
};
int main()
{
priority_queue<float, vector<float>, compare> q;
for (int i = 1; i <= 5; i++)
{
q.push(i * 10.2);
}
q.push(15.3);
q.push(4.4);
int i = 0;
float temp = q.top();
while (!q.empty())
{
temp = q.top();
q.pop();
cout << "No " << i++ << " element is: " << temp << endl;
}
return 0;
}
输出：
No 0 element is: 4.4
No 1 element is: 10.2
No 2 element is: 15.3
No 3 element is: 20.4
No 4 element is: 30.6
No 5 element is: 40.8
No 6 element is: 51
Set容器
1. 简介
Set（集合）属于关联式容器，也是STL中最实用的容器，关联式容器依据特定的排序准则，自动为其元素排序。Set集合的底层使用一颗红黑树（可能读者对此不太了解，等但学到树论与图论的章节的时候就会明白原因），其属于一种非线性的数据结构，每一次插入数据都会自动进行排序，注意，不是需要排序时再排序，而是每一次插入数据的时候其都会自动进行排序。因此，Set中的元素总是顺序的。
Set的性质有：数据自动进行排序且数据唯一，是一种集合元素，允许进行数学上的集合相关的操作。
2. 相关文件
头文件：#include <set>
3. 初始化
初始化格式：
template < class T,
class Compare = less<T>,
class Alloc = allocator<T>
> class set;
基本上就是三个参数，第一个是值，第二个比较器，用于比较内容，默认为less<Key>即降序，第三个是内存配置器，负责内存的分配和销毁。
在实际使用中，我们仅仅为其分配值就足以满足大部分需求。
set<struct ST_Student> students;
4. 迭代器
C98标准下：
set<struct ST_Student>::iterator it;
for (it = students.cbegin(); it != students.cend(); ++it)
cout << it->name << ':' << it->score << ' ';
这也是前文学过的标准用法，接下来，让我们了解一个更加先进和便捷的方法，auto方法迭代，这需要我们编译器开启C11标准，每个编译器的开启标准不一，请具体情况具体分析。
C11标准下：
for (auto it = students.cbegin(); it != students.cend(); ++it)
cout << it->name << ':' << it->score << ' ';
可见我们使用了auto进行了迭代器类型的自动识别，省去了我们的声明迭代器的那一部分内容，这使得代码更加简化。
5.Demo
#include <set>
#include <iostream>
using namespace std;
struct ST_Student
{
int name;
float score;
//重载“<”操作符，自定义排序规则
bool operator<(const ST_Student &a) const
{
//按score从大到小排列
return a.score < score;
}
};
struct compare
{
//这个比较要用结构体表示
bool operator()(const ST_Student &a, const ST_Student &b) const
{
return a.score > b.score;
}
};
int main()
{
//set<ST_Student> students; // 这个使用重载的 重载“<”操作符，自定义排序规则
set<ST_Student, compare> students; // 这种定义方法使用了传递比较方法
for (int i = 1; i <= 5; i++)
{
ST_Student student;
student.name = i;
student.score = rand()%100;
students.insert(student);
}
for (auto it = students.cbegin(); it != students.cend(); ++it)
cout << it->name << ':' << it->score << ' ';
return 0;
}
输出：
5:69 2:67 1:41 3:34 4:0
Map容器
1. 简介
Map也是一种关联容器，它是 键—值对的集合，即它的存储都是以一对键和值进行存储的，Map通常也可以理解为关联数组（associative array）,就是每一个值都有一个键与之一一对应，因此，map也是不允许重复元素出现的。
同时map也具备set的相关功能，其底层也会将元素进行自动排序，
2. 相关文件
头文件：#include <map>
3. 初始化
格式为：
template < class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key,T> >
> class map;
一共有4个值，其中第一个是键，第二个是值，这两个元素呈现对应的关系，接着第三个元素是比较器，其默认是降序排序，第四个是内存配置器，负责内存的分配和销毁。我们常用的可以直接省去第三和第四个值的输入，只输入键和值即可。
4.迭代器
同之前的容器一样，迭代器用法都是类似的
以map<char,int> 为例，代码如下：
for(map<char,int>::iterator it=s.begin();it!=s.end();it++){
cout<< it->first <<" --- " << it->second<<endl;
}
这里我们需要注意一下，我们不能直接通过*it的输出方式输出值，因为map种含有两个元素，相当于一个struct结构体，是一个复合类型，C/C++中输出复合类型需要我们指定复合类型的值。
因此我们输出就变成了it->first 指定输出键，it-<second指定输出值（刚好就是英文的第一和第二的意思）
5.Pair类模板
讲到Map 需要介绍一下Pair类模板
Pair表示“一对”的意思，pair将两个数据合成一组数据，在如下两种变成情况中，我们更加常见与使用pair，第一是使用STL中的map（在上一节讲过），对于map而言，key和value需要分开来进行使用和声明，使用pair可以合二为一（但是数据输出时依旧要分离），第二则是当我们的函数需要返回两个数据的时候，可以使用pair。
Pair的实现是一个结构体而不是一个类因此可以直接使用pair的成员变量。
如下是几种初始化数值的方法：
pair<int,int> p;
pair<int,int> p(10,20);
pair<int,int> p;
p.first=10,p.second=20;
pair<int,int> p;
p=make_pair(10,20);
那么 map的初始化就可以为：
map<char,int> m;
m.insert(pair<char,int>('a',10));
multiset与multimap容器
1. Multiset
Multiset是set集合容器的一种，其拥有set的全部内容，在此基础之上，multiset还具备了可以重复保存元素的功能，因此会有略微和set的差别。
Multise容器在执行insert()时，只要数据不是非法数据和空数据，insert就总是能够执行，无论时一个数据还是一段数据。
Multiset容器中的find()函数回返回和参数匹配的第一个元素的迭代器，即时存在多个元素也只是返回第一个，如{10,20,20,20}搜索20进行匹配将会返回第二个参数，如果没有符合的参数则结束迭代器。
同理诸如lower_bound()等的需要进行一个位置的返回值，则统统返回第一个发现的值。
2. Multimap容器
Multimap时map映射容器的一种，其拥有map的全部内容，并在此基础之上，multimap还具有了可以重复保存元素的功能，与上文的mutliset差不多，任何进行访问单个值得语句访问均只会返回第一个位置，这里不再多说，而是举一个实际中可能用得到得例子。
有没有一种方法，使得一个key值能够对应多个value，产生一种诸如一个学生有多门考试成绩一样的映射
我们都知道map关联容器是使得一个数据与另一个数据发生映射的容器，通过key得到value产生一一对应，那么multimap在此基础上使得map元素可以重复，因此这种情况可以使用multimap。
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
struct ST_exam
{
int name; // 学科
float score; // 成绩
};
int main(){
multiset<int> ms;
ms.insert(10);
ms.insert(20);
ms.insert(10);
ms.insert(20);
ms.insert(30);
ms.insert(50);
//{10,20,10,20,30,50} -----> {10,10,20,20,30,50} 插入时即会自动排序
cout<< "find '20' pointer value:" << *ms.find(20)<<endl; //这样是找不出来的哟
int i=0;
for(multiset<int>::iterator it=ms.begin();it!=ms.find(20);it++,i++){}
cout << "find '20' index:" << i << endl; //由于是从0开始计算的因此答案是2
multimap<string, ST_exam> m_map;
string name = "XiaoMing";
for(int i=0; i < 3; i++) {
ST_exam exam;
exam.name = i;
exam.score = rand()%100;
m_map.insert(make_pair(name, exam));
}
//方式1
cout << "----------method 1-----------" << endl;
int k;
multimap<string, ST_exam>::iterator m;
m = m_map.find(name);
for (k = 0; k != m_map.count(name); k++, m++)
cout << m->first << "--" << m->second.name << ':' << m->second.score << endl;
//方式2
cout << "----------method 2-----------" << endl;
multimap<string, ST_exam>::iterator beg, end;
beg = m_map.lower_bound(name);
end = m_map.upper_bound(name);
for (m = beg; m != end; m++)
cout << m->first << "--" << m->second.name << ':' << m->second.score << endl;
//方式3
cout << "----------method 3-----------" << endl;
beg = m_map.equal_range(name).first;
end = m_map.equal_range(name).second;
for (m = beg; m != end; m++)
cout << m->first << "--" << m->second.name << ':' << m->second.score << endl;
return 0;
}
集合论
1. 集合论简介
集合论，是数学的一个基本的分支学科，研究对象是一般集合。集合论在数学中占有一个独特的地位，它的基本概念已渗透到数学的所有领域。集合论或集论是研究集合（由一堆抽象物件构成的整体）的数学理论，包含了集合、元素和成员关系等最基本的数学概念。
在我们还在高中教育阶段，可能或多或少会接触到一些诸如集合并交差的运算，而集合论与我们C++的STL运算有很多相似而相同的关系。
2. 集合关系
我们假设有两个集合：
A={2,4,6}
B={1,2,3,4,5}
在数学上
交运算可以写为：
交运算
并运算可以写为：
并运算
差运算可以写为：
差运算
我们以该内容为例，进行代码介绍。
3. Algorithm头文件
STL的算法头文件，STL中除了我们常用的这些容器文件以外，还有一个极其重要的头文件，Algorithm，他是我们常用的标准算法的集合，为我们预先封装了我们可能会用到的算法，比如说排序，使用Algorithm头文件中的sort函数可以快速帮我们进行数组排序
4. 集合论与STL集合
在数学上的并运算我们可以使用set_union()函数进行实现，而交运算我们也可以使用set_intersection()函数进行实现，查集则使用set_difference()函数实现，以下是简单的实现代码，这个案例会同时提供一些前面所学的知识，当作一个汇总练习。
Demo
#include <iostream>
#include <set>
#include <vector>
#include <algorithm> //使用算法头文件
using namespace std;
int main() {
set<int> a, b; //建立两个集合
vector<int> c; //建立一个向量，我们用这个向量存储运算结果
int num = 0;
for(int i = 0; i < 5; i++) {
num = rand();
a.insert(num% 100);
b.insert(num%88);
}
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));//并集
for(vector<int>::iterator it=c.begin();it!=c.end();it++){
cout<< *it << ' ';
}
cout<<endl;
c.clear();
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));//交集
for(vector<int>::iterator it=c.begin();it!=c.end();it++){
cout<< *it << ' ';
}
cout<<endl;
c.clear();
//差集 从B中减去A包含的元素
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
for(vector<int>::iterator it=c.begin();it!=c.end();it++){
cout<< *it << ' ';
}
cout<<endl;
c.clear();
return 0;
}
输出
0 12 34 41 67 69 73 75 86
41
0 34 67 69
网友评论