map

_id: “d5a7558560” title: map date: 2019-11-20 22:31 update: 2019-11-20 22:31 author: Rainboy

map/multimap

• map通常理解成关联数组
• 使用平衡二叉树(红黑树)管理元素
• 元素组成(key,value)
• #include <map>
• 根据元素的key自动对元素排序,根据key时行定位很快,根据value很慢
• 不能直接改变key,可以使用 [] 存取元素
• map中key不能相同,multimap中key可以相同

**注意:**map

操作

基本类型

创建map

基本操作

赋值

特殊操作

迭代器相关

插入

删除

map对象的定义

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main(){
    map<string,int> m;
    m["Tom"] = 16;
    map<string,int> m1(m);
    int i;
    vector<pair<string,int> > vec;
    for(i=0;i<10;i++){
        string s;
        s[0] = i;
        vec.push_back(make_pair(s,i));
    }

    map<string,int> m2(vec.begin(),vec.end());

    return 0;
}

键类型约束

使用关联容器的时候,它的键不仅要有一个类型,且这种类型比较函数,默认的情况下,标准库使用<做来实现键的比较.

键类型必须定义<操作符

map容器的迭代器的解引用

• 学会解引用map迭代器
• 知道不能修改key的值
• 学会使用typedef

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main(){
    map<string,int> m;
    m["Tom"] = 16;
    cout << "m[\"Tom\"]:" << m["Tom"] << endl;

    typedef map<string,int> mt;
    mt::iterator map_it = m.begin();
    // 相当于 map<string,int>::iterator map_it = m.begin();

    cout << "map_it->first:" << map_it->first << endl;
    cout << "map_it->second:" << map_it->second << endl;

    //改变值
    //map_it->first = "new key"; //error ,key is const
                                 // 不能改变下标的值
    ++(map_it->second); //ok
    cout << "map_it->second:" << map_it->second << endl;
    return 0;
}

给map添加元素:下标法

我们可以使用两种方法给map容器添加元素:(1.):使用map的insert成员函数.**(2.)**使用下标操作符.但注意:一个键只能对应一个元素

样列

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main(){
    map<string,int> m;
    m["Tom"] = 16;      // 添加元素1
    cout << "m[\"Tom\"]:" << m["Tom"] << endl;

    return 0;
}

下标添加元素的过程:

• 在m中查找键为Tom的元素,没有找到
• 将一个新的键-值对插入到m中,
  • 它的键是const string类型
  • 它的值使用值(0)初始化
• 读取新插入的元素,将它的值赋为16

统计单词个数

使用下标添加元素,可以使程序非常简洁

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
    map<string,int> word_count;
    string word;
    while(cin >> word)
        ++word_count[word];
    return 0;
}

程序含义:如果word在word_cout中不存在,那么就在map中添加这个元素,同时它的值初始化为1(int型默认),然后立刻+1

给map添加元素:insert

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main(){
    map<string,int> m;
    m.insert(map<string,int>::value_type("Tome",16));

    //相当于
    m.insert(pair<string,int>("Tom2",16));

    //简化一点
    m.insert(make_pair("Jerry",16));

    //使用typedef

    typedef map<string,int>::value_type valType;
    m.insert(valType("penpen",16));
    return 0;
}

insert 的返回值

map中一个给定的键只对应一个元素,

如果要插入的元素的键值已经在容器中,则insert不做任何操作.

带有键-值pair形参的insert版本将返回一个值:包含一个迭代器(指向map中的相应元素)和一个bool值(是否插入该元素)的pair对象.

例子:

#include <iostream>
#include <map>
using namespace std;

int main(){
    map<string,int> word_count;

    //先插入一个
    word_count.insert(make_pair("Tom",16));

    //重复插入一个键已经存在的元素
    pair<map<string,int>::iterator,bool> ret = word_count.insert(make_pair("Tom",17));
    cout << "ret.second:" << ret.second << endl; // false 表示没有插入进去

    //迭代器指向map容器中的元素
    cout << "ret.first->first:" << (ret.first->first)  << endl; // false 表示没有插入进去
    cout << "ret.first->second:" << (ret.first->second)  << endl; // false 表示没有插入进去

    cout << endl;
    //插入一个键不存在的元素
    pair<map<string,int>::iterator,bool> ret1 = word_count.insert(make_pair("Jerry",17));
    cout << "ret1.second:" << ret1.second << endl; // true 表示插入进去

    //迭代器指向map容器中的元素
    cout << "ret1.first->first:" << (ret1.first->first)  << endl; // false 表示没有插入进去
    cout << "ret1.first->second:" << (ret1.first->second)  << endl; // false 表示没有插入进去
    return 0;
}

改进后的word_count程序:

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    map<string,int> word_count;
    string word;

    while(cin >> word){
        pair<map<string,int>::iterator,bool> ret =
            word_count.insert(make_pair(word,1));
        if(!ret.second) //已经存在
            ++ret.first->second;
    }
    return 0;
}

查找并读取map中的元素

我们可以使用下标操作来取值.

int occ = word_count["foobar"]

但是这里有一个很大副作用:如果这个键不在map中,就会插入一个新的元素.

我们可以使用map.count,map.find来查检某个健是不是存在.

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    map<string,int> word_count;
    word_count.insert(make_pair("Tom",16));
    word_count["Jerry"] = 17;

    //返回数量
    cout << "word_count.count(\"Tom\"): " << word_count.count("Tom") <<endl;
    //返回迭代器
    cout << "word_count.find(\"Jerry\"): " << word_count.find("Jerry")->second <<endl;
    return 0;
}

删除map的元素

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    map<string,int> word_count;
    word_count.insert(make_pair("Tom",16));
    word_count["Jerry"] = 17;

    //使用键来删除
    cout << "word_count.erase(\"Tom\"): " << endl;
    word_count.erase("Tom");
    cout << "word_count.count(\"Tom\"): " << word_count.count("Tom") <<endl;

    //使用迭代器来删除
    map<string,int>::iterator ite =  word_count.find("Jerry");
    cout << "word_count.erase(ite): " << endl;
    word_count.erase(ite);
    cout << "word_count.count(\"Jerry\"): " << word_count.count("Jerry") <<endl;
    //没有找到,迭代器 为 end
    cout << "word_count.find(\"Jerry\"): " << (word_count.find("Jerry") == word_count.end() )<<endl;
    return 0;
}

map中元素遍历

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    map<string,int> word_count;
    word_count.insert(make_pair("Tom",16));
    word_count["Jerry"] = 17;

    //遍历
    map<string,int>::iterator ite = word_count.begin();
    for(;ite != word_count.end();ite++){
        cout << "first: " << ite ->first << endl;
        cout << "second: " << ite ->second << endl;
        cout << endl;
    }
    return 0;
}