查找1----系统库中的map和set

一：set的使用

问题：给出两个数组，求共同元素，而且要求元素不重复

很明显应该使用集合容器set

#include<iostream>
#include<vector>
#include<set>
using namespace std;

class soluction{
public:
    vector<int> insection(vector<int>& num1,vector<int>& num2){
        //利用set容器记录num1非重复元素
        set<int> record;
        for(int i=0;i<num1.size();i++) record.insert(num1[i]);
        //遍历num2,判断record中是否存在该元素，并把结果记录到result
        set<int> result;
        for(int i=0;i<num2.size();i++)
           if(record.find(num2[i])!=record.end())
              result.insert(num2[i]);
        //将set类型转换成vector<int>
        vector<int> resVector;
        for(set<int>::iterator iter=result.begin();iter!=result.end();iter++)
           resVector.push_back(*iter);
        return resVector;
    }
};

set容器中：

添加函数：insert()

查找函数：find()

find找到该元素的语句：

set对象名.find(元素）！=set对象名.end()--------指针查找

int main(){
    vector<int> n1={1,2,3,3,4,4,5,5,5,6,88,9};
    vector<int> n2={2,4,4,4,6,7,8,9};
    vector<int> n=soluction().insection(n1,n2);
    for(int i=0;i<n.size();i++){
        cout<<n[i]<<" ";
    }
    cout<<endl;
    for(vector<int>::iterator it=n.begin();it!=n.end();it++){
        cout<<(*it)<<" ";
    }
    return 0;
}

 测试函数功能的主函数

注意迭代器的使用：

类型::iterator 迭代器指针名=名称.begin();迭代器指针名!=名称.end();迭代器指针名++

注意迭代器指向的元素本身---（*迭代器指针名）

vector<int> insection(vector<int>& num1,vector<int>& num2){
        //利用set容器记录num1非重复元素
        set<int> record(num1.begin(),num1.end());
        //遍历num2,判断record中是否存在该元素，并把结果记录到result
        set<int> result;
        for(int i=0;i<num2.size();i++)
           if(record.find(num2[i])!=record.end())
              result.insert(num2[i]);
        //将set类型转换成vector<int>
        return vector<int>(result.begin(),result.end());
    }

 简化：直接定义变量后就传入首位指针。

set<int> record(num1.begin(),num1.end());

vector<int>(result.begin(),result.end());

二：map用法

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
    map<int,string> person;
    person.insert(pair<int,string>(1,"jim"));
    person.insert(map<int,string>::value_type(5,"Tom"));
    person[7]="ketty";
    person.erase(7);
    map<int,string>::reverse_iterator iter;
    for(iter=person.rbegin();iter!=person.rend();iter++){
        cout<<"("<<iter->first<<","<<iter->second<<")"<<" ";
    }
    cout<<endl;
}

 map存在默认值0，访问就建立了映射

#include<iostream>
#include<map>
using namespace std;
int main(){
    map<int,int> myMap;
    //初始化没添加元素，42不在元素
    if(myMap.find(42)!=myMap.end())
        cout<<"element 42 in the map"<<endl;
    else
        cout<<"can't find element 42"<<endl;
    //map有初值0
    cout<<myMap[42]<<endl;
    //访问后，就建立了映射
    if(myMap.find(42)!=myMap.end())
        cout<<"element 42 in the map"<<endl;
    else
        cout<<"can't find element 42"<<endl;
    return 0;
}

 注意：map只要访问了该元素，就会建立起映射

三：求出两个数组所有相同元素，重复的要多次写出 

#include<iostream>
#include<vector>
#include<map>//map数据结构：K-V对
using namespace std;
//求出两个数组的所有共同元素，重复元素也要多次出现
class soluction{
public:
     vector<int> insection(vector<int>& num1,vector<int>& num2){
         map<int,int> record;
         for(int i=0;i<num1.size();i++)//遍历分找到找不到两种
             if(record.find(num1[i])==record.end()){
                //找不到要插入----元素是k,频次是v
                record.insert(pair<int,int>(num1[i],1));
             }
             else{
                record[num1[i]]+=1;//频次++
             }
         vector<int> result;
         for(int i=0;i<num2.size();i++)
         //出现删除操作，删除后将频次为0的k-v对删除
            if(record.find(num2[i])!=record.end()&&record[num2[i]]>0){
                result.push_back(num2[i]);
                record[num2[i]]--;
                if(record[num2[i]]==0){
                    record.erase(num2[i]);
                }
            }
         return result;
     }
};
int main(){
    vector<int> n1={1,2,2,3,4,4,5,5,5,6,7};
    vector<int> n2={1,2,2,3,3,4,4,4,5,5,6,7,7};
    vector<int> n3=soluction().insection(n1,n2);
    for(int i=0;i<n3.size();i++){
        cout<<n3[i]<<" ";
    }
}

#include<iostream>
#include<vector>
#include<map>
using namespace std;
class soluction{
public:
     vector<int> interSection(vector<int>& n1,vector<int>& n2){
        /*利用map记录n1：数组值作为k,出现频次作为v*/
        map<int,int> record;
        for(int i=0;i<n1.size();i++){
            if(record.find(n1[i])==record.end()){//没找到
                  record.insert(pair<int,int>(n1[i],1));
            }
            else{
                record[n1[i]]+=1;//对应频次加一
            }
        }
        /*遍历n2,将结果存储在vecord<int>中*/
        vector<int> result;
        for(int i=0;i<n2.size();i++){
            if(record.find(n2[i])!=record.end()&&record[n2[i]]>0){
              //n2[i]的k存在于record中，而且频次大于0
              result.push_back(n2[i]);
              record[n2[i]]--;
              if(record[n2[i]]==0){
                record.erase(n2[i]);
              }
            }
        }
        //别忘了return
        return result;
     }
};
int main(){
    vector<int> a={1,2,3,3,4,4,4,5,6,6,7,8};
    vector<int> b={1,1,2,3,3,3,4,5,5,6,6,7,7};
    vector<int> c=soluction().interSection(a,b);
    //输出结果
    vector<int>::iterator iter;
    for(iter=c.begin();iter!=c.end();iter++){
        cout<<(*iter)<<" ";
    }
    cout<<endl;
    return 0;
}

set和map在c++中有两种实现形式----平衡二叉树和哈希表 

区别在于：

• 哈希表查找很快，只需要O（1）的时间复杂度，但是数据失去了顺序性
• 平衡二叉树的好处在于可以求一个元素的前驱和后继，求出它的元素排序等等。

使用哈希表实现的map和set，头文件：<unordered_set>,<inordered_map>

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class soluction{
public:
     vector<int> interSection(vector<int>& n1,vector<int>& n2){
        /*利用map记录n1：数组值作为k,出现频次作为v*/
        unordered_map<int,int> record;
        for(int i=0;i<n1.size();i++){
                record[n1[i]]+=1;//对应频次加一
        }
        /*遍历n2,将结果存储在vecord<int>中*/
        vector<int> result;
        for(int i=0;i<n2.size();i++){
            if(record[n2[i]]>0){
              result.push_back(n2[i]);
              record[n2[i]]--;
            }
        }
        //别忘了return
        return result;
     }
};