【C++】set/multiset/map/multimap
2023-09-27 14:20:37 时间
一、set/multiset (集合)
1 set概念(自动排序、底层红黑树)
- 所有元素都会在插入时自动被排序(关联式容器)
- set/multiset属于关联式容器,底层结构是用红黑树实现。
set和multiset区别:
- set不允许容器中有重复的元素(插入重复元素进行忽略处理)
- multiset允许容器中有重复的元素
set<int> s;//创建一个int型的set集合
s.insert(1); // 返回插入的位置和插入成功与否(返回pair类型)
s.insert(8);
s.insert(3);
s.insert(1);//因为前面插入了1,所以这行代码会被忽略
2 set构造和赋值(默认、拷贝、=赋值)
//构造:
set<int> s1; //默认构造函数:
set<int> s2(s1); //拷贝构造函数
//赋值:
s3 = s2; //重载等号操作符
总结:
set
容器插入数据时用s1.insert();
#include <set>
void printSet(set<int> & s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//set容器构造和赋值
void test01()
{
set<int> s1;
s1.insert(10);
s1.insert(30);
s1.insert(30);
s1.insert(20);
s1.insert(40);
//set容器特点 ,所有元素插入自动排序
//set不允许插入重复的值
printSet(s1);
//拷贝构造
set<int>s2(s1);
printSet(s2);
//赋值
set<int>s3;
s3 = s2;
printSet(s3);
}
int main()
{
test01();
system("pause");
return 0;
}
3 set大小和交换(size、empty、swap)
- 不允许重新指定大小。
s1.size() //返回容器中元素的数目
s1.empty() //判断容器是否为空
s1.swap(s2); //交换两个集合容器size
//s1.resize(); //不能指定大小
4 set插入和删除(s.insert()、erase、clear)
s1.insert(10); //在容器中插入元素,返回 pair 类型
s1.erase(s1.begin()); //删除pos迭代器所指的元素,返回下一个元素的迭代器。
s1.erase(s1.begin(), s1.end()); //删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。
s1.erase(30); //删除容器中值为30的元素。
s1.clear(); //清除所有元素
5 set查找和统计(find、count)
//查找30是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
pos = s1.find(30);
//统计30的元素个数,对于set而言 统计结果 要么是0 要么是1
int num = s1.count(30); //set不允许容器中有重复的元素
6 set和multiset区别
- set不可以插入重复数据,而multiset不会检测数据,因此可以插入重复数据
pair<set<int>::iterator, bool> ret = s.insert(10); //返回插入成功与否
//set插入数据的同时会返回插入结果bool值,表示插入是否成功
//若有重复元素表示插入不成功
pair<set<int>::iterator, bool> ret = s.insert(10); //set会检测数据,返回键值对(1.插入位置,2.成功与否)
ret.first();
ret.second();
//set和multiset区别
void test01()
{
set<int> s;
pair<set<int>::iterator, bool> ret = s.insert(10);
if (ret.second) {
cout << "第一次插入成功!" << endl;
}
else {
cout << "第一次插入失败!" << endl;
}
ret = s.insert(10);
if (ret.second) {
cout << "第二次插入成功!" << endl;
}
else {
cout << "第二次插入失败!" << endl;
}
//multiset
//允许插入重复值
multiset<int> ms;
ms.insert(10);
ms.insert(10);
for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main() {
test01();
system("pause");
return 0;
}
7 pair对组创建
//pair初始化
pair<string, int> p("Tom", 20);
pair<string, int> p2;
p2 = make_pair("Jerry", 30);
p.first = "xue";
p.second = 25;
p.swap(p2); //交换两个对组
7.1 用pair<int,int>建立优先队列(小根堆)
- 比较对象是pair的第一个元素
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
- 取元素
1.pq.top().first;
2.pq.top().second;
8 set排序 (默认从小到大,利用仿函数改变排序规则)
set<int> s1; //默认排序从小到大 (开头是小)
//等价set<int, less<int> >
set<int, greater<int> > //排序从大到小(开头是大)
set<int, MyCompare> s2; //利用仿函数MyCompare,可以改变排序规则
//对于自定义数据类型Person,set必须指定排序规则comparePerson才可以插入数据
set<Person, comparePerson> s;
class Person
{
public:
Person(string name, int age)
{
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
class comparePerson
{
public:
bool operator()(const Person& p1, const Person &p2)
{
//按照年龄进行排序 降序
return p1.m_Age > p2.m_Age;
}
};
void test01()
{
set<Person, comparePerson> s;
Person p1("刘备", 23);
Person p2("关羽", 27);
Person p3("张飞", 25);
Person p4("赵云", 21);
s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);
for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
{
cout << "姓名: " << it->m_Name << " 年龄: " << it->m_Age << endl;
}
}
int main() {
test01();
system("pause");
return 0;
}
二、map/ multimap(映射表)
//哈希解法
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> hash_map; //哈希表
for(int i=0; i<nums.size(); i++){
hash_map[nums[i]]++; //实值累加,默认实值为0
}
//for(unordered_map<int,int>::iterator it=m.begin();it!=m.end();it++)
for(auto it : hash_map) //it不是迭代器
{
if(it.second == 1)
return it.first;
}
return 0;
}
};
1 map概念(根据元素键值自动排序)
- pair中第一个元素为key(键值),起到索引作用,第二个元素为value(实值)
- 所有元素都会根据元素的键值自动排序
本质:
- map/multimap属于关联式容器,底层结构是用红黑树实现。
map和multimap区别:
- map不允许容器中有重复key值元素
- multimap允许容器中有重复key值元素
2 map构造和赋值(默认、拷贝、=赋值)
构造:
- 当map内元素值为int类型或常量时,默认值为0。
- 当为String类型时,默认值不明,不显示。
//初始化
map<string, int> m;
m["def"]; //默认初始化为{def,0}
map<int, int> m; //默认构造
map<int, int> m2(m); //拷贝构造
赋值:
m3 = m2; //重载等号操作符
#include <map>
void printMap(map<int, int>&m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << (*it).first << " value = " << it->second << endl;
}
cout << endl;
}
//map容器 赋值和构造
void test01()
{
//创建容器
map<int, int>m; //默认构造
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
printMap(m);
map<int, int>m2(m); //拷贝构造
printMap(m2);
map<int, int>m3;
printMap(m3);
}
int main() {
test01();
system("pause");
return 0;
}
3 map大小和交换 (size、empty、swap)
m.size() //返回容器中元素的数目
m.empty() //判断容器是否为空
m.swap(m2); //交换两个集合容器
m.insert(pair<int, int>(1, 10)); //插入数据
m.insert(make_pair(2, 20));
m.insert(map<int, int>::value_type(3, 30));
m[4] = 40; //[]不建议插入用途,可以利用key访问到value
4 map插入和删除(insert、erase、clear)
//pair初始化
pair<string, int> p("Tom", 20);
pair<string, int> p2 = make_pair("Jerry", 30);
m.insert(pair<int, int>(1, 10)); //在容器中插入元素。
m.insert(make_pair(2, 20));
m.insert(map<int, int>::value_type(3, 30));
m[4] = 40; //[]不建议插入用途,可以利用key访问到value
m.erase(m.begin()); //删除pos迭代器所指的元素,返回下一个元素的迭代器。
m.erase(m.begin(), m.end()); //删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。
m.erase(3); //按照键值(key)3删除
m.clear(); //清除所有元素
5 map查找和统计(find、count)
pos = m.find(3) //查找键值key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回m.end();
int num = m.count(3) //统计键值key的元素个数
6 map排序 (默认排序 按照key值 从小到大排序)
- map容器默认排序规则为 按照key值进行 从小到大排序
- 对于自定义数据类型,map必须要指定排序规则,同set容器
map<int, int, MyCompare> m; //利用仿函数MyCompare实现从大到小排序
map<Person, age, comparePerson> s; //对于自定义数据类型,map必须要指定排序规则,同set容器
class MyCompare {
public:
bool operator()(int v1, int v2)
{
//降序
return v1 > v2;
}
};
//map容器的排序
void test01()
{
//默认从小到大排序
//利用仿函数实现从大到小排序
map<int, int, MyCompare> m;
m.insert(make_pair(1, 10));
m.insert(make_pair(2, 20));
m.insert(make_pair(3, 30));
m.insert(make_pair(4, 40));
m.insert(make_pair(5, 50));
for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
cout << "key:" << it->first << " value:" << it->second << endl;
}
}
int main() {
test01();
system("pause");
return 0;
}