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 range-based 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(N log 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 set with the single value . |
|
O(N log N) | Creates a new set which is the union of set1 with set2 . |
|
O(log N) | Adds the single value to set . |
|
O(N log N) | Adds all of the elements from set2 to set1 . |
|
O(N) | Creates a new set which contains all values in set minus value .
| |
O(N log N) | Creates a new set containing the elements in set1 that aren't in set2 . |
|
O(log N) | Removes the single value from set . |
|
O(N log N) | Removes the elements of set2 from set1 . |
|
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(const ValueType& value);
Usage:
set.add(value);
void clear();
Usage:
set.clear();
bool contains(const 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)) ...
ValueType last() const;
last
signals an error.
Usage:
ValueType value = set.last();
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);
void remove(const 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; }
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+(const 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-(const ValueType& value) const;
set1
minus set2
(or minus the single value
).
Usage:
set1 - set2 set1 - value
Set& operator+=(const Set& set2); Set& operator+=(const 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-=(const 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;
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) ...