【C++】——STL关联式容器认识以及使用

STL关联式容器

关联式容器： 跟STL中的序列式容器是相同的都是用来存储数据，与序列式容器不同的是，关联式容器存储的是<key，value>结构的键值对，在数据检索是，关联式容器的效率比序列式容器更高；
键值对： 用来表示具有一一对应关系的的一种结构；该结构值一般只包含量两个成员变量key和vlaue，其中key代表键值，value表示与key值对应的信息；
关联式容器底层数据结构： 树形结构 和 哈希结构
树形结构： set、map、muitimap、multiset
哈希结构： unordered_map、unordered_set
键值的结构表示：

template <class T1,class T2>
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)
    {}
};

make_pair

template <class T1,class T2>
  pair<T1,T2> make_pair (T1 x, T2 y)
  {
    return ( pair<T1,T2>(x,y) );
  }
  
 注意： 是一个函数模板，底层还是调用pair--优点就是--会自动推导出参数的类型

map

树形结构的关联式容器主要有四种：map、set、multimap、multiset，这四个容器的共同特点就是：使用平衡二叉树(红黑树)作为其底层结果，容器中的元素是一个有序的序列。

特性：
1、map是一个关联式容器，它按照特定的次序(按照key来比较)存储key和值value组合而成的元素。
2、在map中，键值key通常用于排序和唯一标识元素，而值value中存储于key值相关联的内容。键值key和值value的值可能不同，但是在map内部都是讲这两个数通过一个成员类型value_type表示：pair
3、在map内部是按照键值key进行排序的。
4、map支持下标访问符，在[]中放入key值，就可以找到key值对应的value。
5、map通常被实现为平衡二叉搜索树。
6、map允许根据顺序对元素进行直接迭代。

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
        key：键值对中key的类型，
        T：键值对中value的类型，
        Compare：比较器的类型，map中元素按照key值来比较的，
        Alloc：空间配置器来申请底层空间，

运用：

int main()
{
        //这个demo体会map运用，实现一个简单字典
        map<string, string>m;
        m.insert(pair<string, string>("peach", "桃子"));
        m.insert(pair<string, string>("banan", "香蕉"));
        m.insert(pair<string, string>("apple", "苹果"));
        m.insert(pair<string, string>("orange", "橙子"));
        m["barbicute"] = "烤肉";
        //m.at("waterme") = "水蜜桃";//c++11 标准若可以不存在，抛出异常   at：返回对由键k标识的元素的映射值的引用。
        cout << "元素个数：" << m.size() << endl;
        
        //用迭代器遍历map中的元素；
        for (auto& e : m)
        {
               std::cout<<e.first << "----------------->" << e.second<<endl;
        }
        //map中的key值一定是唯一的，如果key存在将插入失败
        /*
        insert（）函数原理：
               由于map中的键值对都是惟一的，因此插入前先会在map中检查，当前容器中是否存在
              即将插入的键值，若存在则不插入，返回当前容器该key值得位置，若不存在进行插入；
        */

        auto ret = m.insert(make_pair("waterme", "水蜜桃"));

        if (ret.second)

        {

               cout << "<""waterme 水蜜桃>不存在nap中，已经插入" << endl;

        }
        else
        {

               cout << "键值waterme的元素已经存在：" << ret.first->first << "--->" << 
ret.first->second << "插入失败" << endl;

        }
        /*

        operator[]实现原理：

               用默认函数<key，T()>构造一个键值对(value使用默认值)，然后调用insert()函数将该键值对插入到map中；

               如果key已经存在，插入失败，insert函数返回该key所在的位置迭代器；

               如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器；

               operator[]函数最后通过返回迭代器位置将insert返回键值对中value的引用；

        */
       //删除指定键值key的键值对
        m.erase("waterme");//删除键值为key的元素
        for (auto & e : m)
        {
               std::cout << e.first << "----------------->" << e.second << endl;
        }

        cout << endl;
        //count返回ley值在，map中的个数，因为key值是唯一的，所以返回值只可能是0或1；

        if (1 == m.count("apple"))

        {
               cout << "苹果" << endl;
        }


        cout << "体会map中[]操作符：" << m["apple"] << endl;


        system("pause");
        return 0;

}

注意：
1、map中的元素是键值对也就是pair，使用pair或者是make_pair
2、map中的key值是惟一的，并且不能修改，但是可以的删除
3、默认按照小于的方式对key去比较排序
4、map中元素如果使用迭代器去遍历，可以得到一个有序的数列
5、map底层为平衡搜索树，查找效率logN;
6、支持[]操作符operator[]中实际进行插入查找；

multimap

1. Multimap也是关联式容器，它按照特定的顺序，存储有key值和value映射成的键值对<key，value>，其中多个键值对之间的key值是可以重复的。
2. 在multimap中，通常按照key值排序和惟一的标识元素，而映射的value存储于key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key
   和value的键值对:typedef pair<const Key, T> value_type;
3. 在multimap内部，同样是由着按照key值大小严格的排序，并且通过迭代器遍历就可以得到有序的序列。
   注意：multimap和map的唯一不同就是：map中key值唯一的，而multimap中的key是可以重复的。

问题：multimap中为什么没有重载operator[ ]操作？
首先我们先来回顾一下map中的底层原理：map中重载operator[]的功能：1：查找+插入 2：查找+修改
首先调用默认函数<key，T()>构造一个键值对(value用默认值),然后调用insert函数，进行插入再次之前
如果key只存在，那么插入失败，将insert()函数将返回map中已经存在key值位置的迭代器，
如果key值不存在，那么将key值的键值对插入到map中，并且返回key值所在位置的迭代器，
此时operator[]利用此迭代器将迭代器指向键值对中value的引用返回；
此时强调：key值是惟一的，那么在multimap中key是可以重复的，若果还在调用operator[]是，就会产生混乱；

set

特性：
1、set是按照一定次序存储元素的容器，在set中元素的value也是其唯一标识，set中的元素不能再元素中修改*(因为set中的元素总是const)，但是可以向容器中插入或者删除；
2、在set内部，元素都是按照其内部比较对象所指示的特定规则进行排序；
3、同样的set容器也允许，在内部元素进行迭代；
4、set的底层还是 二叉搜索树或者叫红黑树；

注意：
1、与map不同的是，map中存的是真正的键值对<key,value>，而set中只存放了value，但是在set的底层还是存放的是键值对<value,value>.
2、因为set只存方一个value，所以在插入的时候，不需要再构建键值对了。直接用value就行了；
3、在set中元素是不能够重复的，-------所以可以用set来去重；
4、同样的使用set的迭代器遍历元素，可以得到一个有序的元素数列；
5、set中元素排序是按照小于来比较的也就是按照升序来进行排序的；
6、set中查找元素的时间复杂度为logN

问题：set中的元素为什么不能修改？

int main()
{
        //int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
        //set<int> s(array, array + sizeof(array) / sizeof(array[0]));
        c++11，基于范围for
        //for (auto & e : s)
        //{
        //      cout << e << " ";
        //}
        //cout << endl;
        //s.insert(1111111);
        //s.insert(2222222);

        set<int> s;
        s.insert(1);
        s.insert(1);
        s.insert(7);
        s.insert(1);
        s.insert(2);
        s.insert(4);
        s.insert(6);
        for (auto it = s.begin(); it != s.end(); it++)
        {
               cout << *it << " ";
        }
        cout << endl;
        cout << "元素的出现次数:" << s.count(3) << endl;
        system("pause");
        return 0;
}

multiset

1. multiset是按照特定顺序存储元素，其中key是可以重复的
2. 在multiset中，元素value也会识别它(因为multiset中本身存储的就是<value，value>组成的键值对，因此value本身就是key，key就是value，类型T),multiset元素的值不能再容器中进行修改，因为元素师const，但是可以删除或插入。
3. 在内部，multiset中的元素按照内部规则比较排序
4. multiset容器使用迭代器遍历得到一个有序序列，其底层结果为搜索二叉树；

注意：

1. multiset中再底层中存储的是<value, value>的键值对
2. multiset中的元素可以重复，set是中value是唯一的
   3.multiset中的元素不能修改
   4.查找时间复杂度为log2N
   5.可以对元素进行排序但不去去重

int main()

{

        int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 ,8,7,9,5,4,7,8,9,6,5,2,1,3};

        multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));

        for (auto& e : s)

        {

               cout << e << " ";

        }

        cout << endl;

        system("pause");

        return 0;

}

上面是对STL中较常用的关联式容器的性质和相关接口进行了认识和使用，完后会对STL关联式容器底层进行深入的了解，希望有助于大家！！！