Multiset 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.
Iterators
rbegin
crbegin( )
returns a reverse iterator to the beginning
Parameters
(none)
Return value
Reverse iterator to the first element.
Complexity
Constant.
Iterators
rend
crend( )
returns a reverse iterator to the end
Parameters
(none)
Return value
Reverse 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 start the search (until C++11)
iterator to the position before which the new element will be inserted (since C++11)
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-4) Returns an iterator to the inserted element.
5-6) (none)
7,8) End iterator if nh was empty, iterator pointing to the inserted element otherwise.
Exceptions
1-4) If an exception is thrown by any operation, the insertion has no effect.
This section is incomplete
Reason: cases 5-6
Complexity
1-2) Logarithmic in the size of the container, O(log(size())).
3-4) Amortized constant if the insertion happens in the position just after the hint, logarithmic in the size of the container otherwise.
(until C++11)
3-4) Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.
(since C++11)
5-6) O(N*log(size() + N)), where N is the number of elements to insert.
7) Logarithmic in the size of the container, O(log(size())).
8) Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.
Modifiers
emplace( )
constructs element in-place
Parameters
args - arguments to forward to the constructor of the element
Return value
Returns an iterator to the inserted element.
Exceptions
If an exception is thrown by any operation, this function has no effect.
Complexity
Logarithmic in the size of the container.
Modifiers emplace_hint( )
constructs elements in-place using a hint
Parameters
hint - iterator to the position before which the new element will be inserted
args - arguments to forward to the constructor of the element
Return value
Returns an iterator to the newly inserted element.
Exceptions
If an exception is thrown by any operation, this function has no effect (strong exception guarantee).
Complexity
Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before hint.
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.
Exceptions
1,2) Throws nothing.
3) Any exceptions thrown by the Compare object.
Complexity
Given an instance c of multiset:
1) Amortized constant
2) log(c.size()) + std::distance(first, last)
3) log(c.size()) + c.count(key)
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 Compare objects.
(until C++17) noexcept specification: noexcept(std::allocator_traits::is_always_equal::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) amortized constant
2) log(a.size())
Modifiers
merge( )
splices nodes from another container Parameters source - compatible container to transfer the nodes from Return value (none)
Exceptions
Does not throw unless comparison throws.
Complexity
N*log(size()+N)), where N is source.size().
