map (需#include<map>

map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)。

看这样一个场景:需要判断给定的数字在某个文件中是否出现过,按照正常思路可以开一个bool类型的哈希表,但是如果这些数字很大(例如上千位),那么我们就难以开数组。这时我们就可以用map,把数字看做string,建立string到int的映射(或者直接int到int映射)

map的定义

1
map<typename1,typename2> mp;

注意,如果是字符串到整型的映射,必须是map<string,int>不能是map<char[],int>,因为char数组作为数组是不能作为键值的,如果想用字符串映射,必须用string

map内元素的访问

通过下标访问

可以直接访问,例如对于map<char,int>mp,可以直接使用mp['c']=20这样的方式访问,但是map中的键是唯一的。也就是说,不可能同时存在两个mp['c']分别等于两个不同的值,两次对mp['c']赋值则会使后一次赋值覆盖前一次的值。

map的键和值唯一对应,如果需要一个键对应多个值,需要使用multimap

通过迭代器访问

map<typename1,typename2>::iterator it;定义了map类型迭代器.在使用迭代器时,使用it->first访问键,使用it->second访问值。

注意:map会按照从小到大的顺序自动排序。

map常用函数

  • find()

    用find函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器,如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include <map>
    #include <string>
    #include <iostream>
    Using namespace std;
    Int main()
    {
    Map<int, string> mapStudent;
    mapStudent.insert(pair<int, string>(1, “student_one”));
    mapStudent.insert(pair<int, string>(2, “student_two”));
    mapStudent.insert(pair<int, string>(3, “student_three”));
    map<int, string>::iterator iter;
    iter = mapStudent.find(1);
    if(iter != mapStudent.end())
    {
    Cout<<”Find, the value is ”<<iter->second<<endl;
    }
    else
    {
    Cout<<”Do not Find”<<endl;
    }
    }
  • erase()

    • 删除单个元素

      • mp.erase(it),it为需要删除的元素的迭代器,时间复杂度O(1)
      • mp.erase(key),key为需要删除的元素的迭代器,时间复杂度O(logN)
    • 删除一个区间内所有元素mp.erase(first,last),first和last均为元素对应的迭代器,这个函数删除[first,last)区间内内的元素

      注意:对于迭代器.end()操作,返回的不是最后一个迭代器而是其后面一位。
      换言之,从map.begin()map.end()的左闭右开区间其实是整个map而非除去最后一位的map.

  • size() 获取map中映射对的个数

  • clear() 清空整个map

map的使用场景

  • 需要建立字符串与整数之间映射时可以用map减少代码量
  • 判断大整数或者其他特殊类型数据是否存在,可以把map当作bool数组
  • 字符串和字符串的映射

queue (需#include<queue>

queue的定义

queue为队列,先进先出,定义形式为queue<typename> name;

queue容器内元素的访问

通过front()访问队首元素,通过back()访问队尾元素.

注意:使用front()和back()函数前,必须先用empty()判断队列是否为空,否则可能因为队列为空而产生错误.

queue常用函数实例

  • push() 实现新元素x的入队
  • pop() 实现队首元素x的出队
  • empty() 返回值为布尔类型,若队列为空则返回true,否则为false
  • size() 返回queue中元素的个数

queue的使用场景

  • 广度优先搜索的实现中使用queue

priority_queue (需#include<queue>

priority_queue是优先级队列的意思,简单理解就是队列带有了优先级的区分,和平常我们看到的队列queue的区别在于,平时的队列元素没有优先之分,先进来的数据先出去,其底层是用堆来实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。在优先队列中,没有 front() 函数与 back() 函数,而只能通过 top() 函数来访问队首元素(也可称为堆顶元素),也就是优先级最高的元素。通常情况下,在一些实际的场景中,队列往往有优先级之分,例如这在计算机网络中是非常常见的,举个例子,当一个非常重要的数据进入队列之后,需要快速发出去,就需要让其他数据等待,重要的数据先发出去,这就要求该数据有高于其他数据的优先级标识。而优先级队列也正是这样的原理。

priority_queue的定义

1
priority_queue<typename> name;

priority_queue内元素访问

只能用top()函数访问队首元素(优先级最高的元素)

常用函数

  • push() 令元素x入队
  • pop() 令队首元素x出队
  • empty() 返回值为布尔类型,若队列为空则返回true,否则为false
  • size() 返回queue中元素的个数

priority_queue内元素优先级设置

基本元素优先级设置

此处指的基本数据类型就是 int 型,double 型,char 型等可以直接使用的数据类型,优先队列对他们的优先级设置一般是数字大的优先级高,因此队首元素就是优先队列内元素最大的那个(如果是 char 型,则是字典序最大的)。

1
2
3
//下面两种优先队列的定义是等价的
priority_queue<int> q;
priority_queue<int,vector<int>,less<int> >;//后面有一个空格

其中第二个参数( vector ),是来承载底层数据结构堆的容器,第三个参数( less ),则是一个比较类,less 表示数字大的优先级高,而 greater 表示数字小的优先级高

如果想让优先队列总是把最小的元素放在队首,只需进行如下的定义:

1
priority_queue<int,vector<int>,greater<int> >q;

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void test1(){
//默认情况下,数值大的在队首位置(降序)
priority_queue<int> q;
for(int i = 0;i <= 10;i ++)
q.push(i);
while(!q.empty()){
cout<<q.top()<<" ";
q.pop();
}
cout<<endl;
//greater<int>表示数值小的优先级越大
priority_queue<int,vector<int>,greater<int> > Q;
for(int i = 0;i <= 10;i ++)
Q.push(i);
while(!Q.empty()){
cout<<Q.top()<<" ";
Q.pop();
}
}

结构体的优先级设置

方式一:重载运算符 ‘<’

可以在结构体内部重载 ‘<’,改变小于号的功能(例如把他重载为大于号)

1
2
3
4
5
6
7
8
struct student{
int grade;
string name;
//重载运算符,grade 值高的优先级大
friend operator < (student s1,student s2){
return s1.grade < s2.grade;
}
};

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void test2(){
priority_queue<student> q;
student s1,s2,s3;
s1.grade = 90;
s1.name = "Tom";
s2.grade = 80;
s2.name = "Jerry";
s3.grade = 100;
s3.name = "Kevin";
q.push(s1);
q.push(s2);
q.push(s3);
while(!q.empty()){
cout<<q.top().name<<":"<<q.top().grade<<endl;
q.pop();
}
}
/*
结果:
Kevin:100
Tom:90
Jerry:80
*/
方式二:把重载的函数写在结构体外面

将比较函数写在结构体外面,作为参数传给优先队列。

1
2
3
4
5
6
7
8
9
10
struct fruit{
string name;
int price;
};
struct cmp{
// "<" 表示 price 大的优先级高
bool operator() (fruit f1,fruit f2){
return f1.price < f2.price;
}
};

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void test3(){
priority_queue<fruit,vector<fruit>,cmp> q;
fruit f1,f2,f3;
f1.name = "apple";
f1.price = 5;
f2.name = "banana";
f2.price = 6;
f3.name = "pear";
f3.price = 7;
q.push(f1);
q.push(f2);
q.push(f3);
while(!q.empty()){
cout<<q.top().name<<":"<<q.top().price<<endl;
q.pop();
}
}
/*
结果:
pear:7
banana:6
apple:5
*/