Thursday, November 30, 2023

Algorithms - Modifying

Overview
Modifying Algorithms  operate transparently on containers such as lists, vectors, maps, sets, arrays etc.  using a pair of iterators, These are collectively known as sequences. They perform actions such as  replace, remove, copy etc. 
These function accepts parameters like 
  • iterators such as input, output, forward, bidirectional, randomaccess 
  • predicates such as unary, binary 
  • function pointers and function objects.
  • Unary values
  • random number generators

The parameter type  UnaryPredicate  is a function that accepts a single input and returns bool value (true or false). 
For example, bool isodd(int i) {return (i % 2) == 1;} or [](int i) {return (i % 2) == 1;}

The parameter type  BinaryPredicate  is a function that accepts two inputs and returns bool value (true or false). 
For example, bool issame(int i, int j) {return i == j;} or [](int i, int j) {return i == j;}

The parameter type  UnaryOperation is a function that accepts single input of type T and returns a value of type T. 
For example, int doubler(int i, int j) {return i * 2;} or [](int i) {return i *2;}

The parameter type  BinaryOperation is a function that accepts two inputs of type T and returns a value of type T. 
For example, int adder(int i, int j) {return i + j;} or [](int i, int j) {return i + j;}

The parameter type  RandomNumberGenerator is a function returns a random number. For example, int  rgen(int i) {return rand() % i;} or [](int i) { return rand() % i; }
.
The parameter type  URNG is a uniform random number generator that returns a random number. 
For example, default_random_engine(2018).

Details
NameDescription
OutputIterator copy (
InputIterator first, InputIterator last,
OutputIterator itrdest)
Overwrites contents at iterator itrdest with elements from range [first,last], and returns iterator to itrdest + (last-first).

Examples:
vector<int> v2{1,2}, v{0,0,3,4};

//v:{1,2,3,4}
//itr:begin(v)+2
auto itr = copy(begin(v2), end(v2), begin(v));
OutputIterator copy_n (
InputIterator first, size_t n,
OutputIterator itrdest)
Same as copy except elements from range [first,first+n] are copied.

Examples:
vector<int> v2{1,2}, v{0,0,3,4};

//v:{1,2,3,4}
//itr:begin(v)+2
auto itr = copy_n(begin(v2), 2, begin(v));
OutputIterator copy_if (
InputIterator first, InputIterator last,
OutputIterator itrdest, UnaryPredicate pred)
Same as copy except elements are copied only if the pred returns true.

Examples:
vector<int> v2{1,2}, v{0,0,3,4};

//v:{1,2,3,4}
//itr:begin(v)+2
auto itr = copy_if(begin(v2),  end(v2), begin(v), [](int n){return n<4;});
BidirIterator copy_backward (
BidirIterator first, BidirIterator last,
BidirIterator itrdest)
Same as copy except elements are copied in reverse order from range  [first, last], starting from itrdest-1.
It returns iterator at itrdest - (last-first).

Examples:
vector<int> v2{1,2}, v{0,0,3,4};

//v:{1,2,3,4}
//itr:begin(v)
auto itr = copy_backward(begin(v2),  end(v2), begin(v)+2);
OutputIterator move(
InputIterator first, InputIterator last,
OutputIterator itrdest)
Same as copy except elements are moved instead of copy.

Examples:
vector<string> v2{"one","two"}, v(2);

//v:{"one","two"}
//v2:{"",""}
//itr:end(v)
auto itr = move(begin(v2),  end(v2), begin(v));
BidirIterator move_backward (
BidirIterator first, BidirIterator last,
BidirIterator itrdest)
Same as copy_backward except elements are moved instead of copy.

Examples:
vector<string> v2{"one","two"}, v(2);

//v:{"one","two"}
//v2:{"",""}
//itr:end(v)
auto itr = move_backward(begin(v2),  end(v2), end(v));
 void swap (T& a, T& b)
Exchanges the values of a and b.

Example:
vector<string> v2{"one","two"}, v(2);

//v:{"one","two"}
//v2:{"",""}
swap(v,v2);
ForwardIterator swap_ranges (
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator first2)
Same as copy except elements are swapped instead of copy.

Examples:
vector<int> v2{1,2,1,2}, v{3,4,3,4};

//v:{1,2,3,4}
//v2:{1,2,3,4}
//itr:begin(v2)+2
auto itr = swap_ranges (begin(v2)+2, end(v2), begin(v));
void iter_swap (
ForwardIterator itra, ForwardIterator itrb)
Same as swap except elements at itra and itrb are swapped. 

Examples:
template<typename Iter>
void myreverse(Iter itbeg, Iter itend)
{
    //typename Iter::difference_type
    auto dis = distance(itbeg, itend);
    auto itb=itbeg, ite=itend-1;
    for (decltype(dis) n = 0; n < dis/2; ++n)
        iter_swap (itb++, ite--);
}

vector<int> v{1,2,3,4};

//v:{4,3,2,1}
myreverse(begin(v), end(v));
  1. OutputIterator transform (
    InputIterator     first, InputIterator last, 
    OutputIterator itrdest,
    UnaryOperation     unary_op)
  2. OutputIterator transform (
    InputIterator first, InputIterator last,
    InputIterator first2, OutputIterator itrdest,
    BinaryOperation binary_op)
1st version applies an unary_op () sequentially to the elements of range [first,last] 
2nd version applies  binary_op  sequentially to the elements of range [first,last]  and [first2]. 
Stores the result in the range that begins at itrdest.
The function allows for the destination range to be the same as one of the input ranges to make transformations in place.
Returns an iterator pointing to the element that follows the last element written in the itrdest sequence.
Example
vector<int> v2{1,2,3,4}, v(4);
//1
//v:{2,4,6,8}
transform(begin(v2), end(v2), begin(v), [](int n){return n*2;});

//2
//v:{3,6,9,12}
transform(begin(v2), end(v2), begin(v), begin(v), [](int n, int n2){return n+n2;});
void replace (
ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value)
Assigns new_value to all the elements in the range [first,last]  that compare equal to old_value.
The function uses operator== to compare the individual elements to old_value.

Example:
vector<int> v{1,2,3,4,4,6};

//v:{1, 2, 3, 5, 5, 6}
replace(begin(v), end(v), 4,  5);
void replace_if (
ForwardIterator first, ForwardIterator last, 
BinaryPredicate pred, const T& new_value)
Assigns new_value to all the elements in the range [first,last] that returns true for the pred.

Example:
vector<int> v{1,2,3,4,4,6};

//v:{1, 2, 3, 5, 5, 6}
replace_if(begin(v), end(v), [](int n){return (n == 4);},  5);
OutputIterator replace_copy (
InputIterator first, InputIterator last, 
OutputIterator dstitr, const T& old_value, 
const T& new_value)
Same as replace except output is written to dstitr.
Returns an iterator pointing to the element that follows the last element written in the dstitr sequence.

Examples:
vector<int> v2{1,2,3,4,4,6},v(6);

//v:{1, 2, 3, 5, 5, 6}
//itr:end(v)
auto itr = replace_copy(begin(v2), end(v2), begin(v), 4,  5);
OutputIterator replace_copy_if (
InputIterator first, InputIterator last, 
OutputIterator result, UnaryPredicate pred, 
const T& new_value)

Same as replace_copy except elements from [first,last] that returned true to pred will be replaced by new value.

Examples:
vector<int> v2{1,2,3,4,4,6},v(6);

//v:{1, 2, 3, 5, 5, 6}
//itr:end(v)
auto itr = replace_copy_if(begin(v2), end(v2), begin(v), [](int n){return (n == 4);},  5);
void fill (
ForwardIterator first, ForwardIterator last, 
const T& val)
Assigns val to all the elements in the range [first, last].

Example:
vector<int> v{1,2,3,4,4,6};

//v:{5, 5, 5, 5, 5, 5}
fill(begin(v), end(v), 5);
void fill_n (
ForwardIterator first, size_t n, 
const T& val)
Assigns val to n elements to the elements in the range [first,first+n].

Example:
vector<int> v{1,2,3,4,4,6};

//v:{5, 5, 5, 5, 5, 5}
fill_n(begin(v), 6, 5);
void generate (
ForwardIterator first, ForwardIterator last, 
Generator gen)
Assigns the value returned by successive calls to gen to the elements in the range [first,last].

Example:
vector<int> v{1,2,3,4,4,6};

//v:{83, 86 77, 15, 93, 35 }
generate(begin(v), end(v), [](){return rand()%100; });
void generate_n (
OutputIterator first, size_t n, Generator gen)
Assigns the value returned by successive calls to gen to the elements in the range [first,first+n].

Example:
vector<int> v{1,2,3,4,4,6};

//v:{83, 86 77, 15, 93, 35 }
generate_n(begin(v), 6, [](){return rand()%100; });
ForwardIterator remove (
ForwardIterator first, ForwardIterator last,
const T& val)
Transforms the range [first,last] into a range with all the elements that compare equal to val removed, and returns an iterator to the new end of that range.
The elements are shuffled but size of the sequence does not change.

Examples:
vector<int> v{1,2,3,4,4,6};

//v:{1,2,3,6,?,? }
//itr:begin(v)+4
auto itr = remove(begin(v), end(v), 4);
ForwardIterator remove_if (
ForwardIterator first, ForwardIterator last,  
UnaryPredicate pred)
Same as remove except elements are removed only if the pred returns true.

Examples:
vector<int> v{1,2,3,4,4,6};

//v:{1,2,3,6,?,? }
//itr:begin(v)+4
auto itr = remove_if(begin(v), end(v), [](int n){return (n == 4);});
ForwardIterator remove_copy (
ForwardIterator first, ForwardIterator last,
OutputIterator itrdest,  const T& val)
Same as remove except elements are copied to itrdest and returns an iterator to the new end of that range.

Examples:
vector<int> v2{1,2,3,4,4,6},v(4);

//v:{1,2,3,6}
//itr:begin(v)+4
auto itr = remove_copy(begin(v2), end(v2), begin(v), 4);
ForwardIterator remove_copy_if (ForwardIterator first, ForwardIterator last, OutputIterator itrdest, UnaryPredicate pred)
Same as remove_if except elements are copied to itrdest  and returns an iterator to the new end of that range.

Examples:
vector<int> v2{1,2,3,4,4,6}, v(4);

//v:{1,2,3,6}
//itr:begin(v)+4
auto itr = remove_copy_if(begin(v2), end(v2), begin(v), [](int n){return (n == 4);});
  1. ForwardIterator unique (
    ForwardIterator     first, ForwardIterator last)
  2. ForwardIterator unique (
    ForwardIterator first, ForwardIterator last, 
    BinaryPredicate     pred)
Removes the elements in the range [first,last] to the range beginning at result, except consecutive duplicates (elements that compare equal to the element preceding).
Only the first element from every consecutive group of equivalent elements in the range [first,last] is Removed.
Elements are compared using == operator in the 1st version and pred in the 2nd version.
Example
vector<int> v;

//1
v.assign({1,2,2,3,4,4,6});
//v:{1,2,3,4,6}
//itr:begin(v)+5
auto itr = unique(begin(v), end(v));

//2
v.assign({1,2,2,3,4,4,6});
//v:{1,2,3,4,6}
//itr:begin(v)+5
itr = unique(begin(v), end(v), [] (int n, int n2){return (n == n2);});
  1. ForwardIterator unique_copy (
    ForwardIterator     first, ForwardIterator last, 
    OutputIterator     itrdest)
  2. ForwardIterator unique_copy(
    ForwardIterator first, ForwardIterator last, 
    OutputIterator     itrdest, BinaryPredicate pred)
Copies the elements in the range [first,last] to the range beginning at result, except consecutive duplicates (elements that compare equal to the element preceding).
Only the first element from every consecutive group of equivalent elements in the range [first,last] is copied.
The comparison between elements is performed by either applying operator==, or the template parameter pred (for the second version) between them.
Returns an iterator pointing to the element that follows the last element written in the itrdest sequence.

Examples:
unique_copy ([1,2,2,3].begin(),[1,2,2,3].end(), [1,2,3,4].begin()) 
returns [1,2,3,x].begin()+3.

unique_copy ([1,2,2,3].begin(), 1,2,2,3].end(), [1,2,3,4].begin(), 
issame)
returns [1,2,3,x].begin()+3.
Example
vector<int> v2,v(5);

//1
v2.assign({1,2,2,3,4,4,6});
//v:{1,2,3,4,6}
//itr:end(v)
auto itr = unique_copy(begin(v2), end(v2), begin(v));

//2
v2.assign({1,2,2,3,4,4,6});
//v:{1,2,3,4,6}
//itr:end
itr = unique_copy(begin(v2), end(v2), begin(v), [] (int n, int n2){return (n == n2);});
void reverse (
BidirectionalIterator first, BidirectionalIterator last)
Reverses the order of the elements in the range [first,last].

Examples:
vector<int> v({1,2,3,4,5});

//v:{5,4,3,2,1}
//itr:end(v)
reverse(begin(v), end(v));
OutputIterator reverse_copy (
BidirectionalIterator first, BidirectionalIterator last, 
OutputIterator itrdest)
Same as reverse except output is copied to itrdest.
Returns an iterator pointing to the element that follows the last element written in the itrdest sequence.

Examples:
vector<int> v2({1,2,3,4,5}),v(5);

//v:{5,4,3,2,1}
//itr:end(v)
auto itr = reverse_copy(begin(v2), end(v2), begin(v));
void rotate (
ForwardIterator first, ForwardIterator middle, 
ForwardIterator last)
Rotates the order of the elements in the range [first,last], in such a way that the element pointed by middle becomes the new first element.

Example:
vector<int> v{1,2,3,4};

//v:{3,4,1,2}
rotate (begin(v), begin(v)+2, end(v));
OutputIterator rotate_copy (
ForwardIterator first, ForwardIterator middle, 
ForwardIterator last, OutputIterator itrdst)
Same as rotate except output is copied to itrdest.
Returns an iterator pointing to the element that follows the last element written in the itrdest sequence.

Example:
vector<int> v2{1,2,3,4}, v(4);
//v:{3,4,1,2}
//itr:end(v)
auto itr = rotate_copy (begin(v2), begin(v2)+2, end(v2), begin(v));
  1. void random_shuffle (
    RandomAccessIterator first,
    RandomAccessIterator     last)
  2. void random_shuffle (
    RandomAccessIterator  first,
    RandomAccessIterator last,
    RandomNumberGenerator& gen)
Rearranges the elements in the range [first,last] randomly.
The function swaps the value of each element with that of some other randomly picked element. 
When provided, the function gen determines which element is picked in every case. Otherwise, the function uses some unspecified source of randomness.
Example
srand ( unsigned ( std::time(0) ) );
vector<int> v;
//1
v.assign({1,2,3,4});
//v:{3,4,2,1}}
random_shuffle (begin(v), end(v));
    
//2
//v:{2,1,3,4}
v.assign({1,2,3,4});
random_shuffle (begin(v), end(v), [](int i) { return std::rand()%i;});
void shuffle (
RandomAccessIterator first, 
RandomAccessIterator last, 
URNG&& g)
Rearranges the elements in the range [first,last] randomly, using g as uniform random number generator. The function swaps the value of each element with that of some other 
randomly picked element. The function determines the element picked by calling g().

Examples:
vector<int> v{1,2,3,4};

//v:{2,4,1,3}
shuffle(begin(v), end(v), default_random_engine(2018));

The example depicts the usage.

Summary of Examples
NameDescriptiongithubwandbox
  Example       Usage   source    output      source + output   




at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)