【C++ unordered_map】leetcode常用的哈希表操作_underr map hash

目录

1、声明 unordered_map hash;,value>

2、访问 hash[key];

3、增加（插入）元素 hash.insert(pair(key,value));,vtype>

4、删除元素 hash.erase(it pos)；hash.erase(key);

5、改变元素的值 hash[key]=val;                                                                                

6、查找元素 hash.find(key);                                                                                      

7、遍历                                                                                          

 8.迭代器

 9、leetcode相关例题

---

前言：unordered_map使用了哈希表的原理实现，其增删查改的时间复杂度都是O(1)，空间复杂度是O（n），适用于快速查找。

1、声明 unordered_map<key,value> hash;

unordered_map: 

#include<unordered_map>
unordered_map<int,int> hash;
//<int,int>里第一个是用来查找的键的数据类型，第二个是值的数据类型，如：
 
unordered_map<int,int> hash;
hash[1]=10;

unordered_set:

#include<unordered_set>
unordered_set<string> set;

2、访问 hash[key];

使用下标访问：

hash[key];

 

3、增加（插入）元素 hash.insert(pair<ktype,vtype>(key,value));

unordered_map插入元素
(因为unordered_map无序，所以无所谓从头尾中间插入 )

unordered_map<char,int> hash; 
 
hash["a"]=1; //方法1：直接用[] hash[key]=value;
 
hash.insert(make_pair("a",1)); //方法2：make_pair hash.insert(make_pair(key,value));
 
hash.insert(pair<char,int>("a",1)); //方法3：pair  hash.insert(pair<char,int>(key,value)); 

 unordered_set插入元素

set.insert("a");

4、删除元素 hash.erase(it pos)；hash.erase(key);

 
hash.erase(hash.begin()); // erasing by iterator
 
mymap.erase("a");  // erasing by key
 
mymap.erase(mymap.find("a"), mymap.end()); // erasing by range

5、改变元素的值 hash[key]=val;                                                                                

hash["a"]=1;
hash["a"]=10;// map修改value

6、查找元素 hash.find(key);                                                                                      

1 查找某个元素的下标

hash.find("a");

如果key在map中，find方法会返回key对应的迭代器。如果key不存在，find会返回end。

2 查找某个元素是否存在

hash.find("a")!=hash.end();  //方法一 hash.find()，存在返回迭代器，不存在返回end()
 
bool a_in_map=hash.count("a")>0?true:false;  //方法二 hash.count() 存在返回1，不存在返回0

如果a在哈希表中，find()返回下标，该表达式为true;如果a不在哈希表中，find返回迭代器end(),该表达式为false

3 查找哈希表内元素总数

int count=hash.size();

7、遍历                                                                                          

unordered_map<int,int> map={
        pair<int,int>(1,2),
        pair<int,int>(3,4)
    };
 
//方式一：值传递遍历
for(pair<int,int> kv:map){
        cout<<kv.first<<kv.second<<endl;
    }
 
for(auto kv:map){
        cout<<kv.first<<kv.second<<endl;
    }
 
//遍历set
for (auto tmp : set)
	{
		cout << tmp;
}
 
 
//方式二：引用传递遍历
(注意：要加const)
for(const pair<int,int>& kv:map){
        cout<<kv.first<<kv.second<<endl;
    }
 
for(auto& kv:map){
        cout<<kv.first<<kv.second<<endl;
    }
 
//方式三：使用迭代器遍历
for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
        cout<<it->first<<it->second<<endl;
    }
 
for(auto it=map.begin();it!=map.end();it++){
        cout<<it->first<<it->second<<endl;
    }
 
//方式四：结构化绑定(c++17特性)
//值传递
for(auto [k,v]:map){
        cout<<k<<v<<endl;
    }
//引用传递
for(auto& [k,v]:map){
        cout<<k<<v<<endl;
    }
//其中，如果只想使用键,值可以用_代替
for(auto& [k,_]:map){
        cout<<k<<endl;
    }
//同理，如果指向只用值，键可以用_代替
for(auto& [_,v]:map){
        cout<<v<<endl;
    }

 8.迭代器

定义一个unordered_map的迭代器：

unordered_map<int,int>::iterator it;

 迭代器可以用来：（1）访问元素（包括遍历，遍历就是逐个访问）（2）某些函数会返回迭代器，我们要用迭代器来接收。

hash.begin();
hash.end();

hash.begin()是迭代器，指向第一个元素。

hash.end()是迭代器，指向的是最后一个元素下一个位置，指向不存在的空间，不可以访问！！

（1）访问元素

auto it=hash.begin();
char b=it->first;
int c=it->second;

（2）遍历

unordered_map<int,int>::iterator it;
for(it=hash.begin();it!=hash.end();it++){
        cout<<it->first<<it->second<<endl;
    }

（3）接收函数的返回值

auto it=hash.erase(hash.begin());
 
auto it=hash.find("a");

 9、leetcode相关例题

哈希思想 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

哈希表和链表：

1429

哈希表和队列：

346

哈希表和平衡树：

1146

918

哈希表和随即队列：

380

381

哈希表和前缀和：

325

1248

哈希表和双指针：

395

76

992

---

参考博客：

(39条消息) C++/C--unordered_map常见用法详解_XDWX的博客-CSDN博客_c unordered_map

(39条消息) c++ map unordered_map使用大全_bitcarmanlee的博客-CSDN博客_unordered_map使用