2020-11-20

map和unordered_map的区别

了解map和unordered_map的区别

map和unordered_map的区别

解决问题

输入是某电话公司的若干客户姓名及电话号码，中间用逗号分隔，然后是若干要查询的客户姓名，输出是这些查询的客户姓名及其电话

那么这样一看，我们会选择map，而不是选择暴力解法
因此可以知道map是一种有利于查询的数据结构的一种
所以可以得到答案，很显然答案中有些函数我们都没有利用过

#include<iostream>
#include<map>
#include<string>
using namespace std;

int main(){
  int len;
  cin >> len;
  map<string,string>;
  for(int i = 0;i < len;++i){
    cin.get();//保留回车在输入流队列中的,前面cin后，最后的'\n'还在，需要手动去掉。
    string name;
    getline(cin,name,',')//以','为分隔符，将姓名提取出来,从输入流中读取一行字符，读到终止符时会将'0'存入结果缓冲区中，作为输入的终止。终止符可以是默认的终止符，也可以是定义的终止符
    //getline(<字符数组chs>，<读取字符的个数n>，<终止符>)
    string phone;
    cin>>phone;
    m[name] = phone;
  }
  cin >> len;
  for(int i = 0;i < len;++i){
    string name;
    cin >> name;
    if(m.find(name) == m.end()){
      cout<< name << ":NO" << endl;
    }else{
      cout<< name << ":" <<m[name] << endl;
    }
  }
  system("pause");
  return 0;
}

c++有哈希表吗?

有，hash_map是一个聚合类，它继承自_Hash类，包括一个vector，一个list和一个pair，其中vector用于保存桶，list用于进行冲突处理，pair用于保存key->value结构，但是新版的hash_map都是unordered_map。所以就去了解unordered_map和map

pair是啥？

类模板：template<classT1,class T2>struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

功能：pair将一对值(T1和T2)组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；// 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

unordered_map和map区别时间复杂度空间复杂度

map和unordered_map的区别：

运行效率方面：unordered_map最高，而map效率较低但提供了稳定效率和有序的序列。占用内存方面：map内存占用略低，unordered_map内存占用略高,而且是线性成比例的。

Map的优点：

有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map的优点：

因为内部实现了哈希表，因此其查找速度非常的快缺点：哈希表的建立比较耗费时间适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

总结：

内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。但是unordered_map执行效率要比map高很多对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的

map和unordered_map的使用

unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，但是就外部使用来说却是一致的。

unordered_map和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的函数

使用删除之前的迭代器定位下一个元素。STL建议的使用方式

for(ITER iter=mapTest.begin();iter!=mapTest.end();)
{
  cout<<iter->first<<":"<<iter->second<<endl;
  mapTest.erase(iter++);
}

Hexo

map和unordered_map的区别

map和unordered_map的区别

解决问题

c++有哈希表吗?

pair是啥？

unordered_map和map区别时间复杂度空间复杂度

map和unordered_map的区别：

Map的优点：

unordered_map的优点：

map和unordered_map的使用

Multiset和set的区别

MultiSet

Set