当前位置:网站首页>map和set的实现
map和set的实现
2022-07-06 21:03:00 【芜湖开冲~】
前面我们实现了红黑树,https://blog.csdn.net/qq_55143256/article/details/125118713
今天我们来用用map和set对红黑树进行封装
目录
map
KeyOfValue
如果你仔细看一下红黑树的实现代码,就会发现有一个东西很奇怪,就是KeyOfValue,那这是干什么的呢?就是封装map的时候需要使用的
它在map里面的作用就是对map里面的键值对,提取其中的key,因为我们map比较的时候,其实是比较的键值对里面的key的
[]重载
map里面的[]符号不仅可以取key对应的value,还可以对插入,就是如果没有这个key,就会将这个key插进去
这是官方给的注释,我们就按照它给的注释写就可以了
其他就没有什么注意的,因为map就是对原本的红黑树进行的封装
代码
#pragma once
#include "RBTree.hpp" //这里的这个头文件就是红黑树博客里面的所有代码组成的头文件
namespace cdd {
template<class K, class V>
class map {
typedef pair<K, V> ValueType;
struct KeyOfValue {
const K& operator()(const ValueType& value) {
return value.first;
}
};
typedef RBTree<ValueType, KeyOfValue> tree;
public:
typedef typename tree::iterator iterator;
public:
map()
:_t()
{}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
size_t size()const
{
return _t.Size();
}
bool empty()const
{
return _t.Empty();
}
V& operator[](const K& key)
{
return (*(_t.Insert(make_pair(key, V())).first)).second;
}
pair<iterator, bool> insert(const ValueType& value)
{
return _t.Insert(value);
}
void swap(map<K, V>& m)
{
_t.Swap(m._t);
}
void clear()
{
_t.Clear();
}
iterator find(const K& key)
{
return _t.Find(make_pair(key, V()));
}
private:
tree _t;
};
}
标准库map相关知识点
标准库为 map 容器配备的是双向迭代器(bidirectional iterator)。这意味着,map 容器迭代器只能进行 ++p、p++、–p、p–、*p 操作,并且迭代器之间只能使用 == 或者 != 运算符进行比较。
值得一提的是,相比序列式容器,map 容器提供了更多的成员方法(如表 1 所示),通过调用它们,我们可以轻松获取具有指定含义的迭代器。
map容器默认排序规则为:按照key值进行从小到大的排序,当然,我么可以利用仿函数进行排序
set
set就更没有什么难的了,它没有[]重载,也不是键值对,所以实在没有什么有问题的地方
代码
#pragma once
#include "RBTree.hpp"
namespace zds {
template<class K>
class set {
struct KeyOfValue {
const K& operator()(const K& value) {
return value;
}
};
typedef RBTree<K, KeyOfValue> tree;
public:
typedef typename tree::iterator iterator;
public:
set()
:_t()
{}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
size_t size()const
{
return _t.Size();
}
bool empty()const
{
return _t.Empty();
}
pair<iterator, bool> insert(const K& value)
{
return _t.Insert(value);
}
void swap(set<K>& s)
{
_t.Swap(s._t);
}
void clear()
{
_t.Clear();
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
tree _t;
};
}
标准库set的相关知识点
set里面的方法
begin() ,返回set容器的第一个元素
end() ,返回set容器的最后一个元素
clear() ,删除set容器中的所有的元素
empty() ,判断set容器是否为空
max_size() ,返回set容器可能包含的元素最大个数
size() ,返回当前set容器中的元素个数
rbegin ,返回的值和end()相同
rend() ,返回的值和rbegin()相同
count() ,用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了
erase(iterator) ,删除定位器iterator指向的值
erase(first,second),删除定位器first和second之间的值
erase(key_value),删除键值key_value的值
find() ,返回给定值值得定位器,如果没找到则返回end()。
这些是一些比较常用的,其实set最大的功能是对一组元素排序去重,嗯,就是说它本身的性质就是最大的功能
最后,有什么问题欢迎评论区留言
边栏推荐
- 25.(arcgis api for js篇)arcgis api for js线修改线编辑(SketchViewModel)
- It's too convenient. You can complete the code release and approval by nailing it!
- Basic concepts of Huffman tree
- Baidu map JS development, open a blank, bmapgl is not defined, err_ FILE_ NOT_ FOUND
- Free PHP online decryption tool source code v1.2
- ubuntu20安装redisjson记录
- About Estimation Statistics
- Implementation steps of docker deploying mysql8
- Tencent cloud native database tdsql-c was selected into the cloud native product catalog of the Academy of communications and communications
- 小程序能运行在自有App中,且实现直播和连麦?
猜你喜欢
Ubuntu 20 installation des enregistrements redisjson
1200.Minimum Absolute Difference
25. (ArcGIS API for JS) ArcGIS API for JS line modification line editing (sketchviewmodel)
Machine learning notes - bird species classification using machine learning
A 股指数成分数据 API 数据接口
VHDL implementation of arbitrary size matrix multiplication
Probability formula
What is Ba? How about Ba? What is the relationship between Ba and Bi?
[development software] tilipa Developer Software
24.(arcgis api for js篇)arcgis api for js点修改点编辑(SketchViewModel)
随机推荐
Not All Points Are Equal Learning Highly Efficient Point-based Detectors for 3D LiDAR Point
Kalman filter-1
Principle of attention mechanism
Set WiFi automatic connection for raspberry pie
Graphical tools package yolov5 and generate executable files exe
【DPDK】dpdk样例源码解析之三:dpdk-l3fwd_001
自适应非欧表征广告检索系统AMCAD
Machine learning notes - bird species classification using machine learning
The latest 2022 review of "small sample deep learning image recognition"
线性表的查找
API data interface of A-share index component data
ERROR: Could not build wheels for pycocotools which use PEP 517 and cannot be installed directly
Delete data in SQL
华为小米互“抄作业”
22.(arcgis api for js篇)arcgis api for js圆采集(SketchViewModel)
pip只下载不安装
Open3d mesh filtering
Implementation steps of docker deploying mysql8
海思万能平台搭建:颜色空间转换YUV2RGB
MySQL的存储引擎