STL容器之map和unordered_map

map和unordered_map的作用

提供了key-value的数据存储方式, 内部存储的是pair<key,type>; 可以通过[key]的方式访问获得value。

map和unordered_map的区别

map使用的是红黑树实现, unordered_map使用的是hash算法实现; 所以map存取值的时间复杂度其实并不是O(1), unordered_map的存取才是。

双方的优缺点

如果有排序需要那么使用map, 如果对存取时间有要求使用unordered_map; map实现了一个红黑树, unordered_map使用了链表发解决重复(有rehash的问题).

基本接口

原型

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;

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

map因为实现了红黑树, 所以可以提供一个Compare类. 默认升序排列
unordered_map使用的是hash, 所以可提供hash类(类似于优先级队列中提供一个class, class提供该函数)

实例化方式

    map<int, string> map1;
    map<int, string> map2(map1);
    map<int, string> map3(map1.begin(), map1.end());

    unordered_map<int, string> umap1;
    unordered_map<int, string> umpa2(umap1);
    unordered_map<int, string> umpa3(umap1.begin(), umap1.end());

支持移动构造函数, 和使用迭代器来初始化.

插入元素方式

    map<int, string> map1;

    map1.insert(make_pair(3, "xxx"));
    map1.insert(pair<int,string>(4, "xxx"));
    map1.insert(make_pair(3, "hhh"));
    map1.insert(map<int, string>::value_type(1, "hhh");
    map1[9] = "hhh";

    cout<<map1[3]<<endl;

    map<int, string> map2;
    map2.insert(map1.begin(), map1.end());
    cout<<map2[3]<<endl;

    map<int, string> map3;
    auto it = map3.insert(map3.begin(), make_pair(1, "test"));
    cout<<it->second<<endl;

pair的构造方式有两种, make_pair和pair<keytype, valuetype>以及使用指定map类的类型; 推荐使用第三种, 前两种调用一次构造函数两次复制构造函数, 第三种调用一次构造函数一次复制构造函数.

支持索引方式赋值
insert支持插入pair值和迭代器
insert插入重复key值, 不生效

删除

    map<int, TC> map1;
    map1[1] = TC();
    map1[2] = TC();
    map1[3] = TC();

    map1.erase(1);
    map1.erase(map1.begin());
    cout<<map1.size()<<endl;
    map1.erase(map1.begin(), map1.end());
    cout<<map1.empty()<<endl;
    cout<<map1.max_size()<<endl;

支持删除指定索引或者迭代器的方式, 同时会调用析构函数
size/emtpy获取元素数量以及是否为空
max_size是一个非常大的值

判断是否存在某一个索引

    map<int, int> map1;
    if(&map1[1])
    {
        cout<<"exit 1"<<&map1[1]<<endl;
    }
    if(map1.count(2))
    {
        cout<<"exist 2"<<endl;
    }
    if(map1.end() != map1.find(3))
    {
        cout<<"exist 3"<<endl;
    }

应当通过count或find的方式判断
使用索引的话相当于插入, 这里int默认会是0, 但是已经存在并且可以获得其地址了.

扩展mulimap

与map的区别

  可以插入相同的索引, 在这里count就不简单判断是否存在了而是可以判断数量多少.

find说明

  同样使用了红黑树, 索引甚至可以与map互相用作初始化; 在find查找时,找到第一个就可以顺序往后++即可(红黑树相同的连续在一起).

扩展emplace

    map<int, TC> map1;

    map1.emplace(1, 1);

不用进行多次的构造和赋值构造, 仅调用一次构造函数即可; 不过必须提供有参的构造函数