当前位置:网站首页>Implementation of map and set
Implementation of map and set
2022-07-07 03:56:00 【Wuhu kaichong ~】
In front of us, we realized the red black tree ,https://blog.csdn.net/qq_55143256/article/details/125118713
Let's use it today map and set Encapsulate the red black tree
Catalog
Standard library map Related knowledge
Standard library set Relevant knowledge points of
map
KeyOfValue
If you take a closer look at the implementation code of red black tree , You will find something strange , Namely KeyOfValue, What is this for ? Is the packaging map It needs to be used when
It's in map Its function is to map The key value in it is right , Extract the key, Because we map When comparing , In fact, it is the key value pair of comparison key Of
[] heavy load
map Inside [] Symbols can not only take key Corresponding value, You can also insert , If there is no such key, It will key Insert in
This is the official note , We just write according to the notes it gives
There is nothing else to pay attention to , because map It is the encapsulation of the original red black tree
Code
#pragma once
#include "RBTree.hpp" // The header file here is the header file composed of all the code in the red black tree blog
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;
};
}
Standard library map Related knowledge
The standard library is map The container is equipped with a bidirectional iterator (bidirectional iterator). It means ,map Container iterators can only ++p、p++、–p、p–、*p operation , And you can only use between iterators == perhaps != Operator to compare .
It is worth mentioning that , Compared with sequential containers ,map Containers provide more member methods ( As shown in the table 1 Shown ), By calling them , We can easily get iterators with specified meanings .
map The default collation for containers is : according to key Values are sorted from small to large , Of course , We can use the imitative function to sort
set
set There is nothing more difficult , It has no [] heavy load , Nor is it a key value pair , So there is really nothing wrong
Code
#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;
};
}
Standard library set Relevant knowledge points of
set The method inside
begin() , return set The first element of the container
end() , return set The last element of the container
clear() , Delete set All the elements in the container
empty() , Judge set Whether the container is empty
max_size() , return set The maximum number of elements a container can contain
size() , Returns the current set The number of elements in the container
rbegin , The return value and end() identical
rend() , The return value and rbegin() identical
count() , Used to find set The number of times a key value appears in the . This function is in the set It's not very practical , Because a key value is in set It's only possible 0 or 1 Time , In this way, it becomes to judge whether a key value is set There have been
erase(iterator) , Delete locator iterator The value of the point
erase(first,second), Delete locator first and second Between the value of the
erase(key_value), Delete key value key_value Value
find() , Returns the value of the given value , If not, return end().
These are some commonly used , Actually set The biggest function is to sort and de duplicate a group of elements , Um. , That is to say, its nature is the greatest function
Last , If you have any questions, please leave a message in the comments section
边栏推荐
猜你喜欢
Construction of Hisilicon universal platform: color space conversion YUV2RGB
未来发展路线确认!数字经济、数字化转型、数据...这次会议很重要
[safe office and productivity application] Shanghai daoning provides you with onlyoffice download, trial and tutorial
22. (ArcGIS API for JS) ArcGIS API for JS Circle Collection (sketchviewmodel)
Codeworks 5 questions per day (1700 average) - day 7
Kbone与小程序跨端开发的一些思考
[development software] tilipa Developer Software
卡尔曼滤波-1
小程序能运行在自有App中,且实现直播和连麦?
tflite模型转换和量化
随机推荐
Open3d mesh filtering
Code quality management
PIP download only, not install
A 股指数成分数据 API 数据接口
Native MySQL
Ubuntu 20 installation des enregistrements redisjson
10 ways of interface data security assurance
termux设置电脑连接手机。(敲打命令贼快),手机termux端口8022
红米k40s root玩机笔记
Can the applet run in its own app and realize live broadcast and connection?
20. (ArcGIS API for JS) ArcGIS API for JS surface collection (sketchviewmodel)
C task expansion method
Create commonly used shortcut icons at the top of the ad interface (menu bar)
二叉搜索树的实现
一些常用软件相关
Confirm the future development route! Digital economy, digital transformation, data This meeting is very important
HW notes (II)
23. (ArcGIS API for JS) ArcGIS API for JS ellipse collection (sketchviewmodel)
web服务性能监控方案
Kotlin Android environment construction