C++红黑树应用之set和map怎么使用

这篇文章主要介绍“C++红黑树应用之set和map怎么使用”，在日常操作中，相信很多人在C++红黑树应用之set和map怎么使用问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++红黑树应用之set和map怎么使用”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！扒一扒STL库中set和map的底层结构，不难发现，set和map的底层用的都是红黑树且均为key/value模型。只不过set的key/value均为key值填充，而map的key/value使用key和pair进行填充。因此，set和map中底层虽然都是红黑树，但这两种数据结构中的红黑树实例化类型并不相同。那么使用同一颗红黑树的模板，如何实例化出适配set和/map的对象？map和set的区别在于value的不同，红黑树模板参数T，代表value用以区分set和map。我们会发现红黑树的插入等接口会对key值进行比较大小，像set直接对key进行比较，这没问题，但是map中的节点装的是pair,pair的比较规则是first比完之后可能会再去比较second（而我们仅仅想要比较first，该比较规则不适用）。通过源码启发，我们可以对红黑树新增一个模板参数：仿函数KeyOfT，在set和map类中完善该仿函数的比较对象，用于区分set和map的比较：利用仿函数，传入节点的值，set将会返回key值，map将会的返回pair的first。这样就解决了比较大小的规则问题。因为红黑树的中序遍历是有序的，可以根据中序遍历作为迭代器++–的依据。STL源码采用下图结构，多搞了一个头结点。迭代器begin()可以指向header的左，迭代器end()指向header。不过本文采用无头结点的常规红黑树仿写红黑树的迭代器。1、如果当前节点的右不为空，迭代器++返回右子树的最左节点2、如果当前节点的右为空，迭代器++返回祖先（当前节点是父亲的左）(end()-1迭代器++返回nullptr即end())1、如果当前节点的左不为空，迭代器–返回左子树的最右节点2、如果当前节点的左为空，迭代器–返回祖先（当前节点是父亲的右）对于set和map，它们的key都是不能改的。set的value不能修改，map的value可以修改。因为set的value是不能改的，所以它的底层将普通迭代器和const迭代器全部封装成const迭代器免费云主机域名来“解决”：封装之后又会出现新问题，set使用迭代器其实都是在使用const迭代器，但是自己实现的红黑树的迭代器接口返回普通类型的迭代器，在Set.h中对this加上const“解决”：这时使用迭代器调用上方函数会发现红黑树返回了普通迭代器类型的迭代器，类型不匹配。在红黑树中补齐const版本的迭代器函数解决：map的value是可以改的，所以要分别设计普通迭代器和const迭代器。STL库中的普通迭代器都可以转换为const迭代器，这是迭代器类的拷贝构造所支持的。这个拷贝构造有点特殊：1、当这个模板的的Ref和PTR被实例化为T&和T*时，__RBTreeIterator(const iterator& it)就是一个拷贝构造(没啥意义)2、当这个模板的的Ref和PTR被实例化为const T&和const T*时，__RBTreeIterator(const iterator& it)就是一个构造函数，支持用普通迭代器去构造const迭代器。此时const迭代器的拷贝构造函数则由编译器自动生成，刚好满足迭代器值拷贝的特点。迭代器的begin(),end()接口放在红黑树这个类中，而operator++–放在迭代器这个类中，自己写一下循环遍历红黑树的代码就知道为什么这样设计了。到此，关于“C++红黑树应用之set和map怎么使用”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注百云主机网站，小编会继续努力为大家带来更多实用的文章！

相关推荐: mysql之跨库关联查询问题怎么解决

这篇文章主要介绍了mysql之跨库关联查询问题怎么解决的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇mysql之跨库关联查询问题怎么解决文章都会有所收获，下面我们一起来看看吧。mysql是不支持跨库连接的，如果我们实在要连接的话可…