AlgoDataStruct is an educational, header-only C++ library that implements classic data structures with modern C++20. The project favors clear invariants, clean APIs, and well-documented behavior over micro-optimizations.
Key characteristics:
- Header-only templates with
.tppimplementation files included by the public headers - STL-friendly iteration/traversal where applicable and explicit error handling via custom exceptions
- Focused, testable implementations intended for study and extension
Linear Structures
-
Arrays
- Static Array
- Dynamic Array (vector-like growth)
- Circular Array (wrap-around indexing)
-
Linked Lists
- Singly Linked List
- Doubly Linked List
- Circular Linked List
-
Stacks
- Array-based Stack
- Linked-list-based Stack
-
Queues
- Linked Queue
- Circular Queue
- Circular Deque
- Priority Queue (binary heap)
Trees
- Complete Binary Tree (level-order insertion)
- Binary Search Tree (BST)
- AVL Tree
- Red-Black Tree
- B-Tree
- Trie (Prefix Tree)
- Fenwick Tree (Binary Indexed Tree)
- Segment Tree
Heaps
- Min Heap
- Max Heap
Hashing Structures
- Hash table with chaining
- Hash table with open addressing (linear, quadratic, double hashing)
Associative Structures
- Dictionary interface
- HashMap
- TreeMap
- HashSet
- TreeSet
Graph Structures
- Adjacency List
- Adjacency Matrix
- Disjoint Sets (Union-Find)
Planned, not implemented yet:
- Skip List (advanced)
- B+ Tree, 2-3 Tree, 2-3-4 Tree
- String structures (Suffix Tree/Array, Suffix Automaton, Rope)
- Probabilistic structures (Bloom Filter, Count-Min Sketch, HyperLogLog)
- Spatial structures (KD-Tree, R-Tree, Quad/Oct-tree)
AlgoDataStruct/
├── include/
│ └── ads/
│ ├── arrays/
│ ├── lists/
│ ├── stacks/
│ ├── queues/
│ ├── trees/
│ ├── heaps/
│ ├── hash/
│ ├── associative/
│ └── graphs/
├── src/
│ ├── ads/ # .tpp implementation files
│ └── main_*.cc # usage demos / sample programs
├── tests/ # unit tests (standalone)
├── docs/ # generated documentation
│ └── html/
├── Documentation/ # additional notes and PDFs
├── CMakeLists.txt
├── clang-toolchain.cmake
├── gcc-toolchain.cmake
└── Makefile
- C++: Google C++ Style Guide conventions
- Header-only templates: public headers in
include/ads, implementations insrc/ads - Many structures include iterators or traversal callbacks where they make sense
- Documentation is written in Doxygen style; complexity notes are included when available
- Tests and demos live in
tests/andsrc/main_*.cc
The library is header-only; you can include the headers directly. To build the demo
executables in src/main_*.cc:
cmake -DCMAKE_TOOLCHAIN_FILE=clang-toolchain.cmake -B build
cmake --build buildExecutables are placed in build/bin/. Use gcc-toolchain.cmake if you prefer GCC.
// Example usage of an AVL Tree
#include "ads/trees/AVL_Tree.hpp"
#include <iostream>
int main() {
ads::trees::AVLTree<int> avlTree;
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
std::cout << std::boolalpha << avlTree.contains(20) << "\n"; // true
avlTree.remove(20);
std::cout << std::boolalpha << avlTree.contains(20) << "\n"; // false
std::cout << "In-order traversal: ";
avlTree.in_order_traversal([](const int& value) {
std::cout << value << " ";
});
std::cout << "\n";
return 0;
}#include "ads/associative/Hash_Map.hpp"
#include <iostream>
#include <string>
int main() {
ads::associative::HashMap<std::string, int> scores;
// Adding key-value pairs
scores.put("Alice", 95);
scores.put("Bob", 89);
scores.put("Charlie", 92);
// Retrieving values
std::cout << "Bob's score: " << scores.get("Bob") << "\n"; // 89
// Checking if a key exists
std::cout << "Does David have a score? " << std::boolalpha
<< scores.contains("David") << "\n"; // false
// Updating a value
scores.put("Bob", 91);
std::cout << "Bob's updated score: " << scores.get("Bob") << "\n"; // 91
// Removing a key-value pair
scores.erase("Charlie");
std::cout << "Charlie's score exists? " << std::boolalpha
<< scores.contains("Charlie") << "\n"; // false
return 0;
}Contributions are welcome! Please read our contribution guidelines before submitting a pull request.
- Missing implementations: Check the list of pending structures
- Performance improvements: Optimizations without compromising clarity
- Documentation: Improvements to comments, examples, or guides
- Tests: Add more test cases or improve existing ones
When adding a new structure, please include:
- Public header in
include/ads/<area>/ .tppimplementation insrc/ads/<area>/- A demo in
src/main_<Structure>.ccand a unit test intests/ - An update to this README if it changes the public surface
- Introduction to Algorithms - Cormen, Leiserson, Rivest, Stein
- Algorithms, 4th Edition - Sedgewick & Wayne
- Data Structure in C++ - Michael T. Goodrich, Roberto Tamassia, David M. Mount
- The Art of Computer Programming - Knuth
- Algorithm Design Manual - Steven S. Skiena
- Advanced Data Structures - Peter Brass
- Purely Functional Data Structures - Chris Okasaki
- Graph Algorithms - Shimon Even
- Data Structures and Network Algorithms - Robert Endre Tarjan
- Handbook of Data Structures and Applications - Dinesh P. Mehta, Sartaj Sahni
- Pearls of Functional Algorithm Design - Richard Bird
- Algorithms and Data Structures: The Basic Toolbox - Kurt Mehlhorn, Peter Sanders
- Competitive Programmer's Handbook - Antti Laaksonen
- Real-World Algorithms: A Beginner's Guide - Panos Louridas
- Similarity Search: The Metric Space Approach - Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, Michal Batko
- Nearest Neighbor Methods in Learning and Vision - Gregory Shakhnarovich, Trevor Darrell, Piotr Indyk
- Foundations of Multidimensional and Metric Data Structures - Hanan Samet
- Computational Geometry: Algorithms and Applications - Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
This project is licensed under the MIT License - see the LICENSE file for details.
For questions or suggestions, please open an issue in this repository.