[C++]map和set的坑

使用方法

map用于维护KV对，set以集合的身份维护元素。从命名角度可以知道set中元素不重复，符合数学的定义。结合计算机的底层实现，set中的元素可以按照一定的顺序组织，比如大小，字典序。同时极具计算机特色的一个用法是multiset的使用，允许一个set中有重复元素的出现。代码如下：

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
int main(){
    unordered_multiset<string> _set;
    _set.insert("Scala");
    _set.insert("Haskell");
    _set.insert("C++");
    _set.insert("Java");
    _set.insert("Erlang");
    _set.insert("Erlang");
    unordered_multiset<string>::iterator it;
    for(it = _set.begin(); it != _set.end();it++){
        cout << *it << endl;
    }
    return 0;
}

从用法上违背了数学中set的定义。至于为什么有这种用法？一种可能的理由是为了充分使用set底层的数据结构，原理可以从底层实现部分看到，同时此处的一个坑在坑部分提到。map用于维护KV对，代码如下：

#include <iostream>
#include <unordered_map>
#include <map>
#include <string>
using namespace std;
int main(){
    unordered_map<int, string> map;
    //map<int, string> _map;
    _map.insert(make_pair(1,"Scala"));
    _map.insert(make_pair(2,"Haskell"));
    _map.insert(make_pair(3,"C++"));
    //_map.insert(make_pair(4,"Java"));
    _map.insert(make_pair(4,"JavaScript"));
    _map.insert(make_pair(5,"Erlang"));
    
    for(auto elem:_map){
      cout << elem.first << "," << elem.second << endl;
    }
    unordered_map<int, string>::iterator it;
    //map<int, string>::iterator it;
    for(it = _map.begin(); it != _map.end(); it++){
      cout << it->first << "," << it->second << endl;
    }
    return 0;
}

KV对，就要维持K的唯一，保证K的索引作用。

底层实现

set和map及其unordered版本最大的不同体现在底层实现，其中set和map的实现都是基于红黑树，而unordered_map的实现是基于哈希表。从用法上看，set默认元素有序，unordered_set中元素无序。为啥？红黑树是一棵平衡二叉查找树，能够以O(lgN)的时间复杂度实现插入，删除，访问元素。而哈希表基于散列函数及相关冲突解决方案确定元素的最终位置，不能保证元素的顺序。这里的顺序的概念可以从遍历容器的输出中看到。既然set是基于哈希表实现，那么需要KV，现在有了V，K在哪里呢？对于unordered_set的实现，K=V，为啥？set中元素不重复，保证了K的唯一性呀。那这里问题来了，unordered_multiset的实现呢？相同的K的散列值一般应该保持相同，如果位置冲突，找到一个合理的位置应该能解决问题。

map的原理和set基本相同，map的对K进行顺序的维持。

原理决定了使用的选择。如果是查询密集型程序，显然使用基于哈希表的容器实现更好。但是哈希是用空间换时间的典型技术，故如果对内存要求比较高，基于哈希的实现就不好了。另一个方面，如果要求数据有序，显然选择基于红黑树的实现。

坑

坑一：unordered_set和unordered_multiset都在头文件

#include <unordered_set>

中，至于为什么没有单独拿出来？可能二者在实现上的差别大于set和unordered_set的差别吧。

坑二：在向map中插入元素时，K可以不唯一，但是最终存储的元素中，只会保留K第一次出现的那个元素。代码如下：

    //_map.insert(make_pair(4,"Java"));
    _map.insert(make_pair(4,"JavaScript"));

_map中只会将”Java”成功插入。可能成为坑的一个地方在于当插入K相同的两个元素时，竟然没有警告或者报错。

参考：

1.C++ STL之哈希表