C++ Algorithm

Welcome to The Coding College! In this tutorial, we’ll explore the Algorithm Library in C++. Algorithms are pre-defined, highly optimized functions provided by the Standard Template Library (STL). These functions simplify coding and improve performance by handling complex operations like searching, sorting, and manipulation of containers.

What Is the Algorithm Library?

The algorithm library in C++ provides a collection of functions for common operations such as:

  • Searching
  • Sorting
  • Merging
  • Modifying
  • Other mathematical and logical operations

To use these functions, include the <algorithm> header.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

Categories of Algorithms

1. Non-Modifying Algorithms

Algorithms that don’t change the contents of the container.
Examples: find(), count(), all_of(), any_of()

2. Modifying Algorithms

Algorithms that change the container’s elements.
Examples: sort(), reverse(), replace()

3. Sorting Algorithms

Efficiently sort containers.
Examples: sort(), stable_sort(), partial_sort()

4. Set Algorithms

Perform operations on sets like union, intersection, etc.
Examples: set_union(), set_difference()

Commonly Used Algorithms

1. Searching

find()

Finds the first occurrence of a specific value in a container.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};

    auto it = find(nums.begin(), nums.end(), 30);

    if (it != nums.end()) {
        cout << "Found 30 at position: " << distance(nums.begin(), it) << endl;
    } else {
        cout << "30 not found." << endl;
    }

    return 0;
}

Output:

Found 30 at position: 2

2. Counting

count()

Counts the occurrences of a specific value in a container.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 20, 30, 20};

    int countValue = count(nums.begin(), nums.end(), 20);
    cout << "20 appears " << countValue << " times." << endl;

    return 0;
}

Output:

20 appears 3 times.

3. Sorting

sort()

Sorts a container in ascending order by default.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {40, 10, 30, 20};

    sort(nums.begin(), nums.end());

    cout << "Sorted array: ";
    for (int num : nums) {
        cout << num << " ";
    }

    return 0;
}

Output:

Sorted array: 10 20 30 40

Custom Comparator

Sort in descending order using a custom comparator.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {40, 10, 30, 20};

    sort(nums.begin(), nums.end(), greater<int>());

    cout << "Sorted in descending order: ";
    for (int num : nums) {
        cout << num << " ";
    }

    return 0;
}

Output:

Sorted in descending order: 40 30 20 10

4. Reversing

reverse()

Reverses the order of elements in a container.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 30, 40};

    reverse(nums.begin(), nums.end());

    cout << "Reversed array: ";
    for (int num : nums) {
        cout << num << " ";
    }

    return 0;
}

Output:

Reversed array: 40 30 20 10

5. Min and Max

min_element() and max_element()

Find the smallest or largest element in a container.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {10, 20, 5, 30};

    auto minIt = min_element(nums.begin(), nums.end());
    auto maxIt = max_element(nums.begin(), nums.end());

    cout << "Minimum element: " << *minIt << endl;
    cout << "Maximum element: " << *maxIt << endl;

    return 0;
}

Output:

Minimum element: 5  
Maximum element: 30

6. Set Operations

set_union()

Computes the union of two sorted sets.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> set1 = {1, 2, 3};
    vector<int> set2 = {2, 3, 4};
    vector<int> result(6);

    auto it = set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin());
    result.resize(it - result.begin());

    cout << "Union of sets: ";
    for (int num : result) {
        cout << num << " ";
    }

    return 0;
}

Output:

Union of sets: 1 2 3 4

Advanced Example: Finding Subarrays That Sum to a Target

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

bool checkSum(vector<int> nums, int target) {
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        int sum = 0;
        for (auto jt = it; jt != nums.end(); ++jt) {
            sum += *jt;
            if (sum == target) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int target = 9;

    if (checkSum(nums, target)) {
        cout << "A subarray with the target sum exists!" << endl;
    } else {
        cout << "No subarray matches the target sum." << endl;
    }

    return 0;
}

Summary

  • The C++ Algorithm Library simplifies complex operations on containers.
  • Provides efficient, ready-to-use implementations for searching, sorting, and manipulating data.
  • Can significantly reduce development time and improve performance.

Learn More at The Coding College

Visit The Coding College for more tutorials on C++ algorithms, STL, and data structures!

Leave a Comment