C++: STL Algorithms

1. STL Algorithm Overview

(1) 1.1 What Are STL Algorithms?

STL algorithms are a set of generic function templates provided by the C++ standard library for manipulating data in containers.

Why use STL algorithms?

Writing it yourself	STL algorithms
Need to write loops	One line of code
Error-prone	Thoroughly tested
Performance may vary	Highly optimized
Verbose code	Concise code

Real-life analogy:

Writing algorithms yourself = hand-washing clothes (time-consuming and laborious)
STL algorithms = washing machine (one button and done)

(2) 1.2 Algorithm Header Files

Most STL algorithms are in the algorithm header, and numeric algorithms are in numeric.

▶ Example 2: STL Algorithm Application (Difficulty ⭐)

TEXT 📖 Display only

#include <algorithm> // Most algorithms
#include <numeric> // Numeric algorithms (accumulate, etc.)

TEXT 📖 Display only

(program output)

(3) 1.3 Algorithm Categories

STL algorithms are divided into several major categories by function:

Category	Representative Algorithms	Description
Non-modifying	`find`, `count`, `for_each`	Don't modify container contents
Modifying	`copy`, `transform`, `replace`	Modify container contents
Sorting	`sort`, `stable_sort`, `partial_sort`	Sorting-related
Binary search	`binary_search`, `lower_bound`	Search in sorted ranges
Merge	`merge`, `inplace_merge`	Merge sorted ranges
Numeric	`accumulate`, `inner_product`	Numerical computation
Set	`set_union`, `set_intersection`	Set operations

2. Non-Modifying Algorithms

(1) 2.1 find — Finding Elements

Function: Find a specified element in a container, returning an iterator.

Prototype:

CPP

InputIt find(InputIt first, InputIt last, const T& value);

Example: Finding a score (Difficulty ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Find score 90
 auto it = std::find(scores.begin(), scores.end(), 90);
 
 if (it != scores.end()) {
 // Calculate position (index)
 int index = std::distance(scores.begin(), it);
 std::cout << "Found score 90 at position: " << index << std::endl;
 } else {
 std::cout << "Score 90 not found" << std::endl;
 }
 
 return 0;
}

TEXT 📖 Display only

Found score 90 at position: 3

💡 Tip:

Returns last (typically end()) when not found
Time complexity: O(n)

(2) 2.2 count — Counting

Function: Count the number of elements equal to a specified value.

Example: Counting perfect scores (Difficulty ⭐)

CPP

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

int main() {
 std::vector<int> scores = {100, 85, 100, 92, 78, 100};
 
 // Count perfect scores (100)
 int perfect = std::count(scores.begin(), scores.end(), 100);
 
 std::cout << "Number of perfect scores: " << perfect << std::endl; // Output: 3
 
 return 0;
}

(3) 2.3 for_each — Iteration

Function: Perform a specified operation on each element in a container.

Example: Print all scores (Difficulty ⭐)

TEXT 📖 Display only

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Use a lambda expression to print each score
 std::for_each(scores.begin(), scores.end(), (int s) {
 std::cout << s << " ";
 });
 std::cout << std::endl;
 
 return 0;
}

TEXT 📖 Display only

85 92 78 90 88

💡 Tip:

for_each is more concise than writing loops by hand
Very powerful when combined with lambda expressions

3. Modifying Algorithms

(1) 3.1 copy — Copying

Function: Copy elements from one range to another.

Example: Array copy (Difficulty ⭐)

CPP

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

int main() {
 std::vector<int> src = {1, 2, 3, 4, 5};
 std::vector<int> dst(5); // Destination container, size 5
 
 // Copy
 std::copy(src.begin(), src.end(), dst.begin());
 
 // Print result
 for (int x : dst) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

(2) 3.2 transform — Transformation

Function: Transform elements from one range and copy to another.

Example: Weighted scores (Difficulty ⭐⭐)

TEXT 📖 Display only

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 std::vector<int> adjusted(scores.size()); // Adjusted scores
 
 // Regular coursework 70%, exam 30%
 std::transform(scores.begin(), scores.end(), adjusted.begin(),
 (int s) { return s * 0.7 + 90 * 0.3; });
 
 std::cout << "Adjusted scores: ";
 for (int x : adjusted) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

TEXT 📖 Display only

Adjusted scores: 86.5 91.9 81.6 90 88.6

(3) 3.3 replace — Replacing

Function: Replace elements equal to a certain value with another value.

Example: Makeup exam score processing (Difficulty ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Replace failing scores (<60) with 60 (makeup exam passing line)
 std::replace_if(scores.begin(), scores.end(),
 (int s) { return s < 60; },
 60);
 
 std::cout << "Processed scores: ";
 for (int x : scores) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

4. Sorting Algorithms

(1) 4.1 sort — Sorting

Function: Sort a range in a container (ascending by default).

Example: Sorting scores (Difficulty ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Sort ascending
 std::sort(scores.begin(), scores.end());
 
 std::cout << "Ascending: ";
 for (int x : scores) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 // Sort descending
 std::sort(scores.begin(), scores.end(), std::greater<int>());
 
 std::cout << "Descending: ";
 for (int x : scores) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

TEXT 📖 Display only

Ascending: 78 85 88 90 92 
Descending: 92 90 88 85 78

(2) 4.2 Custom Sort Rules

Example: Sort students by score (Difficulty ⭐⭐)

CPP

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

struct Student {
 std::string name;
 int score;
};

int main() {
 std::vector<Student> students = {
 {"Zhang San", 85},
 {"Li Si", 92},
 {"Wang Wu", 78}
 };
 
 // Sort by score descending
 std::sort(students.begin(), students.end(),
 (const Student& a, const Student& b) {
 return a.score > b.score;
 });
 
 std::cout << "Score ranking:" << std::endl;
 for (const auto& s : students) {
 std::cout << s.name << ": " << s.score << std::endl;
 }
 
 return 0;
}

TEXT 📖 Display only

Score ranking:
Li Si: 92
Zhang San: 85
Wang Wu: 78

5. Numeric Algorithms

(1) 5.1 accumulate — Summation

Function: Compute the cumulative sum of elements in a range.

Example: Calculate total score (Difficulty ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Calculate total score
 int total = std::accumulate(scores.begin(), scores.end(), 0);
 
 std::cout << "Total score: " << total << std::endl; // Output: 433
 std::cout << "Average: " << total / 5.0 << std::endl; // Output: 86.6
 
 return 0;
}

(2) 5.2 Inner Product

Example: Vector dot product (Difficulty ⭐⭐)

CPP

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

int main() {
 std::vector<int> v1 = {1, 2, 3};
 std::vector<int> v2 = {4, 5, 6};
 
 // Compute dot product: 1*4 + 2*5 + 3*6 = 32
 int dot_product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
 
 std::cout << "Vector dot product: " << dot_product << std::endl; // Output: 32
 
 return 0;
}

6. Comprehensive Example

▶ Example 1: Score Analysis System (Difficulty ⭐⭐⭐)

TEXT 📖 Display only

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88, 76, 95, 83, 89, 91};
 
 // 1. Calculate total number of students
 int count = scores.size();
 std::cout << "Total students: " << count << std::endl;
 
 // 2. Calculate total and average score
 int total = std::accumulate(scores.begin(), scores.end(), 0);
 double average = static_cast<double>(total) / count;
 std::cout << "Total score: " << total << ", Average: " << average << std::endl;
 
 // 3. Find highest and lowest scores
 int max_score = *std::max_element(scores.begin(), scores.end());
 int min_score = *std::min_element(scores.begin(), scores.end());
 std::cout << "Highest: " << max_score << ", Lowest: " << min_score << std::endl;
 
 // 4. Count passing students
 int passed = std::count_if(scores.begin(), scores.end(),
 (int s) { return s >= 60; });
 std::cout << "Students passed: " << passed << std::endl;
 
 // 5. Sort and output top 3
 std::vector<int> top3 = scores;
 std::sort(top3.begin(), top3.end(), std::greater<int>());
 std::cout << "Top 3: ";
 for (int i = 0; i < 3; i++) {
 std::cout << top3[i] << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

TEXT 📖 Display only

85 92 78 90 88 76 95 83 89 91

TEXT 📖 Display only

Total students: 10
Total score: 867, Average: 86.7
Highest: 95, Lowest: 76
Students passed: 10
Top 3: 95 92 91

7. Algorithm Usage Tips

(1) 7.1 Iterator Helper Functions

Function	Purpose
`std::distance(first, last)`	Calculate distance between two iterators
`std::advance(it, n)`	Advance an iterator by n steps
`std::next(it)`	Return the next iterator
`std::prev(it)`	Return the previous iterator

(2) 7.2 Advanced Lambda Expressions

Lambda expressions are a great companion for STL algorithms:

CPP

// Basic form
[capture](parameters) -> return_type { body }

// Example: Sort by multiple criteria
std::sort(students.begin(), students.end(),
 (const Student& a, const Student& b) {
 if (a.score != b.score)
 return a.score > b.score; // First by score
 return a.name < b.name; // Then by name
 });

❓ FAQ

Q Are STL algorithms faster than loops?

A STL algorithms are typically faster because: - Highly optimized - Have specialized versions for different containers - Compilers can optimize them better

Q Can all containers use STL algorithms?

A Theoretically yes, but efficiency varies: - Sequential containers (vector, deque): high efficiency - Associative containers (set, map): have their own member functions, which are faster

Basic syntax:

TEXT 📖 Display only

[capture](params) -> return_type { body }

Example:

CPP

auto add = (int a, int b) { return a + b; };
std::cout << add(3, 5) << std::endl; // Output: 8

Q What if an algorithm reports an error?

A Common errors: 1. Using binary search on an unsorted container → sort first 2. Destination container too small → use back_inserter 3. Iterator type mismatch → check container type

▶ Example 3: sort (Difficulty ⭐)

CPP

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9};

    std::sort(v.begin(), v.end());

    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

▶ Try it Yourself

TEXT 📖 Display only

1 2 3 4 5

💡 Tip: std::sort sorts in ascending order by default, taking an iterator range [begin, end).

📖 Summary

STL algorithms: generic function templates for manipulating container data
Non-modifying algorithms: find, count, for_each
Modifying algorithms: copy, transform, replace
Sorting algorithms: sort + custom comparison functions
Numeric algorithms: accumulate (summation)
Lambda: anonymous functions, used in combination with algorithms

Study recommendations:

Use STL algorithms more, write fewer manual loops
Get familiar with common algorithms; look up documentation for less common ones
Combine with Lambda expressions for more concise code

📝 Exercises

Basic (Difficulty ⭐): Create a vector<int> with 10 random numbers, sort it with sort and output, then reverse it with reverse and output.
Intermediate (Difficulty ⭐⭐): Use find to search for a specified string in vectorstring, and use count to count how many times a value appears.
Challenge (Difficulty ⭐⭐⭐): Use remove_if and a lambda to implement "remove all even numbers from a vector". Understand the erase-remove idiom.

STL algorithms operate on iterator ranges, decoupled from containers
Common algorithms: sort/find/count/copy/reverse
Algorithm categories: read-only (find/count), write (copy/fill), sorting (sort)
Lambda expressions as algorithm parameters are more concise
Algorithms + lambda are more concise and safer than hand-written loops

Next lesson: Practice: OOP Comprehensive (#36) — Refactoring the student management system using object-oriented thinking

Web-Tutorial Tech Team

A team of developers maintaining programming tutorials. Each tutorial is written and reviewed by developers with expertise in that field. We work to keep our content accurate and reliable — if you spot an issue, please let us know.

About Us

C++: STL Algorithms

1. STL Algorithm Overview

(1) 1.1 What Are STL Algorithms?

(2) 1.2 Algorithm Header Files

▶ Example 2: STL Algorithm Application (Difficulty ⭐)

(3) 1.3 Algorithm Categories

2. Non-Modifying Algorithms

(1) 2.1 find — Finding Elements

(2) 2.2 count — Counting

(3) 2.3 for_each — Iteration

3. Modifying Algorithms

(1) 3.1 copy — Copying

(2) 3.2 transform — Transformation

(3) 3.3 replace — Replacing

4. Sorting Algorithms

(1) 4.1 sort — Sorting

(2) 4.2 Custom Sort Rules

5. Numeric Algorithms

(1) 5.1 accumulate — Summation

(2) 5.2 Inner Product

6. Comprehensive Example

▶ Example 1: Score Analysis System (Difficulty ⭐⭐⭐)

7. Algorithm Usage Tips

(1) 7.1 Iterator Helper Functions

(2) 7.2 Advanced Lambda Expressions

❓ FAQ

▶ Example 3: sort (Difficulty ⭐)

📖 Summary

📝 Exercises

🙏 帮我们做得更好