set和map的学习

编程入门行业动态更新时间:2024-10-28 10:26:41

set和map的学习

文章目录

0.底层实现
1.set的原型
2.set的成员函数
- 1.构造函数
- 2.代码演示
3.map的原型
4.map的成员函数
- 1.构造函数
- 2.代码演示
5.OJ练习
- 1.前K个高频单词
- - 法一:map+vector+stable_sort
  - 法二:map+vector+sort[控制逻辑]
  - 法三:map+multimap+vector[leetcode巧合]
  - 法四:map+multiset+vector
  - 法五:优先级队列
- 2.两个数组的交集
- 3.随机链表的复制
- - 1.法一:基础法
  - 2.法二:map键值对法

0.底层实现

二叉平衡搜索树[具体见后期文章]

1.set的原型

template <class T,                   //set::key_typeclass Compare = less<T>,   //set::key_compareclass Alloc = allocator<T> //set::allocator_type   > 
class set;

2.set的成员函数

1.构造函数

//全缺省构造
explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//迭代器区间构造
template <class InputIterator>  
set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//拷贝构造
set(const set& x);

2.代码演示

//插入、迭代器、范围for
void test_set1()
{//初始化1.0set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(1);s.insert(2);//初始化2.0//set<int> s = { 1,2,1 }; //set<int,greater<int> s = { 1,2,1 };   //显式传compare//初始化3.0//int a[] = { 1,2,1 };//set<int> s(a, a + sizeof(a) / sizeof(int));set<int>::iterator it = s.begin();while (it != s.end()){// 二叉搜索树不允许修改key--破坏二叉搜索树的原则cout << *it << " ";++it;}cout << endl;// 范围forfor (auto e : s){cout << e << " ";}cout << endl;//set遍历后数据变成有序的 -- 搜索二叉树中序遍历 -- 有序数据
}
//erase 查找是否存在:find/count 删除某个范围的值
void test_set2()
{set<int> s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(1);s.insert(2);s.erase(30);//erase的底层auto pos = s.find(30);if (pos != s.end()){s.erase(pos);}int x;while (cin >> x){/*	auto ret = s.find(x);if (ret != s.end()){cout << "yes" << endl;}else{cout << "no" << endl;}*///count在set里的取值: 1 0if (s.count(x)){cout << "yes" << endl;}else{cout << "no" << endl;}}set<int> s1;set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++)s1.insert(i * 10); //10 20 30 40 50 60 70 80 90itlow = s1.lower_bound(25); //记录25或25后一个元素             itup = s1.upper_bound(60);  //记录55后一个元素的位置                          s1.erase(itlow, itup);      //[ , )             cout << "s1 contains:";for (auto it = s1.begin(); it != s1.end(); ++it)cout << ' ' << *it;cout << '\n';
}//多重set：multiset 允许键值冗余[重复]
void test_set3()
{multiset<int> ms;ms.insert(3);ms.insert(1);ms.insert(4);ms.insert(2);ms.insert(1);ms.insert(1);ms.insert(1);ms.insert(2);multiset<int>::iterator mit = ms.begin();while (mit != ms.end()){cout << *mit << " ";++mit;}cout << endl;//中序遍历的第一个xauto pos = ms.find(1);while (pos != ms.end() && *pos == 1){cout << *pos << " ";++pos;}cout << endl;cout << "1的个数" << ms.count(1) << endl;ms.erase(1);     //删除所有的1cout << "1的个数" << ms.count(1) << endl;cout << "2的个数" << ms.count(2) << endl;//删除第1个3auto pos = ms.find(3);if (pos != ms.end()){ms.erase(pos);}//删除第2个3++pos;if (pos != ms.end()){ms.erase(pos);}
}

3.map的原型

template < class Key,           // key_type     class T,             // mapped_type        class Compare = less<Key>, //key_compareclass Alloc = allocator<pair<const Key,T> >   // allocator_type> 
class map;

4.map的成员函数

1.构造函数

//全缺省默认构造
explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//迭代器区间构造
template <class InputIterator>  
map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
//拷贝构造
map(const map& x);

2.代码演示

/*
template <class T1, class T2>
struct pair
{T1 _key;T2 _value;pair(): _key(T1()), _value(T2()){}pair(const T1& a, const T2& b): _key(a), _value(b){}
};
*//*template <class T1,class T2>inline pair<Tl,T2> make_pair (Tl x, T2 y){return ( pair<T1, T2>(x, y) ); }
*///插入、迭代器、make_pair
void test_map1()
{map<string, string> m;//创建pair -- 传参pair<string, string> p("Kevin", "凯文");m.insert(p);//匿名对象m.insert(pair<string, string>("Kevin", "凯文"));//make_pairm.insert(make_pair("Eddie", "彭于晏"));m.insert(make_pair("Tom", "汤姆"));m.insert(make_pair("Jerry", "杰瑞"));//map<string, string>::iterator auto it = m.begin();while (it != m.end()){//cout << (*it).first << "-" << (*it).second << endl;cout << it->first << "-" << it->second << endl;++it;}cout << endl;for (const auto& e : m){cout << e.first << "-" << e.second << endl;}cout << endl;
}//count的功能[初识at]
/*
pair(const T1& a, const T2& b): _key(a), _value(b)
{}
1.查找
查找key是否存在
存在返回value的引用
不存在插入 pair( key, V() )  返回value的引用
2.查找 + 修改
查找key 存在 返回value的引用 将其赋值成新值--修改
3.查找 + 插入
查找key 不存在 插入key 分配value 返回value引用///
set里的count: 找到返回1找不到返回0
*//*
V& at(const K& key);
查找key是否存在
存在返回value的引用
不存在抛异常
*/void test_map2()
{map<string, string> m;m.insert(make_pair("Eddie", "彭于晏"));m.insert(make_pair("Tom", "汤姆"));m.insert(make_pair("Jerry", "杰瑞"));//m.insert(make_pair("Eddie", "(彭于晏)")); // 插入失败:已经有了string：key不能重复m["abc"];			 // 查找+插入: m中没有abc 插入abc并调用默认构造为其分配一个映射值即value  返回value的引用m["ABC"] = "牛顿";   // 查找+插入+赋值: m中没有ABC 插入ABC并调用默认构造为其分配一个映射值即value  返回value的引用 将value赋值为"牛顿" m["Eddie"] = "埃迪"; // 查找+修改: m中有Eddie 返回与其匹配的value的引用 将其修改为埃迪cout << m["string"] << endl; // 查找输出string对应的value值
}//统计玩具次数
void test_map3()
{string s[] = { "陀螺", "陀螺", "洋娃娃", "陀螺", "洋娃娃", "洋娃娃", "陀螺", "洋娃娃", "悠悠球", "洋娃娃", "悠悠球", "乐高" };//法一://map<string, int> count;//   for (auto& key : s)//{//	auto pos = count.find(key);//	if (pos == count.end()) //没找到 map里没有此元素 插入//	{//		count.insert(make_pair(key, 1));//	}//	else//	{//		pos->second++;//	}//}//法二:map<string, int> count;for (auto& key : s){/*template<class K,class V>class map{K _key;V _value;};template <class T1, class T2>struct pair{T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a) , second(b){}};insert函数调用 pair<iterator,bool> insert(const pair<K,V>& p);       iterator insert(iterator pos, const pair<K,V>& p);     //在pos处 插入一个键值对 返回pos迭代器template <class InputIterator>  void insert(InputIterator first, InputIterator last);  //迭代器区间构造 返回值为voidV& operator[](const K& key){pair<iterator, bool> it = insert( make_pair( key, V() ) );//插入一个键值对  返回键值对类型return it.first->second; //返回value的引用//it是一个键值对类型 //it.first: 访问类pair的first成员变量 在此pair里first类型为iterator 即it.first为指向key的迭代器[结构体指针类型]//访问value: (*it.first).second == it.first->second}*///key不在count 插入pair( key, int() ) iterator指向key      bool-true//key在count                          iterator指向原有key  bool-falsecount[key]++;}for (auto& toy : count){cout << toy.first << ":" << toy.second << endl;}
}

5.OJ练习

1.前K个高频单词

前K个高频单词

法一:map+vector+stable_sort

class Solution 
{typedef pair<string, int> p;
public:struct cmp{bool operator()(const p& a, const p& b){return a.second > b.second;}};vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;//记录次数[按ascii码 此处已经按字典顺序存储]for (auto& str : words)m[str]++;//迭代器区间构造vector<p> v(m.begin(), m.end());//降序排序//sort的参数迭代器是随机迭代器 但是map的迭代器是双向迭代器//vector的构造函数可以接收任意类型的迭代器stable_sort(v.begin(), v.end(), cmp());//存储数据vector<string> ret;for (size_t i = 0; i < k; ++i)ret.push_back(v[i].first);return ret;}
};

法二:map+vector+sort[控制逻辑]

class Solution 
{typedef pair<string, int> p;
public:struct cmp{bool operator()(const p& a, const p& b){if (a.second > b.second)return true;else if (a.second == b.second && a.first < b.first)return true;elsereturn false;}};vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;//记录次数for (auto& str : words)m[str]++;//迭代器区间构造vector<p> v(m.begin(), m.end());//降序排序sort(v.begin(), v.end(), cmp());//存储数据vector<string> ret;for (size_t i = 0; i < k; ++i)ret.push_back(v[i].first);return ret;}
};

法三:map+multimap+vector[leetcode巧合]

class Solution 
{typedef pair<string, int> p;
public:vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;//记录次数--同时排序//[二叉搜索树:ascii码小的在左 大的在右]for (auto& str : words)m[str]++;//创建多重map //多重map[greater]的底层巧合:// 大key在左 小key在右 相等key在右 // m中的string是按照ascii码排的// M去遍历m时 string的顺序不变// 当遇到相等key即int时 插在了右边 //使得中序遍历结果正确multimap<int, string, greater<int>> M;for (auto& e : m)M.insert(make_pair(e.second, e.first));vector<string> v;auto it = M.begin();while (k--){v.push_back(it->second);++it;}return v;}
};

法四:map+multiset+vector

class Solution 
{typedef pair<string, int> p;
public:struct cmp{bool operator()(const p& a, const p& b) const{if (a.second > b.second)return true;else if (a.second == b.second && a.first < b.first)return true;elsereturn false;}};vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;for (auto& e : words)m[e]++;multiset<p, cmp> s(m.begin(), m.end());vector<string> v;auto it = s.begin();while (k--){v.push_back(it->first);++it;}return v;}
};

法五:优先级队列

class Solution
{typedef pair<string, int> p;
public:struct Cmp{bool operator()(const p& a, const p& b) const{//second是int--即单词的次数 a比b小 返回true后 底层if语句为真 把小的放到堆下面 大的放到堆顶 if (a.second < b.second)return true;if (a.second == b.second && a.first > b.first)return true;return false;}};vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;for (auto& e : words)m[e]++;priority_queue<p, vector<p>, Cmp> heap(m.begin(), m.end());vector<string> v;while (k--){v.push_back(heap.top().first);heap.pop();}return v;}
};

2.两个数组的交集

两个数组的交集

交集
1、不相等小的++
2、相等同时++
3.一个集合走完就结束
差集
1、相等同时++
2.不相等小的就是差集小的++
3.一个走完，另一个没有走完的集合的值也是差集

class Solution
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//排序+去重// 法一: sort + unique// sort(nums1. begin(), nums1. end());// unique( nums1. begin(), nums1.end());// 法二: setset<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();vector<int> v;while (it1 != s1.end() && it2 != s2.end()){if (*it1 < *it2)++it1;else if (*it2 < *it1)++it2;else{v.push_back(*it1);++it1;++it2;}}return v;}
};

拓展:给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。


class Solution 
{
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());int len1 = nums1.size(), len2 = nums2.size();vector<int> v;int i = 0, j = 0;while (i < len1 && j < len2) {if (nums1[i] < nums2[j]) i++;else if (nums1[i] > nums2[j])j++;else{v.push_back(nums1[i]);i++;j++;}}return v;}
};

3.随机链表的复制

随机链表的复制

1.法一:基础法

链表oj中有相同题目解析

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct Node
{int val;struct Node* next;struct Node* random;
};
struct Node* copyRandomList(struct Node* head)
{// 1、拷贝连接struct Node* cp = head;while (cp){struct Node* tmp = (struct Node*)malloc(sizeof(struct Node));//拷贝valtmp->val = cp->val;//拷贝next 即：原结点next指向谁 拷贝结点的next就指向谁tmp->next = cp->next;//cp和tmp连接cp->next = tmp;//cp后移cp = tmp->next;}//2、匹配randomcp = head;while (cp){struct Node* tmp = cp->next;if (cp->random == NULL)tmp->random = NULL;elsetmp->random = cp->random->next;cp = tmp->next;}//3、旧连旧--新连新cp = head;struct Node* Head = NULL, * Tail = NULL;while (cp){struct Node* tmp = cp->next;struct Node* next = tmp->next;if (Tail == NULL){Head = Tail = tmp;}else{Tail->next = tmp;Tail = Tail->next;}cp->next = next;cp = next;}return Head;
}

2.法二:map键值对法

struct Node
{int val;struct Node* next;struct Node* random;
};class Solution
{
public:Node* copyRandomList(Node* head){map<Node*, Node*> m;Node* cp = head;Node* Head = nullptr;Node* Tail = nullptr;Node* tmp = nullptr;while (cp){tmp = new Node(cp->val);m[cp] = tmp;  //存储键值对[cp , tmp]if (Tail == nullptr)Tail = Head = tmp;else{Tail->next = tmp;Tail = Tail->next;}cp = cp->next;}cp = head;tmp = Head;while (cp){if (cp->random == nullptr)tmp->random = nullptr;elsetmp->random = m[cp->random]; //键值对形式访问tmp自己的randomcp = cp->next;tmp = tmp->next;}return Head;}
};

更多推荐

set和map的学习

本文发布于:2024-02-11 03:53:02，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/1678987.html