【STL】关联式容器

分手后的思念是犯贱 2022-06-13 04:52 160阅读 0赞

【STL】常用容器总结，带有复习性质的学习更有效率；

--------------------

【STL】 关联式容器复习

在复习关联式容器之前，先回忆一下底层的基本数据机构；

【树】: 常见的树有二叉树，搜索二叉树，RB\_tree, AVL \_tree, 哈弗曼树；

：下面只做特点的回顾，代码及具体细节有前面专门的博客，后面给出链接；

普通的二叉树即一种左右子树的结构，没有什么特别的地方，只是查找的时间复杂度为logn;

搜索二叉树的特点则是左子树的节点比中间节点的值小，右子树的节点的值比中间节点要大，关于搜索二叉树的面试题有一大堆，最后列出一些题作为巩固；

AVL\_tree : 高度平衡二叉树，左右子树的高度差的绝对值不超过1；通过旋转达到平衡的目的，其中分为单旋转个双旋转，这是平衡二叉树的关键，面试的时候不会让你去写这个代码，但是旋转的过程一定要了解，曾经面去哪网的时候让我手画AVL树的旋转，恩，有些懵逼！

关于ALV树的面试题，有一道经典的题：判断一颗AVL树是否平衡；

RB\_tree : 红黑树是在二叉搜索树节点的结构中加入了颜色属性，通过颜色的限制来平衡二叉树，达到尽量降低二叉树高度的目的；

关于红黑树的几个特点：
    1.根节点是黑节点
    2.没有连续的两个红色节点
    3.最长路径是最短路径的两倍
    4.所有叶子节点的孩子节点都是黑节点
    5.对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

下面是我以前写的关于红黑树比较详细的一篇文章：  
[红黑树][Link 1]

在STL中以红黑树作为底层容器有map, set, multiset, multimap; 但其实在C++标准库中 ，即C++11中加入了unordered\_map，和unordered \_set，set\_symmetric\_difference；

【set】 ： 所有元素都会格局元素键值自动排序，set只有key值，其实因为底层是红黑树，底层是将value和key变为一样的； 同时set不允许有重复的key； set不允许通过迭代器改变key值，这样会破坏树的结构；

STL的set提供了相关算法，顺带一提，面cvte的时候，有一道编程题：求出2个字符串的差集；

我当时第一时间就想到了set， 愚蠢的是对set的接口的相关算法不熟悉了，导致伪代码都写得很挫；下面就以这道题为例子复习set；

set提供的相关算法：set_union(并集)， set_difference(差集)， set_intersection(交集)等;

#include <iostream>
    #include <set>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        char arr1[] = "dasdfasf2";
        char arr2[] = "dswdadss3";
        set<char> s1(arr1, arr1+9);
        set<char> s2(arr2, arr2+9);
    
        vector<char> diff(10);
        set_symmetric_difference(s1.begin(),s1.end(),s2.begin(), s2.end(),diff.begin());
        for(int i = 0; i < diff.size(); ++i)
    
        {
            cout<<diff[i]<<" ";
        }
        cout<<endl;
    
        system("pause");
        return 0;
    }

set\_symmetric\_difference： 对称差集，即 （s1 - s2）U （s2 - s1）; 这才是完整的两个字符串的差集；

当然，我当时采用的并不是这个算法，因为当时不知道有这个算法，于是只能自己造个轮子了；

#include <iostream>
    #include <set>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
        char* arr1 = "dasdfasf2";
        char* arr2 = "dswdadss3";
        set<char> s1(arr1, arr1+9);
        set<char> s2(arr2, arr2+9);
    
        vector<char> diff;
    
        while ('\0' != *arr1 || '\0' != *arr2)
        {
            while('\0' != *arr1)
            {
                pair<set<char>::iterator, bool> ret = s2.insert(*arr1);
                if(ret.second == true)
                {
                    diff.push_back(*arr1);
                }
                ++arr1;
            }
            while('\0' != *arr2)
            {
                pair<set<char>::iterator, bool> ret = s1.insert(*arr2);
                if(ret.second == true)
                {
                    diff.push_back(*arr2);
                }
                ++arr2;
            }
        }
        for(int i = 0; i < diff.size(); ++i)
    
        {
            cout<<diff[i]<<" ";
        }
        cout<<endl;
    
        system("pause");
        return 0;
    }

值得一提的是，set的insert返回的是一个pair类型的结构体，其中两个成员first 和 second;

【map】: map和set底层的数据结构都是红黑树，最大的不同之处就是map完整的采用了 key\_value结构，可以通过map的迭代器来修改map的value值但是不可以修改key值，原因和set一样，会破坏树的结构；

map相比于set 还有一个新的特点就是重载了 ‘\[ \]’; 可以通过\[ \] 直接来查找或者插入新的元素；

比如说：

#include <iostream>
    #include <map>
    
    using namespace std;
    
    int main()
    {
        map<char, int> m;
        m['a'] = 1;
        m['b'] = 2;
        m['c'] = 3;
    
        map<char, int>::iterator it = m.begin();
        while(it != m.end())
        {
            cout<<it->first<<" : "<<it->second<<endl;
            it++;
        }
        return 0;
    }

【multiset 和 multimap】：可重复key值的 set 和 map, 同样为了复用，使用的是同一颗红黑树结构，不同的是 set 和 map 在插入元素时调用的是 insert\_unique, 而 multiset 和 multimap 调用的是 insert\_equal;

[二叉树常见面试题][Link 2]

[Link 1]: http://blog.csdn.net/bitboss/article/details/52983757
[Link 2]: http://blog.csdn.net/bitboss/article/details/53423903