C++ STL Algorithms Basics | sort· find

C++ STL Algorithms Basics | sort· find

· 35분 읽기 · 수정 Beginner Concept
C++ STL Algorithms Basics | sort· find

Introduction: Manual loops bred bugs

“Sorting, searching, summing—I rewrite loops every time”

Hand-rolled bubble sort, linear search, and sum loops are error-prone (off-by-one, invalid iterators). STL algorithms take half-open ranges [first, last) and a predicate or operation—usually clearer and well-tested. STL rewrite of the naive example:

#include <algorithm>
#include <numeric>
std::vector<int> vec = {5, 2, 8, 1, 9};
std::sort(vec.begin(), vec.end());
auto it = std::find(vec.begin(), vec.end(), 8);
int index = (it != vec.end()) ? static_cast<int>(std::distance(vec.begin(), it)) : -1;
int sum = std::accumulate(vec.begin(), vec.end(), 0);
flowchart TB
  subgraph problem[Common mistakes]
    P1[Manual loops → index bugs]
    P2["Sorted data but linear find"]
    P3[remove without erase]
    P4[Wrong comparator]
  end
  subgraph solution[Fix]
    S1[STL algorithms]
    S2[lower_bound / binary_search]
    S3[erase-remove idiom]
    S4[Strict weak ordering]
  end
  P1 --> S1
  P2 --> S2
  P3 --> S3
  P4 --> S4

Table of contents

  1. Problem scenarios
  2. sort
  3. find
  4. count and accumulate
  5. transform
  6. Examples
  7. Common errors
  8. Best practices
  9. Production patterns
  10. Checklist

1. Problem scenarios

  • Big data sorted with O(n²) → use std::sort O(n log n)
  • Sorted range search with find → use lower_bound O(log n)
  • Counting with manual loops → count_if
  • remove without erase → size unchanged → erase-remove
  • Product with accumulate(..., 0, multiplies) — wrong; use initial value 1 for products

2. sort

std::sort(vec.begin(), vec.end());
std::sort(vec.begin(), vec.end(), std::greater<int>());

Custom comparator: strict weak ordering—typically return a < b for ascending. stable_sort preserves relative order of equal elements.

3. find

  • find: linear search for value
  • find_if: first element satisfying predicate
  • Sorted range: binary_search, lower_bound, upper_bound

4. count and accumulate

int n2 = std::count(vec.begin(), vec.end(), 2);
int evens = std::count_if(vec.begin(), vec.end(), [](int x){ return x % 2 == 0; });
int sum = std::accumulate(vec.begin(), vec.end(), 0);
int prod = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>());

String concatenation: start from std::string(), not "" as const char* (avoid subtle issues).

5. transform

Unary: transform each element to output range. In-place: output vec.begin(). Binary: combine two sequences element-wise (same length discipline).

6. Examples

A self-contained pass that combines sort, find, count, transform, and the erase-remove idiom:

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> scores = {72, 95, 48, 88, 61, 95, 30};
    // sort
    std::sort(scores.begin(), scores.end());
    // find (sorted, so binary_search/lower_bound are valid here)
    bool has95 = std::binary_search(scores.begin(), scores.end(), 95);
    // count_if: how many passing scores (>= 60)
    int passing = std::count_if(scores.begin(), scores.end(),
                                 [](int s) { return s >= 60; });
    // transform: curve every score by +5, capped at 100
    std::vector<int> curved(scores.size());
    std::transform(scores.begin(), scores.end(), curved.begin(),
                    [](int s) { return std::min(100, s + 5); });
    // accumulate: average of the curved scores
    double avg = std::accumulate(curved.begin(), curved.end(), 0.0) / curved.size();
    // erase-remove: drop any score below 40 from the original list
    scores.erase(std::remove_if(scores.begin(), scores.end(),
                                 [](int s) { return s < 40; }),
                 scores.end());
    std::cout << "has95=" << has95 << " passing=" << passing
              << " avg=" << avg << " remaining=" << scores.size() << "\n";
    return 0;
}

Each step reuses the same half-open-range convention (begin()/end()), so no index bookkeeping is needed between steps — the output of one algorithm feeds directly into the next.

7. Common errors

  1. Dereference find result without != end()
  2. remove only—must erase from new_end to end()
  3. transform output range too small—size or back_inserter
  4. Product accumulate with initial 0
  5. lower_bound on unsorted data → meaningless
  6. Comparator <= for sort → not a strict weak ordering

8. Best practices

  • Use const Person& in predicates for large structs
  • reserve before back_inserter when size known
  • Check is_sorted before binary search if unsure

9. Production patterns

  • erase-remove / erase-remove_if
  • sort + unique + erase for duplicates
  • minmax_element for min and max in one pass
  • merge on sorted inputs

10. Checklist

  • Sorted? → binary search APIs
  • remove → paired erase
  • find → check end
  • accumulate product → init 1

FAQ

Default toolkit?

A. sort, find/find_if, count_if, accumulate, transform cover most loops.

Sorted vector vs set?

A. Many searches, few inserts: sorted vector + binary search can be faster/more cache-friendly. Frequent inserts/erases: set/map.

C++20 ranges?

A. std::ranges::sort(vec) and friends reduce iterator noise—see cppreference. One-line summary: Prefer STL algorithms over ad-hoc loops; pair remove with erase, and use lower_bound on sorted data. Previous: vector basics
Next: STL algorithms deep dive

Keywords

C++, STL, algorithm, std::sort, std::find, std::transform, std::accumulate, lambda, predicate

References

Other articles related to this topic.

Keywords Covered in This Article (Related Search Terms)

This article covers C++, STL, Algorithm, std::sort, std::find, std::count, std::transform, std::accumulate.