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

妖狐艹你老母 2022-11-04 09:03 222阅读 0赞

### 文章目录 ###

*  1. 模拟实现map需要理解的概念
 *  2. 模拟实现map

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

*  STL中的map的底层数据结构是一个`红黑树`
 *  map 中存储数据是以`key - value`的形式存储的

# 2. 模拟实现map #

以下代码可以运行的前提是，拥有[红黑树的模拟实现][Link 1]中红黑树的代码

> map.hpp

#include "RBTree.hpp" // 红黑树的模拟实现
    
    // map 中放置的是 K—V 模型
    template<class K, class V>
    class map
    { 
    	typedef pair<K, V> ValueType;
    	struct KOFP	// 为了方便红黑树中的插入：比较的是K而不是Pair结构体地址
    	{ 
    		const K& operator()(const ValueType& data)
    		{ 
    			return data.first;
    		}
    	};
    
    	typedef RBTree<ValueType, KOFP> RBT;
    public:
    	// iterator可能是红黑树中的类型，也可能是静态成员变量，需要显式说明
    	typedef typename RBT::iterator iterator;
    
    	map() :_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(map<K, V>& m)
    	{ 
    		_t.swap(m._t);
    	}
    	void clear()const
    	{ 
    		_t.clear();
    	}
    	iterator find(const K& key)
    	{ 
    		return _t.find(key, V());
    	}
    
    	// acess
    	V& operator[](const K& key)
    	{ 
    		return (*(_t.insert(make_pair(key, V()))).first).second;
    	}
    private:
    	RBT _t;
    };

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

发表评论取消回复

表情：

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

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

相关阅读

相关 c++ stl容器 map_C ++ STL映射容器– std :: map

![9654888ffe92f06309f309ab5b5f0f4f.png][] c++ stl容器 map In this tutorial you will lear

左手的ㄟ右手/ 2022年12月07日 13:55/ 0 赞/ 273 阅读

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

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

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

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

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

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

相关 Map容器的用法(STL)

转自[http://blog.csdn.net/uqapuqap/archive/2009/08/14/4448067.aspx][http_blog.csdn.net_uqa

傷城~/ 2022年08月26日 05:59/ 0 赞/ 199 阅读

相关 STL容器（四）——hash_map

STL容器（四）——hash\_map 1. hash\_map简介 hash\_map和前面介绍的map既有很多的联系，也要必须要了解的区别~ has

向右看齐/ 2022年08月06日 02:27/ 0 赞/ 204 阅读

相关 STL容器（三）——对map排序

STL容器（三）——对map排序对于map的排序问题，主要分为两部分：根据key排序；根据value排序。下面我们就分别说一下~ 1. 根据key进行排序

本是古典何须时尚/ 2022年08月06日 02:07/ 0 赞/ 229 阅读

相关 STL_MAP

// accessing mapped values include <iostream> include <m

水深无声/ 2022年07月17日 04:16/ 0 赞/ 219 阅读

相关 STL中map介绍

本文主要介绍 C++ 编程语言的 STL（Standard Template Library）中 map 的相关知识，同时通过示例代码介绍 map 的使用方法。 1 概念

忘是亡心i/ 2022年05月27日 13:42/ 0 赞/ 227 阅读

相关 STL容器 -- map/multimap

1、map/multimap容器基本概念 map的特性是，所有元素都会根据元素的键值自动排序。map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键

向右看齐/ 2022年02月04日 10:21/ 0 赞/ 305 阅读

相关 c++ stl（4）map容器

map的定义 map<typename1,typename2> mp; map<int,int> mp; map<string,i

我会带着你远行/ 2021年06月22日 15:38/ 0 赞/ 438 阅读