无论是在算法竞赛中，还是在日常编程中，它们都是不可或缺的工具 我们将从map和set的定义和特性开始，介绍它们的基本用法和常用成员函数。接着，我们将通过示例代码，展示如何在实际编程中使用它们。...set set s2(v.begin(),v.end()); set s3(s2); // set的拷贝构造 return 0; } set的迭代器 set的迭代器有点多...返回set最后一个元素下一个位置的反向const迭代器，即crbegin 因而有迭代器的存在，set可以跟方便的遍历整个结构 迭代器实现（示例）： int main() { vector...而set则以其独特的元素唯一性特点，为我们提供了一种确保集合中元素不重复的方法，然而学习之路永无止境。对于map和set的理解和应用，仅仅停留在基本的使用层面是远远不够的。...我们需要进一步探索它们的高级用法 学习STL中的容器并不仅仅是为了掌握它们的使用方法。更重要的是，我们要学会如何根据问题的需求选择合适的容器类型，以及如何优化我们的代码以提高程序的性能和可维护性。
---- 关于pair pair是一个struct的模板类，里面有两个成员，通常我们将first认为是key而second认为是value，但它们的类型具体是什么则由我们自己决定，，一般我们将pair...KV结构可以解决更多的问题 2.lower_bound&&upper_bound lower_bound返回大于等于目标值的迭代器，upper_bound返回大于目标值的迭代器，在set中用于返回目标值的迭代器...（可以将获取到的两个迭代器作为一个迭代器区间用于删除或插入） 可以看到这个erase将2和3都给删掉了，可以理解为删除的是一个这样的区间：[2,3] 3.find和count find find...insert 在之前的搜索树和set中因为不允许键值冗余所以插入的返回值就是一个bool值，这里却给了一个迭代器，文档中对返回值这样说：如果不存在这个元素，那么返回的迭代器是新插入的元素的迭代器...不存在就插入在返回迭代器 2.根据迭代器获取pair的first，再由first获取到second 3.因为operator[]只给了key，因此value（ret.first->second;）给的是默认值
在使用set迭代器进行遍历时，set的迭代器走的是中序遍历的顺序，每一个迭代器都指向对应位置的键值对，当然set容器的元素我们也可以叫做键值对，只不过key和value相等罢了。 6....map中比较时比较的是key类型，但我们可以通过key找到value，这里多说一句，无论是map还是set，他们的迭代器走的都是中序的顺序。 2.2 map的使用 1....对于map来说，*it拿到的是pair的对象，所以我们还需要再加一个.操作符才能访问pair对象里面的first和second值，但这样写起来有点麻烦，所以map的迭代器也重载了→操作符，→重载的函数会返回迭代器指向对象的地址...然后我们将键值对利用sort来进行排序，但由于map的迭代器是双向迭代器，而sort要求支持随机访问，因为他底层是快排，那就需要随机迭代器，所以我们将map中的键值对语法糖式的尾插到vector里面，vector...这道题目就比较简单了，我们可以利用set先进行排序+去重，然后比较两个set里面的值，如果两个值相等时，说明这个值是两个数组的交集，两个迭代器同时往后走，去后面继续比较，如果不相等，那就让较小元素对应的迭代器往后
和 map 的插入删除查找等各种功能都是封装复用的红黑树的接口，对于 map来说，key_type 就是我们平常所理解的 K，但是 value_type 却是 pair 类型，它的两个参数分别是模板参数...在明白了 stl 源码是如何解决 set K模型 和 map KV模型 的问题后，我们就可以参照它的做法将我们自己实现的红黑树改造一下： //节点颜色 enum Color { RED, BLACK...红黑树的迭代器和 list 迭代器不同的地方在于红黑树 end() 迭代器的位置以及迭代器如何进行 ++ 与 –； end() 迭代器的位置 STL 明确规定，begin() 与 end() 代表的是一段前闭后开的区间...set 模拟实现的前面部分很简单，在类中定义一个 RBTree 类型的成员变量，然后插入、查找等函数都直接调用红黑树的对应函数即可；set 模拟实现的重难点在于 set 迭代器的实现； 我们可以直接将红黑树的迭代器封装为...--红黑树的const迭代器就是set的普通迭代器 return std::pair(p.first, p.second); } 至此，我们使用红黑树来封装 set
，我们肯定要尝试去看看源码是如何实现的！...1.3 改造并模拟实现红黑树的迭代器 但是最最关键的逻辑就是，实现++和--这样迭代器才能跑的起来，下面我们来进行分析 迭代器的封装 template<class T,class Ref,class Ptr..._RBTreeIterator(const iterator& it) //隐私类型转化 为了set去服务的 因为set的普通迭代器也是const迭代器 :_node(it....，编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题 2、对于insert返回值的改造，本质上是为了map去服务的，set只是配合而已。...三、map的模拟实现 3.1 insert的改装 在stl中 insert的返回值是pair 一开始我不太能理解为什么要这么设计。
map篇 放码过来 map的迭代器 自定义排序 [] 运算符重载函数 C++map迭代器的++操作是如何实现的？...---- set的迭代器 set的迭代器都是const的，因此无法通过迭代器修改set元素。 正常，人家的迭代器是主键，要用来排序的。你可以删，但不可以改。...，并返回指向该元素的迭代器 s.upper_bound(x)表示查找>x的元素中最小的一个，并返回指向该元素的迭代器 举个例子： 在set{3,5,7,8,13,16}中 对于在set中存在的元素，比如...8 s.lower_bound(8)返回8所在位置的迭代器 s.upper_bound(8)返回13所在位置的迭代器 对于在set中不存在的元素，比如12 两个函数返回的则都是13所在位置的迭代器 特殊地...---- C++map迭代器的++操作是如何实现的？ ++操作就是中序遍历。 但是别看遍历一次二叉树的复杂度是O(N)，一旦拿二叉树遍历跟vector的遍历来比较，性能就大大降低了。
---- 前言 红黑树的基本情况我们已经在上一篇文章中学习过了，本文主要研究的是红黑树的实际应用：封装实现 set 和 map，看看如何通过一棵红黑树满足两个不同的数据结构；在正式封装之前，先要对之前的红黑树进行完善...((*this) == it); //复用 } 注意： 是迭代器和迭代器比较，所以参数是 Self 即迭代器对象 1.2.5、迭代器测试 有了这些模块后，我们的 红黑树 类中就可以引入 迭代器 的相关操作了..._node) //构造 或 拷贝构造 {} 如何做到的？...---- 总结 以上就是本次关于 C++【一棵红黑树封装 set 和 map】的全部内容了，在本文中，我们首先将 红黑树 进行了完善，解决了一些深拷贝问题，新增了迭代器，同时还用反向迭代器适配器适配出了...反向迭代器，当红黑树完善后，我们用同一棵红黑树同时封装实现了 set 和 map，其中涉及大量 泛型编程思想，值得仔细推敲 ----
3.2.1 构造函数 1、空的set 2、迭代器区间构造（可以是其他容器的迭代器） 3、拷贝构造 3.2.2 迭代器 有着和vector和list一样的迭代器，但是要注意的是： （1）该迭代器是一个双向迭代器...我们来看看 pair 究竟代表了什么含义，我们前面说明了，set是不允许键值冗余的，也就是说我们的set可能会插入失败，如上图的后两个1就是插入失败的例子，bool就是为了区分插入成功还是失败...比如说1 2 3 4 5 8 9 10，如果我们想插入一个7，那么如果我们传的是5或者8的迭代器，此时就是一个高效的插入（因为相邻），但是如果我们传的迭代器是9，那么此时就不是一个高效的插入，因为找到9...3、第三个的参数是迭代器区间，其实就是插入一个迭代器的区间返回（可以是其他容器的迭代器） 3.2.4 find find的就是去set容器中找到对应键值并返回他对应的迭代器，如果找不到，就会返回end...（2）和之前的set一样，参数传进去的迭代器相当于是一个暗示在该迭代器附近，如果相邻的话，可以实现最高效率的插入，如果不相邻的话就不存在。
，默认为升序，即符合 二叉搜索树 中序遍历的结果：升序，参数3 Alloc 是空间配置器，现在不必深究 作为 STL 中的容器，set 当然少不了迭代器，树型关联式容器迭代器的遍历结果为有序，所以迭代器遍历的本质是...中序遍历，同时 set 的迭代器还是一个 双向迭代器，支持 ++ 和 -- 操作 下面来看看 set 的相关操作 2.2、set 的使用 set 的构造函数如下图所示： 可以直接创建一个空.../迭代器遍历 cout << "迭代器遍历结果: "; set::iterator it = s1.begin(); while (it !...，因此即使是 set 中的普通迭代器，本质上也是 const 迭代器，非常神奇 2.3、set 的特点 set 具有以下特点： set 还有一个亲兄弟：multiset，它允许数据冗余，即数据插入一定是成功的...make_pair("B", 66)}; map m1(arr.begin(), arr.end()); //迭代器遍历 cout << "迭代器遍历结果: ";
二.set 2.1 set的介绍 set的底层为二叉搜索树，也就是上一节中所实现的，不过在此之上，set作为容器来说，封装了和以前的vector、list、deque相关的迭代器、运算符重载等，方便我们去进行一系列的操作...set set ( const set& x); set的拷贝构造 3.set的迭代器 对于set的迭代器，和之前的vector、list相同，有正向迭代器...、反向迭代器、const迭代器。...在文档中发现，有两个函数：lower_bound，upper_bound，这两个实际上也是迭代器类型，传入的只有一个参数，同样是左闭右开，传值之后可以标记对应的位置： int main() { set...上面所标注的就是map[]重载的返回值，发现还有insert的操作，所以我们应该先知道insert的返回值： 发现insert返回类型为pair类型，看看文档是如何说明的
可以按我们之前的理解，map里面存的就是一个pair（键值对）嘛，pair的first对应key，second对应value。 但是它里面为什么value的类型就是一个pair呢？...而map的查找返回的是整个pair的迭代器（其实还是结点里面元素的迭代器，map里面存的就是pair嘛。）...然后大家可以看一下这个图理解一下 ，那这个问题我们就解决了 3.6 红黑树迭代器实现 那接下来我们来实现一下迭代器，实现好之后也可以测试一下我们上面插入之后到底对不对。...3.7 封装set和map的迭代器并测试 那红黑树的迭代器实现的差不多了，我们就可以用它封装set和map的迭代器了。...我们可以看一下库里面是怎么解决的： 先来看set里面的迭代器 我们看到它里面的普通迭代器和const迭代器都是用的红黑树的const迭代器。
map与set大多数情况是用来检索的工具，我们底层使用红黑树来完成map与set的封装。 进行封装之前，我们先来实现一个非常重要的东西：迭代器 2 红黑树的迭代器 迭代器的好处是可以方便遍历。...如果想要给红黑树增加迭代器，需要考虑以前问题： 迭代器的框架如何实现，才能满足泛型编程的需求？？...实现了迭代器接下来我们就来实现map与set的封装 3 map与set的封装 3.1 红黑树的改进 我们先来看我们写的红黑树的节点代码： // 节点结构体 template<class K, class...如果我们想实现set的封装还要在写一份红黑树代码，因为set的节点数据是K 。这样就太不优雅了！ 为了更好实现map与set的封装，我们来看STL源码里是如何实现的吧！...4 总结 通过近一周的学习，我们终于将map和set从零建立起来了，这里不仅需要二叉搜索树的知识还需要AVL树和红黑树的使用！！！甚至还需要对于模版的更深理解！！！
如果给定值在set中不存在，它将返回指向下一个更大的元素的迭代器；如果给定值大于set中的任何元素，它将返回指向set末尾的迭代器。...换句话说，lower_bound 返回的是指向set中第一个不小于（即大于等于）给定值的元素的迭代器 用法示例: std::set s; s.insert(1); s.insert(3); s.insert...如果所有的元素都小于给定值，它将返回指向set末尾的迭代器。 upper_bound 返回的是指向set中第一个大于给定值的元素的迭代器。...它返回一个包含两个迭代器的 pair，这对迭代器分别代表键等于给定键的元素序列的开始和结束 当在普通的（非multi）容器中使用 equal_range 时，返回的范围包含零个或一个元素。...，并返回一个包含两个迭代器的 pair，这些迭代器标记着范围的开始和结束。
需要对 扩容 的地方进行改造 在改造之后，哈希表 的初始大小变为 53 1.4、新增：迭代器类 哈希表 中理应提供一个 迭代器 对其中的值进行判断，因为 桶 是一个 单链表，只能向前走，不能回头，因此我们的...} 在这个函数中，访问了 哈希表类 中的私有成员 _table，这是不行的，为了让其能成功访问，我们可以把 迭代器类 设为 哈希表类 的 友元类 同时，在 哈希表类 中增加 迭代器操作 的相关函数 template...迭代器非法操作 unordered_set 中只有 键值，而 键值 是不能被随意修改的（通过迭代器的方式） void TestUS2() { vector arr = { 7,3,6,9,3,1,6,2...库中的解决方法：不管你 unordered_set 申请的是什么迭代器，我都给你 const 迭代器 //迭代器 typedef typename HT::const_iterator iterator...这是因为 unordered_set 中 普通对象版的 begin() 或 end() 使用的是 哈希表中 const 迭代器，但哈希表中的迭代器相关函数返回的是 普通迭代器 啊，也就是说，存在一个 普通迭代器
<< " "; cout << endl; } set的迭代器 函数声明 功能介绍 iterator begin() \end() 返回set中起始位置元素的迭代器\返回set中最后一个元素后面的迭代器...const_iterator cbegin()\cend() const 返回set中起始位置元素的const迭代器\返回set中最后一个元素后面的const迭代器 reverse_iterator...rbegin() \rend() 返回set第一个元素的反向迭代器，即end\返回set最后一个元素下一个位置的反向迭代器，即 rbegin const_reverse_iterator crbegin...() \crend() const 返回set第一个元素的反向const迭代器，即cend\返回set最后一个元素下一个位置的反向const迭代器， 即crbegin 我们简单来看一看代码把： void...; } 默认是升序，如果是想要降序：使用反向迭代器 仿函数：lessgreater： set的修改操作 find&&erase 对于find和erase我们都是比较熟悉的了，我们可以直接上手代码的实现
) 映射(map) 迭代器(iterator)：可以理解为C语言里的地址，而迭代器就是容器的一个指针，十分重要！！！...// 清空容器内的所有元素 a.begin(); // 容器的一个元素的迭代器 a.end(); // 容器尾后迭代器 vector v; vector::iterator...queue, int> > qpp; set: 1.需要头文件#include； 2.set保存了不可重复的元素–二叉搜索树-红黑树 set<int...// 从字典中删除 m.count('a'); // 字典中是否存在 m.find('a'); // 返回对应值的迭代器（若无则返回尾后迭代器） 通常称map的first元素为key，second...map是按照key进行排序的； 5、key和value一定是成对出现的； 6、map的迭代器指向的内容是一个pair； priority_queue: 1.需要头文件#include
一.改良红黑树的数据域结构 对于如何设计针对map、set的红黑树结构，看源码的实现无疑是最好的方式： 对于源码的实现，我们知道set是的键值对，但是在使用时却只显示一个k，map是...迭代器 需要将有关迭代器的功能都封装起来，这在之前的vector、list模拟实现时已经了解过。对于map和set的迭代器，重要的函数重载就是++和–了。...答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置： 但由于我们上一届中设计的RBTree没有头结点这个结构，因此我们也就不与...如果是const迭代器，那可以在迭代器类中多加上两个模板参数：T&, T*偏特化，当然实际上是Ref，Ptr的全特化；由于set不能修改，因此set的普通迭代器和const迭代器都应该是const类型...，但map的value可以修改，因此我们就需要在RBTree中把普通迭代器和const迭代器均实现出来。
为了方便大家的理解，我们在stl的源码中提取了对于键值对的定义： 我们从map的官方解释中可以看到，键值对的类型是 pair 源码中就是定义了pair的结构体 在结构体...，除非用户不想使用标准库提供的空间配置器 注意：在使用map时，需要包含头文件，set也一样 map的构造： map的迭代器： 关于迭代器的使用我们依旧用代码来了解，更容易理解 map...使用set的迭代器遍历set中的元素，可以得到有序序列 set中的元素默认按照小于来比较 set中的元素不允许修改 set中的底层使用二叉搜索树(红黑树)来实现。...= st.end(); i++) { cout << *i << endl; } return 0; 从本段代码的输出结果来看就知道set的去重效果了 我们可以用迭代器来排出一个有序的序列：...使用迭代器对multiset中的元素进行遍历，可以得到有序的序列 multiset中的元素不能修改 multiset的作用：可以对元素进行排序 其实set和multiset的区别就在于multiset
哈希表迭代器的实现 接着我们来实现一下哈希表的迭代器 我们来思考一下它的迭代器应该怎么搞： 那按照我们以往的经验，它的迭代器应该还是对结点指针的封装，然后顺着每个不为空的哈希桶（链表）进行遍历就行了。...然后end用空构造就行了 6. unordered_set和unordered_map的迭代器封装 那哈希表的迭代器实现好，我们就可以封装unordered_set和unordered_map的迭代器了...那unordered_set搞好了，unordered_map的迭代器我们也来封装一下： 来测试一下 没有问题。...，随意改散列就出问题了： 那我们来处理一下： 那其实解决方法和set那里是一样的，库里面也是一样的方法，让unordered_set的迭代器都是哈希表的const迭代器。...那首先我们得实现一下const迭代器： 先得给哈希表实现一下，还是之前的方法，通过增加两个模板参数 然后const版本的begin和end： 那然后我们把set的迭代器重新封装一下： 然后再运行：
data的大小如何去进行比较：我们并不知道是什么类型是key，还是pair的比较，而我们刚开始kv结构就直接用kv.first去比较了。...对于set是Key，可以比较 对于map是pair，那我们要取其中的first来比较，但是pair的大小并不是直接按照first去进行比较的，而我们只需要按照first去进行比较 由于底层的红黑树不知道传的是...红黑树的正向迭代器是对结点指针进行了封装，所以这里的正向迭代器就只有一个成员变量：结点的指针，并没有什么其他的地方，迭代器的定义： template<class T,class Ref,class Ptr..._node; } 这里的迭代器重点是迭代器的++: 一个结点的正向迭代器进行++操作后，根据红黑树中序(左、根、右)找到当前结点的下一个结点，中序的第一个节点是最左，迭代器的++怎么去找： 如果节点的右子树不为空...);//用普通迭代器构造const迭代器 } private: RBTree _t; }; void test_set() { int a[] =
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
