一、map

1、map成员

上面可以看到Map接口的几个实现方式。简要说明：

TreeMap是基于树（红黑树）的实现方式，即添加到一个有序列表，在O(log n)的复杂度内通过key值找到value，优点是空间要求低，但在时间上不如HashMap。C++中Map的实现就是基于这种方式

HashMap是基于HashCode的实现方式，在查找上要比TreeMap速度快，添加时也没有任何顺序，但空间复杂度高。C++ unordered_Map就是基于该种方式。

HashTable与HashMap类似，只是HashMap是线程不安全的，HashTable是线程安全的，现在很少使用

ConcurrentHashMap也是线程安全的，但性能比HashTable好很多，HashTable是锁整个Map对象，而ConcurrentHashMap是锁Map的部分结构。

 

2、map简介

map时STL的一个关联容器，它提供一对一的hash。第一个模板参数可以称为关键字key，每个关键字只能在map中出现一次；第二个模板参数可以称为value。

map以模板（泛型）方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射的情况，在map内部所有的数据都是有序的。

 

3、map的功能和使用

自动建立key--value的对应，key和value可以是任意你需要的类型。

使用map需要包含map类所在头文件：

#include <map>    //STL头文件时没有扩展名.h的

map对象时模板类，需要关键字和存储对象两个模板参数：

std::map<int,string> school;

这里定义了一个用int作为索引，并拥有相关联的指向string的指针。

 

3、map的构造函数

a.插入元素

//定义一个map对象
std::map<int,string> school;

//第一种，用insert函数插入pair
school.insert(pair<int,string>(0,"zero"));

//第二种，用insert函数插入value_type数据
school.insert(map<int,string>::value_type(1,"one"));

//第三种，用array方法插入
school[2] = "two";
school[3] = "three";

b、查找元素

//当所查找的关键字key出现时，它返回数据所在对象的位置，如果没有，返回iter与end函数的值相同
//利用find返回指向当前查找元素的位置的迭代器，找不到则返回map::end()位置
iter = school.find("1");
if(iter != school.end())
    cout<<"the value is"<<iter->second<<endl;
esle
    cout<<"do not find"<<endl;

c、删除与清空元素

//迭代器删除
iter = school.find("2");
school.erase(iter);

//用关键字删除,删除成功返回1，否则返回0；
int n = school.erase("2);

//用迭代器范围删除
school.erase(school.begin(),school.end());  //将整个school清空

d、map的基本操作函数

     begin()         //返回指向map头部的迭代器

     clear(）        //删除所有元素

     count()         //返回指定元素出现的次数

     empty()         //如果map为空则返回true

     end()           //返回指向map末尾的迭代器

     equal_range()   //返回特殊条目的迭代器对

     erase()         //删除一个元素

     find()          //查找一个元素

     get_allocator() //返回map的配置器

     insert()        //插入元素

     key_comp()      //返回比较元素key的函数

     lower_bound()   //返回键值>=给定元素的第一个位置

     max_size()      //返回可以容纳的最大元素个数

     rbegin()        //返回一个指向map尾部的逆向迭代器

     rend()          //返回一个指向map头部的逆向迭代器

     size()          //返回map中元素的个数

     swap()           //交换两个map

     upper_bound()    //返回键值>给定元素的第一个位置

     value_comp()     //返回比较元素value的函数

 

二、HashMap

HashMap简介

HashMap简称哈希表，主要思想和流程如下：

HashMap在添加值时需要给定两个参数，一个是key，一个是value。为了能很快的通过key值找到对应的value，因此有必要建立一个key值和内存指针的映射，举个简单的例子，如果说key值是int型，那么其实最简单的方式就是定义一个数组，以这个key值作为下标，value作为内存中的值。然而由于key值可能会很大，或者是string或着其他类型的值，因此就不能单纯的简单对应了，这时候就需要做一个转换。这个在Java和C#中是通过一个int HashCode()的函数实现的。具体的实现可能是通过地址、字符串或数字算出来的值，然后如果是自己定义的对象，则需要自己实现HashCode()和equal().

注意，hashcode的实现需要满足以下要求：

a、如果两个对象equals相等，那么这两个对象的HashCode一定也相同

b、如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置

 

hash_map(size_type n) 如果讲究效率，这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。n越大，效率越高，但是内存消耗也越大。

const_iterator find(const key_type& k) const. 用查找，输入为键值，返回为迭代器。

data_type& operator[](const key_type& k) . 这是我最常用的一个函数。因为其特别方便，可像使用数组一样使用。不过需要注意的是，当你使用[key ]操作符时，如果容器中没有key元素，这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，你可以使用find。如果你希望插入该元素时，你可以直接使用[]操作符。

insert 函数。在容器中不包含key值时，insert函数和[]操作符的功能差不多。但是当容器中元素越来越多，每个桶中的元素会增加，为了保证效率，hash_map会自动申请更大的内存，以生成更多的桶。因此在insert以后，以前的iterator有可能是不可用的。
erase 函数。在insert的过程中，当每个桶的元素太多时，hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后，其他元素的iterator还是可用的。