Algorithms

Credits- 105 STL Algorithms in Less Than an Hour

Sort Example

The code examples will probably be given on the test.

1st way - Lambda

#include <iostream>
#include <algorithm>
#include <vector>
using std::vector, std::cout, std::endl;

int main() {
    std::vector<int> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    std::sort(s.begin(), s.end(), [](int a, int b) {return a > b;});

    for (const auto a : s)
        cout << a << " ";
}

9 8 7 6 5 4 3 2 1 0

2nd way - Functor (Function object)

struct my_functor {
    bool operator() (int i,int j) { return (i<j);}
};

int main(){
    vector<int> v {1,2,3,4,-1};
    sort(v.begin(), v.end(),my_functor{});

    for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << ' ' << *it;
}

-1 1 2 3 4

3rd way - function

bool my_compare (int i,int j) { return (i<j); }

int main(){
    vector<int> v {1,2,3,4,-1};
    sort(v.begin(), v.end(),my_compare);
    for (auto it=v.begin(); it!=v.end(); ++it)
        cout <<  *it  << ' ';
}

-1 1 2 3 4

Now will sort work on a list or a deque?

Hint: look at the iterator type

Hide

The solution is on the other tab.

Solution

Lets Start 🤩

Permutations

Province of Heaps

• make_heap

• push_heap

• pop_heap

Max Heap

std::make_heap

make_heap - C++ Reference

using std::vector, std::cout, std::endl;
int main() {
    vector<int> s = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::make_heap(s.begin(), s.end());

    for (const auto a : s)
        cout << a << " ";
}

9 8 6 7 4 5 2 0 3 1

std::push_heap

push_heap - C++ Reference

#include <iostream>
#include <algorithm>
#include <vector>
using std::vector, std::cout, std::endl;

int main() {
    vector<int> h = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::make_heap(h.begin(), h.end());

    h.push_back(99);
    std::push_heap (h.begin(),h.end());

    for (const auto a : h)
        cout << a << " ";
}

99 9 6 7 8 5 2 0 3 1 4

std::pop_head

pop_heap - C++ Reference

using std::vector, std::cout, std::endl;

int main() {
    vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::make_heap(v.begin(), v.end());
    std::cout << "max heap BEFORE pop : " << v.front() << '\n';

    std::pop_heap (v.begin(),v.end());
    v.pop_back();
    std::cout << "max heap AFTER pop : " << v.front() << '\n';

    for (const auto a : v)
        cout << a << " ";
}

max heap BEFORE pop : 9
max heap AFTER pop : 8
8 7 6 3 4 5 2 0 1

Heap Sort

sorting using pop_head

using std::vector, std::cout, std::endl;

int main() {
    vector<int> v = {0, 1, 2, 3, 4, 5};
    std::make_heap(v.begin(), v.end());

    for (int i = 0; i < v.size(); ++i)
        std::pop_heap (v.begin(),v.end()-i);

    for (const auto a : v)
        cout << a << " ";
}

0 1 2 3 4 5

Shore of Sorting

• sort

• partial_sort

• nth_element

• sort_heap

• inplace_merge

std::sort

sort - C++ Reference

#include <iostream>
#include <algorithm>
#include <vector>
using std::vector, std::cout, std::endl;

int main() {
    std::vector<int> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    std::sort(s.begin(), s.end(), [](int a, int b) {return a > b;});

    for (const auto a : s)
        cout << a << " ";
}

9 8 7 6 5 4 3 2 1 0

std::nth_element

nth_element - C++ Reference

int main() {
    vector<int> v = {0, 1, 2, 3, 4, 5, 7, 6, 8, 9};
    std::nth_element (v.begin(), v.begin()+5, v.end());

    for (const auto a : v)
        cout << a << " ";
}

1 0 4 3 2 5 7 6 8 9

std::inplace_merge

inplace_merge - C++ Reference

Takes two sorted partitions and combines them to one sorted partition

int main() {
    vector<int> v = {0, 2, 4, 6, 8, 1, 3, 5, 10};
    std::inplace_merge  (v.begin(), v.begin()+5, v.end());

    for (const auto a : v)
        cout << a << " ";
}

0 1 2 3 4 5 6 8 10

Partioning

• std::partition

• std::partition_point

partition_point - C++ Reference

Take any element that fulfills the predicate (the blues) and divide into two groups (blues and whites)

The first white is the partition point

#include <iostream>
#include <algorithm>
#include <vector>
using std::vector, std::cout, std::endl;

int main() {
    vector<int> v = {0, 2, 4, 6, 8, 1, 3, 5, 10};
    int N = 5;
    auto upper = std::partition(v.begin(), v.end(), [N](const auto& x){return x <= N;});

    cout  << "lower: ";
    for (auto it=v.begin(); it!=upper; ++it)
        cout  << *it  << " ";

    cout  << "\nupper: ";
    for (auto it=upper; it!=v.end(); ++it)
        cout  << *it  << " ";
}

lower: 0 2 4 5 3 1 
upper: 8 6 10

Other Permutations

• std::rotate

• std::shuffle

• std::next_permutation

• std::prev_permutation

rotate - C++ Reference

shuffle - C++ Reference

next_permutation - C++ Reference

prev_permutation - C++ Reference

Algo combination

Algos we can combine with other algos to create new algos

• stable

  • stable_sort - std::stable_sort preserves the original order for equal elements, while std::sort doesn't.

  • stable_partition - while partitioning keep relative order

• is

  • is_sorted

  • is_partitioned

  • is_heap

• is_until

  • is_sort_until

  • is_partitioned_until

  • is_heap_until

std::stable_sort

stable_sort - C++ Reference

int main() {
    vector<double> v = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};
    std::stable_sort (v.begin(), v.end(), [](int i, int j){ return int(i)< int(j); });
    for (const auto i : v)
        cout  << i  << " ";
}

1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67

Here we cast the doubles to ints: int(i)< int(j)

std::is_sorted

is_sorted - C++ Reference

Returns true if the range is sorted into ascending order.

int main() {
    std::array<int,4> arr {2,4,1,3};
    do {
        std::prev_permutation(arr.begin(),arr.end());
        cout << "arr:";
        for (int& x:arr) std::cout << ' ' << x; cout << '\n';
    } while (!std::is_sorted(arr.begin(),arr.end()));
}

arr: 2 3 4 1
arr: 2 3 1 4
...
arr: 1 2 3 4

std::is_sorted_until

is_sorted_until - C++ Reference

Find first unsorted element in range

int main() {
    std::array<int,4> arr {2,4,1,3};
    auto it=std::is_sorted_until(arr.begin(),arr.end());
    cout << *it << endl;
}

1

Queries

Numerical Algos

• count

• accumulate

• transform

• reduce (c++17, can run in parrallel)

• partial_sum

• inclusive_scan ( can run in parrallel)

• exclusive_scan

• inner_product

• adjacent_difference

• sample

std::count

count - C++ Reference

int main() {
    int arr[] {1, 2, 1, 2, 2};
    cout << "2 appears: " << std::count (arr, arr+5, 2) << " times";
}

2 appears: 3 times

std::accumulate

accumulate - C++ Reference

#include <numeric>
using std::vector, std::cout, std::endl;

int main() {
    vector<int>v {1,2,3,4,5};
    cout << "sum is: " << std::accumulate (v.begin(), v.end(), 0) << endl;
    cout << "x+3*y:  " << std::accumulate (v.begin(), v.end(), 0,[](int x, int y) {return x+3*y;});
}

sum is: 15
x+3*y:  45

$sum=\sum_{i=1}^{5} i = 15$ $x+3*y=1*3 + 2*3 + 3*3 + 4*3 + 5*3=\sum_{x=1}^{5} 3*x=45$

std::partial_sum

partial_sum - C++ Reference

int main() {
    vector<int>v {1,2,3,4,5}, result(5);
    std::partial_sum (v.begin(), v.end(), result.begin());

    for (const auto i : result)
        cout  << i  << " ";
}

1 3 6 10 15

$x[i]=\sum_{n=0}^{i} x[n]$

std::sample

std::sample - cppreference.com

Selects n elements from the sequence without replacement such that each possible sample has equal probability of appearance

int main(){
    std::string in = "abcdefgh", out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),5, std::mt19937{std::random_device{}()});
    std::cout << "five random letters out of " << in << ", result : " << out << '\n';
}

five random letters out of abcdefgh, result : bcfgh

or

int main() {
    vector<int>v {1,2,3,4,5,6,7,8,9,10}, result; //result doesn't need allocation, back_inserter will push_back automatically
    std::sample(v.begin(), v.end(), std::back_inserter(result),5, std::mt19937{std::random_device{}()});

    for (const auto i : result)
        cout  << i  << " ";
}

1 5 6 7 9

Querying a property - 1 range

• all_of

• any_of

• none_of

std::any_of

any_of - C++ Reference

int main() {
    vector<int>v {1,2,3,4,5,6,7,-8,9,10};
    cout << (std::any_of(v.begin(), v.end(),[](int i){return i<0;}) ? "there's a negatives" : "no negative");
}

there's a negatives

std::all_of

int main() {
    vector<int>v {1,2,3,4,5,6,7,8,9,10};
    cout << (std::all_of(v.begin(), v.end(), [](int i){return i>=0;}) ? "all are positive" : "there's a negative");
}

all are positive

Querying a property - 2 ranges

• equal

• lexicographical_compare

• mismatch

Searching a value

• unsorted

  • find

  • adjacent_find

• sorted

  • equal_range

  • lower_bound

  • upper_bound

  • binary_search

Movers

• move

• copy

• swap_ranges

• move_backward

• copy_backward

std::copy

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int result[5];
    std::copy(arr, arr + 5, result);

    for(const auto i : result)
        cout << i << " ";
}

1 2 3 4 5

Example 2

#include <vector>
#include <deque>
#include <iostream>
#include <iterator>
#include <algorithm>
int main(){
    std::vector<int> v{1,2,3,4,5};
    std::deque<int> d;
    std::copy(v.begin(), v.end(), std::front_inserter(d));
    for(int n : d)
        std::cout << n << ' ';
}

5 4 3 2 1

• A std::front_insert_iterator which can be used to add elements to the beginning of the container that supports a push_front operation

• A std::back_insert_iterator which can be used to add elements to the end of the container that supports a push_back operation

std::move

int main() {
    std::vector<std::string> old_v = {"air","water","fire","earth"};
    std::vector<std::string> new_v (4);
    std::move ( old_v.begin(), old_v.begin()+4, new_v.begin() ); //old_v.begin()+4==old.end()

    cout << "old_v, size: " << old_v.size() << endl;
    for(const auto i : old_v)
        cout << i << " "; cout << endl;

    cout << "new_v\n";
    for(const auto i : new_v)
        cout << i << " ";
}

old_v, size: 4

new_v
air water fire earth

Example 2

int main() {
    std::vector<std::string> old_v = {"air","water","fire","earth"};
    std::vector<std::string> new_v;
    new_v = std::move (old_v);

    cout << "old_v, size: " << old_v.size() << endl;
    for(const auto i : old_v)
        cout << i << " "; cout << endl;

    cout << "new_v\n";
    for(const auto i : new_v)
        cout << i << " ";
}

old_v, size: 0

new_v
air water fire earth

Notice the size is 0.

For more about std::move look at R-value references and move constructors.

std::copy_backward

Value Modifiers

• fill

• generate

• iota

• replace

std::generate

int main(){
    vector<int> v(5);
    std::generate(v.begin(), v.end(), std::rand);
    for (auto i1: v)
        std::cout << i1 << " ";
}

1804289383 846930886 1681692777 1714636915 1957747793

std::generate_n

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <map>
using std::vector, std::string, std::cout;

class Point{
    int x;
    int y;
public:
    Point(int ix = 0 , int iy = 0) :x(ix), y(iy) {} //use only this construction
    int getX() const { return x; }
    int getY() const { return y; }
    friend std::ostream& operator<< (std::ostream& ostr, const Point& p) { ostr << p.x << "  " << p.y << "\n"; return ostr; }
};


Point&& genPoint(){
    srand(time(0));
    return std::move(Point(rand() % 100, rand() % 100));
}

int main() {
    vector<Point> v2(5);
    std::generate_n(v2.begin(), 5, genPoint);
    for (auto i1 : v2) {
        cout << i1 << " ";
    }
}

39  42
 39  42
 39  42
 39  42
 39  42

Structure Changers

• remove

• unique

std::remove

int main() {
    vector<int> v = { 1, 1, 3, 3, 3, 10, 1, 3, 3, 7, 7, 8 }, i;
    auto it_end = std::remove(v.begin(), v.end(),3); //remove 3's

    for (auto it = v.begin(); it != it_end; ++it)
        cout << *it << " "; cout << endl;

    for (auto i : v)
        cout << i << " ";
}

1 1 10 1 7 7 8 
1 1 10 1 7 7 8 3 3 7 7 8

std::unique

int main() {
    vector<int> v = { 1, 1, 3, 3, 3, 10, 1, 3, 3, 7, 7, 8 }, i;
    auto it_end = std::unique(v.begin(), v.begin() + 12);// Now v becomes {1 3 10 1 3 7 8 * * * * *} , * means undefined

    for (auto it = v.begin(); it != it_end; ++it)
        cout << *it << " "; cout << endl;

    for (auto i : v)
        cout << i << " ";
}

1 3 10 1 3 7 8 
1 3 10 1 3 7 8 3 3 7 7 8

Notice it didn't get rid of all the duplicates and return a set but rather got rid of each duplicate adjacent to another.

std-unique.jpg

*_COPY

• remove_copy

• unique_copy

• reverse_copy

• rotate_copy

• replace_copy

• partition_copy

• partial_sort_copy

std::remove_copy

Example 1:

int main () {
    int myints[] = {10,20,30,30,20,10,10,20};                             // 10 20 30 30 20 10 10 20
    std::vector<int> new_vector (8);
    auto end_it = std::remove_copy (myints,myints+8,new_vector.begin(),20);// 10   30 30    10 10  0 0 0

    for (auto it=new_vector.begin(); it!=end_it; ++it)
        std::cout << ' ' << *it;
}

10 30 30 10 10

Example 2:

int main () {
    int myints[] = {10,20,30,30,20,10,10,20};                // 10 20 30 30 20 10 10 20
    std::vector<int> new_vector (8);
    std::remove_copy (myints,myints+8,new_vector.begin(),20);// 10    30 30    10 10  0 0 0

    for (const auto i : new_vector)
        cout << i << ' ';
}

10 30 30 10 10 0 0 0

*_IF

• find_if

• find_if_not

• count_if

• remove_if

• remove_copy_if

• replace_if

• replace_copy_if

• copy_if

std::count_if

int main(){
    vector<int> v {1,2,3,4,-1};
    int N=2;
    cout << count_if(v.begin(), v.end(),[N](int a){ return (a >= N);}) <<endl;
}

3

transform

int main(){
    std::vector<int> foo;
    std::vector<int> bar(6);
    for (int i=1; i<6; i++)
        foo.push_back (i*10);// foo: 10 20 30 40 50

    int N = 2;
    std::transform (foo.begin(), foo.end(), bar.begin(), [N](int i) { return i+=N; }); // bar: 12 22 32 42 52
    std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
    for (auto i : foo)
        cout << i << " ";
}

foo.begin(), std::plus: foo is the output and std::plus adds together its two arguments, we could have use a lambda instead