Skip to content

Latest commit

 

History

History
43 lines (28 loc) · 1.56 KB

README.md

File metadata and controls

43 lines (28 loc) · 1.56 KB
Raw

tries

Tries in C++

Directory structure

  • benchmark contains benchmark results.
  • catch2 contains the library used for testing
  • res contains benchmark data
  • trie.hpp is the main header file
  • test.cpp and testcases.cpp contain test cases
  • benchmark-trie.cpp contains benchmark cases

Usage & Requirements

This work is licensed under GNU-GPL 2.0; see LICENSE.txt for more information.

Usage only

Since this is a header-only library, it is enough to include trie.hpp into the file you want to use tries in! A C++20 compliant compiler is needed. I confirmed that gcc 10.0.1 and 10.1.0 work; Clang doesn't seem to work (at least in version 10.0.0).

Tests

In order to execute tests, the dependency catch2 must be available under catch2/catch.hpp. The tests can be executed with make unittests.

Benchmarks

In order to execute benchmarks, the dependency catch2 must be available under catch2/catch.hpp. Further it is necessary that gcc is used because we compare the library at hand with GNU's trie implementation. The performance-benchmarks can be executed with make benchmark. The memory-benchmarks can be executed with make benchmark_memory. The results can be found in benchmark/ (I tested on an Intel Core i7 from 2012). Here are my results for the performance benchmarks:

bm1

bm2

This library is listed in four different configurations and compared to std::map and __gnu_pbds::trie (A GNU trie implementation).