-
This is a minimal C++ Library of Algorithms and Data Structures for fun and for practice. Implementations are not production ready (concise/clarity over performance/features)
-
Headers only, most implementations are contained in respective headers.
-
CI Status:
Branch Name Build Status Coverity Status Grok Access Master Grokbit
-
Below are a list of algorithms categorized by topic. Refer to the per-directory Readme for more details:
Topic List of algorithms Bit manipulation algorithms Almost branchless and type safe implementations for:
- Population Count, Gray code, Parity Check, Bit reverse, Log2, etc.Dynamic Programming - Subset Sum, Binary Knapsack
- Longest Common Substring and Subsequence, Longest Increasing Subsequence
- Levenstein Minimum edit distanceString Related - Substring Search - Brute Force, KMP, Boyer Moore, Rabin Karp (Monte Carlo approach)
- Base64 Encode / DecodeGraph Algorithms -Shortest Path - Dijkstra single source shortest path
- Time and #cycle measurement API.
- Micro-benchmarks:
- Measure cost of gettid system-call which does not have glibc vDSO wrapper
- Compare rdtsc, clock_gettime and gettimeofday
- Compare basic spinlock with pthread_lock
-
Below are a list of data structure implementations. Refer to the per-directory Readme for more details:
Data Structure Implementation Details Bitmap Simple, template based, resizable bitmap implementation using STL Vector LRU Cache O(1) Least Recently Used Cache implementation (STL Unordered Map + List) Binary Tree Binary Tree implementation with below tree traversal operations
- BFS, Pre/In/Post DFS Order, Spiral Order, Bottom-up Order.Binary index tree/Fenwick Tree Binary Index Tree implementation. Useful for O(log n) range sum operations.
-
All implementations can be found in respective header files:
Algo Description Shuffle Knuth Shuffle implementation Factorial Iterative factorial Large factorial(bigger than uint64_t) Number of Zeros in factorial