C++ का unordered_set

unordered_set क्या है?

std::unordered_set बिना किसी guaranteed order के unique elements store करता है, internally एक hash table इस्तेमाल करते हुए। यह average O(1) insertion, deletion, और lookup offer करता है, sorted order की ज़रूरत न होने पर set से तेज़।

उदाहरण: What is unordered_set?

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s = {3, 1, 2}; // hash table, no guaranteed order
	std::cout << s.size() << std::endl;
	return 0;
}

Insert और Erase करना

insert() और erase() std::set जैसे behave करते हैं लेकिन एक tree की बजाय hash buckets पर operate करते हैं, इसलिए insertion order और iteration order के बीच कोई relationship नहीं है।

यह trade-off average constant-time insertion और lookup के बदले ordering guarantees छोड़ देता है।

उदाहरण: Inserting and Erasing

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s;
	s.insert(5);
	s.erase(5); // operates on hash buckets, not a tree
	std::cout << s.size() << std::endl;
	return 0;
}

Hashing और Performance

unordered_map की तरह, unordered_set elements को buckets में hash करता है। Average-case operations O(1) हैं, लेकिन एक poor hash या कई collisions worst case O(n) तक degrade हो सकते हैं।

अपने key type के लिए एक अच्छा hash function चुनना या customize करना actually वह average O(1) performance achieve करने के लिए essential है।

उदाहरण: Hashing & Performance

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s;
	s.insert(42); // hashed into a bucket -- average O(1)
	std::cout << (s.count(42) > 0) << std::endl;
	return 0;
}

Iterating (Unordered)

एक unordered_set iterate करना elements को hash table layout से determined एक unspecified order में visit करता है। यह इसके insertion order से match करने पर depend न करें।

अगर आपको elements एक predictable order में चाहिए, std::set (या manually एक copy sort करना) इसकी बजाय बेहतर choice है।

उदाहरण: Iterating (Unordered)

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s = {3, 1, 2};
	for (int n : s) { // order determined by hash layout, not insertion or value
		std::cout << n << " ";
	}
	std::cout << std::endl;
	return 0;
}

एक unordered_set Search करना

find() और count() hashing के जरिए average O(1) time में elements locate करते हैं, यही वजह है कि unordered_set बड़े datasets पर fast membership tests के लिए एक common choice है।

यह unordered_set को natural choice बनाता है जब भी goal बस order की परवाह किए बिना 'क्या यह value यहाँ exist करती है' यह देखना हो।

उदाहरण: Searching an unordered_set

#include <iostream>
#include <unordered_set>

int main() {
	std::unordered_set<int> s = {1, 2, 3};
	if (s.find(2) != s.end()) { // average O(1) via hashing
		std::cout << "Found" << std::endl;
	}
	return 0;
}