MENU

枚举+优化(2)——哈希表优化

June 5, 2018 • Read: 3190 • 算法阅读设置

问题:查找一个元素是不是存在?

unordered_set

unordered_set可以想象成一个集合,它提供了三个函数让我们增删查,下面三个函数的时间复杂度都是O(1)

  1. unordered_set::insert()
  2. unordered_set::find()
  3. unordered_set::erase()
#include <unordered_set>
#include <iostream>
using namespace std;
int main()
{
    unordered_set<int> myset;
    myset.insert(3);//插入
    myset.insert(5);
    myset.insert(3);//set不会存入重复的值
    cout<<myset.size()<<endl;
    myset.erase(3);//删除3这个元素
    if(myset.find(3) == myset.end())//如果找到了会返回指向目标元素的迭代器,没找到会返回end()
        cout<<"3 not found"<<endl;
    return 0;
}

unordered_map

同样,unordered_map也提供了增删查函数,时间复杂度也都是O(1)

  1. unordered_map::insert()
  2. unordered_map::find()
  3. unordered_map::erase()
#include <unordered_map>
#include <iostream>
#include <string>
using namespace std;
int main()
{
    unordered_map<string,int> mymap;
    mymap.insert(make_pair("c++",100));
    mymap.insert(make_pair("java",100));//用make_pairh函数把字符串和整数打包成一个pair
    auto it = mymap.find("c++");
    cout<<it->first<< ' ' <<it->second<<endl;
    mymap.erase("java");
    if(mymap.find("java") == mymap.end())
        cout<<"java not found";
    return 0;
}

unordered_map还重载了[]运算符,我们可以把key放在中括号里,像操作数组一样操作unordered_map

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main()
{
    unordered_map<string,int> mymap;
    mymap["c++"] = 100;
    mymap["c++"]++;
    cout<<mymap["c++"]<<endl;
    return 0;
}
Last Modified: November 9, 2021
Archives Tip
QR Code for this page
Tipping QR Code