STL源码刨析:关联式容器之map

2024-08-21 04:28
文章标签 源码 容器 map 关联 stl 刨析

本文主要是介绍STL源码刨析:关联式容器之map,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

        1.前言

        2.了解容器map

        3.容器map的结构

        4.容器map的构造函数

        5.容器map的操作函数

        6.容器map的重载运算符函数


前言

        在上一篇博客中主要讲解了关联式容器set,其set的主要操作是调用RB-tree的操作函数来实现的,而本篇博客将重点讲解关联式容器map


了解容器map

        容器map的特性主要是:所有元素都会根据元素的键值自动被排序

        关于容器map中的元素,其所有元素都是pair,即是一对值。其中pair分为实值(value)和键值(key),在pair中第一个元素被视为键值,第二个元素被视为实值,在map中不允许两个元素拥有相同的键值(容器set只有实值)。具体的pair定义如下:

//pair源码实现
template<class T1, class T2>
struct pair{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1(), second()){}pair(const T1& a, const T2& b) : first(a), second(b) {}
}

        在容器map中可以通过提供的迭代器对实值进行修改,但不能修改其键值。而在容器set中,迭代器不能修改实值(它并没有键值)


容器map的结构

        在容器map中除去有关于STL的萃取定义以外,还在其中定义了仿函数用于比较容器map中的键值,具体源码如下:

//容器map的结构源码
template<class Key, class T,class Compare = less<Key>,    //默认采用递增排序class Alloc = alloc>
class map{
public:typedef Key key_type;   //键值类型typedef T data_type;    //实值类型   typedef T mapped_type;typedef pair<const Key, T> value_type;    //元素类型typedef Compare key_compare;    //键值比较函数//定义用于键值比较的仿函数class value_compare : public vinary_function<value_type, value_type, bool>{friend class map<Key, T, Compare, Alloc>;protected:Compare comp;value_compare(Compare c) : comp(c){}public:bool operator()(const value_type& x, const value_type& y) const{return comp(x.first, y.first);}};private://封装红黑树定义typedef rb_tree<key_type, value_type, select1st<value_type>,key_compare, Alloc> rep_type;rep_type t;
public://指针与常数指针typedef typename rep_type::pointer pointer;typedef typename rep_type::const_pointer const_pointer;//引用与常数引用typedef typename rep_type::reference redefence;typedef typename rep_type::const_rederence const rederence;//迭代器与常数迭代器typedef typename rep_type::iterator iterator;typedef typename rep_type::const_iterator const_iterator;//反向迭代器与常量反向迭代器typedef typename rep_type::reverse_iterator reverse_iterator;typedef typename rep_type::const_reverse_iterator const_reverse_iterator;typedef typename rep_type::size_type size_type;                //容器大小类型typedef typename rep_type::difference_type difference_type;    //迭代器间距离
}

容器map的构造函数

        在了解了容器map的模板结构后,以下是容器map的构造函数:

//容器map的构造函数
map() : t(Compare()){}
explicit map(const Compare& comp) : t(comp){}template <class InputIterator>
map(InputIterator first, InputIterator last) : t(Compare){t.insert_unique(first, last);
}template <class InputIterator>
map(InputIterator first, InputIterator last, const Compare& comp) : t(comp){t.insert_unique(first, last);
} map(const map<Key, T, Compare, Alloc>& x) : t(x.t){}
map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& x){t = x.t;return *this;
}

容器map的操作函数

        以下代码是关于map的操作函数,关于map的许多操作也是调用RB-tree的操作来实现的

//容器map的操作函数
key_compare key_comp() const { return t.key_com; }value_compare value_comp() const { return value_compare(t.key_comp()); }iterator begin() { return t.begin(); }const_iterator begin() const { return t.begin(); }iterator end() { reutrn t.end(); }const_iterator end() const { return t.end(); }reverse_iterator rbegin() { return t.rbegin(); }const_reverse_iterator rbegin() { return t.rbegin(); }reverse_iterator rend() { return t.rend(); }const_reverse_iterator rend() { return t.rend(); }bool empty() const { return t.empty(); }size_type size() const { return t.size(); }size_type max_size() const { return t.max_size(); }void swap(map<Key, T, compare, Alloc>& x) { t.swap(x.t); }pair<iterator, bool> insert(const value_type& x){return t.insert_unique(x);
}iterator insert(iterator position, const value_type& x){return t.insert_unique(position, x);
}template<class InputIterator>
void insert(InputIterator first, InputIterator last){t.insert_unique(first, last);
}void erase(iterator position) { t.rease(position); }size_type erase(const key_type& x) { return t.rease(x); }void erase(iterator first, iterator last) { t.erase(first, last); }void clear() { t.clear(); }iterator find(const key_type& x) { return t.find(x); }const_iterator find(const key_type& x) const { return t.find(x); }size_type count(const key_type& x) const { return t.count(x); }iterator lower_bound(const key_type& x) { return t.lower_bound(x); }const_iterator lower_bound(const key_type& x) const {return t.upper_bound(x);
}pair<iterator, iterator> equal_range(const key_type& x){return t.equal_range(x);
}pair<const_iterator, const_iterator> equal_range(const key_type& x) const {return t.equal_range(x);
}

容器map的重载运算符函数

//容器map的重载运算符函数
friend bool operator==_STL_NULL_TMPL_ARGS (const map&, const map&);friend bool operator<_STL_NULL_TMPL_ARGS (const map&, const map&);T& operator[](const key_type& k){return (*((insert(value_type(k, T()))).first)).second;
}template<class Key, class T, class Compare, class Alloc>
inline bool operator==(const map<Key, T, Compare, Alloc>& x,const map<Key, T, Compare, Alloc>& y){return x.t == y.t;
}template<class Key, class T, class Compare, class Alloc>
inline bool operator<(const map<Key, T, Compare, Alloc>& x,const map<Key, T, Compare, Alloc>& y){return x.t < y.t;
}

PS:由于关联式容器中的set和map大多数是基于RB-tree实现的,所以就没有过多分析其源码,想了解其内容可以具体阅读博客《STL源码刨析:红黑树(RB-tree)》

这篇关于STL源码刨析:关联式容器之map的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092117

相关文章

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》:本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整(可选)重新构建和运行总结Tomcat容器替

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql