STL
ALGORITHMS




This course is still related to the ST library and focuses on the algorithms.

• Efficient pre-defined algorithms to manipulate containers
• Usually have an at most linear complexity
• Usually have a range refering to a container as argument
• Use iterators
  

//Heading
#include<algorithm>

• Nonmodifying algorithms
• Modifying algorithms (for sequence containers only !)
• Removing algorithms (for sequence containers only !)
• Mutating algorithms (for sequence containers only !)
• Sorting algorithms
• Numeric algorithms
• Miscellaneous but crucial further examples
  

1 - Nonmodifying algorithms


Essentially searching algorithms

Operation	Effect
count( )	Returns the number of elements with a given value
count_if ( )	Returns the number of elements that match a given criterion
min_element ( )	Returns the index of the element having the smallest value
max_element ( )	Returns the index of the element having the largest value
find ( )	Searches for the first element with a given value
find_if ( )	Searches for the first element verifying a given criterion
search_n( )	Searches for the first m consecutive elements verifying a given criterion
search( )	Searches for the first occurence in a subrange
find_end( )	Searches for the last occurence in a subrange
adjacent_find( )	Searches for two adjacent elements that verify a given property
find_first_of ( )	Searches the first several possible elements
equal( )	Returns whether two ranges are equal
mismatch( )	Returns the first elements of two sequences that differ

1-1 Counting elements

// Counting elements having for value val in the range [beg,end)
//(or the key value val when dealing with maps):
count (input_iterator beg,input_iterator end,val);

Example: Let S be the int-typed multiset 1,1,4,3,5,7,5,6,5
count (S.begin( ),S.end( ),5);  // return 3


//Counting elements verifying a certain unary predicate pred in the range [beg,end) (ie: verifying
//pred(elem)=true); the predicate is implemented as a function:
count_if (input_iterator beg,input_iterator end,unary_predicate pred);

Example: Count the number of even values in the previous multiset.
//Definition (outside the main) of the predicate as a function
bool Even (int elem) {
    return elem%2= =0;
}

//Counting command line (for example inside the main)
count (S.begin( ),S.end( ),Even) // returns 2


1-2 Minimum and Maximum

// Returns the position of the minimum value in the range [beg,end) using an iterator
min_element (input_iterator beg,input_iterator end);

// Returns the position of the maximum value in the range [beg,end) using an iterator
max_element (input_iterator beg,input_iterator end);

Example: Let S be the int-typed multiset 1,1,4,3,5,7,5,6,-9,5

*max_element (S.begin( ),S.end( )); //returns 7 (the value  of the maximum)


// Returns the position of the minimum value in the range [beg,end) according to
// the comparison function comp
min_element (input_iterator beg,input_iterator end,comparison_function comp);

// Same with the maximum
min_element (input_iterator beg,input_iterator end,comparison_function comp);


Example: Return the maximum value of the absolute values in the previous multiset.
//Definition (outside the main) of the comparison function less_abs
bool less_abs (int elem1,int elem2) {
    return abs(elem1) < abs(elem2);
}

//Finding the maximum with respect to the function less_abs (for example inside the main)

*max_element (S.begin( ),S.end( ),less_abs); //returns 9 (value)


1-3 Searching elements

1-3-1 Search first matching element
// Returns the position of the first element having for value val, or end if no matching element is found
find (input_iterator beg,input_iterator end,val);

!!! It's faster to use the C.find(val) container function !!!

//Returns the position of the first element according to a certain unary predicate pred,
//or end if no matching element is found
find_if (input_iterator beg,input_iterator end,unary_predicate pred);

Example: Return the position of the first element greater than 4 in the multiset 1,1,4,3,5,7,5,6,5
find_if (S.begin( ),S.end( ),bind2nd(greater<int>(),5) );

Example: Return the position of the first even element in the previous multiset
//Definition (outside the main) of the predicate as a function
bool Even (int elem) {
    return elem%2= =0;
}

//find command line
find_if (S.begin( ),S.end( ),Even);


1-3-2 Search first n matching elements
// Search the position of the n consecutive elements having for value val
search_n (input_iterator beg,input_iterator end,n,val);

// Search the position of the n consecutive element for which
//the value of the binary predicate pred(current_elem,val) is true
search_n (input_iterator beg,input_iterator end,n,val,pred);

!!! Return end if no matching alements are found !!!

Example: Return the position of the 2 first consecutive elements with value 5 in the multiset 1,1,2,2,2,4,3,5,5,5,6,5
  search(S.begin( ),S.end( ),2,5);

Example: Return the position of the first 3 consecutive elements greater 1 in the previous multiset
search (S.begin( ),S.end( ),3,1,greater<int>() );


1-3-3 Search first subrange
// Return the position of 1st element of the first subrange equal to the range [beg2,end2)
// in the range [beg1,end1); return end1 if no matching elements are found
search (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2);

Example: Consider the vector V=3,6,2,5,6,1,1 and the set S=2,5,6.
search (V.begin( ),V.end( ),S.begin( ),S.end( ));


// Return the position of 1st element of the first subrange matching  the range [beg2,end2)
// in the range [beg1,end1), according to the binary predicate pred(current_elem1,current_elem2)
search (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,pred);

Example: With the previous vector V=3,1,2,5,6,1,1 and set S=2,5,6,
search (V.begin( ),V.end( ),S.begin( ),S.end( ),less<int>());
returns 2, because less<int>(3,2)="false, less<int>(1,6)="false", and less<int>(2,6)="true".


1-3-4 Search last subrange
Same than 1-3-3, using the algorithm find_end( ) instead of search.
The result is the position of the first element of the last subrange, instead of the first subrange.

1-3-5 Search two adjacent matching elements
// Return the position of the first element the value of which is the same
// than the value of the following element; return end if no matching elements are found
adjacent_find (input_iterator beg,input_iterator end);

Example: With the previous vector V=3,1,2,5,6,1,1
adjacent_find (V.begin( ),V.end( ));
adjacent_find (V.begin( ),V.end( ),less<int>());


// Return the position of the first element the value of which matches
// with the value of the following element in the sense of the binary predicate pred
adjacent_find (input_iterator beg,input_iterator end,binary_predicate pred);


1-3-6 Search first of several possible elements

// Return the position of 1st element in the range [beg1,end1) that belongs also
// to the range [beg2,end2); return end1 if no matching elements are found
find_first_of (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2);

// Return the position of 1st element in the range [beg1,end1) that matches
// with an element of the range [beg2,end2) according to the binary predicate pred
find_first_of (input_iterator1 beg1,input_iterator1 end1,
input_iterator2 beg2,input_iterator2end2,pred);


1-3-7 Comparing ranges
// Return "true" if the elements of the range [beg1,end1) match
// with the elements in the range starting with beg2, and false "otherwise".
equal (input_iterator beg1,input_iterator end1,input_iterator beg2); // accroding to "= ="
equal (input_iterator beg1,input_iterator end1,input_iterator beg2,pred); // accroding to pred

!!! The range starting with beg2 has to contain enough elements !!!

// Return the first two corresponding values of the range [beg1,end1) and
// the range starting with beg2 that mismatch
mismatch (input_iterator beg1,input_iterator end1,input_iterator beg2); // accroding to "= ="
mismatch (input_iterator beg1,input_iterator end1,input_iterator beg2,pred); // accroding to pred


1-4 Exercise
Assign a multiset S with the values -2, 3, -8, -8, 3, 5, and a vector V with -2,3.
Using algorithms, display the number of negative elements of S.
Display the maximum of the square of the values of S, together with the first index where this maximum lies.
Display the positive values of S.
Display the first element in S from where V matches S.

Answer:



  2- Modifying algorithms

2-1 Copying elements
// Copy elements of the source range [source_beg,source_end) into the destination range starting with
// destination_beg
copy (iterator1 source_beg,iterator1 source_end,iterator2,destination_beg);

// Copy backward elements of the source range [source_beg,source_end) into the destination range
// ending with destination_end copy_backward
copy_backward( iterator1 source_beg,iterator1 source_end,iterator2 destination_end);

2-2 Transforming elements

// Transform elements of the source range [source_beg,source_end) by using the function op
// and copy the resulting elements into the destination range starting with destination_beg
transform(iterator1 source_beg,iterator1 source_end,iterator2 destination_beg,unary function op)

Example: Assign a vector V (integer) with the opposite values of a set S (integer)
transform (S.begin( ),S.end( ),V.begin( ),negate<int>);

2-3 Swapping elements

// Swap elements in the range [source_beg,source_end) and elements in
// the destination range starting with destination_beg
swap(iterator1 source_beg,iterator1 source_end,iterator2 destination_beg,unary function op);

2-4 Assigning new values
// Assign elements in the range [beg,end) with the value val
fill (input_iterator beg,input_iterator end,val);

// Assign elements in the range [beg,end) by using the operator op
generate (input_iterator beg,input_iterator end,func op);

Example: Assign random values in a vector V
transform (V.begin ( ),V.end( ),rand);

2-5 Replacing elements
// Replace values old_val with new_val in the range [beg,end)
replace (input_iterator beg,input_iterator end,old_val,new_val);

// Replace values verifying the unary predicate pred with the value new_val in the range [beg,end)
replace_if (input_iterator beg,input_iterator end,pred,new_val);


Combinations:
// copy the range [source_beg,source_end) into the range starting destination_beg while replacing the
// values old_val with new_val
replace_copy (iterator1 source_beg,iterator1 source_end,iterator2 destination_beg,old_val,old_val);

// Same using suffix "if" and the predicate pred
replace_copy_if (iterator1source_beg,iterator1source_end,
    iterator2,destination_beg,pred,old_val);

!!! The range [beg1,end1) is not modified here !!!


3- Removing algorithms

3-1 Removing elements
remove(input_iterator beg,input_iterator end,val);
also provides the suffix "if" refering to a given predicate pred:
remove_if(input_iterator beg,input_iterator end,pred);

Also available:
// destination_beg
remove_copy (iterator1 source_beg,iterator1 source_end,iterator2 destination_beg,val);
where val is a value and
remove_copy_if (iterator1 source_beg,iterator1 source_end,iterator2 destination_beg,pred);
where pred is a unary predicate


3-2 Removing duplicates
unique (input_iterator beg,input_iterator end);

Also available:
unique_copy (iterator1 source_beg,iterator1 source_end,iterator2 destination_beg);


4- Mutating algorithms

4-1 Reversing elements
reverse (input_iterator beg,input_iterator end);

Also available:
reverse_copy (iterator1 source_beg,iterator1 source_end,iterator2 destination_beg);

4-2 Rotating elements
// Rotate elements in the range [beg,end) so that new_beg becomes the new first elemement
rotate (input_iterator beg,input_iterator new_beg,input_iterator end);

Also available:
rotate_copy (iterator1 source_beg,iterator1 source_new_beg,iterator1 source_end,iterator2 destination_beg);


4-3 Shuffling elements
random_shuffle (input_iterator beg,input_iterator end);

5- Sorting algorithms

5-1 Sorting all elements in a range
// Sorting using the binary operator "<"
sort(input_iterator beg,input_iterator end);

// Sorting using the sorting criterion operator "sorting_criterion"
sort(input_iterator beg,input_iterator end,sorting_criterion);

Example: Sort a vector V
sort(V.begin( ),V.end( ));

5-2 Partial sorting

// Sorting the elements in the range [beg,sort_end) that is included in the whole range [beg,end) by using "<"
partial_sort(input_iterator beg,input_iterator sort,input_iterator end);

Example: Sort the elements in the range [V.begin( ),V.begin( ) +5) in a vector V
 sort(V.begin( ),V.begin( )+5,V.end( ));

Version specifying the sorting criterion "sorting_criterion":
partial_sort(input_iterator beg,input_iterator sort_end,input_iterator end,sorting_criterion);


6- Numeric algorithms

Algorithms for numerical processing.

//Additional heading
#include<numeric>

6-1 Processing results
// Sum val + sum of all the elements in the range [beg,end)
accumulate (input_iterator beg,input_iterator end,val);

Example: Let S be the int-typed multiset 1,4,3,5,-8
accumulate (S.begin( ),S.end( ),3); // returns 8, thamks to the interesting property 3+1+4+3+5+ (-8)  = 8

// Same using the binary operator op instead of "+"
accumulate (input_iterator beg,input_iterator end,val,op);

If a containers is assigned with the values a_1,a_2,...,a_n, the command line
accumulate (input_iterator beg,input_iterator end,val,op);
returns val op a_1 op a_2 op ... op a_n

Example: Let S be the int-typed multiset 1,3,5
accumulate (S.begin( ),S.end( ),3,multiplies<int>( )); // returns 45, as 3*1*3*5

Rmq: if the range is empty, both forms return the value val

6-2 Inner product
// Sum of val + inner product of the range [beg1,emd1) with the range starting from beg2
inner_product (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,val);

If a containers C1 is assigned with the values a_1,a_2,...,a_n, and a container C2is assigned with the values b_1,b_2,...,b_m, where m>=n, the command line
inner_product (C1.begin( ),C1.end( ),C2.begin( ),val);
returns val + a_1*b_1 + a_2*b_2 + ... + a_n*b_n

// Same operator, but using op1 instead of "+" and op2 instead of "*"
inner_product (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,val,op1,op2);

In the previous example, the result would be val op1 (a_1 op2 b_1) op1 ... op1 (a_n op2 b_n)

6-3 Processing containers
// Computes the partial sum in the range [beg1,end1) and put the results in the range begining with beg2
partial_sum (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2);

If a containers C is assigned with the values a_1,a_2,...,a_n, and C' is a containers having at least n elements, the command line
partial_sum (C.begin ( ),C.end( ),C'.begin( ) );
assigns the first n elements of C' with a_1 , a_1+a_2 , a_1+a_2+a_3 , ... , a_1+ a_2 +... +a_n

// Same algorithm using the binary operator op instead of "+"
partial_sum (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,op);


In the same way, if a containers C is assigned with the values a_1,a_2,...,a_n, and C' is a containers having at least n elements, the command line
adjacent_difference (C.begin ( ),C.end( ),C'.begin( ) );
assigns the first n elements of C' with a_1 , a_2-a_1 , a_3-a_2+a_4-a_3 , ... , a_n-a_n-1

and the command
adjacent_difference (C.begin ( ),C.end( ),C'.begin( ),op );
does the same, using the binary operator op instead of "-"

7- Exercise
Assign a vector V1 with 3,-2,25,-1,8,6, a vector V2 with 1,2,3,4,5,6,7,8, and declare an empty vector V3.
Display the inner product ov V1 and V2.
Sort V1 in the decreasing order.
Replace the values of V1 by their absolute values.
Copy V1 at the end of V2.
Assign V3 by inserting V2, assign V4 by inserting V2 in the reverse order, and replace the values greater than 5 with 5 in V3.
Copy V3 into V2 while replacing the values less than 3 with 3.
Display V1, V2, V3,V4, and the sum of all the elements of these four vectors.


Answer:


8 - Miscellaneous


8- 1 The "for each" algorithm

// Applies the unary operation op to the elements in the range [beg,end)
for each (input_iterator beg,input_iterator end,op);
 
!!! Not necessarily a transformation !!!

Example: Display the elements of a integer container C

void display (int elem) {
    cout << elem;
}

for each (C.begin( ),C.end,display);

8- 2 Bounds
// Returns the position of the first element the value of which is less than or equal to val in the range [beg,end), or end if it does not find such element
lower_bound (input_iterator beg,input_iterator end,val);

// Version using a binary sorting criterion
lower_bound (input_iterator beg,input_iterator end,sorting_criterion);


// Returns the position of the first element the value of which is greater than val in the range [beg,end), or end if it does not find such element
upper_bound (input_iterator beg,input_iterator end,sorting_criterion);

// Version using a binary sorting criterion
upper_bound (input_iterator beg,input_iterator end,sorting_criterion);


// Returns the range of elements that match the value val
equal_range (input_iterator beg,input_iterator end,val); // acording to "="
equal_range (input_iterator beg,input_iterator end,val,pred); // acording to the binary predicate pred


8- 3 Union, Intersection

// Establishes the union of the sorted ranges [beg1,end1)  and [beg2,end2), and store the result in the range begining with beg3, in the sorted order "<"
set_union (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,output iterator beg3);

!!! The input ranges have to be sorted !!!
!!! If the input ranges contain duplicates, the number of occurences of a given duplicate number in the output range is the maximum number of occurences of this number in each source ranges !!!

Example: The union of 1 2 2 4 6 7 7 9 and 2 2 2 3 6 6 8 9 is
1 2 2 2 3 4 6 6 7 7 8 9

// Version using a binary predicate pred:
set_union (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,output iterator beg3,pred);


// Establishes the intersection of the sorted ranges [beg1,end1)  and [beg2,end2), and store the result in the range begining with beg3, in the sorted order "<"
set_intersection (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,output iterator beg3);

!!! The input ranges have to be sorted !!!
!!! If the input ranges contain duplicates, the number of occurences of a given duplicate number in the output range is the minimum number of occurences of this number in each source ranges !!!

Example: The intersection of 1 2 2 4 6 7 7 9 and 2 2 2 3 6 6 8 9 is
2 2 6 9

// Version using a binary predicate pred:
set_intersection (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,output iterator beg3,pred);



// Store in the range begining with beg3 the elements contained in the sorted range [beg1,end1)  but not in the sorted range [beg2,end2)
set_intersection (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,output iterator beg3);

!!! The input ranges have to be sorted !!!
!!! If the input ranges contain duplicates, the number of occurences of a given duplicate number in the output range is the difference between its number of occurences in both source ranges !!!

Example: The difference of 1 2 2 4 6 7 7 9 and 2 2 2 3 6 6 8 9 is
1 4 7 7

// Version using a binary predicate pred:
set_difference (input_iterator1 beg1,input_iterator1 end1,input_iterator2 beg2,input_iterator2 end2,output iterator beg3,pred);