< Previous
Next >

 

C++ Algorithms

Introduction

In C++, the Standard Template Library (STL) provides a vast collection of algorithms designed to simplify common tasks like searching, sorting, transforming, and modifying data stored in containers such as vectors, lists, arrays, etc. The algorithms are generic, meaning they work seamlessly with different types of containers, provided the data structure supports iterators.

These algorithms make C++ programming easier and more efficient, enabling developers to focus on solving problems rather than writing low-level code for fundamental tasks.

Types of C++ Algorithms

C++ algorithms can be broadly categorized into the following types:

  1. Searching Algorithms: Used to find elements within a container.
  2. Sorting Algorithms: Used to arrange the elements of a container in a specified order.
  3. Transforming Algorithms: Used to modify or manipulate elements in a container.
  4. Non-modifying Algorithms: Used for tasks that don't modify the container, such as counting elements or checking conditions.
  5. Partitioning Algorithms: Used to partition a container into subsets.
  6. Numeric Algorithms: Algorithms designed specifically for numerical operations.

Using Algorithms in C++

Algorithms in C++ are included via the <algorithm> header file. Most algorithms take two iterators as parameters, representing the range of elements to apply the algorithm to.

Here's a basic template of how to use an algorithm:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 5, 3, 4, 2};

    // Use algorithm with iterators
    std::sort(vec.begin(), vec.end());

    // Print sorted vector
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

1. Sorting Algorithms

Sorting is one of the most commonly used operations in programming. C++ provides a built-in algorithm for sorting, std::sort(), which can sort elements in ascending or descending order.

Example: Sorting a Vector in Ascending Order

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {4, 1, 3, 9, 2};

    // Sort the vector in ascending order
    std::sort(vec.begin(), vec.end());

    // Print the sorted vector
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

Output:

1 2 3 4 9

Example: Sorting in Descending Order

You can sort in descending order by providing a custom comparator:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {4, 1, 3, 9, 2};

    // Sort the vector in descending order using a lambda function
    std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });

    // Print the sorted vector
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

Output:

9 4 3 2 1

2. Searching Algorithms

Searching algorithms are used to find a specific element within a container. One of the most commonly used search algorithms is std::find(), which returns an iterator to the first occurrence of the specified element.

Example: Searching for an Element

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Search for element 3 in the vector
    auto it = std::find(vec.begin(), vec.end(), 3);

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

    return 0;
}

Output:

Element found at position: 2

3. Non-modifying Algorithms

These algorithms do not alter the container but perform operations such as counting, checking conditions, or finding the maximum/minimum element.

Example: Count Occurrences of an Element

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 2, 3, 4, 2, 5};

    // Count occurrences of the number 2
    int count = std::count(vec.begin(), vec.end(), 2);

    std::cout << "Number of occurrences of 2: " << count << std::endl;

    return 0;
}

Output:

Number of occurrences of 2: 3

4. Transforming Algorithms

Transforming algorithms modify elements of a container. One such algorithm is std::transform(), which applies a function to each element in a range.

Example: Squaring Each Element in a Vector

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Square each element using transform
    std::transform(vec.begin(), vec.end(), vec.begin(), [](int n) { return n * n; });

    // Print the transformed vector
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

Output:

1 4 9 16 25

5. Partitioning Algorithms

Partitioning algorithms divide the elements of a container into two groups based on a condition.

Example: Partitioning a Vector

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6};

    // Partition the vector into even and odd numbers
    auto it = std::partition(vec.begin(), vec.end(), [](int n) { return n % 2 == 0; });

    // Print the partitioned vector
    for (auto i = vec.begin(); i != it; ++i) {
        std::cout << *i << " ";  // Even numbers
    }
    std::cout << "| ";
    for (auto i = it; i != vec.end(); ++i) {
        std::cout << *i << " ";  // Odd numbers
    }

    return 0;
}

Output:

2 4 6 | 1 3 5

6. Numeric Algorithms

Numeric algorithms are designed specifically for performing arithmetic or mathematical operations on containers.

Example: Accumulate the Sum of Elements

#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Calculate the sum of all elements in the vector
    int sum = std::accumulate(vec.begin(), vec.end(), 0);

    std::cout << "Sum of elements: " << sum << std::endl;

    return 0;
}

Output:

Sum of elements: 15

 



< Previous
Next >