Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
返回腾讯云官网
社区首页 >专栏 >C++(STL):36---关联式容器multiset、multimap源码剖析

C++(STL):36---关联式容器multiset、multimap源码剖析

作者头像
用户3479834
发布于 2021-02-03 06:48:19
发布于 2021-02-03 06:48:19
62900
代码可运行
举报
文章被收录于专栏：游戏开发司机游戏开发司机
运行总次数：0
代码可运行
关联问题
换一批

一、multiset

  • multiset的特性以及用法和set完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层RB-tree的insert_equal()而非insert_unique()

multiset源码

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
//以下代码摘录于stl_multiset.h
template <class _Key, class _Compare, class _Alloc>
class multiset {
// requirements:


__STL_CLASS_REQUIRES(_Key, _Assignable);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);


public:


// typedefs:


typedef _Key     key_type;
typedef _Key     value_type;
typedef _Compare key_compare;
typedef _Compare value_compare;
private:
typedef _Rb_tree<key_type, value_type,
_Identity<value_type>, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t;  // red-black tree representing multiset
public:
typedef typename _Rep_type::const_pointer pointer;
typedef typename _Rep_type::const_pointer const_pointer;
typedef typename _Rep_type::const_reference reference;
typedef typename _Rep_type::const_reference const_reference;
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::const_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;
typedef typename _Rep_type::allocator_type allocator_type;


// allocation/deallocation


multiset() : _M_t(_Compare(), allocator_type()) {}
explicit multiset(const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) {}


#ifdef __STL_MEMBER_TEMPLATES


template <class _InputIterator>
multiset(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_equal(__first, __last); }


template <class _InputIterator>
multiset(_InputIterator __first, _InputIterator __last,
const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }


#else


multiset(const value_type* __first, const value_type* __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_equal(__first, __last); }


multiset(const value_type* __first, const value_type* __last,
const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }


multiset(const_iterator __first, const_iterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_equal(__first, __last); }


multiset(const_iterator __first, const_iterator __last,
const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }


#endif /* __STL_MEMBER_TEMPLATES */


multiset(const multiset<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
multiset<_Key,_Compare,_Alloc>&
operator=(const multiset<_Key,_Compare,_Alloc>& __x) {
_M_t = __x._M_t;
return *this;
}


// accessors:


key_compare key_comp() const { return _M_t.key_comp(); }
value_compare value_comp() const { return _M_t.key_comp(); }
allocator_type get_allocator() const { return _M_t.get_allocator(); }


iterator begin() const { return _M_t.begin(); }
iterator end() const { return _M_t.end(); }
reverse_iterator rbegin() const { return _M_t.rbegin(); }
reverse_iterator rend() const { return _M_t.rend(); }
bool empty() const { return _M_t.empty(); }
size_type size() const { return _M_t.size(); }
size_type max_size() const { return _M_t.max_size(); }
void swap(multiset<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }


// insert/erase
iterator insert(const value_type& __x) {
return _M_t.insert_equal(__x);
}
iterator insert(iterator __position, const value_type& __x) {
typedef typename _Rep_type::iterator _Rep_iterator;
return _M_t.insert_equal((_Rep_iterator&)__position, __x);
}


#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(_InputIterator __first, _InputIterator __last) {
_M_t.insert_equal(__first, __last);
}
#else
void insert(const value_type* __first, const value_type* __last) {
_M_t.insert_equal(__first, __last);
}
void insert(const_iterator __first, const_iterator __last) {
_M_t.insert_equal(__first, __last);
}
#endif /* __STL_MEMBER_TEMPLATES */
void erase(iterator __position) {
typedef typename _Rep_type::iterator _Rep_iterator;
_M_t.erase((_Rep_iterator&)__position);
}
size_type erase(const key_type& __x) {
return _M_t.erase(__x);
}
void erase(iterator __first, iterator __last) {
typedef typename _Rep_type::iterator _Rep_iterator;
_M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
}
void clear() { _M_t.clear(); }


// multiset operations:


iterator find(const key_type& __x) const { return _M_t.find(__x); }
size_type count(const key_type& __x) const { return _M_t.count(__x); }
iterator lower_bound(const key_type& __x) const {
return _M_t.lower_bound(__x);
}
iterator upper_bound(const key_type& __x) const {
return _M_t.upper_bound(__x);
}
pair<iterator,iterator> equal_range(const key_type& __x) const {
return _M_t.equal_range(__x);
}


#ifdef __STL_TEMPLATE_FRIENDS
template <class _K1, class _C1, class _A1>
friend bool operator== (const multiset<_K1,_C1,_A1>&,
const multiset<_K1,_C1,_A1>&);
template <class _K1, class _C1, class _A1>
friend bool operator< (const multiset<_K1,_C1,_A1>&,
const multiset<_K1,_C1,_A1>&);
#else /* __STL_TEMPLATE_FRIENDS */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const multiset&, const multiset&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const multiset&, const multiset&);
#endif /* __STL_TEMPLATE_FRIENDS */
};

二、multimap

  • multimap的特性以及用法和map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层RB-tree的insert_equal()而非insert_unique()
  • multimap

multimap源码

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
//下面代码摘录于stl_multimap.h
template <class _Key, class _Tp, class _Compare, class _Alloc>
class multimap {
// requirements:


__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);


public:


// typedefs:


typedef _Key                  key_type;
typedef _Tp                   data_type;
typedef _Tp                   mapped_type;
typedef pair<const _Key, _Tp> value_type;
typedef _Compare              key_compare;


class value_compare : public binary_function<value_type, value_type, bool> {
friend class multimap<_Key,_Tp,_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 _M_t;  // red-black tree representing multimap
public:
typedef typename _Rep_type::pointer pointer;
typedef typename _Rep_type::const_pointer const_pointer;
typedef typename _Rep_type::reference reference;
typedef typename _Rep_type::const_reference const_reference;
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;
typedef typename _Rep_type::allocator_type allocator_type;


// allocation/deallocation


multimap() : _M_t(_Compare(), allocator_type()) { }
explicit multimap(const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { }


#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
multimap(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_equal(__first, __last); }


template <class _InputIterator>
multimap(_InputIterator __first, _InputIterator __last,
const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
#else
multimap(const value_type* __first, const value_type* __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_equal(__first, __last); }
multimap(const value_type* __first, const value_type* __last,
const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }


multimap(const_iterator __first, const_iterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_equal(__first, __last); }
multimap(const_iterator __first, const_iterator __last,
const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
#endif /* __STL_MEMBER_TEMPLATES */


multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { }
multimap<_Key,_Tp,_Compare,_Alloc>&
operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {
_M_t = __x._M_t;
return *this;
}


// accessors:


key_compare key_comp() const { return _M_t.key_comp(); }
value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
allocator_type get_allocator() const { return _M_t.get_allocator(); }


iterator begin() { return _M_t.begin(); }
const_iterator begin() const { return _M_t.begin(); }
iterator end() { return _M_t.end(); }
const_iterator end() const { return _M_t.end(); }
reverse_iterator rbegin() { return _M_t.rbegin(); }
const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
reverse_iterator rend() { return _M_t.rend(); }
const_reverse_iterator rend() const { return _M_t.rend(); }
bool empty() const { return _M_t.empty(); }
size_type size() const { return _M_t.size(); }
size_type max_size() const { return _M_t.max_size(); }
void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }


// insert/erase


iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
iterator insert(iterator __position, const value_type& __x) {
return _M_t.insert_equal(__position, __x);
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(_InputIterator __first, _InputIterator __last) {
_M_t.insert_equal(__first, __last);
}
#else
void insert(const value_type* __first, const value_type* __last) {
_M_t.insert_equal(__first, __last);
}
void insert(const_iterator __first, const_iterator __last) {
_M_t.insert_equal(__first, __last);
}
#endif /* __STL_MEMBER_TEMPLATES */
void erase(iterator __position) { _M_t.erase(__position); }
size_type erase(const key_type& __x) { return _M_t.erase(__x); }
void erase(iterator __first, iterator __last)
{ _M_t.erase(__first, __last); }
void clear() { _M_t.clear(); }


// multimap operations:


iterator find(const key_type& __x) { return _M_t.find(__x); }
const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
size_type count(const key_type& __x) const { return _M_t.count(__x); }
iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
const_iterator lower_bound(const key_type& __x) const {
return _M_t.lower_bound(__x);
}
iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
const_iterator upper_bound(const key_type& __x) const {
return _M_t.upper_bound(__x);
}
pair<iterator,iterator> equal_range(const key_type& __x) {
return _M_t.equal_range(__x);
}
pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
return _M_t.equal_range(__x);
}


#ifdef __STL_TEMPLATE_FRIENDS
template <class _K1, class _T1, class _C1, class _A1>
friend bool operator== (const multimap<_K1, _T1, _C1, _A1>&,
const multimap<_K1, _T1, _C1, _A1>&);
template <class _K1, class _T1, class _C1, class _A1>
friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&,
const multimap<_K1, _T1, _C1, _A1>&);
#else /* __STL_TEMPLATE_FRIENDS */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const multimap&, const multimap&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const multimap&, const multimap&);
#endif /* __STL_TEMPLATE_FRIENDS */
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除
sql
c++

本文分享自 游戏开发司机 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

sql
c++
评论
登录后参与评论
暂无评论
登录 后参与评论
推荐阅读
编辑精选文章
换一批
鹅厂写码13年，我总结的程序员高效阅读方法论
5757
进程，线程，协程 - 你了解多少？
2384
微服务与分布式系统设计看这篇就够了！
2011
腾讯文档表格卡顿指标探索之路
1850
从Hadoop1.0到Hadoop2.0架构的优化和发展探索详解
1826
微服务架构：由浅入深带你了解底层注册中心
1799
C++(STL):27 ---关联式容器set源码剖析
java编程算法c++
一、set set语法使用参阅： set的特性 set所有元素都会根据元素的键值自动被排序 set中的键值就是实值，实值就是键值 默认情况下set不允许两个元素重复 set的迭代器 不能根据set的迭代器改变set元素的值。因为其键值就是实值，实值就是键值，如果改变set元素值，会严重破坏set组织 在后面的源码中会看到，set的迭代器set<T>::iterator被定义为底层RB-tree的const_iterator。因此set的迭代器是一种constant iterators set拥有与lis
用户3479834
2021/02/03
7360
C++(STL):31 ---关联式容器map源码剖析
javasql
map的特性 所有元素都会根据元素的键值自动被排序 map中的pair结构 map的所有元素类型都是pair，同时拥有实值（value）和键值（key） pair的第一个元素视为键值，第二个元素视为实值 map不允许两个元素拥有相同的键值 下面是stl_pair.h中pair的定义： //代码摘录与stl_pair.h template <class _T1, class _T2> struct pair { typedef _T1 first_type; typedef _T2 second_type;
用户3479834
2021/02/03
1.6K0
C++(STL):31 ---关联式容器map源码剖析
C++(STL):33---hash_set、hash_map、hash_multiset、hash_multimap源码剖析
c++sql
这些关联容器底层都是使用hash table实现的. 一、hash_set 由于hash_set底层是以hash table实现的，因此hash_set只是简单的调用hash table的方法即可 与set的异同点： hash_set与set都是用来快速查找元素的 但是set会对元素自动排序，而hash_set没有 hash_set和set的使用方法相同 在介绍hash table的hash functions的时候说过，hash table有一些无法处理的类型（除非用户自己书写hash function
用户3479834
2021/02/03
2K0
C++(STL):33---hash_set、hash_map、hash_multiset、hash_multimap源码剖析
STL之set与multiset那些事
容器javasql
set/multiset以rb_tree为底层结构，因此有元素自动排序特性。排序的依据是key，而set/multiset元素的value和key合二为一：value就是key。
公众号guangcity
2019/10/23
4270
C++ STL源码剖析之map、multimap、initializer_list
c++sqlide
map/multimap 以rb_tree为底层结构，因此有元素自动排序特点，排序的依据是key。
公众号guangcity
2019/10/23
1.2K0
C++ STL源码剖析之map、multimap、initializer_list
【C++】树型结构关联式容器：map/multimap/set/multisetの使用指南（27）
mapset排序c++容器
YY的秘密代码小屋
2024/01/23
2140
【C++】树型结构关联式容器：map/multimap/set/multisetの使用指南（27）
​C++ STL源码剖析之unordered_xxx
容器java
前面学到了hashtable，而这节是hashtable的容器适配器：unordered_map。
公众号guangcity
2019/10/31
1.9K0
map和set的概念及使用
c++容器java
树型结构的关联式容器主要有四种：map、set、multimap、multiset四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。
海盗船长
2020/08/27
6430
C++ STL源码剖析之双向环形链表list
javac++node.js编程算法
双向环状链表从节点值为3开始插入，红色框表示最后一个节点(end()指向的节点)。黄色线条表示指向前驱节点，黑色线条表示指向后继节点。
公众号guangcity
2019/10/09
1.6K0
STL源码剖析-map/multimap容器
其他
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877204
bear_fish
2018/09/14
6740
C++STL源代码学习（之slist篇）[通俗易懂]
编程算法javahttps网络安全
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/115332.html原文链接：https://javaforall.cn
全栈程序员站长
2022/07/10
5340
c++ map和set_STLset和map的区别
容器javac++
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
全栈程序员站长
2022/10/02
4220
c++ map和set_STLset和map的区别
STL 源码剖析之动态数组 vector
javac++
vector 的数据安排以及操作方式，与 array 非常相似。两者的唯一差别在于空间的运用的灵活性，array 是静态的，一旦配置了就不能改变，而 vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。下面一起来看一下 vector 的"内部机制"，怎么来实现空间配置策略的。
公众号guangcity
2019/10/15
1.6K0
STL 源码剖析之动态数组 vector
再探 set/map
sqljava二叉树c++容器
set和map底层数据结构都是红黑树，红黑树的data域段为==pair<key, value>==类型。
看、未来
2021/10/09
7040
再探 set/map
C++11:基于std::unordered_map和共享锁构建线程安全的map
c++编程算法安全
版权声明：本文为博主原创文章，转载请注明源地址。 https://blog.csdn.net/10km/article/details/52072061
10km
2019/05/25
9K0
【C++】STL梳理
java容器jqueryc++编程算法
C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。
后端码匠
2022/12/05
6970
【C++】STL梳理
STL关联容器-红黑树
其他
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877064
bear_fish
2018/09/14
5400
STL关联容器-红黑树
STL源码剖析-set容器
其他
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877141
bear_fish
2018/09/14
5460
STL容器的线程安全性了解多少？
容器javahttps网络安全编程算法
STL的意思是与迭代器合作的C++标准库的一部分，包括标准容器（包括string），iostream库的一部分，函数对象和算法，它不包括标准容器适配器（stack,queue和priority_queue）以及bitset和valarray容器，因为它们缺乏迭代器的支持，也不包括数组。数组以指针的形式支持迭代器，但数组是C++语言的一部分，并非库。
用户9831583
2022/12/04
1.5K0
STL源码剖析-hashtable
其他
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877353
bear_fish
2018/09/14
8950
STL源码剖析-hashtable
推荐阅读
编辑精选文章
鹅厂写码13年，我总结的程序员高效阅读方法论进程，线程，协程 - 你了解多少？微服务与分布式系统设计看这篇就够了！
相关讨论
大佬，求求源码？源码怎么上传？如何下载源码？
相关课程
AI驱动的TDSQL-Cserverless实战营ES Serverless一站式日志分析入门到精通C/Python
C++(STL):27 ---关联式容器set源码剖析
7360
C++(STL):31 ---关联式容器map源码剖析
1.6K0
C++(STL):33---hash_set、hash_map、hash_multiset、hash_multimap源码剖析
2K0
STL之set与multiset那些事
4270
C++ STL源码剖析之map、multimap、initializer_list
1.2K0
【C++】树型结构关联式容器：map/multimap/set/multisetの使用指南（27）
2140
​C++ STL源码剖析之unordered_xxx
1.9K0
map和set的概念及使用
6430
C++ STL源码剖析之双向环形链表list
1.6K0
STL源码剖析-map/multimap容器
6740
C++STL源代码学习（之slist篇）[通俗易懂]
5340
c++ map和set_STLset和map的区别
4220
STL 源码剖析之动态数组 vector
1.6K0
再探 set/map
7040
C++11:基于std::unordered_map和共享锁构建线程安全的map
9K0
【C++】STL梳理
6970
STL关联容器-红黑树
5400
STL源码剖析-set容器
5460
STL容器的线程安全性了解多少？
1.5K0
STL源码剖析-hashtable
8950
相关推荐
C++(STL):27 ---关联式容器set源码剖析
更多 >
用户34798340
LV.1
这个人很懒，什么都没有留下～
文章
171
获赞
612
专栏
1
作者相关精选
换一批
加入讨论
的问答专区 >
用户115295150
相关课程
一站式学习中心 >
AI驱动的TDSQL-Cserverless实战营
1403人在学
云原生数据库 TDSQL-C
ES Serverless一站式日志分析入门到精通
1142人在学
Elasticsearch Service
C/Python
670人在学
c 语言
python
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论
2
目录
查看详情【社区公告】 技术创作特训营有奖征文
本文部分代码块支持一键运行，欢迎体验
本文部分代码块支持一键运行，欢迎体验