Simple Trie Implementation in C++11
xorz57.netlify.com
xorz57.netlify.com
I would consider switching the unordered_map to a sorted vector<pair<T, Node>>; or even better, move the key into Node and simply store as vector<Node>. Hash tables are relatively expensive to create in exchange for excellent performance for large tables, and you're creating a lot of tiny tables. A regular map would likely fall somewhere in between performance-wise since they're cheaper to create.
I think absl::flat_hash_map<T, std::unique_ptr<Node>> would be worth considering in this application. Keys and values are stored inline, so the memory and creation costs should be comparable to std::vector - https://abseil.io/docs/cpp/guides/container#abslflat_hash_ma...
Nodes it is then :)
Do you have any links to share describing the change?
Thanks!
Just getting rid of the hash buckets and shared_ptrs would be a giant leap in the right direction.
Nice. I have no experience from absl, but I've sucessfully used sorted vectors to speed up these kinds of solutions on several occasions [0].
[0] https://github.com/codr7/cidk/blob/master/src/cidk/env.hpp
As of C++17, certain containers have minimal support for incomplete types.
Traditional books fail me in most of the cases as I want modern techniques combined with (maybe) "old" algorithms.
I would love it if people could show me modern examples and implementations (and reasoning) about let's say things from clrs for example:
- trees (red/black, splay, B, quadtrees, k-trees
- dynamic programming
- hasing (extendible, linear)
- pairing heaps, binomial queues
- shortest distances with dijkstra, johnson, bellman-ford
- finite state machines etc
- string algorithms like boyer-moore, knuth-morris-pratt
- (...)
FYI: I had no account prior to this comment, created one just for you ;) Keep up the good work OP!
Technically it's been a solid implementation and the post probably contains a few helpful bits. But I overengineered the implementation by splitting in too many source files, and relying on source code generation.
A much cleaner "no bullshit" version of it now lives as part of my current project: https://github.com/jstimpfle/astedit . I've also added augmentation facilities (not heavily tested). I think it's pretty good, I just might open up the internals even more than they already are.
(I think the std::map approach from STL definitely has merits, especially when one needs just an associative container, quickly. But it's not a very efficient nor flexible approach.)
That project also has a text rope implementation that uses the red-black tree. I think a rope is much like a B-tree, but I might be wrong.
Also have a look at the linux kernel rbtree implementation. But I think it's not easily usable outside the linux tree.
It's not too bad to traverse the tree using non-owning raw pointers.
Edit: on second thought, having a class contain a container of itself actually isn't allowed (though you would think it would be in cases like this).
Edit again: apparently it depends on the container. unordered_map does not allow instantiation with an incomplete type, but other containers do (e.g. vector or map).
struct example {
std::vector<example> xs;
};In terms of space complexity, it does consume more space than a single element / node tree, (especially for maps with super low load factor) but trie data structure can accommodate all that extra space easily.
In practice, the map implementation trades speed for space efficiency.
For an array implementation, the entire array of pointers has to be allocated for all possible character set for each node. This leads to wasted space since trie nodes usually only have child pointers for a subset of character sets. Map implementation don’t have to allocate space to store pointers for the entire character set, so it can be more space efficient. However, the hash function is probably an order of magnitude more cycle than that for array (usually just the ascii code with offset and some bound checking).
* Well, maybe there is something like small vector optimization going on for small unordered_maps, though.
For the standard implementation, the dynamically allocated array may be bigger than 256. I would imagine, since it’s C++, it’s probably possible to set the initial array size.
Edit: well, of course you could break up the UTF8 string in bytes and stick with a `std::array<std::unique_ptr<Node>,256>` structure. Is this how people do it (supposing normalizing the string is not an option)?.
There are lots of options, but to a first approximation, yes, that's standard.
The key is to think of a trie as a special case of a finite state machine:
1. Your transition table should be a single contiguous block of memory. Namely, going from state s1 for byte b should be something like `trans[s1 * 256 + b]`. This reduces the amount of pointer chasing at search time.
2. With a small runtime cost (typically imperceptible for a large enough FSM), you can map your 256-sized alphabet down to a set of equivalence classes. e.g., Only to a set of bytes that discriminate a match. So your transition lookup becomes `trans[si * num_equiv_classes + equiv_class(b)]`. Although, this is harder to pull off if your trie supports mutation.
3. Instead of storing state identifiers in your transition table, you can store premultiplied state identifiers, which avoids the additional stride calculation at search time. So your transition lookup then becomes `trans[si + equiv_class(b)]`.
Those all mostly apply to dense representations. But if memory is more important, then you can use a sparse representation. In a sparse representation, the size of each state is variable, which means moving to the next transition is more costly. But it uses much less space.
#include "trie.hpp" #include <iostream>
int main() { trie<char16_t> trie;
// Greek
std::cout << trie.search(u"υπολογιστής") << std::endl;
std::cout << trie.search(u"υπολογιστης") << std::endl;
// English
std::cout << trie.search(u"computer") << std::endl;
std::cout << trie.search(u"compute") << std::endl;
// Greek
trie.insert(u"υπολογιστής"); //crash
// English
trie.insert(u"computer");
// Greek
std::cout << trie.search(u"υπολογιστής") << std::endl;
std::cout << trie.search(u"υπολογιστης") << std::endl;
// English
std::cout << trie.search(u"computer") << std::endl;
std::cout << trie.search(u"compute") << std::endl;
return 0;
} trie<char16_t> trie;
trie.insert(u"a");
trie.search(u"ab");
trie.insert(u"ab");My bad! I fixed it!
Also read this https://stackoverflow.com/questions/19618759/c-11-auto-compi...
[1] Like by taking the approach that results in a cast, e.g. here: https://news.ycombinator.com/item?id=20493263
typedef std::vector<bool> Vec;
Vec f(1, false);
for (typename Vec::value_type &&x : f) { std::cout << typeid(x).name() << std::endl; }
for (auto &&x : f) { std::cout << typeid(x).name() << std::endl; } template<class It> struct iterator_range { It b, e; It begin() const { return b; } It end() const { return e; } };
template<class It> iterator_range<It> make_iterator_range(It b, It e) { iterator_range<It> r = { b, e }; return r; }
template<class T> struct endian_reversed_iterator {
T *p;
struct reference {
T *p;
operator T() const { return boost::endian::endian_reverse(*p); }
reference &operator =(T const &other) const { *p = boost::endian::endian_reverse(other); }
};
endian_reversed_iterator(T *p) : p(p) { }
reference operator *() { reference r = { p }; return r; }
endian_reversed_iterator &operator++() { ++p; return *this; }
bool operator!=(endian_reversed_iterator const &other) const { return p != other.p; }
};
int main() {
unsigned arr[] = { 1, 2 };
for (auto x : make_iterator_range<endian_reversed_iterator<unsigned> >(&arr[0], &arr[2])) {
++x; // whatever
}
}