Various algorithms and data structures implementation in STL style.

Use with caution! Most of the code in this repository was written in 2018 and has no longer been maintained since then. It is more like a collection of code that I use to learn and experiment with algorithms and data structures rather than a library intending to be correct and stable. For example, only part of the classes implement proper C++-style copy control, and many implementations can not comply with the STL specification or exception safety.

Algorithm: Generic algorithms, including binary searches (corresponding to std::lower/upper_bound), heap algorithms (corresponding to std::push/pop/make_heap), sorting (corresponding to std::sort, which is a combination of quick sort, insertion sort and heap sort), etc.

sequential

• Vector: Dynamic-size array (corresponding to std::vector). Internally uses realloc for space growth, which is generally faster and can handle most cases. However, it can break classes containing self-referencing pointers (e.g., some versions of libstdc++ std::string use self-referencing pointers for SSO).
• List: Doubly linked list (corresponding to std::list). The sorting algorithms of List and ForwardList are quite tricky.
• ForwardList: Singly linked list (corresponding to std::forward_list).
• CircularQueue/Deque: Both are doubly ended queue. Deque corresponds to std::deque, and guarantees that "push_front, push_back, emplace_front and emplace_back do not invalidate any references to elements of the deque.", while Vector/CircularQueue cannot guarantee it.
• String: Provides class String (essentially Vector<char>), StringView (corresponding to std::string_view), and several substring-searching algorithms such as KMP and KarpRabin.

associative

• Map: Sorted associative container (corresponding to std::map). The map iterator supports offsettings integer and from each other in logarithmic time by storing sub-tree sizes in tree nodes. It is the driver for various balanced trees, and uses template parameter to select one from:
  • RBTree/AVL/Splay/Treap
• BTree: Sorted associative container implemented with B-Tree. B-Tree in memory may be faster than your imagination. See Rust BTreeMap documentation for some explanations.
• SkipList: Sorted associative container implemented with skip list. Generally slower than balanced trees, but said to be easier to extend for concurrency.
• HashMap: Hash map with closed hashing (corresponding to std::unordered_map). Generally slower and consumes more memory than open hashing. But it guarantees that iterators are only invalidated when rehashing occurs in insertion, and references are not invalidated, while open hashing cannot guarantee it.
• HashMap-OpenAddress: Hash map with open hashing. Uses template parameter to select from Linear, Quadratic, Double or a user-defined function for probing.

heap

• FibHeap: Fibonacci heap. min: constant; insert/decrease-key/merge: amortized constant; delete: amortized logarithmic.
• PairingHeap: Pairing heap. min: constant; insert/merge: amortized constant; delete-min: amortized logarithmic; decrease-key: not clear, amortized sub-logarithmic. Although its theoretical time complexity is not as good as FibHeap, it is much easier to implement and has a smaller constant factor.
• LeftistTree: Leftist tree. min: constant; insert/merge/delete: amortized logarithmic.
• MinMaxHeap: Min-max heap. min/max: constant; delete-min/delete-max: logarithmic.
• PriorityQueue: Container adaptor that implements heap by applying functions defined in Algorithm on a underlying container (corresponding to std::priority_queue).

integer

• BitSet: Fixed-size sequence of bits (corresponding to std::bitset).
• BIT: Binary indexed tree (Fenwick tree) that supports range addition and sum.
• BITTree: Extends BIT to support dynamic order statistics for integers.
• UInt: Fixed-size arbitrary-precision unsigned integer.
• BigInt: Dynamic-size arbitrary-precision integer.
• vEBTree: Fixed-size van Emde Boas tree. Use some template tricks to get rid of pointers and store the tree compactly. insert/delete/find/predecessor/successor for M-bit integer: logarithmic to M.

toy

• Calculator: A simple calculator that uses a stack to parse operators with precedence.
• Complexity: Measures algorithm runtime and uses Least Squares Method to estimate asymptotic time complexity (try to put it into one of the predefined categories).
• DynamicSegTree: Segment tree that allocates nodes dynamically.
• IntrusiveList: Similar to Boost.Intrusive list.
• KDTree: Static k-d tree. Built on initialization. Supports k-NN query.
• Matrix: Naive implementation of fixed-size matrix.
• MemPool: Caches allocations of a single kind of object. Organizes the deallocated memory with a linked list. Never deallocates any memory chunks halfway, and deallocates them at one time on destruction.
• Polynomial: Naive implementation of polynomial +-*/%.
• Profiler: Records duration using the constructor/destructor pair.
• Ptr32: Stores a 64-bit pointer in a 32-bit word by assuming its most significant 32 bits to be zero.
• SharedPtr: Intrusive shared pointer. Unlike std::shared_ptr, it doesn't support polymorphic deleter or atomic reference counting.
• TimSort: Timsort, a hybrid stable sorting algorithm, derived from merge sort and insertion sort.
• Trie: Quite a failure, sometimes even slower than Map<std::string, V>.
• PersistentArray: Persistent array implemented with a tree. I only have used PersistentArray, PersistentTreap and WBT to solve online judge problems, and they are completely immature for any practical usage.
• PersistentTreap: Functional balanced tree implemented with treap.
• WBT: Weight-balanced tree. It is also a functional balanced tree, and is the data structure that Haskell Data.Map uses.

toy/legacy

• Map-List: Maintain an implicit linked list in RBTree nodes to find predecessor/successor in worst-case constant time. It is useless in practice because finding predecessor/successor originally only needs average constant time.
• NaiveDB: A naive trial to store B-tree on disk.
• SegmentTree: Fixed-size abstract segment tree. The heavy use of templates here greatly slows compiling speed with little improvement on runtime speed.
• vEBTree-pointer: vEBTree implementation using pointers. Size can be specified on runtime initialization, but much slower and consumes much more memory than the template version.

toy/template

• SetT: PersistentTreap at compile time.
• ListT: ForwardList at compile time.
• ArrayT: Stores variadic template parameter pack in an array.
• Function: Polymorphic function wrapper (corresponding to std::function).
• IterTool: A small part of C++20 Ranges library.
• RefWrapper: Wraps reference in copyable, assignable object (corresponding to std::reference_wrapper).
• SIUnit: See Compile-time numerical unit dimension checking.
• TypeName: Compute type name precisely at compile time. On the contrary, typeid may lose reference/const information. Useful to debug other template metaprogramming programs.