【C++庖丁解牛】基于红黑树实现的两种常用的关联容器map和set以及multimap

目录

• 1. 关联式容器
• 2. 键值对
• 3. 树形结构的关联式容器
• 4. set的介绍
• 5. set的使用
• • 5.1 set的模板参数列表
  • 5.2 set的构造
  • 5.3 set的迭代器
  • 5.4 set的容量
  • 5.5 set修改操作
  • 5.6 set的使用举例
  • • 构造及其遍历
    • find and erase
    • count
    • lower_bound
    • upper_bound
    • equal_range
    • 6. map的介绍
    • 7.map的使用
    • • 7.1 map的模板参数说明
      • 7.2 map的构造
      • 7.3 map的迭代器
      • 7.4 map的容量与元素访问
      • 7.5 map中元素的修改
      • 7.5 pair函数
      • 8. multiset的介绍
      • 9.multiset的使用

        ---

        1. 关联式容器

        在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

        关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

        2. 键值对

        用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

        SGI-STL中关于键值对的定义：

        template 
        struct pair
        {
        	typedef T1 first_type;
        	typedef T2 second_type;
        	T1 first;
        	T2 second;
        	
        	pair()
        	: first(T1())
        	, second(T2())
        	{}
        	
        	pair(const T1& a, const T2& b)
        	: first(a)
        	, second(b)
        	{}
        };
        

        3. 树形结构的关联式容器

        根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

        4. set的介绍

        1. set是按照一定次序存储元素的容器
        2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
        3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
        4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
        5. set在底层是用二叉搜索树(红黑树)实现的。

        注意：

        1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
        2. set中插入元素时，只需要插入value即可，不需要构造键值对。
        3. set中的元素不可以重复(因此可以使用set进行去重)。
        4. 使用set的迭代器遍历set中的元素，可以得到有序序列
        5. set中的元素默认按照小于来比较
        6. set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2​n
        7. set中的元素不允许修改(为什么?)
        8. set中的底层使用二叉搜索树(红黑树)来实现

        5. set的使用

        5.1 set的模板参数列表

        

        T:set中存放元素的类型，实际在底层存储的键值对。

        Compare：set中元素默认按照小于来比较

        Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

        5.2 set的构造

        函数声明	功能介绍
        set (const Compare& comp = Compare(), const Allocator& = Allocator() );	构造空的set
        set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[first, last)区间中的元素构造set
        set ( const set& x);	set的拷贝构造

        5.3 set的迭代器

        函数声明	功能介绍
        iterator begin()	返回set中起始位置元素的迭代器
        iterator end()	返回set中最后一个元素后面的迭代器
        const_iterator cbegin() const	返回set中起始位置元素的const迭代器
        const_iterator cend() const	返回set中最后一个元素后面的const迭代器
        reverse_iterator rbegin()	返回set第一个元素的反向迭代器，即end
        reverse_iterator rend()	返回set最后一个元素下一个位置的反向迭代器，即rbegin
        const_reverse_iterator crbegin() const	返回set第一个元素的反向const迭代器，即cend
        const_reverse_iterator crend() const	返回set最后一个元素下一个位置的反向const迭代器，即crbegin

        5.4 set的容量

        函数声明	功能介绍
        bool empty ( ) const	检测set是否为空，空返回true，否则返回true
        size_type size() const	返回set中有效元素的个数

        5.5 set修改操作

        函数声明	功能介绍
        pair insert ( const value_type& x )	在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回,如果插入失败，说明x在set中已经存在，返回
        void erase ( iterator position )	删除set中position位置上的元素
        size_type erase ( const key_type& x )	删除set中值为x的元素，返回删除的元素的个数
        void erase ( iterator first, iterator last )	删除set中[first, last)区间中的元素
        void swap ( set& st );	交换set中的元素
        void clear ( )	将set中的元素清空
        iterator find ( const key_type& x ) const	返回set中值为x的元素的位置
        size_type count ( const key_type& x ) const	返回set中值为x的元素的个数

        5.6 set的使用举例

        构造及其遍历

        #include
        using namespace std;
        #include
        void test_set1()
        {
        	set s;
        	s.insert(5);
        	s.insert(1);
        	s.insert(2);
        	s.insert(3);
        	s.insert(4);
        	s.insert(4);
        	s.insert(6);
        	s.insert(6);
        	set::iterator it = s.begin();
        	while (it != s.end())
        	{
        		cout 
        		cout 
        	test_set1();
        	return 0;
        }
        
        	set
        		cout 
        		cout 
        		cout 
        	test_set1();
        	return 0;
        }
        
        	set
        		cout 
        		cout 
        		cout 
        	test_set1();
        	return 0;
        }
        
            set10, 20, 30, 40, 50};
            auto it = mySet.lower_bound(25);
            if (it != mySet.end()) {
                cout 
                cout 
            set10, 20, 30, 40, 50};
            auto it = mySet.upper_bound(25);
            if (it != mySet.end()) {
                cout 
                cout 
            set1, 2, 3, 4, 5};
            auto range = mySet.equal_range(3);
            cout 
                cout 
        	typedef T1 first_type;
        	typedef T2 second_type;
        	T1 first;
        	T2 second;
        	pair();
        	pair(const T1& x, const T2& y);
        	template
        	map"peach", "桃子"});
        	// 将键值对
         	int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
         
        	// 注意：multiset在底层实际存储的是