README.md

avl-order-statistic-set

A C++11 header-only library providing an AVL tree-based, std::set-compatible set with order statistic operations (find by index & rank queries), inspired by GNU PBDS's tree_order_statistics_set but portable.

Motivation

Order statistic trees are essential for solving many problems which require queries like "what is the k-th smallest element?" or "how many elements are strictly less than x?" in logarithmic time.

While GCC's pbds::tree provides this, it is not part of the C++ standard and is often unavailable or non-portable - especially on Windows and Mac and in many online judges.

Most projects and codebases thus fall back to manual implementations or lack order statistics entirely, or must sacrifice portability.

avl-order-statistic-set addresses this gap by:

• Providing a cross-platform, header-only, pure C++11 solution.
• Aiming to be a drop-in replacement for std::set with a similar API.
• Supporting:
  • O(log n) insertion, deletion, and search.
  • O(log n) find_by_order (element at k-th index) and order_of_key (rank of given key) operations.
  • Full value-const, bidirectional iterators allowing for-range and standard algorithms.
  • Custom comparators.

Example (main.cpp)

#include <functional>
#include <iostream>

#include "avl_order_statistic_set.hpp"

int main() {
  avl_order_statistic_set::AVLOrderStatisticSet<int, std::greater<int>> s = {5, 1, 6, 3, 8, 4, 7};

  // [8, 7, 6, 5, 4, 3, 1]
  std::cout << "Forward traversal: ";
  for (int x : s) std::cout << x << ' ';
  std::cout << '\n';

  // [1, 3, 4, 5, 6, 7, 8]
  std::cout << "Reverse traversal: ";
  for (auto it = s.rbegin(); it != s.rend(); ++it) std::cout << *it << ' ';
  std::cout << '\n';

  std::cout << "Inserting duplicate 5...\n";
  auto p = s.insert(5);
  // 0
  std::cout << "Inserted? " << p.second << '\n';

  s.erase(4);
  std::cout << "After erase(4): ";
  // [8, 7, 6, 5, 3, 1]
  for (int x : s) std::cout << x << ' ';
  std::cout << '\n';

  s.emplace(2);
  s.emplace(9);
  std::cout << "After emplacing 2 and 9: ";
  // [9, 8, 7, 6, 5, 3, 2, 1]
  for (const auto &x : s) std::cout << x << ' ';
  std::cout << '\n';

  std::cout << "find_by_order(0): ";
  auto it = s.find_by_order(0);
  // 9
  if(it!=s.end()) std::cout << *it << '\n';

  // 3
  std::cout << "order_of_key(6): " << s.order_of_key(6) << '\n';

  std::cout << "lower_bound(5): ";
  auto lb = s.lower_bound(5);
  // 5
  if(lb!=s.end()) std::cout << *lb << '\n';

  std::cout << "upper_bound(8): ";
  auto ub = s.upper_bound(8);
  // 7
  if(ub!=s.end()) std::cout << *ub << '\n';

  std::cout << "Erase 8 by iterator: ";
  auto e = s.find(8);
  if(e!=s.end()) s.erase(e);
  // [9, 7, 6, 5, 3, 2, 1]
  for (int x : s) std::cout << x << ' ';
  std::cout << "\n";

  return 0;
}

To generate a coverage report:

1. Compile the program with instrumentation: clang++ -std=c++11 -g -Og -fprofile-instr-generate -fcoverage-mapping main.cpp -o main
2. Run the program (generates default.profraw): ./main
3. Merge the data: llvm-profdata merge -sparse default.profraw -o default.profdata
4. Generate an HTML report in htmlcov/: llvm-cov show ./main -instr-profile=default.profdata -format=html -output-dir=./htmlcov

API Reference

Class: avl_order_statistic_set::AVLOrderStatisticSet<T, Compare = std::less<T>>

Method	Description	Time Complexity
AVLOrderStatisticSet()	Default constructor, creates empty set	O(1)
AVLOrderStatisticSet(iterator first, iterator last)	Construct from iterator range	O(n log n)
AVLOrderStatisticSet(std::initializer_list<T> init)	Construct from initializer list	O(n log n)
AVLOrderStatisticSet(const AVLOrderStatisticSet& other)	Copy constructor	O(n)
AVLOrderStatisticSet(AVLOrderStatisticSet&& other)	Move constructor	O(1)
iterator find(const T& key)	Returns iterator to element equivalent to key, or end() if not found	O(log n)
iterator find_by_order(size_t k)	Returns iterator to k-th smallest element (0-based)	O(log n)
size_t order_of_key(const T& key)	Returns number of elements strictly less than key	O(log n)
iterator lower_bound(const T& key)	Returns iterator to first element not less than key	O(log n)
iterator upper_bound(const T& key)	Returns iterator to first element greater than key	O(log n)
bool empty() const	Checks whether container is empty	O(1)
size_t size() const	Returns number of elements	O(1)
pair<iterator, bool> insert(const T& value)	Inserts element, returns iterator and success bool	O(log n)
pair<iterator, bool> insert(T&& value)	Inserts element (move semantics)	O(log n)
iterator erase(iterator pos)	Removes element at position, returns next iterator	O(log n)
size_t erase(const T& key)	Removes element with given key, returns count	O(log n)
void clear()	Erases all elements	O(n)
iterator begin()	Returns iterator to first element	O(1)
iterator end()	Returns iterator to end	O(1)
const_iterator cbegin() const	Returns const iterator to first element	O(1)
const_iterator cend() const	Returns const iterator to end	O(1)
reverse_iterator rbegin()	Returns reverse iterator to last element	O(1)
reverse_iterator rend()	Returns reverse iterator to before-first element	O(1)
const_reverse_iterator crbegin() const	Returns const reverse iterator to last element	O(1)
const_reverse_iterator crend() const	Returns const reverse iterator to before-first element	O(1)

Note: All iterators remain valid through insert/erase operations except those pointing to erased elements.

Contributing

Contributions are welcome! Please submit pull requests or open issues on the GitHub repository.

License

This project is licensed under the Apache License.