class HashSet<ValueType>
Set
class except for the fact that it uses a hash table as its underlying
representation. The advantage of the HashSet
class is that
it operates in constant time, as opposed to the O(log N)
time for the Set
class. The disadvantage of
HashSet
is that range-based for loops and other iteration patterns
will access the elements in an unpredictable and seemingly random order.
The HashSet operations to add/access/remove an element run in O(1) time.
Constructor | ||
O(1) | Initializes a new HashSet of the specified element type. | |
Methods | ||
O(1) | Adds an element to this HashSet, if it was not already there. | |
O(N) | Removes all elements from this HashSet. | |
O(1) | Returns true if the specified value is in this HashSet. |
|
O(N) | Subtracts otherSet from this HashSet. The difference removes those elements that appear in otherSet . |
|
O(N) | Returns true if the two sets contain the same elements. |
|
O(1) | Returns the first value in this HashSet in the order established by a for-each loop. | |
O(N) | Intersects otherSet with this HashSet. The intersection retains only those elements also contained in otherSet . |
|
O(1) | Returns true if this HashSet contains no elements. |
|
O(N) | Returns true if this HashSet is a subset of otherSet . |
|
O(N) | Returns true if this HashSet is a superset of otherSet . |
|
O(1) | Returns the last value in this HashSet in the order established by a for-each loop. | |
O(N) | Calls fn(value) for each element of this HashSet. |
|
O(1) | Removes an element from this HashSet. | |
O(1) | Returns the number of elements in this HashSet. | |
O(N) | Returns a printable string representation of this set. | |
O(N) | Unions otherSet with this HashSet. 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) | Creates a new set which is the union of set with the single value . |
|
O(N) | Adds all of the elements from set2 to set1 . |
|
O(1) | Adds the single value to set . |
|
O(N) | Creates a new set which is the difference of set1 minus set2 . |
|
O(N) | Creates a new set which is the difference of set minus the single value .
| |
O(N) | Removes the elements of set2 from set1 . |
|
O(1) | Removes the single value from set . |
|
O(N) | Creates a new set which is the intersection of set1 and set2 . |
|
O(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) | Reads the contents of the given input stream into set . |
HashSet();
Usage:
HashSet<ValueType> set; HashSet<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 HashSet.
Usage:
if (set.contains(value)) ...
HashSet& difference(const HashSet& set2);
set2
. Returns a reference to this HashSet, which has been modified in place. If you want a new HashSet, consider set1 - set2
instead.
Usage:
set1.difference(set2);
bool equals(const HashSet& set2) const;
true
if the two HashSets 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();
HashSet& intersect(const HashSet& set2);
set2
. Returns a reference to this HashSet, which has been modified in place. If you want a new HashSet, consider set1 * set2
instead.
Usage:
set1.intersect(set2);
bool isEmpty() const;
true
if this HashSet contains no elements.
Usage:
if (set.isEmpty()) ...
bool isSubsetOf(const HashSet& set2) const;
true
if every element of this HashSet is
contained in set2
.
Usage:
if (set1.isSubsetOf(set2)) ...
bool isSupersetOf(const HashSet& set2) const;
true
if every element of set2
is
contained in this HashSet.
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 unpredictable order.
Usage:
set.mapAll(fn);
void remove(const ValueType& value);
Usage:
set.remove(value);
int size() const;
Usage:
count = set.size();
string toString() const;
"{value1, value2, value3}"
.
The values are listed in unpredictable order.
Usage:
string str = set.toString();
HashSet& unionWith(const HashSet& set2);
set2
. Returns a reference to this HashSet, which has been modified in place. If you want a new HashSet, consider set1 + set2
instead.
Usage:
set1.unionWith(set2);
for (ValueType elem : set)
Usage:
for (ValueType elem : set) { cout << elem << endl; }
bool operator==(const HashSet& set2) const;
true
if set1
and set2
contain the same elements.
Usage:
set1 == set2
bool operator!=(const HashSet& set2) const;
true
if set1
and set2
are different.
Usage:
set1 != set2
HashSet operator+(const HashSet& set2) const; HashSet operator+(const ValueType& element) const;
set1
with set2
(or with the single value
).
Usage:
set1 + set2 set1 + value
HashSet operator*(const HashSet& set2) const;
set1
and set2
.
Usage:
set1 * set2
HashSet operator-(const HashSet& set2) const; HashSet operator-(const ValueType& element) const;
set1
minus set2
(or minus the single value
).
Usage:
set1 - set2 set1 - value
HashSet& operator+=(const HashSet& set2); HashSet& operator+=(const ValueType& value);
set2
(or the single value
) to set1
.
Usage:
set1 += set2; set1 += value;
HashSet& operator*=(const HashSet& set2);
set1
that are not present in
set2
.
Usage:
set1 *= set2;
HashSet& operator-=(const HashSet& set2); HashSet& operator-=(const ValueType& value);
set2
(or the single value
) from set1
.
Usage:
set1 -= set2; set1 -= value;
ostream& operator<<(const HashSet& 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 unpredictable order.
Usage:
cout << set << endl;
istream& operator>>(HashSet& 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) ...