Set Collection

• A collection with no duplicate elements
• Objects
  • Are not indexed
  • Do not reveal order of insertion of items
  • Enable efficient search and retrieval of information
  • Allow removal of elements without moving other elements around
• Sets

Operations

• Basic
  • Test for membership (find)
  • Add Element (insert)
  • Remove Element (remove)
• Between Sets
  • Union: $A\cup B=$ elements either in A or B
  • Intersection: $A\cap B=$ elements in both A and B
  • Difference: $A-B=$ elements in A but not B
• Subset
  • Returning a subset
  • Checking if a subset

In C++

	set	unordered_set
Ordered	Yes	No
Common Methods	insert, erase, find, count, size, empty	(those) bucket_size, load_factor
Implementations	Balanced Binary Search Tree (Red Black Tree)	Hash Table
Time Complexity	$O(\log n)$	$O(1)+O(k)$ for hash

Examples

Two Sum Problem

• Given an array and a value, find two elements in the array that add up to the value
• Fundamental version of n sum problem

set<int> s
 
for elem in array
	diff = target - elem
	
	if diff in s
		return (elem, diff)
		
	add elem to s
	
return null

• If you need to return the indexes, use a map of (value → index) instead of the set