从零开始写STL—set/map
2024-08-29 02:05:10
这一部分只要把搜索树中暴露的接口封装一下，做一些改动。
set源码剖析
template<typename T>
class set
{
public:
typedef T key_type;
typedef BStree_iterator<T> iterator;
private:
BStree<T> sequence;
public:
set() :sequence() {}
iterator begin()
{
return sequence.begin();
}
iterator end()
{
return sequence.end();
}
void erase(iterator pos)
{
if (pos.p.node == NULL)
return;
sequence.erase(pos);
}
iterator find(const key_type& key)
{
return sequence.find(key);
}
size_t count(const key_type& x)
{
iterator pos = sequence.find(x);
if (pos.p.node == NULL)
return 0;
else
return 1;
}
size_t erase(const key_type& x)
{
iterator pos = sequence.find(x);
if (pos.p.node == NULL)
return 0;
else
{
erase(pos);
return 1;
}
}
bool empty()
{
return sequence.empty();
}
size_t size()
{
return sequence.size();
}
iterator insert(const T& val)
{
iterator f = sequence.find(val);
if (f == NULL)
return sequence.insert(val);
else
return f;
}
iterator lower_bound(const key_type& x)
{
return sequence.lower_bound(x);
}
iterator upper_bound(const key_type& x)
{
return sequence.upper_bound(x);
}
};
map
二叉搜索树中存储的元素—map_pair
template<typename K, typename T>
struct map_pair
{
typedef map_pair<K, T> self;
K first;
T second;
operator pair<K, T>()
{
return ministl::make_pair<K, T>(first, second);
}
map_pair(const pair<K, T>& rhs)
{
first = rhs.first;
second = rhs.second;
}
map_pair(const K& key, const T& val)
{
first = key, second = val;
}
bool operator==(const self& rhs) const
{
return first == rhs.first;
}
bool operator!=(const self& rhs) const
{
return !(*this == rhs);
}
bool operator<(const self& rhs) const
{
return first < rhs.first;
}
bool operator>(const self& rhs) const
{
return first > rhs.first;
}
bool operator>=(const self& rhs) const
{
return !(first < rhs.first);
}
bool operator<=(const self& rhs) const
{
return !(first > rhs.first);
}
};
map源码
template<typename K, typename T>
class map
{
private:
typedef map_pair<K, T> key_value;
typedef size_t size_type;
BStree<key_value> sequence;
public:
typedef BStree_iterator<key_value> iterator;
map() :sequence() {}
iterator begin()
{
return sequence.begin();
}
iterator end()
{
return sequence.end();
}
bool empty()
{
return sequence.empty();
}
size_type size()
{
return sequence.size();
}
iterator find(const K& x)
{
return sequence.find(map_pair<K, T>(x, T()));
}
size_type count(const K& x)
{
if (sequence.find(map_pair<K, T>(x, T())).p.node == NULL)
return 0;
else
return 1;
}
auto insert(const key_value& key)
{
return sequence.insert(map_pair<K,T>(key,T()));
}
template <class InputIterator>
void insert(InputIterator first, InputIterator last)
{
for (auto it = first; it != last; it++)
insert(*first);
}
void erase(const K& key)
{
return sequence.erase(map_pair<K, T>(key, T()));
}
iterator upper_bound(const K& key)
{
return sequence.upper_bound(map_pair<K, T>(key, T()));
}
iterator lower_bound(const K& key)
{
return sequence.lower_bound(map_pair<K, T>(key, T()));
}
T& operator [](const K& x)
{
pair<iterator,bool> res = sequence.insert(map_pair<K,T>(x,T()));
return (*res.first).second;
}
};
最新文章
- XML格式示例 与 XML操作(读取)类封装
- sqlalchemy ORM
- 一篇让Java程序猿随时可以翻看的Oracle总结
- guake默认快捷键
- Java 递归算法
- 老鸟都应该注意的git 提交规范
- unittest单元测试框架总结
- php代码审计－－sql注入
- 剑指offer编程题Java实现——面试题11数值的整数次方
- maven项目转成web项目没有生成WebContent目录
- Eclipse安装Git插件以及通过Git导入华为软件开发云项目
- Jmeter_针对响应信息不明确的接口做关联
- Spring Boot消息队列应用实践
- 【Linux基础】查看硬件信息-CPU
- nginx+腾讯云免费ssl证书+阿里云ECS实现Https配置
- mysql报错：Cause: com.mysql.jdbc.PacketTooBigException
- spring boot 跨域请求
- Android Studio中实现AIDL
- 无法在web服务器下启动调试。该Web服务器未及时响应
- How to Set Up an Rsync Daemon on Your Linux Server