A modern, header-only C++20 library of classic algorithms and data
structures — written with concepts, ranges, std::span, std::optional
and constexpr throughout, and verified by a self-contained test suite
of 217 checks including randomized cross-validation against the
standard library.
#include "algo/algo.hpp"
std::vector<int> v = {42, 7, 19, 3};
algo::sorting::quick_sort(v); // 3 7 19 42
auto dist = algo::graph::dijkstra(g, /*source=*/0); // shortest paths
auto steps = algo::dp::edit_distance("kitten", "sitting"); // 3
bool prime = algo::math::is_prime(1'000'000'007ULL); // true, exact- Modern C++20. Every comparison sort is constrained by a
strict_weak_orderconcept; searches takestd::spanand returnstd::optionalinstead of-1sentinels; most of the math module is usable inconstexprcontexts. - Header-only. Add
include/to your include path (or use CMake as shown below) and you are done. No linking, no dependencies. - Tested like it matters. Sorts are cross-checked against
std::sorton randomized inputs, the Fenwick and segment trees against brute force, Rabin–Karp against KMP, and the sieve against Miller–Rabin. Adversarial cases (sorted input for quicksort, Carmichael numbers, collinear hull points, negative-weight cycles) are covered explicitly. - Honest complexity notes. Every function documents its time and space complexity, and the implementations deliver them: LIS is the O(n log n) patience variant, quicksort uses median-of-three with O(log n) stack depth, Miller–Rabin is deterministic for all 64-bit integers.
| Algorithm | Time | Space | Stable |
|---|---|---|---|
bubble_sort |
O(n²), O(n) if nearly sorted | O(1) | yes |
selection_sort |
O(n²) | O(1) | no |
insertion_sort |
O(n²), O(n) if nearly sorted | O(1) | yes |
shell_sort (Ciura gaps) |
≈ O(n^1.3) | O(1) | no |
merge_sort |
O(n log n) always | O(n) | yes |
quick_sort (median-of-3 Hoare) |
O(n log n) avg | O(log n) | no |
heap_sort |
O(n log n) always | O(1) | no |
counting_sort |
O(n + k) | O(k) | yes |
radix_sort (LSD, base 256) |
O(d·(n + 256)) | O(n) | yes |
All comparison sorts accept a custom comparator:
quick_sort(words, [](auto& a, auto& b){ return a.size() < b.size(); });
| Algorithm | Time | Requirement |
|---|---|---|
linear_search |
O(n) | none |
binary_search |
O(log n) | sorted |
lower_bound_index / upper_bound_index |
O(log n) | sorted |
exponential_search |
O(log i) | sorted, target near front |
interpolation_search |
O(log log n) avg | sorted, uniform integers |
ternary_search_max |
O(log range) | unimodal function |
| Algorithm | Time | Notes |
|---|---|---|
bfs_order, bfs_distances |
O(V + E) | unweighted shortest paths |
dfs_order |
O(V + E) | iterative, no stack overflow |
dijkstra |
O((V+E) log V) | non-negative weights |
bellman_ford |
O(V·E) | negative edges; nullopt on negative cycle |
floyd_warshall |
O(V³) | all-pairs |
topological_sort (Kahn) |
O(V + E) | nullopt on cycle |
connected_components |
O(V + E) | DSU based |
has_cycle |
O(V + E) | directed (3-color) and undirected |
kruskal_mst, prim_mst |
O(E log E) / O(E log V) | nullopt if disconnected |
fibonacci (constexpr) · longest_common_subsequence (rolling row) ·
longest_increasing_subsequence (O(n log n)) · knapsack_01 (O(capacity)
space) · edit_distance · coin_change_min · coin_change_ways ·
max_subarray_sum (Kadane) · matrix_chain_order · climb_stairs
prefix_function · kmp_search · z_function · rabin_karp_search
(verified matches, no false positives) · longest_palindromic_substring
(Manacher, O(n)) · is_palindrome (constexpr)
gcd / lcm / extended_gcd (constexpr) · power · mod_pow
(overflow-safe) · mod_inverse · is_prime (deterministic Miller–Rabin,
exact for all 64-bit integers) · sieve_of_eratosthenes ·
prime_factorization · euler_totient · binomial · catalan
activity_selection · fractional_knapsack · minimum_platforms ·
huffman_codes (deterministic, prefix-free)
| Structure | Operations | Cost |
|---|---|---|
DisjointSetUnion |
find, unite, connected, set_size |
~O(1) amortized |
FenwickTree<T> |
add, prefix_sum, range_sum |
O(log n) |
SegmentTree<T, Op> |
update, query over any monoid |
O(log n) |
Trie<AlphabetSize, Base> |
insert, contains, count_with_prefix |
O(word length) |
is_power_of_two · count_set_bits · lowest_set_bit /
highest_set_bit · next_power_of_two · reverse_bits ·
single_number · gray_code · all_submasks · xor_swap
Integer-exact (no epsilons): cross · orientation ·
squared_distance · convex_hull (monotone chain) ·
polygon_area_doubled (shoelace) · segments_intersect (all collinear
touch cases handled)
- A C++20 compiler — GCC 11+, Clang 14+, or MSVC 19.30+
- CMake 3.20+ (only for the tests, examples and benchmarks; the library itself is plain headers)
Option 1 — copy the headers. Copy include/algo/ into your project
and #include "algo/algo.hpp" (or just the module you need).
Option 2 — CMake subdirectory / FetchContent:
include(FetchContent)
FetchContent_Declare(algo
GIT_REPOSITORY https://github.com/ObaidUllah-10/cpp-algorithms-collection.git
GIT_TAG main)
FetchContent_MakeAvailable(algo)
target_link_libraries(your_target PRIVATE algo::algo)git clone https://github.com/ObaidUllah-10/cpp-algorithms-collection.git
cd cpp-algorithms-collection
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failure./build/examples/tour
cmake -B build -DALGO_BUILD_BENCHMARKS=ON -DCMAKE_BUILD_TYPE=Release
cmake --build build --target benchmark_sorting
./build/benchmarks/benchmark_sorting 100000Sample benchmark output (30,000 elements, Release, GCC 13):
algorithm random sorted reversed few-uniq
std::sort 1.55ms 0.34ms 0.22ms 0.62ms
quick_sort 2.27ms 0.44ms 0.42ms 0.95ms
merge_sort 2.55ms 0.56ms 0.69ms 1.48ms
heap_sort 2.64ms 1.55ms 1.72ms 1.78ms
counting_sort 8.71ms 0.18ms 0.09ms 0.16ms
include/algo/ the library (header-only)
data_structures/ DSU, Fenwick tree, segment tree, trie
algo.hpp umbrella header
tests/ zero-dependency test suite (CTest)
benchmarks/ sorting benchmark
examples/ guided tour of every module
.github/workflows/ CI: GCC + Clang matrix, build + ctest
std::optionalover sentinels. A search that can fail returnsoptional<size_t>; a graph algorithm that can be undefined (MST of a disconnected graph, topological order of a cyclic graph, shortest paths under a negative cycle) returnsoptionaltoo. Failure is in the type, not in a magic value.- Iterative where it counts. DFS, cycle detection and Huffman traversal are all iterative, so deep or degenerate inputs cannot overflow the call stack. Quicksort recurses only into the smaller partition.
- Integer-exact geometry. All predicates use
long longcross products — no epsilon tuning, no false intersections. - Strict warnings. Everything builds clean under
-Wall -Wextra -Wpedantic -Wconversion -Wshadow.
Contributions are welcome — see CONTRIBUTING.md for the workflow and code style. Good first contributions: A*, strongly connected components (Tarjan/Kosaraju), suffix arrays, sparse tables, or a lazy-propagation segment tree.
MIT — free to use in personal, academic and commercial projects.