Algorithms and the string class

3.1 Loops with names

The <algorithm> header provides operations that take an iterator range: sort, find, count, find_if, transform, and many more. A range is written as begin() and end(), and algorithms do not know which container produced it. The same find works for a vector, a list, and a string's characters.

Many algorithms take a predicate or a comparison. A lambda is the shortest way to supply one: [](int value) { return value > 10; }. The compiler turns the lambda into a function object at the call site, so there is no function-pointer overhead in the usual case.

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

int main() {
    std::vector<int> scores = {72, 91, 64, 85};
    std::sort(scores.begin(), scores.end(), [](int a, int b) {
        return a > b;
    });
    for (int score : scores) {
        std::cout << score << "\n";
    }
    return 0;
}

91
85
72
64

3.1.1 Searching a range

std::find compares elements with == and returns an iterator to the first match, or end() when no element matches. std::find_if takes a predicate instead, which lets you search by a property rather than an exact value.

Always compare the result with the range's end() before dereferencing it. The operator* on end() is undefined. To get a position, subtract begin() from the iterator when the container supports random access. An index is convenient for a vector and meaningless for a list.

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

int main() {
    std::vector<int> scores = {61, 78, 92, 85};
    auto it = std::find_if(scores.begin(), scores.end(), [](int score) {
        return score >= 90;
    });
    if (it != scores.end()) {
        std::cout << "First high score: " << *it << "\n";
        std::cout << "Index: " << (it - scores.begin()) << "\n";
    }
    return 0;
}

First high score: 92
Index: 2

3.1.2 Sorting and comparing

std::sort orders a range in place and requires random-access iterators, so it works with vectors and arrays. A custom comparator decides which of two elements comes first. The comparator must return true when the first argument belongs before the second, and it must not return true for equal elements.

A lambda comparator fits short rules well. A named function is easier to reuse and test. For a stable order among equal elements, std::stable_sort keeps their original relative order. Pass the comparator after the two iterators, as in std::sort(first, last, compare).

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

int main() {
    std::vector<std::string> names = {"Mei", "Alex", "Ravi", "Jo"};
    std::sort(names.begin(), names.end(), [](const std::string& a, const std::string& b) {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    });
    for (const std::string& name : names) {
        std::cout << name << "\n";
    }
    return 0;
}

Jo
Mei
Alex
Ravi

3.1.3 The string class

std::string owns a sequence of characters and manages its storage. size() and empty() report the length, [] and at() access characters, and substr(start, length) returns a new string. find returns the first position of a substring, and rfind searches from the end.

find reports failure with std::string::npos, a special value that no valid position can equal. Compare the result with npos before using it as an index. Strings can be concatenated with +, appended with +=, and compared with the usual operators. A C API that needs a const char* accepts the pointer from c_str().

#include <iostream>
#include <string>

int main() {
    std::string line = "user: meera";
    auto colon = line.find(':');
    if (colon != std::string::npos) {
        std::string key = line.substr(0, colon);
        std::string value = line.substr(colon + 2);
        std::cout << "Key: " << key << "\n";
        std::cout << "Value: " << value << "\n";
    }
    std::cout << "Position: " << colon << "\n";
    return 0;
}

Key: user
Value: meera
Position: 4

3.1.4 Strings and numbers

std::to_string converts a number to text. std::stoi, std::stod, and their relatives convert text back, and they throw std::invalid_argument when the text is not a number. They also take an optional position pointer that reports where parsing stopped.

Reading a whole line needs std::getline(std::cin, line), because >> stops at the first space. If a previous >> read left a newline in the stream, call std::cin.ignore() before getline. These rules matter when a program mixes formatted reads with line reads.

#include <cstddef>
#include <iostream>
#include <string>

int main() {
    std::string text = "one two three";
    std::size_t start = 0;
    while (start < text.size()) {
        auto space = text.find(' ', start);
        if (space == std::string::npos) space = text.size();
        std::cout << text.substr(start, space - start) << "\n";
        start = space + 1;
    }
    return 0;
}

one
two
three

3.1.5 Changing size and combining algorithms

std::remove_if moves unwanted elements to the end and returns an iterator to the new logical end. It does not erase anything, because an algorithm cannot change a container's size. The erase call does the removal: v.erase(std::remove_if(...), v.end());. This combination is the remove-erase idiom.

std::accumulate from <numeric> folds a range into one value. std::transform reads one range and writes the result of a function into another. accumulate takes a range and an initial value whose type controls the result type.

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

int main() {
    std::vector<double> prices = {2.5, 4.0, 3.5};
    double total = std::accumulate(prices.begin(), prices.end(), 0.0);
    std::cout << std::fixed << std::setprecision(1);
    std::cout << "Total: " << total << "\n";
    std::cout << "Average: " << total / prices.size() << "\n";
    return 0;
}

Total: 10.0
Average: 3.3

3.1.6 Common mistakes and practice

Mistakes to watch for:

• Dereferencing the iterator returned by a failed find.
• Passing size() where an iterator range is expected.
• Writing a comparator that returns true for equal values.
• Using npos as an index.
• Modifying a container while an algorithm is walking it.
• Forgetting that remove_if does not erase elements.

Practice:

1. Sort a vector of integers in descending order with a lambda.
2. Use find_if to locate the first even number and print its index.
3. Sort names by length, then alphabetically for ties.
4. Split "key=value" at the equals sign and print both parts.
5. Read a line with getline, count its words, and print each word on a line.