关键词：
map和set
vector、list、deque……称为序列式容器 ——push系列 pop系列
map、set称为关联式容器 ——insert系列 erase系列
set
- set是按照一定次序存储元素的容器
- 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
- set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
- set在底层是用二叉搜索树(红黑树)实现的。
- T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
- Compare：set中元素默认按照小于来比较
- Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
set的使用举例
#include <set>
void TestSet()
// 用数组array中的元素构造set
int array[] = 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 ;
set<int> s(array, array + sizeof(array) / sizeof(array));
cout << s.size() << endl;
// 正向打印set中的元素，从打印结果中可以看出：set可去重
for (auto& e : s)
cout << e << " ";
cout << endl;
// 使用迭代器逆向打印set中的元素
for (auto it = s.rbegin(); it != s.rend(); ++it)
cout << *it << " ";
cout << endl;
// set中值为3的元素出现了几次
cout << s.count(3) << endl;
void test_set()
//排序+去重
set<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(6);
s.insert(8);
s.insert(0);
s.insert(15);
set<int>::iterator it = s.begin();
while (it != s.end())
cout << *it << " ";
it++;
cout << endl;
auto ret = s.find(10); //O(logN)
// auto ret = find(s.begin(), s.end(), 10); //O(N)
if (ret != s.end())
s.erase(ret); //erase如果ret没在s中，那么用迭代器erase会出现报错（assert暴力检查），而用key_value erase就不会有那样的情况
for (const auto& e : s)
cout << e << " ";
cout << endl;
补充：
-
set中可以存储键值对，实例化set时，将set中元素类型设置为pair即可
-
set中的key是不能重复的
-
set中任意类型元素都可以存储，存储对象时，需要用户提供比较规则
-
set默认是升序，但是其内部默认不是按照大于比较，而是按照小于比较
multiset
- multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
- 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
- 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
- multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
- multiset底层结构为二叉搜索树(红黑树)。
注意：
- multiset中再底层中存储的是<value, value>的键值对
- mtltiset的插入接口中只需要插入即可
- 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
- 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
- multiset中的元素不能修改
- 在multiset中找某个元素，时间复杂度为O(logN)
- multiset的作用：可以对元素进行排序
补充：
- multiset在底层实际存储的是<k，k>的键值对
- multiset大部分接口与set的接口用法相同
multiset的使用
void test_multiset()
//排序+去重
multiset<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(6);
s.insert(8);
s.insert(8);
s.insert(0);
s.insert(15);
s.insert(6);
s.insert(6);
s.insert(6);
s.insert(6);
for (const auto& e : s)
cout << e << " ";
cout << endl;
auto pos = s.find(8);
while (pos != s.end() && *pos == 8)
cout << *pos << " ";
pos++;
cout << endl;
cout << s.count(1) << endl;
cout << s.count(6) << endl;
cout << s.count(8) << endl;
注：
- multiset中的find接口查找的是中序中第一个索要查找的值
- multiset中的count接口用于查看set中key出现的次数
map
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
typedef pair value_type; - 在内部，map中的元素总是按照键值key进行比较排序的。
- map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(平衡二叉搜索树(红黑树))
key: 键值对中key的类型
T： 键值对中value的类型
Compare:比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
注意：在使用map时，需要包含头文件。
void test_map1()
map<string, string> dict;
dict.insert(pair<string, string>("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
map<string, string>::iterator it = dict.begin();
while (dict.end() != it)
cout << it->first << " " << it->second << endl;
it++;
cout << endl;
for (const auto& e : dict)
cout << e.first << " " << e.second << endl;
cout << endl;
void test_map2()
string str[] = "sort","test", "insert", "sort", "sort", "sort", "test", "sort" ;
map<string, int> countmap;
方法一：
//for (const auto& e : str)
//
// auto ret = countmap.find(e);
// if (ret == countmap.end())
// countmap.insert(make_pair(e, 1));
// else
//
// ret->second++;
//
//
//for (const auto& e : countmap)
//
// cout << e.first << " " << e.second << endl;
//
//方法二：
for (const auto& e : str)
countmap[e]++;
for (const auto& e : countmap)
cout << e.first << " " << e.second << endl;
应用统计单词次数
void test_map()
//统计单词次数
方法一
//string str[] = "sort","test", "insert", "sort", "sort", "sort", "test", "sort" ;
//map<string, int> countmap;
//for (const auto& e : str)
//
// auto ret = countmap.find(e);
// if (ret == countmap.end())
// countmap.insert(make_pair(e, 1));
// else
//
// ret->second++; //ret->->second++;
//
//
//for (const auto& e : countmap)
//
// cout << e.first << " " << e.second << endl;
//
方法二：
//string str[] = "sort","test", "insert", "sort", "sort", "sort", "test", "sort" ;
//map<string, int> countmap;
//for (const auto& e : str)
//
// //pair<map<string, int>::iterator, int> ret = countmap.insert(make_pair(e, 1));
// auto ret = countmap.insert(make_pair(e, 1));
// //插入失败，表示e对应字符串已经在countmap中了，++次数
// if (ret.second == false)
//
// ret.first->second++;
//
//
//
//for (const auto& e : countmap)
//
// cout << e.first << " " << e.second << endl;
//
//方法三：
string str[] = "sort","test", "insert", "sort", "sort", "sort", "test", "sort" ;
map<string, int> countmap;
for (const auto& e : str)
countmap[e]++;
for (const auto& e : countmap)
cout << e.first << " " << e.second << endl;
operator[]的应用：
void test_map2()
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict["string"] = "字符串"; //先插入（"string"，""），再修改value
dict["map"]; //先插入（"map"，""）
dict["map"] = "地图"; //查找+修改
cout << dict["map"] << endl; //查找
注意：
- map中的operator[]：
-
- k在map中，insert插入失败，因为k已经有了，insert返回的pair会带出k在map中存储节点的迭代器，通过这个迭代器，可以拿到k对应的value的值进行返回
-
- k不在map中，insert插入成功，插入的值是pair<k,value()>，insert返回值会带出刚插入的k所在节点迭代器，通过这个迭代器，可以拿到k对应的value值进行返回
总结map的operator[]的特征：
- k不存在，插入默认的构造函数生成缺省值的value的pair<k,v()>
- k存在，返回k对应的value的值
- operator[]用于插入、查找、修改
补充：
- map和set底层结构都是红黑树，而其底层红黑树在实现时并没有区分是存k模型还是KV 模型
multimap
- Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。
- 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:
typedef pair<const Key, T> value_type;
- 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
- multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
- multimap在底层用二叉搜索树(红黑树)来实现。
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
multimap的使用
multimap中的接口可以参考map，功能都是类似的。
注意：
- multimap中的key是可以重复的。
- multimap中的元素默认将key按照小于来比较
- multimap中没有重载operator[]操作(找到key之后，但是无法确定用哪个key对应的value值（因为multimap中key是可以重复的）)。
- 使用时与map包含的头文件相同：
void test_multimap()
multimap<string, string> dict;
dict.insert(make_pair("sort", "排序1"));
dict.insert(make_pair("sort", "排序2"));
dict.insert(make_pair("sort", "排序3"));
for (const auto& e : dict)
cout << e.first << " " << e.second << endl;
补充：multiamp中的find接口查找的是中序中第一个索要查找的k值
红黑树模拟实现STL中的map与set
红黑树的迭代器
begin()与end()：
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置即nullptr
注：在STL库中红黑树的迭代器实现：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，对end()位置的迭代器能找最后一个元素，将end()放在头结点的位置
operator++()（对于迭代器it）
- 如果it指向节点的右子树不为空，下一个就++到右子树中序第一个节点，也就是右子树的左节点
- 如果it指向节点的右子树为空，下一个++要访问的节点是，沿着it指向节点到根节点的路径中，孩子是父亲做的那个父亲节点
operator–()（对于迭代器it）
- 如果it指向节点的左子树不为空，下一个就–到左子树中序第最后个节点，也就是左子树的右节点
- 如果it指向节点的左子树为空，下一个–要访问的节点是，沿着it指向节点到根节点的路径中，孩子是父亲做的那个父亲节点
改造红黑树
注意（在红黑树中）：
- KeyOfT: 通过value来获取key的一个仿函数类
- T: 如果是map，则为pair<K, V>; 如果是set，则为k
- K：k为key的类型，
红黑树的代码（改装后）
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
enum Color
RED,
BLACK
;
template<class T>
struct RBTreeNode
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
;
template<class T, class Ref, class Ptr>
struct RBTreeIterator
typedef RBTreeIterator<T, Ref, Ptr> Self;
typedef RBTreeNode<T> Node;
RBTreeIterator(Node* node = nullptr)
:_node(node)
Node* _node=nullptr;
Ref operator*()
return _node->_data;
Ptr operator->()
return &_node->_data;
bool operator==(const Self& it)const
return _node == it._node;
bool operator!=(const Self& it)const
return _node != it._node;
Self& operator++()
Node* cur = _node;
if (cur && cur->_right)
Node* n = cur->_right;
while (n->_left)
n = n->_left;
//*this = Self(n);
_node = n;
else
cur = _node;
Node* parent =cur ->_parent;
Node* n = nullptr;
if (parent->_left == cur)
n = parent;
else
while (parent&&parent->_right == cur)
cur = parent;
parent = cur->_parent;
n = parent;
_node = n;
return *this;
Self operator++(int)
Self it(_node);
if (_node->_right)
// 右子树中序第一个节点，也就是右子树的最左节点
Node* subLeft = _node->_right;
while (subLeft->_left)
subLeft = subLeft->_left;
_node = subLeft;
else
// 当前子树已经访问完了，要去找祖先访问，沿着到根节点的路径往上走，
// 找孩子是父亲左的那个父亲节点
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
cur = parent;
parent = parent->_parent;
_node = parent;
return it;
Self& operator--()
if (_node->_left)
Node* subLeft = _node->_left;
while (subLeft->_right)
subLeft = subLeft->_right;
_node = subLeft;
else
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left == cur)
cur = parent;
parent = parent->_parent;
c++之stlmap和set的模拟实现(代码片段)
模拟实现map和set文章目录模拟实现map和set源码中红黑树的结构模板参数中的仿函数红黑树的迭代器的模拟实现迭代器的基本结构红黑树的迭代器的整体代码map的模拟实现set的模拟实现我们首先来看一下源码当中的set和map的结构&#x... 查看详情
codeforces501bmishaandchanginghandles（stlmap）(代码片段)
MishahackedtheCodeforcessite.Thenhedecidedtoletalltheuserschangetheirhandles.Ausercannowchangehishandleanynumberoftimes.Buteachnewhandlemustnotbeequaltoanyhandlethatisalreadyusedorthatwasusedatsomepoi 查看详情
javascript:手撕new构造函数(代码片段)
...目正则规则的熟悉、prototype和__proto__属性的区别和联系、手撕new构造函数问题解答/*地区：([1-6][1-9]|50) 查看详情
set和map的内部结构
摘要：本文列出几个基本的STLmap和STLset的问题，通过解答这些问题讲解了STL关联容器内部的数据结构，最后提出了关于UNIX/LINUX自带平衡二叉树库函数和map,set选择问题，并分析了map,set的优势之处。对于希望深入学... 查看详情
c++stlmap(代码片段)
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程... 查看详情
多线程常见手撕问题(代码片段)
1.多线程按序循环打印ABCpackagecom.demo.test;/***基于一个锁和一个状态变量实现连续打印ABCABC...*@authorlixiaoxi**/publicclassStateLockPrinter//状态变量privatevolatileintstate=0;//打印线程privateclassPrinterimplementsRunnable//打 查看详情
手撕stlunordered_setunordered_map(用哈希表封装)(代码片段)
哈希unordered系列关联式容器unordered_mapunordered_map的接口说明unordered_setunordered系列关联式容器的使用底层结构哈希冲突常见哈希函数哈希冲突解决闭散列线性探测二次探测开散列开散列增容开散列与闭散列比较开散列的代码实现模... 查看详情
手撕redux(代码片段)
reduxredux是一个全局状态管理库，通过Provider,依赖注入store,sotre可以看作一个容器，用来存放state。通过用户触发dispatchaction,store会调用对应的reducer，并且传入两个参数：当前State和收到的Action。Reducer会返回新的State... 查看详情
和12岁小同志搞创客开发：手撕代码，做一款遥控灯(代码片段)
...net/m0_38106923/category_11097422.html 本篇博文是创客开发：手撕代码篇的最后一节，项目在之前使用Mind+编程中讲到过：和12岁小同志搞创客开发：如何 查看详情
和12岁小同志搞创客开发：手撕代码，点亮led灯(代码片段)
目录1、Arduino编程架构2、点亮LED灯机缘巧合在网上认识一位12岁小同志，从零开始系统辅导其创客开发思维和技巧。项目专栏：https://blog.csdn.net/m0_38106923/category_11097422.html 本篇博文将在ArduinoIDE软件中手写第一个小Demo... 查看详情
零基础都能看懂的stlmap详解(代码片段)
🎈作者：Linux猿🎈简介：CSDN博客专家🏆，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！🎈关注专栏：C/C++面试通关集锦 （优质好文持续更新中……）... 查看详情
手撕代码(代码片段)
1、筛选数组arr中重复的元素，考虑时间复杂度。时间复杂度为O(n)packagewrittenTest01;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;//手写代码：筛选数组arr中重复的元素，考虑时间复杂度。publicclassfilterDuplicateElementspublicstati 查看详情
算法手撕代码81~85(代码片段)
深度学习/机器视觉/数字IC/FPGA/算法手撕代码目录总汇目录1.2-3-4树算法2.B_树算法3.B+树算法4.B树算法5.KMP算法1.2-3-4树算法publicclassTree234privateNoderoot=new 查看详情
stlmap与multimap(代码片段)
1.map（映射）、multimap（多映射）2.红黑树（数据结构）3.1）insert：4种方法 2）count和find 3）erase：3种方法注意：不能通过find进行修改！#include<iostream>#include<map>#include<string>usingnamespacestd;intmap_function()//这个map是用... 查看详情
手撕代码之反转单链表(代码片段)
今天去际链面试，结果在coding这一关又折了。那就总结一下吧，就当再手撕一下代码首先定义一个listNode：publicclasslistNodeintdata;listNodenext;publiclistNode(intdata,listNodenext)this.data=data;this.next=next;定义方法：publicclasslistNodeReversepu 查看详情
手撕汇编。。。(代码片段)
汇编系列文章已经更新了三篇，每一篇都是笔者用心总结，希望对你有帮助手把手教你汇编Debug爱了爱了，这篇寄存器讲的有点意思之前的文章我们主要聊了一些基本的汇编指令，并且通过一个名为Debug的调试软件... 查看详情
手撕死锁代码(代码片段)
手撕死锁代码0.死锁基础知识1.产生死锁代码12.运行结果23.产生死锁代码24.运行结果25.避免死锁修改线程2（靠按序申请资源来预防）6.运行结果30.死锁基础知识多个线程同时被阻塞，它们中的⼀个或者全部都在等待某... 查看详情
fpga/数字ic手撕代码6——数据奇偶校验(代码片段)
深度学习/机器视觉/数字IC/FPGA/算法手撕代码目录总汇目录数据奇偶校验1.程序2.测试3.仿真结果4.分析数据奇偶校验1.程序`tim 查看详情