map 与 set 简单用法

map 与 set 简单用法

map  |  set

（用于查找时用set）

一：map

map中元素的插入

在map中元素有两种插入方法：

• 使用下标
• 使用insert函数

在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素。

insert函数的插入方法主要有如下：

• m.insert(e)
• m.insert(beg, end)
• m.insert(iter, e)

上述的e一个value_type类型的值。beg和end标记的是迭代器的开始和结束。

#include <stdio.h>
#include <map>
using namespace std;

int main(){
        map<int, int> mp;
        for (int i = 0; i < 10; i ++){
                mp[i] = i;
        }
        for (int i = 10; i < 20; i++){
                mp.insert(make_pair(i, i));
        }
        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d-->%d\n", it->first, it->second);
        }
        return 0;
}

map中元素的查找和读取

注意：上述采用下标的方法读取map中元素时，若map中不存在该元素，则会在map中插入。

因此，若只是查找该元素是否存在，可以使用函数count(k)，该函数返回的是k出现的次数；若是想取得key对应的值，可以使用函数find(k)，该函数返回的是指向该元素的迭代器。

上述的两个函数的使用如下所示：

#include <stdio.h>
#include <map>
using namespace std;

int main(){
        map<int, int> mp;
        for (int i = 0; i < 20; i++){
                mp.insert(make_pair(i, i));
        }

        if (mp.count(0)){
                printf("yes!\n");
        }else{
                printf("no!\n");
        }

        map<int, int>::iterator it_find;
        it_find = mp.find(0);
        if (it_find != mp.end()){
                it_find->second = 20;
        }else{
                printf("no!\n");
        }

        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d->%d\n", it->first, it->second);
        }
        return 0;
}

从map中删除元素

从map中删除元素的函数是erase()，该函数有如下的三种形式：

• m.erase(k)
• m.erase(p)
• m.erase(b, e)

第一种方法删除的是m中键为k的元素，返回的是删除的元素的个数；第二种方法删除的是迭代器p指向的元素，返回的是void；第三种方法删除的是迭代器b和迭代器e范围内的元素，返回void。

#include <stdio.h>
#include <map>
using namespace std;

int main(){
        map<int, int> mp;
        for (int i = 0; i < 20; i++){
                mp.insert(make_pair(i, i));
        }

        mp.erase(0);

        mp.erase(mp.begin());

        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d->%d\n", it->first, it->second);
        }


        return 0;
}

二：set

set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索，不可直接去修改键值。

常用操作：
1.元素插入：insert()

2.中序遍历：类似vector遍历（用迭代器）

3.反向遍历：利用反向迭代器reverse_iterator。
    例：
    set<int> s;
    ......
    set<int>::reverse_iterator rit;
    for(rit=s.rbegin();   rit!=s.rend();   rit++)

4.元素删除：与插入一样，可以高效的删除，并自动调整使红黑树平衡。
            set<int> s;
            s.erase(2);        //删除键值为2的元素
            s.clear();

5.元素检索：find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。
            set<int> s;
            set<int>::iterator it;
            it=s.find(5);    //查找键值为5的元素
            if(it!=s.end())    //找到
                cout<<*it<<endl;
            else            //未找到
                cout<<"未找到";

6.自定义比较函数
    (1)元素不是结构体：
        例：
        //自定义比较函数myComp,重载“（）”操作符
        struct myComp
        {
            bool operator()(const your_type &a,const your_type &b)
            [
                return a.data-b.data>0;
            }
        }
        set<int,myComp>s;
        ......
        set<int,myComp>::iterator it;
    (2)如果元素是结构体，可以直接将比较函数写在结构体内。
        例：
        struct Info
        {
            string name;
            float score;
            //重载“<”操作符，自定义排序规则
            bool operator < (const Info &a) const
            {
                //按score从大到小排列
                return a.score<score;
            }
        }
        set<Info> s;
        ......
        set<Info>::iterator it;