STL

STL之map

Posted by Liao on 2019-08-16

一 定义

C++中map提供的是一种键值对容器，里面的数据都是成对出现的。每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。

map的底层实现时红黑树，查询的时间复杂度时log(n)

1
map<type,type> mymap;

二 声明

1
#include<map>

三 插入操作

1.通过inset插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<map>
map<int,string> mymap;
    mymap.insert(pair<int,string>(2019,"hello world"));
    map<int,string>::iterator it;
    for(it=mymap.begin();it!=mymap.end();it++)
    {
        cout << it->first << " ";
        cout << it->second ;
    }
    cout <<endl;

//输出
//2019 hello world

2.数组插入

1
2
3
4
5
6
7
8
 map<string,int> mymap;
    mymap["hello"] = 2019;
    cout << mymap.begin()->first << " " <<  mymap.begin()->second;
    return 0;

//输出 
// hello 2019

3.列表插入

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    map<string,int> mymap;
    mymap.insert({"hello",2020},{"world",2021});
    map<string,int>::iterator it;
    for(it = mymap.begin();it!=mymap.end();it++)
    {
        cout << it->first <<  " " <<it->second;
        cout <<endl;
    }

    return 0;
}

4.指定位置插入（类型为char会按照ascii从小到大排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    map<char,int>mymap;
    mymap.insert(pair<char,int>('a',100));
    mymap.insert(pair<char,int>('b',200));
    map<char, int>::iterator it = mymap.begin() ;

    mymap.insert(it,pair<char,int>('c',105));

    auto iter = mymap.begin();
    while(iter!=mymap.end())
    {
        cout << iter->first << " " << iter->second ;
        iter++;
    }

    return 0;
}
//输出：a 100b 200c 105


四 取值

1
2
3
4
5
6
7
8
9
int main()
{
    map<char,int>mymap;
    mymap.insert(pair<char,int>('a',100));
    map<char,int>::iterator iter;
    iter = mymap.begin();  //得从map起始位置开始遍历
    cout << iter->first << " " << iter->second ;
    return 0;
}

五 容量查询

1.查询map是否为空
mymap.empty();

2.查询map中键值对的数量
mymap.size();

3.查询map所能包含的最大键值对数量，和系统和应用库有关。此外，这并不意味着用户一定可以存这么多，很可能还没达到就已经开辟内存失败了
mymap.max_size();

5.查询关键字为key的元素的个数，在map里结果非0即1

mymap.count( const Key& key ) const

mymap.clear() //清空map

六 查找

1
2
3
4
5
// 关键字查询，找到则返回指向该关键字的迭代器，否则返回指向end的迭代器
// 根据map的类型，返回的迭代器为 iterator 或者 const_iterator
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

七 利用返回值检验map的key是否相同

​ 内容不同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    map<string,int> mymap;
    mymap.insert(pair<string,int>("hello world",2020));

    pair<map<string,int>::iterator, bool> ret;   //ret用于检验map的key是否存在
    ret = mymap.insert(pair<string,int>("hello",2020));  //key不相同
    if(ret.second == false)   //ret.second 指的是bool
    {
        cout <<"already exists" <<endl;
    }
    else
    {
        cout << ret.first->first << " ";
        cout << ret.first->second;
    }
    return 0;
}

//输出
//hello 2020

​ 内容相同： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int main()
{
    map<string,int> mymap;
    mymap.insert(pair<string,int>("hello",2020));

    pair<map<string,int>::iterator, bool> ret;   //ret用于检验map的key是否存在
    ret = mymap.insert(pair<string,int>("hello",2020));  //key不相同
    if(ret.second == false)   //ret.second 指的是bool
    {
        cout <<"already exists" <<endl;
    }
    else
    {
        cout << ret.first->first << " ";
        cout << ret.first->second;
    }
    return 0;
}
//输出
//already exists

八 删除元素

1.通过key值删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    map<string,int>mymap;
    mymap.insert(pair<string,int>("hello world",10));
    mymap.insert(pair<string,int>("good morning",100));

    map<string, int>::iterator it;

  // string name{"good morning"};
    mymap.erase("good morning");
        for(it = mymap.begin();it!=mymap.end();it++)
        {
            cout << it->first <<endl;
        }
    return 0;
}
//输出结果： hello world

2.删除指定位置的元素 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    map<string,int>mymap;
    mymap.insert(pair<string,int>("hello world",10));
    mymap.insert(pair<string,int>("good morning",100));
    map<string, int>::iterator it;
    mymap.erase(mymap.find("good morning"));
     for(it = mymap.begin();it!=mymap.end();it++)
     {
         cout << it->first <<endl;
     }
    return 0;
}
//输出 hello world

九 交换

1
2
// 两个map的内容互换
   void swap( map& other );

十 题目

HDU2648

看到输入样例有数字 => 字符串的格式

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<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
    int n,m,p[10000];
    string s;
    map<string,int> shop;
    while(cin >> n)
    {
        for(int i=0;i<n;i++)
        {
            cin >> s;
            shop[s] = 0;   //每个商店初始化  s为键 0为值
        }
        int days;
        cin >> days;
        while(days--)
        {
            int ranks = 1;

            for(int i=1;i<=n;i++)
            {
                cin >> m >> s;
                shop[s] += m;  
                /*
                第一次：shop[memory] = 49  p[1] = 49
               			shop[kfc] = 49     p[2] = 49
                        shop[wind] = 48    p[3] = 48
                第二次：shop[memory] = 80  p[0] = 80
               			shop[kfc] = 85     p[1] = 85
                        shop[wind] = 83    p[2] = 83                   
                */
                  				
                p[i] = shop[s];
            }

            for(int i=1;i<=n;i++)
            {
                if(p[i]>shop["memory"])
                    ranks++;
            }
            cout << ranks <<endl;
        }
    }
    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
#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <cstring>
using namespace std;

int romanToInt(string s) {
    map<char,int> roman_map{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int pre = roman_map[s[0]];
    int ans = 0;
    for(int i=1;i<s.length(); )
    {
        int cur = roman_map[s[i]];  //记录目前的位置
        if(pre >= cur) //正常情况 前>后
        {
            ans = ans + pre;
            pre = cur; //不断向前
            i++;
        }
        else //特殊情况 IV 4，IX 9，XL 40, XC 90, CD 400, CM 900
        {
            ans = ans + cur - pre;
            pre = roman_map[s[i+1]];
            i = i+2;
        }
    }
    ans = ans + pre;
    return ans;

}
int main()
{
    string s;
    cin >> s;
    int c = romanToInt(s);
    cout << c <<endl;

    return 0;
}
FEATURED TAGS
STL
FRIENDS