Forward_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

Iterators
before_begin
cbefore_begin( )

Answer 2

returns an iterator to the element before beginning
Parameters
(none)

Return value
Iterator to the element before the first 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

Capacity

empty( )

Answer 5

checks whether the container is empty
Parameters
(none)

Return value
true if the container is empty, false otherwise

Complexity
Constant.

Question 6

Capacity

max_size( )

Answer 6

returns the maximum possible number of elements
Returns the maximum number of elements the container is able to hold due to system or library implementation limitations, i.e. std::distance(begin(), end()) for the largest container.

Parameters
(none)

Return value
Maximum number of elements.

Complexity
Constant.

Question 7

Modifiers

clear( )

Answer 7

clears the contents
Parameters
(none)

Return value
(none)

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

Question 8

Modifiers

insert_after( )

Answer 8

inserts elements after an element
Parameters
pos - iterator after which the content will be inserted
value - element value to insert
count - number of copies to insert
first, last - the range of elements to insert
ilist - initializer list to insert the values from
Type requirements
-InputIt must meet the requirements of LegacyInputIterator.
Return value
1-2) Iterator to the inserted element.
3) Iterator to the last element inserted, or pos if count==0.
4) Iterator to the last element inserted, or pos if first==last.
5) Iterator to the last element inserted, or pos if ilist is empty.
Exceptions
If an exception is thrown during insert_after there are no effects (strong exception guarantee).

Complexity
1-2) Constant.
3) Linear in count
4) Linear in std::distance(first, last)
5) Linear in ilist.size()

Question 9

Modifiers

emplace_after( )

Answer 9

constructs elements in-place after an element
Parameters
pos - iterator after which the new element will be constructed
args - arguments to forward to the constructor of the element
Return value
iterator to the new element.

Complexity
Constant.

Exceptions
If an exception is thrown (e.g. by the constructor), the container is left unmodified, as if this function was never called (strong exception guarantee).

Question 10

Modifiers

erase_after( )

Answer 10

erases an element after an element
Parameters
pos - iterator to the element preceding the element to remove
first, last - range of elements to remove
Return value
1) Iterator to the element following the erased one, or end() if no such element exists.
2) last
Complexity
1) Constant.
2) Linear in distance between first and last.

Question 11

Modifiers

push_front( )

Answer 11

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

Complexity
Constant.

Question 12

Modifiers

emplace_front( )

Answer 12

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 13

Modifiers

pop_front( )

Answer 13

removes the first element
Parameters
(none)

Return value
(none)

Complexity
Constant.

Question 14

Modifiers

resize( )

Answer 14

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. Additional complexity possible due to list traversal to reach the first element to erase/the end position to insert

Question 15

Modifiers

swap( )

Answer 15

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 16

Operations

merge( )

Answer 16

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 forward_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 17

Operations

splice_after( )

Answer 17

moves elements from another forward_list
Parameters
pos - element after which the content will be inserted
other - another container to move the content from
it - iterator preceding the iterator to the element to move from other to *this
first, last - the range of elements to move from other to *this
Return value
(none)

Exceptions
Throws nothing.

Complexity

1) Linear in the size of other
2) Constant
3) Linear in std::distance(first, last)

Question 18

Operations
remove
remove_if( )

Answer 18

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 19

Operations

reverse( )

Answer 19

reverses the order of the elements
Parameters
(none)

Return value
(none)

Complexity
Linear in the size of the container

Question 20

Operations

unique( )

Answer 20

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 forward_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 std::distance(begin(), end()) - 1 comparisons of the elements, if the container is not empty. Otherwise, no comparison is performed.

Question 21

Operations

sort( )

Answer 21

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 forward_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.