List

Question 1

Element access

front( )

Answer 1

access the first element
Parameters
(none)

Return value
reference to the first element

Complexity
Constant

Question 2

Element access]

back( )

Answer 2

access the last element
Parameters
(none)

Return value
Reference to the last element.

Complexity
Constant.

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 or linear. (until C++11)
Constant. (since C++11)

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
Parameters
pos - iterator before which the content will be inserted. pos may be the end() iterator
value - element value to insert
first, last - the range of elements to insert, can’t be iterators into container for which insert is called
ilist - initializer list to insert the values from
Type requirements
-T must meet the requirements of CopyInsertable in order to use overload (1).
-T must meet the requirements of MoveInsertable in order to use overload (2).
-T must meet the requirements of CopyAssignable and CopyInsertable in order to use overload (3).
-T must meet the requirements of EmplaceConstructible in order to use overload (4,5).

Return value
1-2) Iterator pointing to the inserted value
3) Iterator pointing to the first element inserted, or pos if count==0.
4) Iterator pointing to the first element inserted, or pos if first==last.
5) Iterator pointing to the first element inserted, or pos if ilist is empty.
Complexity
1-2) Constant.
3) Linear in count
4) Linear in std::distance(first, last)
5) Linear in ilist.size()

Question 12

Modifiers

emplace( )

Answer 12

constructs element in-place
Parameters
pos - iterator before which the new element will be constructed
args - arguments to forward to the constructor of the element
Type requirements
-T (the container’s element type) must meet the requirements of EmplaceConstructible.
Return value
Iterator pointing to the emplaced element.

Complexity
Constant.

Question 13

Modifiers

erase( )

Answer 13

erases elements
Parameters
pos - iterator to the element to remove
first, last - range of elements to remove
Return value
Iterator following the last removed element.

If pos refers to the last element, then the end() iterator is returned.

If last==end() prior to removal, then the updated end() iterator is returned.

If [first, last) is an empty range, then last is returned.

Exceptions
(none)

Complexity

1) Constant.
2) Linear in the distance between first and last.

Question 14

Modifiers

push_back( )

Answer 14

adds an element to the end
Parameters
value - the value of the element to append
Type requirements
-T must meet the requirements of CopyInsertable in order to use overload (1).
-T must meet the requirements of MoveInsertable in order to use overload (2).
Return value
(none)

Complexity
Constant.

Question 15

Modifiers

emplace_back( )

Answer 15

constructs an element in-place at the end
Parameters
args - arguments to forward to the constructor of the element
Type requirements
-T (the container’s element type) must meet the requirements of EmplaceConstructible.
Return value
(none)

(until C++17)
A reference to the inserted element.

(since C++17)
Complexity
Constant.

Question 16

Modifiers

pop_back( )

Answer 16

removes the last element
Parameters
(none)

Return value
(none)

Complexity
Constant.

Question 17

Modifiers

push_front( )

Answer 17

inserts an element to the beginning
Parameters
value	-	the value of the element to prepend
Return value
(none)

Complexity
Constant.

Question 18

Modifiers

emplace_front( )

Answer 18

constructs an element in-place at the beginning
Parameters
args - arguments to forward to the constructor of the element
Type requirements
-T (the container’s element type) must meet the requirements of EmplaceConstructible.
Return value
(none) (until C++17)
A reference to the inserted element. (since C++17)
Complexity
Constant.

Question 19

Modifiers

pop_front( )

Answer 19

removes the first element
Parameters
(none)

Return value
(none)

Complexity
Constant.

Question 20

Modifiers

resize( )

Answer 20

changes the number of elements stored
Parameters
count - new size of the container
value - the value to initialize the new elements with
Type requirements
-T must meet the requirements of DefaultInsertable in order to use overload (1).
-T must meet the requirements of CopyInsertable in order to use overload (2).
Return value
(none)

Complexity
Linear in the difference between the current size and count.

Question 21

Modifiers

swap( )

Answer 21

swaps the contents
Parameters
other	-	container to exchange the contents with
Return value
(none)

Exceptions
(none)

(until C++17)
noexcept specification:  
noexcept(std::allocator_traits::is_always_equal::value)
(since C++17)
Complexity
Constant.

Question 22

Operations

merge( )

Answer 22

merges two sorted lists
Parameters
other - another container to merge
comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second.
The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)).
The types Type1 and Type2 must be such that an object of type list::const_iterator can be dereferenced and then implicitly converted to both of them.​

Return value
(none)

Exceptions
If an exception is thrown, this function has no effect (strong exception guarantee), except if the exception comes from the comparison function.

Complexity
at most std::distance(begin(), end()) + std::distance(other.begin(), other.end()) - 1 comparisons.

Question 23

Operations

splice( )

Answer 23

moves elements from another list
Parameters
pos - element before which the content will be inserted
other - another container to transfer the content from
it - the element to transfer from other to *this
first, last - the range of elements to transfer from other to *this
Return value
(none)

Exceptions
Throws nothing.

Complexity
1-2) Constant.
3) Constant if other refers to the same object as *this, otherwise linear in std::distance(first, last).

Question 24

Operations
remove
remove_if( )

Answer 24

removes elements satisfying specific criteria
Parameters
value - value of the elements to remove
p - unary predicate which returns ​true if the element should be removed.
The expression p(v) must be convertible to bool for every argument v of type (possibly const) T, regardless of value category, and must not modify v. Thus, a parameter type of T&is not allowed, nor is T unless for T a move is equivalent to a copy (since C++11).​

Return value
(none)

(until C++20)
The number of elements removed.

(since C++20)
Complexity
Linear in the size of the container

Question 25

Operations

reverse( )

Answer 25

reverses the order of the elements
Parameters
(none)

Return value
(none)

Complexity
Linear in the size of the container

Question 26

Operations

unique( )

Answer 26

removes consecutive duplicate elements
Parameters
p - binary predicate which returns ​true if the elements should be treated as equal.
The signature of the predicate function should be equivalent to the following:

bool pred(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)).
The types Type1 and Type2 must be such that an object of type list::const_iterator can be dereferenced and then implicitly converted to both of them.​

Return value
(none)

(until C++20)
The number of elements removed.

(since C++20)
Complexity
Exactly size() - 1 comparisons of the elements, if the container is not empty. Otherwise, no comparison is performed.

Question 27

Operations

sort( )

Answer 27

sorts the elements
Parameters
comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second.
The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)).
The types Type1 and Type2 must be such that an object of type list::const_iterator can be dereferenced and then implicitly converted to both of them.​

Return value
(none)

Complexity
Approximately N log N comparisons, where N is the number of elements in the list.