C++中set/multiset与map/multimap的使用详解

2023-02-14 12:02:15 set multiset 详解

一、关联式容器

vector、list、deque、forward_list(c++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。

而关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。 (插入删除只需挪动指针指向,无需挪动数据,查找时间logN)

关联式容器有两种,一种是map、set、multimap、multiset采用树形结构,他们的底层都是红黑树,另一种是哈希结构。

二、set的介绍

1、set是关联式容器,它表面上只存放value,实际底层中存放的是由<value,value>组成的键值对。

2、set调用find将采用中序遍历,可以用于排序+去重。

3、为了保证元素的唯一性,set中的元素均为const,所以并不能对元素进行修改,但可以进行插入删除。

1、接口count与容器multiset

count和find的作用一样,都是用于查找set中是否存在某个元素。

其实count是为了容器multiset设计的,该容器允许插入重复的元素,此时count会返回红黑树中被搜索元素的个数。

#include <iOStream>
#include <set>
 
int main ()
{
  std::set<int> myset;
 
  // set some initial values:
  for (int i=1; i<5; ++i) myset.insert(i*3);    // set: 3 6 9 12
 
  for (int i=0; i<10; ++i)
  {
    std::cout << i;
    if (myset.count(i)!=0)
      std::cout << " is an element of myset.\n";
    else
      std::cout << " is not an element of myset.\n";
  }
 
  return 0;
}

2、接口lower_bound和upper_bound

lower_bound返回大于等于目标值的迭代器,upper_bound返回大于目标值的迭代器,在set中用于返回目标值的迭代器。(比如找到两个边界的迭代器,就可以使用erase对数据进行删除)

#include <iostream>
#include <map>
 
int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator itlow,itup;
 
  mymap['a']=20;
  mymap['b']=40;
  mymap['c']=60;
  mymap['d']=80;
  mymap['e']=100;
 
  itlow=mymap.lower_bound ('b');  // itlow points to b
  itup=mymap.upper_bound ('d');   // itup points to e (not d!)
 
  mymap.erase(itlow,itup);        // a => 20  e => 100
 
  // print content:
  for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';
 
  return 0;
}

三、map的介绍

map是关联式容器,根据特定的存储顺序,用于存储由键值及其映射值组合的元素。

可以看到Alloc中有一个键值对pair,这个pair是一个key/value结构的struct模板类。这个类将一对键值耦合在一起,所以,map的存储方式是通过在搜索二叉树中存储键值对pair,而搜索二叉树的k/v模型是在节点中存储key和value,并不相同。pair的结构:

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair(): first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b): first(a), second(b)
	{}
};

1、接口insert

make_pair是一个函数模板:

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
	return ( pair<T1,T2>(x,y) );
}

2、接口insert和operator[]和at

使用map统计每个字符出现个数

写法2的[]详解:

Value& operator[] (const Key& k)
{
	pair<iterator,bool> ret=insert(make_pair(k,Value() ) );
	//在结构体pair中找到first(一个map的迭代器),->解引用找到该迭代器的pair,再找该pair的second(即value)
	return ret.first->second;
}
//map的insert
pair<iterator,bool> insert (const value_type& pair);
//插入
dict["迭代器"];//在dict中找不到"迭代器"这个key,将新增一个节点,该节点的key为"迭代器",value为value类型的默认构造
//修改
dict["迭代器"]="iterator";//将key为"迭代器"的节点的value修改为"iterator"

不难看出map的operator[]兼具查找、插入、修改三种功能。(注意如果搜寻值不在map中,map可是会帮你新增一个节点的,map底层的红黑树将发生改变)

使用operator[],编译器会去调用insert(pair<const key,value()>)进行插入,如果没有找到key所对应的节点,则会新增一个节点并将该节点中pair的value置为value类型的默认构造;如果找到了,则返回该节点pair中value的引用。(可读可写)

at的功能和[]一样,区别在于用at找不到key将不会发生插入新节点,而是抛出异常。

3、容器multimap

multimap多个键值对中的key可以重复,所以并没有operator[]。同样的,使用find将返回中序遍历找到的第一个key值所处节点的迭代器。

四、map和set相关OJ

1、前K个高频单词

struct Compare
{
    bool operator()(const pair<int,string>& a,const pair<int,string>& b)
    {
        return a.first>b.first || (a.first==b.first&&a.second<b.second);
    }
};
class Solution {
public:
    vector<string> topKFrequent(vector<string>& Words, int k) {
        vector<string> ret;
        map<string,int> dataMap;
        for(const auto& str : words)
        {
            dataMap[str]++;
        }
        vector<pair<int,string>> v;
        for(auto& kv : dataMap)
        {
            v.push_back(make_pair(kv.second,kv.first));//dataMap的first是string,second是int
        }
        sort(v.begin(),v.end(),Compare());
        for(int i=0;i<k;++i)
        {
            ret.push_back(v[i].second);
        }
        return ret;
    }
};

2、两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(),nums1.end());//nums1排序+去重    
        set<int> s2(nums2.begin(),nums2.end());//nums2排序+去重
        vector<int> ret;
        for(auto& e : s1)
        {
            if(s2.find(e)!=s2.end())
            {
                ret.push_back(e);
            }
        }
        return ret;
    }
};

或者将两个数组排序+去重完毕后,使用双指针求解。(可用于找交集,差集)

以上就是C++中set/multiset与map/multimap的使用详解的详细内容,更多关于C++ set/multiset map/multimap的资料请关注其它相关文章!

相关文章