修正

一辈子这么长，我不会就喜欢你一个人的。
关于map和unordered_map还需要知道的
map 与unordered_map的效率问题

unordered_map的初始化比较耗时，我们都知道map是红黑树，unordered_map是哈希表，造成性能差异的原因在于，红黑树初始化时，节点只需要一个，后续的插入只是插入新的节点，但是哈希表初始化时就不是那么简单了，哈希表初始化时需要申请一个数组，数组的每个元素都指向一条链表，所以初始化时需要申请很多内存，相比于map，的确更耗时。
unorder_map的插入效率随着数量的增加，基本是map的一点多倍以上,查找方面来说，跟map基本可以说差不多，而如果map中如果放string的话,查找效率明显比存int类型这种类型的消耗很多。因此，如果对排序没有什么要求的话，又要求key为string类型的，强烈要求使用unorder_map。

typedef pair<int, int> edgePair;
typedef unordered_map<edgePair, int, pairHash> edgeMap;//这个在频繁查找中有优势
typedef map<edgePair, int> edgeMap;     //这个比较省时

使用空间换取时间。
map/unordered_map原理和使用整理
map的内部实现是二叉平衡树(红黑树)；hash_map内部是一个hash_table一般是由一个大vector，vector元素节点可挂接链表来解决冲突，来实现，新版的hash_map都是unordered_map了。

1、 map和hash_map

关于STL中的map和hash_map

  1. STL的map底层是用红黑树实现的，查找时间复杂度是log(n)；
  2. STL的hash_map底层是用hash表存储的，查询时间复杂度是O(1)；
  3. 什么时候用map，什么时候用hash_map？
    这个要看具体的应用，不一定常数级别的hash_map一定比log(n)级别的map要好，hash_map的hash函数以及解决地址冲突等都要耗时间，而且众所周知hash表是以空间换时间的，因而hash_map的内存消耗肯定要大，一般情况下，如果记录非常大，考虑hash_map，查找效率会高很多，如果要考虑内存消耗，则要谨慎使用hash_map。

map的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
map<string, string> namemap;

//增加。。。
namemap["岳不群"]="华山派掌门人，人称君子剑";
namemap["张三丰"]="武当掌门人，太极拳创始人";
namemap["东方不败"]="第一高手，葵花宝典";
...

//查找。。
if(namemap.find("岳不群") != namemap.end())
{
        ...
}

2、hash_map的使用

下面是SGI STL的hash_map声明。

template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
class _EqualKey = equal_to<_Key>,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map
{
        ...
}

键，值，hash函数，比较函数，alloc(忽略)

hash函数

在SGI STL中，提供了以下hash函数：
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash

也就是说，如果你的可以key是以上类型中的一种，你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量，例如对于string，就必须自定义hash函数，可以用char代替。例如：
struct str_hash{
size_t operator()(const string& str) const
{
unsigned long h = 0;
for (size_t i = 0 ; i < str.size() ; i ++) h = 5h + str[i];
return size_t(h);
}
};
//如果你希望利用系统定义的字符串hash函数，你可以这样写：
struct str_hash{
size_t operator()(const string& str) const
{
return return __stl_hash_string(str.c_str());
}
};

hash_map<int, string> mymap;
//等同于:
hash_map<int, string, hash<int>, equal_to<int> > mymap;

比较函数

在map中的比较函数，需要提供less函数。如果没有提供，缺省的也是less。在hash_map中，要比较桶内的数据和key是否相等，因此需要的是是否等于的函数equal_to。 先看看equal_to的源码：

//本代码可以从SGI STL
//先看看binary_function 函数声明，其实只是定义一些类型而已。
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
        typedef _Arg1 first_argument_type;
        typedef _Arg2 second_argument_type;
        typedef _Result result_type;
};
//看看equal_to的定义：
template <class _Tp>
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
        bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};

如果你使用一个自定义的数据类型，如struct mystruct或者const char*的字符串，如何使用比较函数？使用比较函数，有两种方法。第一种是：重载==操作符，利用equal_to；看看下面的例子：

struct mystruct{
        int iID;
        int len;
        bool operator==(const mystruct & my) const{
                return (iID==my.iID) && (len==my.len) ;
        }
};

这样，就可以使用equal_to作为比较函数了。另一种方法就是使用函数对象。自定义一个比较函数体：

struct compare_str{
        bool operator()(const char* p1, const char*p2) const{
                return strcmp(p1,p2)==0;
        }
};

hash_map中几个常用函数

1、hash_map(size_type n) 如果讲究效率，这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。n越大，效率越高，但是内存消耗也越大。
2、const_iterator find(const key_type& k) const. 用查找，输入为键值，返回为迭代器。
3、data_type& operator . 这是我最常用的一个函数。因为其特别方便，可像使用数组一样使用。不过需要注意的是，当你使用[key ]操作符时，如果容器中没有key元素，这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，你可以使用find。如果你 希望插入该元素时，你可以直接使用[]操作符。
4、insert 函数。在容器中不包含key值时，insert函数和[]操作符的功能差不多。但是当容器中元素越来越多，每个桶中的元素会增加，为了保证效率， hash_map会自动申请更大的内存，以生成更多的桶。因此在insert以后，以前的iterator有可能是不可用的。
5、erase 函数。在insert的过程中，当每个桶的元素太多时，hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后，其他元素的iterator还是可用的。

3、示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
-bash-2.05b$ cat my.cpp  
#include <hash_map>  
#include <string>  
#include <iostream>  
  
using namespace std;  
//define the class  
class ClassA{  
    public:  
        ClassA(int a):c_a(a){}  
        int getvalue()const { return c_a;}  
        void setvalue(int a){c_a=a;}  
    private:  
        int c_a;  
};  
  
//1 define the hash function  
struct hash_A{  
        size_t operator()(const class ClassA & A)const{  
                // return hash<int>(classA.getvalue());  
                return A.getvalue();  
        }  
};  
  
//2 define the equal function  
struct equal_A{  
        bool operator()(const class ClassA & a1, const class ClassA & a2)const{  
                return a1.getvalue() == a2.getvalue();  
        }  
};  
  
int main()  
{  
        hash_map<ClassA, string, hash_A, equal_A> hmap;  
        ClassA a1(12);  
        hmap[a1]="I am 12";  
        ClassA a2(198877);  
        hmap[a2]="I am 198877";  
         
        cout<<hmap[a1]<<endl;  
        cout<<hmap[a2]<<endl;  
        return 0;  
}  
-bash-2.05b$ make my  
c++ -O -pipe -march=pentiumpro my.cpp -o my  
-bash-2.05b$ ./my  
I am 12  
I am 198877</span>

4、pair

pair是一种模板类型，其中包含两个数据值，两个数据的类型可以不同，基本的定义如下：

pair a;

表示a中有两个类型，第一个元素是int型的，第二个元素是string类型的，如果创建pair的时候没有对其进行初始化，则调用默认构造函数对其初始化。

pair a(“James”, “Joy”);

对于pair类，由于它只有两个元素，分别名为first和second，因此直接使用普通的点操作符即可访问其成员。

pair<string, string> a("Lily", "Poly"); 
string name;
name = pair.second;

生成新的pair对象，可以使用make_pair对已存在的两个数据构造一个新的pair类型：

int a = 8;
string m = "James";
pair<int, string> newone;
newone = make_pair(a, m);

5、举栗子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#pragma once
#include "stdafx.h"
#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;

struct pairHash {
public:
    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U> &x) const
    {
        return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
    }
};

typedef pair<int, int> edgePair;
typedef unordered_map<edgePair, int, pairHash> edgeMap;

class Truss {

public:
    edgeMap sup; //边的支持度
    edgeMap edgeTrussness; //边的trussness
    set<pair<int, edgePair>> nonDecSup;
}