Map

Question 1

Element access

at( )

Answer 1

access specified element with bounds checking
Parameters
key - the key of the element to find
Return value
Reference to the mapped value of the requested element

Exceptions
std::out_of_range if the container does not have an element with the specified key

Complexity
Logarithmic in the size of the container.

Question 2

Element access

operator[]

Answer 2

access or insert specified element
Parameters
key	-	the key of the element to find
Return value
Reference to the mapped value of the new element if no element with key key existed. Otherwise a reference to the mapped value of the existing element whose key is equivalent to key.

Exceptions
If an exception is thrown by any operation, the insertion has no effect

Complexity
Logarithmic in the size of the container.

Question 3

Iterators
begin
cbegin( )

Answer 3

returns an iterator to the beginning
Parameters
(none)

Return value
Iterator to the first element.

Complexity
Constant.

Question 4

Iterators
end
cend( )

Answer 4

returns an iterator to the end
Parameters
(none)

Return value
Iterator to the element following the last element.

Complexity
Constant.

Question 5

Iterators
rbegin
crbegin( )

Answer 5

returns a reverse iterator to the beginning
Parameters
(none)

Return value
Reverse iterator to the first element.

Complexity
Constant.

Question 6

Iterators
rend
crend( )

Answer 6

returns a reverse iterator to the end
Parameters
(none)

Return value
Reverse iterator to the element following the last element.

Complexity
Constant.

Question 7

Capacity

empty( )

Answer 7

checks whether the container is empty
Parameters
(none)

Return value
true if the container is empty, false otherwise

Complexity
Constant.

Question 8

Capacity

size( )

Answer 8

returns the number of elements
Parameters
(none)

Return value
The number of elements in the container.

Complexity
Constant.

Question 9

Capacity

max_size( )

Answer 9

returns the maximum possible number of elements
Parameters
(none)

Return value
Maximum number of elements.

Complexity
Constant.

Question 10

Modifiers

clear( )

Answer 10

clears the contents
Parameters
(none)

Return value
(none)

Complexity
Linear in the size of the container, i.e., the number of elements.

Question 11

Modifiers

insert( )

Answer 11

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-3) 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.
4-6) Returns an iterator to the inserted element, or to the element that prevented the insertion.
7-8) (none)
9) 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().
10) 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-6) If an exception is thrown by any operation, the insertion has no effect.
This section is incomplete
Reason: cases 7-10
Complexity
1-3) Logarithmic in the size of the container, O(log(size())).
4-6) Amortized constant if the insertion happens in the position just after the hint, logarithmic in the size of the container otherwise.
(until C++11)
4-6) Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.
(since C++11)
7-8) O(N*log(size() + N)), where N is the number of elements to insert.
9) Logarithmic in the size of the container, O(log(size())).
10) Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.

Question 12

Modifiers

insert_or_assign( )

Answer 12

inserts an element or assigns to the current element if the key already exists
Parameters
k - the key used both to look up and to insert if not found
hint - iterator to the position before which the new element will be inserted
obj - the value to insert or assign
Return value
1,2) The bool component is true if the insertion took place and false if the assignment took place. The iterator component is pointing at the element that was inserted or updated
3,4) Iterator pointing at the element that was inserted or updated
Complexity
1,2) Same as for emplace
3,4) Same as for emplace_hint

Question 13

Modifiers

emplace( )

Answer 13

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
Logarithmic in the size of the container.

Question 14

Modifiers
emplace_hint( )

Answer 14

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.

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
Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before hint.

Question 15

Modifiers
try_emplace( )

Answer 15

inserts in-place if the key does not exist, does nothing if the key exists
Parameters
k - the key used both to look up and to insert if not found
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
1,2) Same as for emplace
3,4) Same as for emplace_hint
Complexity
1,2) Same as for emplace
3,4) Same as for emplace_hint

Question 16

Modifiers

erase( )

Answer 16

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.

Question 17

Modifiers

swap( )

Answer 17

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.

Question 18

Modifiers

extract( )

Answer 18

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())

Question 19

Modifiers

merge( )

Answer 19

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().

Question 20

Lookup

count( )

Answer 20

returns the number of elements matching specific key
Parameters
key - key value of the elements to count
x - alternative value to compare to the keys
Return value
Number of elements with key that compares equivalent to key or x, which is either 1 or 0 for (1).

Complexity
Logarithmic in the size of the container.

Question 21

Lookup

find( )

Answer 21

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
Logarithmic in the size of the container.

Question 22

Lookup

contains( )

Answer 22

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
Logarithmic in the size of the container.

Question 23

Lookup
equal_range( )

Answer 23

returns range of elements matching a specific key
Parameters
key - key value to compare the elements to
x - alternative value that can be compared to Key
Return value
std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key.

If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.

Complexity
Logarithmic in the size of the container.

Question 24

Lookup

lower_bound( )

Answer 24

returns an iterator to the first element not less than the given key
Parameters
key - key value to compare the elements to
x - alternative value that can be compared to Key
Return value
Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.

Complexity
Logarithmic in the size of the container.

Question 25

Lookup

upper_bound( )

Answer 25

returns an iterator to the first element greater than the given key
Parameters
key - key value to compare the elements to
x - alternative value that can be compared to Key
Return value
Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned.

Complexity
Logarithmic in the size of the container.

Question 26

Observers

key_comp( )

Answer 26

returns the function that compares keys
Parameters
(none)

Return value
The key comparison function object.

Complexity
Constant.

Question 27

Observers

value_comp( )

Answer 27

returns the function that compares keys
Parameters
(none)

Return value
The value comparison function object.

Complexity
Constant.