stl中的容器,常见的stl容器有哪些
目录
优先级队列的默认实现使用优先级队列实现小根堆优先级队列结构自定义优先级队列的比较规则优先级队列的默认实现在STL容器中提供priority_queue(优先级队列)实现类堆函数。
为了方便解释其用法,在下面的叙述中priority_queue直接描述为堆。
和用于排序的sort函数一样,priority_queue的默认比较规则是(小于号)。
默认情况下,Sort将根据小于号从小到大对元素进行排序;
默认情况下,根据小于号的比较规则,priority_queue中的元素将最大的元素作为其堆顶部元素。这种想法有点不同。priority_queue的意思是“我比你小,所以我把你推到最上面”。
也就是说,默认情况下,priority_queue中最大的元素总是顶部的元素。
所以默认的priority_queue是一个巨大的堆。
定义priority_queue的一般格式是:
Priority_queue类型名称容器名称;最常用的成员资格方法有:
Push(a):将一个元素A推入堆中;Top():获取堆的顶部元素;Pop():弹出顶部元素;Empty():判断容器是否为空(如果为空,则返回true);Size():返回该容器中当前包含的元素数量。示例程序:
#包含位/标准数据。h
使用命名空间std
优先级队列int que
int main() {
for(int I=3;我我)
que.push(一);
que . push(1);
que . push(8);
cout size= que . size()endl;
而(!que.empty()) {
cout que.top(),;
que . pop();
}
返回0;
}输出结果:
尺寸=6
8,6,5,4,3,1,用优先级队列实现小根堆。默认的比较规则是(小于号),但是我们也可以在定义priority_queue时修改它。例如,下面的代码片段定义了一个大的根堆:
priority_queue int,vector int,greater int que其中,在priority_queue后面的尖括号中:
Int表示数据类型;Vector int表示数据的存储方式,这里用Vector存储(据说这样写会更快,但我主要是想在这里占个位置,方便写第三个参数);更大的int代表比较规则,这个更大的int对应的比较规则是(大于号),也就是“我比你大,我把你顶上去”。应该注意的是,如果priority_queue存储其他类型的数据,则相应的数据类型必须相应地修改。以下代码段定义了一个用于存储双精度数据的小型根堆:
priority_queue double,vector double,greater double que示例程序(优先级队列实现小根堆):
#包含位/标准数据。h
使用命名空间std
priority_queue int,vector int,greater int que
int main() {
for(int I=3;我我)
que.push(一);
que . push(1);
que . push(8);
cout size= que . size()endl;
而(!que.empty()) {
cout que.top(),;
que . pop();
}
返回0;
}输出结果:
尺寸=6
1,3,4,5,6,8,优先级队列结构。对于结构类型的变量,默认情况下没有(小于号)。在这种情况下,显然不可能直接使用这种结构类型的priority_queue(会报错)。
所以你可以考虑为新定义的结构类型定义一个新的函数。这种操作称为重载操作符。
例如,在下面的程序中,我将定义一个名为Node的结构,并为它重载操作符(因为priority_queue默认情况下会查看操作符),并实现一个Node类型的优先级队列。示例程序:
#包含位/标准数据。h
使用命名空间std
结构节点{
int x,y;
//重载小于运算符
布尔运算符(常量节点b)常量{
return x b . x x==b . x y b . y;
}
};
优先级_队列节点que//使用节点的默认比较规则
int main() {
que.push({3,5 });
que.push({2,4 });
que.push({1,3 });
que.push({4,2 });
que.push({3,3 });
而(!que.empty()) {
node u=que . top();
que . pop();
cout ( u.x , u . y ) endl;
}
返回0;
}程序输出结果:
(4 , 2)
(3 , 5)
(3 , 3)
(2 , 4)
(1,3)优先级队列的自定义比较规则有时,某些数据类型可能有封装的运算符,或者它们的运算符有其他用途。在这种情况下,我们不能再为它们重载运算符。那么这个时候我们该怎么办呢?
回过头来看,在使用排序函数时,我们定义了比较函数(俗称cmp,国际惯例)。
然后我们在sort中谈到cmp函数作为sort函数的第三个参数。
类型函数也可以用在priority_queue中,只是priority_queue使用了比较结构。
我们可以定义一个名为Cmp的结构并重载它的()操作符,然后在定义priority_queue的时候用它作为尖括号里的第三个参数。例如,下面的程序为节点类型匹配一个相应的Cmp类型,并使用Cmp的比较规则来实现一个优先级队列。
#包含位/标准数据。h
使用命名空间std
结构节点{
int x,y;
};
结构Cmp {//比较结构
布尔运算符()(节点a,节点b) {
return a . x b . x a . x==b . x a . y b . y;
}
};
priority_queue节点,vector节点,Cmp que//定义que时使用Cmp作为比较规则
int main() {
que.push({3,5 });
que.push({2,4 });
que.push({1,3 });
que.push({4,2 });
que.push({3,3 });
而(!que.empty()) {
node u=que . top();
que . pop();
cout ( u.x , u . y ) endl;
}
返回0;
}输出结果:
(4 , 2)
(3 , 5)
(3 , 3)
(2 , 4)
(1 , 3)
转载请联系作者取得转载授权,否则将追究法律责任。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。