C++ unordered_set基础概念、对象创建、赋值操作、数据插入、数据删除、代码练习 1 2

unordered_set的底层是哈希表。

增删改查的时间复杂度：

数组 O(n)  二叉树O(logn)  哈希表 O(1)

哈希表的本质原理：哈希键--（哈希函数）--哈希值--（取模、位于）--桶/ID

这里的哈希键一般是任意类型，所以需要先通过哈希函数转换为整数，我们叫他哈希值，再通过取模（一般使用的时候采用位于运算），映射到某个桶中。这样就可以把任意类型的数据存储到数组中，且能够快速查找到。

桶：下标索引又叫桶ID，桶ID是用来索引到某个具体位置的桶。因为用的取模，所以得到的桶ID都是连续的自然数，这样桶可以用数组来实现

哈希冲突：是指两个元素的键不同，但是它们计算得到桶ID一样的情况

哈希冲突解决方案：常见的解决方案，是在一个桶中放多个元素，这样就可以通过哈希算法快速找到桶，再通过遍历桶中所有元素，来实现快速查找。在STL中，数据不是存在一个bucket桶中，而是利用了（bucket<<1）和（bucket<<1 ）+ 1 两个位置，并且把所有桶中元素串联成一个链表，它里面的元素，是从（bucket<<1）的位置作为链表的起点，（bucket<<1 ）+ 1的位置作为链表终点，来存储哈希表中所有桶ID为bucket的节点。所有的哈希表节点会被链接到一个全局的双向链表中，双向链表有个虚拟头结点_Head

哈希表的增删查：哈希表的元素插入，便是直接插入到头部。哈希表的元素查找：从后往前来查找。哈希表的元素删除：先找到桶ID，然后从后往前逆序遍历，执行双向链表的删除操作。

散列容器：unordered_set unordered_map

线形容器：vector、string、list

树形容器：set、multiset、map、multimap

线性模拟树：priority_queue

unordered_set 对象创建，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {// 1 默认构造函数unordered_set<int> s1;cout << "s1: ";printUSet(s1);// 2 初始化列表unordered_set<int> s2_1 = { 9, 8, 7, 6, 5, 1, 2, 3, 4, 6 };cout << "s2_1: ";printUSet(s2_1);unordered_set<int> s2_2 ({ 9, 8, 7, 6, 5, 1, 2, 3, 4, 6, 6, 6, 6, 6 });cout << "s2_2: ";printUSet(s2_2);// 3 迭代器unordered_set<int> s3(s2_1.begin(), s2_1.end());cout << "s3: ";printUSet(s3);// 4 拷贝构造unordered_set<int> s4(s2_2);cout << "s3: ";printUSet(s3);return 0;
}

unordered_set 赋值操作，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {unordered_set<int> s = {9, 8, 5, 2, 1, 1};cout << "s: ";printUSet(s);// = set对象unordered_set<int> s1;s1 = s;cout << "s1: ";printUSet(s1);// = 初始化列表unordered_set<int> s2;s2 = { 9,3, 4, 6, 1, 3 };cout << "s2: ";printUSet(s2);return 0;
}

unordered_set 大小操作，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {unordered_set<int> s1;cout << "s1.empty()" << s1.empty() << endl;cout << "s1.size()" << s1.size() << endl;unordered_set<int> s2 = {5, 6, 8, 3, 1, 3};cout << "s2.empty()" << s2.empty() << endl;cout << "s2.size()" << s2.size() << endl;unordered_multiset<int> s3 = { 5, 6, 8, 3, 1, 3, 1, 1, 1 };cout << "s3.empty()" << s3.empty() << endl;cout << "s3.size()" << s3.size() << endl;return 0;
}

结果见下，助于理解

unordered_set 数据插入，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {unordered_set<int> s1;s1.insert(5); printUSet(s1);s1.insert(4); printUSet(s1);s1.insert(7); printUSet(s1);s1.insert(1); printUSet(s1);s1.insert(2); printUSet(s1);s1.insert(6); printUSet(s1);s1.insert(9); printUSet(s1);vector<int> v = { 1, 9, 9, 0 };s1.insert(v.begin(), v.end());printUSet(s1);return 0;
}

结果见下，助于理解：

5
5 4
5 4 7
5 4 7 1
5 4 7 1 2
5 4 7 1 2 6
5 4 7 9 1 2 6
5 4 7 9 1 2 6 0

最后一行这个结果只是将不重复的0插入了set中，具体原因可见源码截图

unordered_set 数据查找，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {unordered_set<int> s = { 4, 3, 7, 9, 1 };unordered_set<int>::iterator it = s.find(3);if (it != s.end()) {cout << "find: " << *it << endl;}it = s.find(10);if (it == s.end()) {cout << "can't find 10" << endl;}return 0;
}

unordered_set 数据删除，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {unordered_set<int> s = { 8, 4, 3, 7, 1 };s.erase(3);printUSet(s);unordered_set<int>::iterator it = s.find(4);if (it != s.end()) {s.erase(it);}printUSet(s);s = { 13, 14, 56, 72, 34, 45, 23, 67 };unordered_set<int>::iterator it1 = s.find(23);unordered_set<int>::iterator it2 = s.find(14);//s.erase(it1, it2); //不建议用printUSet(s);s.clear();return 0;
}

unordered_set 数据统计，代码见下

#include<iostream>
#include<unordered_set>using namespace std;void printUSet(const unordered_set<int>& s) {for (unordered_set<int>::const_iterator it = s.begin(); it != s.end(); it++) {cout << *it << " ";}cout << endl;}
int main() {unordered_set<int> s = { 5, 6, 7, 8, 9 };for (int i = 0; i < 8; i += 2) {cout << "元素：" << i << "的出现次数为" << s.count(i) << endl;}printUSet(s);return 0;
}

代码练习 1，对应力扣，相交链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*> us;while(headA){us.insert(headA);headA = headA -> next;} while(headB){if(us.find(headB) != us.end()){return headB;}headB = headB->next;}return NULL;}};

代码练习 2，对应力扣，重复DNA序列

class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {unordered_multiset<string> ums;vector<string> ans;for(int i=0; i+10 <= s.size(); ++i){string sub = s.substr(i, 10);ums.insert(sub);if(ums.count(sub) == 2){ans.push_back(sub);}}return ans;}
};