Generic Algorithms
typedef ptin_iterator<int> ptin;
typedef ptout_iterator<int> ptout;
vector<int> V(ptin(0), ptin());
Show(V.begin(), V.end(), "V: ");
//copy(V.begin(), V.end(), ptout());
Search Algorithms
STL3Alg1°. Given a vector V. Remove the second of the vector elements equal to zero. If there are fewer than two zero elements, do not change the vector. Use two calls to the find algorithm and the member function erase.
STL3Alg2°. Given a deque D. Remove the last zero element of the deque. If there are no zero elements, do not change the deque. Use the find algorithm with reverse iterators and the member function erase. Note. The find algorithm can return a reverse iterator; however, the member function erase does not allow its use for element deletion. It is necessary to convert from the reverse iterator r to the associated regular iterator using the member function of the reverse iterator r.base(). It should be taken into account that the function r.base() returns an iterator associated with the element following the one associated with the reverse iterator r. Therefore, in the member function erase, one of the following expressions should be specified (assuming that r is the reverse iterator returned by the find algorithm and this iterator is not equal to rend): --r.base() or (++r).base().
STL3Alg3°. Given a list L. Remove the first and last zero element of the list. If there are no zero elements, do not change the list; if there is only one zero element, remove only it. Use two calls to the find algorithm and two calls to the member function erase. Note. The remove member function available in the list class cannot be used in this case because it removes all elements with a specific value. Also see the note for task STL3Alg2.
STL3Alg4°. Given a list L. Remove all elements of the list located between the first and second negative element (not including the negative elements themselves). If the list contains no negative elements, do not change it; if there is only one negative element, remove all elements following this negative element. Use two calls to the find_if algorithm and one call to the member function erase.
STL3Alg5°. Given a list L, containing both negative and positive elements. Insert a zero element after the first negative element and before the last positive element. Use two calls to the find_if algorithm and two calls to the member function insert. Note. Regarding the use of the find_if algorithm with a reverse iterator, see the note for task STL3Alg2.
STL3Alg6°. Given a vector V and a list L; the vector V has an even number of elements. Duplicate the last element of the list that matches any element from the first half of the initial vector. If the list does not contain the required elements, do not change it. Use the find_first_of algorithm and the member function insert for the list.
STL3Alg7°. Given a vector V with an even number of elements. Add a zero element before the last element in the first half of the vector that matches any element from the second half of the same vector. If the vector does not contain the required elements, do not change it. Use the find_first_of algorithm and the member function insert.
STL3Alg8°. Given an integer K (> 0) and a vector V, containing only zeros and ones. Remove in the vector V the last set of K consecutively located zeros (if this set has more than K zeros, then only the last K of them should be removed). If the vector does not contain the required set of zeros, do not change it. Use the search_n algorithm and the member function erase, as well as reverse iterators.
STL3Alg9°. Given an integer K (> 0) and a vector V. Duplicate in the vector V the first set of K consecutively located positive numbers, by inserting a copy of this set after it (if the set has more than K positive numbers, the extra numbers are not taken into account, and only the initial part of the set containing K numbers is duplicated). If the vector does not contain the required set of numbers, do not change it. Use the search_n algorithm with a parameter — a function object.
STL3Alg10°. Given a list L and a deque D; the deque D contains an even number of elements. Duplicate in the deque D the first set of elements located in its second half and matching the elements of the list L taken in reverse order. For example, for the list 1, 2 and the deque 2, 1, 1, 2, 3, 2, 1, 1, 2, 1 the deque should be transformed as follows: 2, 1, 1, 2, 3, 2, 1, (2, 1,) 1, 2, 1 (inserted elements are enclosed in parentheses). If the deque does not contain the required set of numbers, do not change it. Use the search algorithm and the member function insert.
STL3Alg11°. Given a vector V and a deque D; the deque D contains an even number of elements. Remove in the vector V the last set of elements in which even and odd numbers are arranged in the same order as in the first half of the deque D. For example, for the deque 1, 2, 3, 4, 5, 6 and the vector 11, 14, (15, 16, 17,) 17, 18, 10 the elements enclosed in parentheses should be removed from the vector. If the vector does not contain the required set of numbers, do not change it. Use the search algorithm with a parameter — a function object and the member function erase.
STL3Alg12°. Solve task STL3Alg11 using the find_end algorithm with a parameter — a function object and the member function erase.
STL3Alg13°. Given a list L. Double the values in the last pair of adjacent matching elements. For example, the list 1, 2, 2, 3, 3, 1, 2, 2, 2, 4 should be transformed as follows: 1, 2, 2, 3, 3, 1, 2, 4, 4, 4. If the list does not contain adjacent matching elements, do not change it. Use the adjacent_find algorithm and reverse iterators.
STL3Alg14°. Given a vector V. Zero out the first pair of adjacent elements that have the same parity. For example, the list 1, 2, 3, 4, 6, 8, 3, 1 should be transformed as follows: 1, 2, 3, 0, 0, 8, 3, 1. If the list does not contain adjacent elements with the same parity, do not change it. Use the adjacent_find algorithm with a parameter — a function object.
STL3Alg15°. Given a deque D. Double the values of all pairs of adjacent elements whose initial values differ only in sign (the transformed elements should not be re-analyzed in subsequent calls to the algorithm). For example, the deque 1, −1, 2, −3, 3, 3, −3, 6 should be transformed as follows: 2, −2, 2, −6, 6, 6, −6, 6. Use the adjacent_find algorithm with a parameter — a function object in a loop over a deque iterator.
Basic Modifying Algorithms. Insert Iterators
STL3Alg16°. Given numbers A and B and vectors V1 and V2, each containing at least 10 elements. Fill the first 5 elements of each vector with values A, and the last 5 with values B. When transforming vector V1, use two calls to the fill algorithm; when transforming vector V2, use two calls to the fill_n algorithm.
STL3Alg17°. Given numbers A and B and vectors V1 and V2. Add to the beginning of each vector 5 elements with values A, and to the end — 5 elements with values B. When transforming vector V1, use two calls to the fill_n algorithm with the functions inserter and back_inserter (these functions return insert iterators); when transforming vector V2, use two calls to the member function insert. Remark. The second method is more efficient.
STL3Alg18°. Given a number N (> 0) and a deque D, containing at least 2N elements. Fill the first N elements of the deque with the sequence of numbers 1, 2, …, N, and the last N elements of the deque — with the sequence N, N−1, …, 2, 1. Use two calls to the generate algorithm with the same parameter — a function object, as well as reverse iterators.
STL3Alg19°. Given a number N (> 0) and a deque D. Add to the beginning of the deque the sequence of numbers 1, 2, …, N, and to its end — the sequence N, N−1, …, 2, 1. Use two calls to the generate_n algorithm with the same parameter — a function object, as well as insert iterators returned by the functions front_inserter and back_inserter.
STL3Alg20°. Given lists L1 and L2, each containing an even number of elements. Swap the first and second half of each list (for example, the list 1, 2, 3, 4 should be transformed as follows: 3, 4, 1, 2). For the first list, use the swap_ranges algorithm; for the second — the rotate algorithm. Also use the function advance.
STL3Alg21°. Given a number K (0 < K < 10) and lists L1 and L2, each containing at least 10 elements. Perform for list L1 a cyclic shift of elements to the right by K positions, and for list L2 — a cyclic shift to the left by K positions. Use the rotate algorithm and the function advance.
STL3Alg22°. Given a number K (0 < K < 5) and a list L, containing at least 10 elements. Copy the set of the first 5 elements of the list to the end of the list, performing for this copy a cyclic shift by K positions to the right, and copy the set of the last 5 elements of the initial list to the beginning of the list, performing for this copy a cyclic shift by K positions to the left. Use two calls to the rotate_copy algorithm and insert iterators, as well as the function advance.
STL3Alg23°. Given lists L1 and L2, each with a number of elements divisible by 4. In the first list, invert (arrange in reverse order) the first half of the elements; in the second list — the second half. For the first list, use the swap_ranges algorithm and reverse iterators; for the second — the reverse algorithm. Also use the function advance.
STL3Alg24°. Given lists L1 and L2, each containing an even number of elements. In each list, duplicate the first half by adding its elements to the end of the list in reverse order. For the first list, use the reverse_copy algorithm and an insert iterator; for the second — the member function insert and reverse iterators. Also use the function advance. Remark. The second method is more efficient.
STL3Alg25°. Given a vector V with an even number of elements. In the first half of the initial vector, replace all negative numbers with −1, and in the second — all positive numbers with 1. Use two calls to the replace_if algorithm with different parameters — function objects.
STL3Alg26°. Given a list L with an even number of elements. Copy to the end of the list all elements located in its first half, replacing negative elements with zeros and arranging the copied elements in reverse order. Use the replace_copy_if algorithm, an insert iterator and reverse iterators, as well as the function advance.
STL3Alg27°. Given a deque D with an even number of elements. Solve task STL3Alg26 for it. Since the insertion operation invalidates all iterators of the deque, use an auxiliary deque D0 to solve the task. Initialize the deque D0 with the first half of the elements of the deque D, then apply the replace_copy_if algorithm, using deque D0 as the source and deque D as the data destination.
STL3Alg28°. Given a list L with an even number of elements. Copy to the beginning of the list all positive elements located in its second half, preserving their original order. Use the remove_copy_if algorithm and an insert iterator, as well as the function advance.
STL3Alg29°. Given a vector V with an even number of elements. Solve task STL3Alg28 for it. Since the operation of inserting at the beginning of a vector invalidates all its iterators, use an auxiliary vector V0 to solve the task. Initialize the vector V0 with the second half of the elements of the vector V, then apply the remove_copy_if algorithm, using vector V0 as the source and vector V as the data destination.
STL3Alg30°. Given a vector V with an even number of elements. Remove all zero elements located in the second half of the initial vector. Use the remove algorithm and the member function erase. Note. The remove algorithm and other algorithms related to element removal do not actually remove the required elements, but only move them to the end of the specified range and return an iterator to the beginning of the range with the moved elements. To actually remove the elements, it is necessary to call the member function erase after executing the algorithm.
STL3Alg31°. Given a vector V with an even number of elements. Remove all even elements located in the first half of the initial vector. Use the remove_if algorithm and the member function erase. Note. See the note for task STL3Alg30.
STL3Alg32°. Given a vector V. In each group of consecutively located elements with the same parity, remove all elements except the initial one. Use the unique algorithm with a parameter — a function object and the member function erase. Note. See the note for task STL3Alg30.
STL3Alg33°. Given a deque D. From each group of consecutively located positive, negative, or zero elements, select the last one and copy the selected elements in the same order to the beginning of the deque. For example, the deque 1, 2, −3, 4, 0, 0, −5, −6, 7, 8, 9 should be transformed as follows: (2, −3, 4, 0, −6, 9,) 1, 2, −3, 4, 0, 0, −5, −6, 7, 8, 9 (added elements are enclosed in parentheses). Use an auxiliary deque D0 (initializing it using deque D), the unique_copy algorithm with a function object and reverse iterators, as well as a suitable insert iterator (in the algorithm, deque D0 should be the source and deque D the data destination).
STL3Alg34°. Given a deque D with an even number of elements. Replace its second half with doubled values of the elements of the first half, arranging these doubled values in reverse order. Use the transform algorithm with a reverse iterator.
STL3Alg35°. Given a list L with an even number of elements N. Add to the beginning of the list N/2 new elements with the following values: A1 + AN, A2 + AN-1, …, AN/2 + AN/2+1, where A1, A2, …, AN denote the initial elements of the list. Use the transform algorithm with a reverse iterator and an insert iterator.
Sorting and Merging
STL3Alg36°. Given a vector V with an odd number of elements N (≥ 3). Determine the values of the three middle elements of the vector after it is sorted (in ascending order), and output them in ascending order. Use the algorithms nth_element (to find the central element), max_element (to find the element preceding the central one), and min_element (to find the element following the central one).
STL3Alg37°. Given a vector V, containing at least 3 elements. Determine the values of the three initial elements of the vector after it is sorted (in ascending order), and output them in ascending order. Use one call to the partial_sort algorithm and the copy algorithm to output the required elements.
STL3Alg38°. Given a vector V, containing at least 3 elements. Determine the values of the three final elements of the vector after it is sorted (in ascending order) and output them in descending order. Use one call to the partial_sort algorithm with a parameter — the function object greater and the copy algorithm to output the required elements.
STL3Alg39°. Given a vector V with an even number of elements. Add to its end the first half of the elements that the sorted (in ascending order) version of the initial vector would contain. Use the member function insert to increase the number of vector elements by the required amount and the partial_sort_copy algorithm.
STL3Alg40°. Given a list L. Determine the number of even and odd numbers in the initial list (first output the number of even, then the number of odd numbers). Use the partition algorithm and two calls to the function distance for iterators.
STL3Alg41°. Given a list L. Regroup the elements of the list, placing first the positive and then the non-positive elements (the order of elements in each group should match the original). Use the stable_partition algorithm.
STL3Alg42°. Given a list L. Regroup the elements of the list, placing first the negative, then the zero, and then the positive elements (the order of elements in each group should match the original). Use two calls to the stable_partition algorithm.
STL3Alg43°. Given a list L with an even number of elements. Regroup the elements of the list, placing first all even elements from the first half of the initial list, then all odd elements, and then — all even elements from the second half of the list (the order of elements in each group should match the original). Use two calls to the stable_partition algorithm.
STL3Alg44°. Given a deque D. Solve task STL3Alg42 for it, using one call to the stable_sort algorithm with a parameter — a function object.
STL3Alg45°. Given a deque D, whose elements are English words. Sort its elements in ascending order of their lengths, and elements of the same length — in alphabetical order. Use the sort algorithm for alphabetical sorting and then the stable_sort algorithm with a parameter — a function object for sorting by length. Output the new contents of the deque after applying each algorithm.
STL3Alg46°. Given a deque D, whose elements are English words. Sort its elements in descending order of their lengths, and elements of the same length — in alphabetical order. Use a single call to the sort algorithm with a parameter — a function object that includes both string comparison and their length comparison.
STL3Alg47°. Given a vector V with an even number of elements. It is known that the first half of the vector is already sorted in ascending order. Sort all elements of the vector in ascending order, first by sorting its second half with the sort algorithm, and then by merging both halves with the inplace_merge algorithm. Output the new contents of the vector V after applying each algorithm.
STL3Alg48°. Given a vector V, the number of elements of which is divisible by 3. It is known that each third of the vector is already sorted in ascending order. Transform the vector V similarly to how list L was transformed in task STL3Alg42 (first negative, then zero, then positive elements), but using two calls to the inplace_merge algorithm with the same parameter — a function object.
Permutations and Heap Operations
STL3Alg49°. Given a vector V, whose elements are not sorted in descending order. Obtain all permutations of the initial elements that are greater than the initial vector in lexicographical order and output the obtained permutations in ascending order of their lexicographical order (the last output permutation should contain elements sorted in descending order). Use the next_permutation algorithm in a loop.
STL3Alg50°. Given a vector V, whose elements are not sorted in descending order. Solve task STL3Alg49 using the prev_permutation algorithm with a parameter — the function object greater in a loop.
STL3Alg51°. Given a vector V, containing at least 3 elements. Solve task STL3Alg38 for it, using one call to the make_heap algorithm, a loop of three iterations in which the pop_heap algorithm is called, and the copy algorithm (with reverse iterators) to output the required elements.
STL3Alg52°. Given a vector V, containing at least 3 elements. Solve task STL3Alg37 for it, using one call to the make_heap algorithm, a loop of three iterations in which the pop_heap algorithm is called, and the copy algorithm (with reverse iterators) to output the required elements. Note. Use variants of the algorithms with a parameter — a function object.
STL3Alg53°. Given a deque D1, containing at least 3 elements, and a deque D2, containing exactly 3 elements. Determine the three maximum elements among all elements of the set obtained from deque D1 by removing its three maximum elements and adding to it all elements from deque D2. Output the required elements in descending order. Use the algorithms make_heap, pop_heap, and push_heap, as well as the copy algorithm (with reverse iterators) to output the required elements. Do not change the sizes of the initial deques; use the make_heap algorithm once. Note. The make_heap algorithm is used to transform the elements of the first deque into a heap. Then a loop with three calls to the pop_heap algorithm is executed to remove the three maximum elements from the heap, a loop with three calls to the push_heap algorithm to add the elements from the second deque to the heap, and another loop with three calls to the pop_heap algorithm to determine the required elements. The copy algorithm is called after the loop.
STL3Alg54°. Given a deque D1, containing at least 3 elements, and a deque D2, containing exactly 3 elements. Determine the three minimum elements among all elements of the set obtained from deque D1 by removing its three minimum elements and adding to it all elements from deque D2. Output the required elements in ascending order. Use the algorithms make_heap, pop_heap, and push_heap, as well as the copy algorithm (with reverse iterators) to output the required elements. Do not change the sizes of the initial deques; use the make_heap algorithm once. Note. See the notes for tasks STL3Alg52 and STL3Alg53.
Numeric Algorithms
STL3Alg55°. Given a vector V with an even number of elements. Find the sum of the elements from the first and from the second half of the vector. Use two calls to the accumulate algorithm.
STL3Alg56°. Given a vector V. Find the sum of the negative and the sum of the positive elements of the vector. Use two calls to the accumulate algorithm with parameters — function objects.
STL3Alg57°. Given a vector V, whose elements are English words. Obtain a string containing the initial characters of all elements of the vector, arranged in reverse order. Use the accumulate algorithm with a parameter — a function object.
STL3Alg58°. Given a vector V, whose elements are English words. Obtain a string containing the final characters of all elements of the vector, arranged in the original order. Use the accumulate algorithm with a parameter — a function object.
STL3Alg59°. Given a vector V, whose elements are English words. Obtain a string that is the sum of the strings described in tasks STL3Alg57 and STL3Alg58 (in the specified order). Use one call to the accumulate algorithm with a parameter — a function object.
STL3Alg60°. Given a list L. Obtain a vector V of real numbers, containing the values of the arithmetic mean for all pairs of adjacent elements of the initial list (the number of elements of the vector V should be 1 less than the number of elements of the list L). For example, for the initial list 1, 3, 4, 6 the resulting vector should contain the values 2.0, 3.5, 5.0. Use the adjacent_difference algorithm with an insert iterator and a function object, as well as the member function erase for the vector V.
STL3Alg61°. Given a list L, whose elements are English words. Obtain a deque D with string elements, each of which is constructed from a pair of adjacent elements of the initial list L as follows: the last letter of the right element of the pair is appended to the right of the first letter of the left element of the pair. The number of elements of the deque D should be 1 less than the number of elements of the list L. For example, for the initial list ABC, DEF, KLM, XYZ the resulting deque should contain the strings AF, DM, KZ. Use the adjacent_difference algorithm with an insert iterator and a function object, as well as the member function erase for the deque D.
STL3Alg62°. Given vectors V1 and V2 of the same size N, each containing the coordinates of a point in N-dimensional space with Euclidean metric r(x,y) = (Σ(xi − yi)2)1/2 (the sum is taken over all i from 0 to N−1). Find the value of the squared metric for the two given points. Use the inner_product algorithm with two function objects (the standard object plus can be specified as the first one).
STL3Alg63°. Given vectors V1 and V2 of the same size N, each containing the coordinates of a point in N-dimensional space with the metric r(x,y) = max{|xi − yi|} (the maximum is taken over all i from 0 to N−1). Find the value of the metric for the two given points. Use the inner_product algorithm with two function objects.
STL3Alg64°. Given an integer N (1 ≤ N ≤ 16). Obtain a vector V of real numbers, equal to the factorials of all numbers from 1 to N (real numbers are used to avoid integer overflow). For this, sequentially call the constructor of the vector V, filling it with ones, the partial_sum algorithm (with a parameter — a function object) to obtain all numbers from 1 to N in the vector, and the partial_sum algorithm (with a parameter — a function object, for which the standard object multiplies can be used) to obtain the required factorials in the vector.
|
