Sets

Motivating example: count the number of unique words in some text.

Common operation in real world: e.g., identify the vocabulary in a document, or count the unique types of objects
Common operation in computer science: e.g., unique number of visitors to a website, plagiarism detection in code

Sets only answer the question of membership (no duplicates).

Operations:

find(elem)
insert(elem)
erase(elem)

Comparison to Vector

Does not maintain order
No duplicates
Really fast at finding membership

Looping over Sets

Sets don't have indices, so we use a for-each loop
Iterates in sorted order (alphabetical order for strings)
Can't edit while we iterate (general property of for-each loops)

#include "set.h"

Set<string> friends; 
friends.insert("xyz"); 
friends.add("abc"); 
//prints in alphabetical order 
for (string myFriend : friends) {
  cout << "Hi " << myFriend << endl; 
}

Recall the common set operations (show Venn diagrams)

Union: set1 + set2
Diff: set1 - set2
Intersection: set1 n set2

Member functions

`s.add(value)`	`s.insert(value)`	O(log N)	adds an element to the set if it was not already there.
`s.clear()`	`s.clear()`	O(N)	removes all elements from this set.
`s.contains(value)`	`s.find(value) != s.end()`	O(log N)	returns true if value is in set.
`s.equals(set)`	`s == set`	O(N)	returns true if the two sets contain exactly the same elements (number and value).
`s.first()`	`*s.begin()`	O(log N)	returns the first value in the set in order.
`s.isEmpty()`	`s.empty()`	O(1)	returns true if the set contains no elements.
`s.isSubsetOf(s2)`	`no counterpart (can write your own subroutine)`	O(N)	returns true if all the elements in s are also present in s2.
`s.remove(value)`	`s.erase(value)`	O(log N)	removes an element from this set.
`s.size()`	`s.size()`	O(1)	returns the number of elements in the set.
`s.toString()`	`no counterpart (can write your own subroutine)`	O(N)	converts the set to a printable string representation.

ADT soup: When to use what?

1-D or 2-D? If 2-D, use Grid.
If 1-D, do I care only about membership? If yes, use Set
If 1-D and I need duplicates and care about order of elements (different from the lexicographic order):
- Which elements do I need to access? If frequent looping over middle elements, use Vector. If only use last element, use Stack. If only use first element, use Queue