【STL】模拟实现STL中set容器

淩亂°似流年 2022-11-04 09:03 203阅读 0赞

### 文章目录 ###

*  1. 模拟实现set需要理解的概念
 *  2. 模拟实现set代码

# 1. 模拟实现set需要理解的概念 #

*  在 STL 中的 set 容器，其底层数据结构是`红黑树`
 *  set 中存储的数据是以 key - value 的形式存储的
 *  用户存储的数据是放在 key 中的， value 用户是无法访问的

# 2. 模拟实现set代码 #

改代码可以运行的前提是需要[红黑树的模拟实现][Link 1]中的红黑树代码

> map.hpp

#pragma once
    #include "RBTree.hpp" // 红黑树的模拟实现
    
    // set 中防止的是
    template<class K>
    class set
    { 
    
    	typedef K ValueType;
    	struct KOFP
    	{ 
    		const K& operator()(const ValueType& data)
    		{ 
    			return data;
    		}
    	};
    	typedef RBTree<ValueType, KOFP> RBT;
    	typedef typename RBT::iterator iterator;
    public:
    	set() :_t(){ }
    
    	// iterator
    	iterator begin()
    	{ 
    		return _t.begin();
    	}
    	iterator end()
    	{ 
    		return _t.end();
    	}
    
    	// capacity
    	size_t size()
    	{ 
    		return _t.size();
    	}
    	bool empty()
    	{ 
    		return _t.empty();
    	}
    
    	// modify
    	pair<iterator, bool> insert(const ValueType& data)
    	{ 
    		return _t.insert(data);
    	}
    	void swap(set<K>& s)
    	{ 
    		_t.swap(s._t);
    	}
    	void clear()const
    	{ 
    		_t.clear();
    	}
    	iterator find(const K& key)
    	{ 
    		return _t.find(key);
    	}
    
    private:
    	RBT _t;
    };

[Link 1]: https://blog.csdn.net/weixin_45437022/article/details/114273659

发表评论取消回复

表情：

评论列表（有 0 条评论，203人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】STL 标准模板库 ③ ( STL 容器简介 | STL 容器区别 | STL 容器分类 | 常用的 STL 容器 )

文章目录一、STL 容器简介 1、STL 容器区别 2、STL 容器分类 3、常用的 STL 容器

逃离我推掉我的手/ 2024年02月19日 11:30/ 0 赞/ 53 阅读

相关 stl set容器_C ++ STL设置容器– std :: set

![6495602ae9fd2526e245115a23f7e51f.png][] stl set容器 In this tutorial you will learn ab

偏执的太偏执、/ 2022年12月07日 13:54/ 0 赞/ 257 阅读

相关 STL容器之 set(原理，成员函数)

文章目录底层实现：红黑树查找效率迭代器的值不会变为什么set, map等的插入效率比vector，deque高

缺乏、安全感/ 2022年11月24日 14:20/ 0 赞/ 230 阅读

相关【STL】模拟实现STL中set容器

文章目录 1. 模拟实现set需要理解的概念 2. 模拟实现set代码 1. 模拟实现set需要理解的概念在 STL 中的 set 容器，其底

淩亂°似流年/ 2022年11月04日 09:03/ 0 赞/ 204 阅读

相关【STL】模拟实现STL中map容器

文章目录 1. 模拟实现map需要理解的概念 2. 模拟实现map 1. 模拟实现map需要理解的概念 STL中的map的底层数据结构是一个`红

妖狐艹你老母/ 2022年11月04日 09:03/ 0 赞/ 218 阅读

相关 c++ STL容器 set使用介绍

顺序容器包括vector、deque、list、forward\_list、array、string，所有顺序容器都提供了快速顺序访问元素的能力。关联容器包括set、map

╰半夏微凉°/ 2022年10月22日 13:56/ 0 赞/ 290 阅读

相关 STL中的set容器的一点总结

http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html 1.关于set C++ ST

喜欢ヅ旅行/ 2022年07月21日 02:51/ 0 赞/ 238 阅读

相关 STL — set容器的使用详解

set容器的使用详解其实map和set是一个爸爸 - 红黑树爸爸，只不过set力气不够，不像map那么可以拥有一个主键

古城微笑少年丶/ 2022年06月06日 10:12/ 0 赞/ 262 阅读

相关 C++进阶STL-set、multiset容器

set、multiset容器 set和multiset基于红黑树，自动排序 set中元素不可以重复，multiset中元素可以重复，都在<set>头文件中

淩亂°似流年/ 2022年05月09日 07:14/ 0 赞/ 269 阅读

相关 c++ STL容器（2）set容器

set翻译为集合，是一个内部自动有序且不含重复元素的容器 set的定义 set<typename> name; set<int> vi;

港控/mmm°/ 2021年06月22日 15:38/ 0 赞/ 590 阅读