Unordered_set Flashcards
Iterators
begin
cbegin( )
returns an iterator to the beginning
Parameters
(none)
Return value
Iterator to the first element.
Complexity
Constant.
Iterators
end
cend( )
returns an iterator to the end
Parameters
(none)
Return value
Iterator to the element following the last element.
Complexity
Constant.
Capacity
empty( )
checks whether the container is empty
Parameters
(none)
Return value
true if the container is empty, false otherwise
Complexity
Constant.
Capacity
size( )
returns the number of elements
Parameters
(none)
Return value
The number of elements in the container.
Complexity
Constant.
Capacity
max_size( )
returns the maximum possible number of elements
Parameters
(none)
Return value
Maximum number of elements.
Complexity
Constant.
Modifiers
clear( )
clears the contents
Parameters
(none)
Return value (none)
Complexity
Linear in the size of the container, i.e., the number of elements.
Modifiers
insert( )
inserts elements or nodes
Parameters
hint - iterator, used as a suggestion as to where to insert the content
value - element value to insert
first, last - range of elements to insert
ilist - initializer list to insert the values from
nh - a compatible node handle
Type requirements
-InputIt must meet the requirements of LegacyInputIterator.
Return value
1-2) Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.
3-4) Returns an iterator to the inserted element, or to the element that prevented the insertion.
5-6) (none)
7) Returns an insert_return_type with the members initialized as follows: if nh is empty, inserted is false, position is end(), and node is empty. Otherwise if the insertion took place, inserted is true, position points to the inserted element, and node is empty. If the insertion failed, inserted is false, node has the previous value of nh, and position points to an element with a key equivalent to nh.key().
8) End iterator if nh was empty, iterator pointing to the inserted element if insertion took place, and iterator pointing to an element with a key equivalent to nh.key() if it failed.
Exceptions
1-4) If an exception is thrown by any operation, the insertion has no effect.
This section is incomplete
Reason: cases 5-8
Complexity
1-4) Average case: O(1), worst case O(size())
5-6) Average case: O(N), where N is the number of elements to insert. Worst case: O(N*size()+N)
7-8) Average case: O(1), worst case O(size())
Modifiers
emplace( )
constructs element in-place
Parameters
args - arguments to forward to the constructor of the element
Return value
Returns a pair consisting of an iterator to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place (true if insertion happened, false if it did not).
Exceptions
If an exception is thrown by any operation, this function has no effect.
Complexity
Amortized constant on average, worst case linear in the size of the container.
Modifiers emplace_hint( )
constructs elements in-place using a hint
Parameters
hint - iterator, used as a suggestion as to where to insert the new element
args - arguments to forward to the constructor of the element
Return value
Returns an iterator to the newly inserted element.
If the insertion failed because the element already exists, returns an iterator to the already existing element with the equivalent key.
Exceptions
If an exception is thrown by any operation, this function has no effect (strong exception guarantee).
Complexity
Amortized constant on average, worst case linear in the size of the container
Modifiers
erase( )
erases elements
Parameters
pos - iterator to the element to remove
first, last - range of elements to remove
key - key value of the elements to remove
Return value
1-2) Iterator following the last removed element.
3) Number of elements removed (0 or 1).
Exceptions
1,2) Throws nothing.
3) Any exceptions thrown by the Compare object.
Complexity
Given an instance c of unordered_set:
1) Average case: constant, worst case: c.size()
2) Average case: std::distance(first, last), worst case: c.size()
3) Average case: c.count(key), worst case: c.size()
Modifiers
swap( )
swaps the contents
Parameters
other - container to exchange the contents with
Return value
(none)
Exceptions
Any exception thrown by the swap of the Hash or KeyEqual objects.
(until C++17) noexcept specification: noexcept(std::allocator_traits::is_always_equal::value && std::is_nothrow_swappable::value && std::is_nothrow_swappable::value) (since C++17) Complexity Constant.
Modifiers
extract( )
extracts nodes from the container
Parameters
position - a valid iterator into this container
x - a key to identify the node to be extracted
Return value
A node handle that owns the extracted element, or empty node handle in case the element is not found in overload (2)
Complexity
1,2) Average case O(1), worst case O(a.size()).
Modifiers
merge( )
splices nodes from another container Parameters source - compatible container to transfer the nodes from Return value (none)
Complexity
Average case O(N), worst case O(N*size()+N), where N is source.size().
Lookup
count( )
returns the number of elements matching specific key
Parameters
key - key value of the elements to count
x - a value of any type that can be transparently compared with a key
Return value
1) Number of elements with key key, that is either 1 or 0.
2) Number of elements with key that compares equivalent to x.
Complexity
Constant on average, worst case linear in the size of the container.
Lookup
find( )
finds element with specific key
Parameters
key - key value of the element to search for
x - a value of any type that can be transparently compared with a key
Return value
Iterator to an element with key equivalent to key. If no such element is found, past-the-end (see end()) iterator is returned.
Complexity
Constant on average, worst case linear in the size of the container.
Lookup
contains( )
checks if the container contains element with specific key
Parameters
key - key value of the element to search for
x - a value of any type that can be transparently compared with a key
Return value
true if there is such an element, otherwise false.
Complexity
Constant on average, worst case linear in the size of the container.
Lookup equal_range( )
returns range of elements matching a specific key
Parameters
key - key value to compare the elements to
x - a value of any type that can be transparently compared with a key
Return value
std::pair containing a pair of iterators defining the wanted range. If there are no such elements, past-the-end (see end()) iterators are returned as both elements of the pair.
Complexity
Average case linear in the number of elements with the key key, worst case linear in the size of the container.
Bucket interface
begin(size_type)
cbegin(size_type)
returns an iterator to the beginning of the specified bucket Parameters n - the index of the bucket to access Return value Iterator to the first element.
Complexity
Constant.
Bucket interface
end(size_type)
cend(size_type)
returns an iterator to the end of the specified bucket
Parameters
n - the index of the bucket to access
Return value
iterator to the element following the last element
Complexity
Constant
Bucket interface
bucket_count( )
returns the number of buckets
Parameters
(none)
Return value
The number of buckets in the container.
Complexity
Constant.
Bucket interface
max_bucket_count( )
returns the maximum number of buckets
Parameters
(none)
Return value
Maximum number of buckets.
Complexity
Constant.
Bucket interface
bucket_size( )
returns the number of elements in specific bucket Parameters n - the index of the bucket to examine Return value The number of elements in the bucket n.
Complexity
Linear in the size of the bucket n.
Bucket interface
bucket( )
returns the bucket for specific key Parameters key - the value of the key to examine Return value Bucket index for the key key.
Complexity
Constant.
Hash policy
load_factor( )
returns average number of elements per bucket
Parameters
(none)
Return value
Average number of elements per bucket.
Complexity
Constant.
Hash policy
max_load_factor( )
manages maximum average number of elements per bucket Parameters ml - new maximum load factor setting Return value 1) current maximum load factor.
2) none.
Complexity
Constant
Hash policy
rehash( )
reserves at least the specified number of buckets and regenerates the hash table Parameters count - new number of buckets Return value (none)
Complexity
Average case linear in the size of the container, worst case quadratic.
Hash policy
reserve( )
reserves space for at least the specified number of elements and regenerates the hash table Parameters count - new capacity of the container Return value (none)
Complexity
Average case linear in the size of the container, worst case quadratic.
Observers hash_function( )
returns function used to hash the keys
Parameters
(none)
Return value
The hash function.
Complexity
Constant.
Observers
key_eq( )
returns the function used to compare keys for equality
Parameters
(none)
Return value
The key comparison function.
Complexity
Constant.
