class Set<ValueType>
The set uses a binary search tree (BST) structure internally.
Because of this choice of internal representation, the ValueType
for the type of elements stored in a Set
must define a natural ordering through a less
function and/or <
operator so that the elements can be compared and ordered. The rangebased for loop will iterate over the elements in sorted order. The Set operations to add/find/remove an element run in O(logN) time.
Constructor  
O(1)  Initializes a new set of the specified element type.  
Methods  
O(log N)  Adds an element to this set, if it was not already there.  
O(N)  Removes all elements from this set.  
O(log N)  Returns true if the specified value is in this set. 

O(Nlog N)  Subtracts otherSet from this set. The difference removes those elements that appear in otherSet . 

O(N)  Returns true if the two sets contain the same elements. 

O(log N)  Returns the first value in this set when considered in sorted order.  
O(N log N)  Intersects otherSet with this set. The intersection retains only those elements also contained in otherSet . 

O(1)  Returns true if this set contains no elements. 

O(N)  Returns true if this set is a subset of otherSet . 

O(N)  Returns true if this set is a superset of otherSet . 

O(log N)  Returns the last value in this set when considered in sorted order.  
O(N)  Calls fn(value) for each element of this set. 

O(log N)  Removes an element from this set.  
O(1)  Returns the number of elements in this set.  
O(N)  Returns a printable string representation of this set.  
O(N log N)  Unions otherSet with this set. The union adds all elements from otherSet . 

Operators  
O(N)  Iterates through the elements in a set.  
O(N)  Evaluates to true if set1 and set2 contain the same elements. 

O(N)  Evaluates to true if set1 and set2 are different. 

O(N)  Creates a new set which is the union of set1 with set2 . 

O(N log N)  Creates a new set which is the union of set with the single value . 

O(N log N)  Adds all of the elements from set2 to set1 . 

O(log N)  Adds the single value to set . 

O(N log N)  Creates a new set containing the elements in set1 that aren't in set2 . 

O(log N)  Creates a new set which contains all values in set minus value .
 
O(N log N)  Removes the elements of set2 from set1 . 

O(log N)  Removes the single value from set . 

O(N log N)  Creates a new set which is the intersection of set1 and set2 . 

O(N log N)  Removes any elements from set1 that are not present in set2 . 

O(N)  Outputs the contents of set to the given output stream. 

O(N log N)  Reads the contents of the given input stream into set . 
Set();
Usage:
Set<ValueType> set; Set<ValueType> set = { value1, value2, value3 };
void add(ValueType value);
Usage:
set.add(value);
void clear();
Usage:
set.clear();
bool contains(ValueType value) const;
true
if the specified value is in this set.
Usage:
if (set.contains(value)) ...
Set& difference(const Set& set2);
set2
. Returns a reference to this set, which has been modified in place. If you want a new set, consider set1  set2
instead.
Usage:
set1.difference(set2);
bool equals(const Set& set2) const;
true
if the two sets contain exactly the same element values.
Identical in behavior to the ==
operator.
Usage:
if (set1.equals(set2)) ...
ValueType first() const;
first
signals an error.
Usage:
ValueType value = set.first();
Set& intersect(const Set& set2);
set2
. Returns a reference to this set, which has been modified in place. If you want a new set, consider set1 * set2
instead.
Usage:
set.intersect(set2);
bool isEmpty() const;
true
if this set contains no elements.
Usage:
if (set.isEmpty()) ...
bool isSubsetOf(const Set& set2) const;
true
if every element of this set is
contained in set2
.
Usage:
if (set1.isSubsetOf(set2)) ...
bool isSupersetOf(const Set& set2) const;
true
if every element of set2
is
contained in this set.
Usage:
if (set1.isSupersetOf(set2)) ...
Documented: Fall Quarter 2020
ValueType last() const;
last
signals an error.
Usage:
ValueType value = set.last();
Documented: Fall Quarter 2020
void mapAll(std::function<void (const ValueType&)> fn) const;
fn(value)
for each one. The elements are processed in sorted order.
Usage:
set.mapAll(fn);
Documented: Fall Quarter 2020
void remove(ValueType value);
Usage:
set.remove(value);
int size() const;
Usage:
int count = set.size();
string toString() const;
"{value1, value2, value3}"
.
The values are listed in sorted order.
Usage:
string str = set.toString();
Set& unionWith(const Set& set2);
set2
. Returns a reference to this set, which has been modified in place. If you want a new set, consider set1 + set2
instead.
Usage:
set1.unionWith(set2);
for (ValueType elem : set)
Usage:
for (ValueType elem : set) { cout << elem << endl; }
Documented: Fall Quarter 2020
bool operator==(const Set& set2) const;
true
if set1
and set2
contain the same elements.
Usage:
set1 == set2
bool operator!=(const Set& set2) const;
true
if set1
and set2
are different.
Usage:
set1 != set2
Set operator+(const Set& set2) const; Set operator+(ValueType element) const;
set1
with set2
(or with the single value
).
Usage:
set1 + set2 set1 + value
Set operator*(const Set& set2) const;
set1
and set2
.
Usage:
set1 * set2
Set operator(const Set& set2) const; Set operator(ValueType value) const;
set1
minus set2
(or minus the single value
).
Usage:
set1  set2 set1  value
Set& operator+=(const Set& set2); Set& operator+=(ValueType value);
set2
(or the single value
) to set1
.
Usage:
set1 += set2; set1 += value;
Set& operator*=(const Set& set2);
set1
that are not present in
set2
.
Usage:
set1 *= set2;
Set& operator=(const Set& set2); Set& operator=(ValueType value);
set2
(or the single value
) from set1
.
Usage:
set1 = set2; set1 = value;
ostream& operator<<(const Set& set);Outputs the contents of
set
to the given output stream.
The output is in the form {value1, value2, value3}
where elements are listed in sorted order.
Usage:
cout << set << endl;
Documented: Fall Quarter 2020
istream& operator>>(Set& set);Reads the contents of the given input stream into
set
. Any previous
contents of the set are replaced.
The input is expected to be in the form {value1, value2, value3}
. If unable to read a proper
set from the stream, the operation results in a stream fail state.
Usage:
if (infile >> set) ...
Documented: Fall Quarter 2020