C++ STL Algorithms Besides Sort

1. Binary Search Family (std::lower_bound, std::upper_bound, std::binary_search)

These algorithms operate on partitioned or sorted ranges. They require at least Forward Iterators. If provided Random Access Iterators, they execute in logarithmic time; otherwise, logarithmic comparisons but linear iterator advancements.

Under the Hood

• std::lower_bound: Returns an iterator pointing to the first element that is not less than (i.e., \ge) the target value.
• std::upper_bound: Returns an iterator pointing to the first element that is greater than (i.e., >) the target value.
• std::binary_search: Returns a boolean. Typically implemented as a direct call: lower_bound(first, last, val) != last && !(val < *lower_bound(...)).

Implementation details: The algorithm calculates the distance between first and last. It repeatedly halves the distance using bitwise shifts (step = count >> 1). It advances an iterator by step. If the element is strictly less than the target, first is moved past the element, and count is updated to count - (step + 1).

Big-O Complexity

• Time: O(log N) comparisons. O(log N) iterator operations for Random Access Iterators (e.g., std::vector), O(N) iterator operations for Forward/Bidirectional Iterators (e.g., std::list).
• Space: O(1).

Memory Layout & State Diagram

[ Sorted Array: Target = 45 ]
+----+----+----+----+----+----+----+----+----+
| 10 | 20 | 30 | 45 | 45 | 45 | 60 | 70 | 80 |
+----+----+----+----+----+----+----+----+----+
                 ^              ^
                 |              |
           lower_bound    upper_bound
           (First >= 45)  (First > 45)

[ Binary Search Halving ]
Distance = 9. Half = 4. Mid = index 4 (Value 45).
45 is not < 45. Search left half.

Typical Usage Scenarios

• lower_bound: Finding the insertion point in a sorted array to maintain order.
• upper_bound: Finding the strict upper limit for range queries.
• Range length: std::distance(lower_bound, upper_bound) yields the exact count of duplicates of a specific value in a sorted array (O(log N) compared to O(N) for std::count).

Usage Example

#include <vector>
#include <algorithm>

void searchRoutines(const std::vector<int>& sortedData) {
    int target = 45;
    
    // Check existence
    bool exists = std::binary_search(sortedData.begin(), sortedData.end(), target);
    
    // Find boundaries
    auto lower = std::lower_bound(sortedData.begin(), sortedData.end(), target);
    auto upper = std::upper_bound(sortedData.begin(), sortedData.end(), target);
    
    // Extract sub-range of all identical elements
    int duplicateCount = std::distance(lower, upper);
}

---

2. Linear Scan Algorithms (std::find, std::count, std::replace)

Sequential algorithms executing unconditional or conditional operations across a range.

Under the Hood

• std::find: Requires Input Iterators. Iterates via while (first != last). Checks *first == value. Returns first upon match, or last if exhausted.
• std::count: Requires Input Iterators. Accumulates an internal counter when *first == value.
• std::replace: Requires Forward Iterators (must be able to write). Modifies *first = new_value when *first == old_value.

Big-O Complexity

• Time: Strict O(N). Evaluates exactly N elements (except find, which short-circuits on first match).
• Space: O(1).

Memory Layout & State Diagram

[ std::replace(first, last, 0, 99) ]
+----+----+----+----+----+----+
| 5  | 0  | 3  | 0  | 0  | 8  |  <- Initial
+----+----+----+----+----+----+
       |         |    |
       v         v    v
+----+----+----+----+----+----+
| 5  | 99 | 3  | 99 | 99 | 8  |  <- Mutated State
+----+----+----+----+----+----+

Typical Usage Scenarios

• find: Checking existence in unsorted data or retrieving object references.
• count: Validating frequencies of specific error codes in logs.
• replace: Data sanitization (e.g., replacing spaces with underscores in a string).

Usage Example

#include <vector>
#include <algorithm>

void linearRoutines(std::vector<int>& data) {
    // Short-circuiting linear search
    auto it = std::find(data.begin(), data.end(), -1);
    if (it != data.end()) {
        // Match found
    }

    // Replace in-place
    std::replace(data.begin(), data.end(), -1, 0);

    // Count occurrences
    int zeros = std::count(data.begin(), data.end(), 0);
}

---

3. Sequence Mutation (std::reverse, std::unique)

Algorithms that permute the physical order of elements in a container.

Under the Hood

• std::reverse: Requires Bidirectional Iterators. Implemented using two pointers/iterators moving inward. Executes std::iter_swap(first, --last) then ++first until first == last or first == last + 1. Swaps leverage move semantics.
• std::unique: Requires Forward Iterators. Removes consecutive duplicate elements. It does not resize the container. It uses a read pointer and a write pointer. The read pointer advances, and if it encounters a new value, it move-assigns it to the write pointer's position, then advances the write pointer. Returns the iterator to the new logical end.

Big-O Complexity

• Time: O(N). reverse performs exactly N/2 swaps. unique evaluates N-1 pairs.
• Space: O(1).

Memory Layout & State Diagram

[ std::reverse ]
  First                 Last
    |                     |
+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+
  └-----------------------┘   <- Swap (1, 7)
      └---------------┘       <- Swap (2, 6)
          └-------┘           <- Swap (3, 5)

[ std::unique ]
Initial: { 1, 1, 2, 2, 2, 3 }
Read/Write pointers advance. Overwrite duplicates.

Result Array : { 1, 2, 3, 2, 2, 3 }
                          ^
                          |
                   Logical End (Returned Iterator)
*(Elements past logical end are left in a valid but unspecified state)*

Typical Usage Scenarios

• reverse: Endianness conversion, BigInt implementation arrays, converting a post-order traversal to topological sort.
• unique: Used immediately after std::sort to completely eliminate duplicates from a dataset (Erase-Remove Idiom).

Usage Example

#include <vector>
#include <algorithm>

void mutationRoutines(std::vector<int>& data) {
    // Reverse
    std::reverse(data.begin(), data.end());

    // Sort then Unique to remove all duplicates (Erase-Remove Idiom)
    std::sort(data.begin(), data.end());
    auto logicalEnd = std::unique(data.begin(), data.end());
    
    // Container size is unchanged until erase is explicitly called
    data.erase(logicalEnd, data.end());
}

---

4. Numeric Algorithms (std::accumulate)

Defined in <numeric>. Represents a left-fold operation over a sequence.

Under the Hood

Requires Input Iterators. It initializes an accumulator with an initial value, then sequentially applies a binary operation (operator+ by default) between the accumulator and each element. Type strictly matters: The type of the initial value dictates the type of the accumulator. Passing 0 initializes an int accumulator, risking overflow. Passing 0LL initializes a long long accumulator.

Big-O Complexity

• Time: Strict O(N). Performs exactly N additions or custom binary operations.
• Space: O(1).

Memory Layout & State Diagram

[ std::accumulate(first, last, 0) ]
Array:[ 10,   20,   30,   40 ]
Init: 0
       \ /
       10
         \  /
          30
            \  /
             60
               \  /
               100 -> Final Result

Typical Usage Scenarios

• Summing values, calculating averages.
• Concatenating an array of strings (using std::string("") as init).
• Applying custom reducers via C++11 lambdas (e.g., product of elements, logical OR).

Usage Example

#include <vector>
#include <numeric> // Required for std::accumulate
#include <string>
#include <iostream>

void numericRoutines() {
    std::vector<int> data = {2, 3, 4, 5};

    // 1. Basic Summation
    // The type of the result is deduced from the initial value (0LL -> long long).
    // Using simple '0' would risk overflow if the sum exceeds 2^31-1.
    long long total = std::accumulate(data.begin(), data.end(), 0LL); 
    // total = 14

    // 2. Custom Binary Operation (Product)
    // We pass a lambda or function object as the 4th argument.
    // Logic: accumulator = accumulator * value
    long long product = std::accumulate(data.begin(), data.end(), 1LL, 
        [](long long acc, int val) {
            return acc * val;
        });
    // product = 120

    // 3. String Concatenation (Folding Strings)
    std::vector<std::string> words = {"System", " ", "Failure", " ", "Detected"};
    
    // CRITICAL: The initial value must be an explicit std::string object.
    // If you pass literal "", the compiler deduces 'const char*', causing 
    // pointer arithmetic errors instead of string concatenation.
    std::string log = std::accumulate(words.begin(), words.end(), std::string(""));
    // log = "System Failure Detected"
}

ASCII Visualization: The Fold Operation (std::accumulate)

std::accumulate represents a "Left Fold". It reduces a sequence to a single value by repeatedly applying a binary operator.

[ Data:  A,   B,   C,   D ]
         |    |
       (Op)   |
         \    |
        Result1
              \   |
             (Op) |
               \  |
              Result2
                    \   |
                   (Op) |
                     \  |
                    Final Result

Summary

Algorithm	Type	Iterator Req	Time Complexity	Space
Sort	Introsort (Quick/Heap/Insert)	Random Access	O(N log N)	O(log N)
Binary Search	Bisection	Forward*	O(log N)	O(1)
Lower/Upper Bound	Bisection	Forward*	O(log N)	O(1)
Find	Linear Scan	Input	O(N)	O(1)
Count	Linear Scan	Input	O(N)	O(1)
Replace	Linear Scan	Forward	O(N)	O(1)
Reverse	Mutation	Bidirectional	O(N)	O(1)
Unique	Mutation	Forward	O(N)	O(1)
Accumulate	Fold	Input	O(N)	O(1)

*Binary Search family requires Random Access Iterators for O(log N) time. With Forward Iterators, the number of comparisons is O(log N), but iterator advancement is O(N).