11 ms·
Simple Trie Implementation in C++11
- stabbles 7y agoIs `shared_ptr` just used for convenience? I think `unique_ptr` would be excellent for this tree structure. It's not too bad to traverse the tree using non-owning raw pointers.
- nemetroid 7y agoI don't think there's need for smart pointers at all, really. The "children" member could just be an unordered_map<T, Node>. 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).
- stabbles 7y agoYes, I was playing around with it as well. It seems the support has been out there for a while, but officially since C++17 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4371.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n437... was accepted, s.t. std::vector, std::list and std::forward_list can work with incomplete types: struct example { std::vector<example> xs; };
- saagarjha 7y agoI believe containers can contain incomplete types as of C++17, but you cannot use their members.
- xorz57 7y agoYes `unique_ptr` would be better!
- riffraff 7y agoDoesn't using a map to implement a trie defeat the purpose? I mean, would such an implementation make sense in some situation?
- bhaavan 7y agoYes, it will, because map has O(1) GET operations, and that's all the trie needs. 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.
- stabbles 7y agoWhat is the best alternative still supporting UTF8? Yeah, sure, if you only support ASCII input you could use std::array<std::unique_ptr<Node>, 128>. 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)?.
- burntsushi 7y ago> 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.
- bhaavan 7y agoI couldn't come up with such a concise and succinct implementation even if I tried.
- egwor 7y agoI tried giving this a run from CLion and it crashes if I search first, see #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; }
- Ciberth 7y agoI really love this! I saw your github repo "forest" as well. I wish there were more bundled resources or code examples like this. Not because I think everything should be out there in the open, free to get. But more as a way of retrieving examples about (maybe complex) algorithms. 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!
- xorz57 7y agoI am pleased to hear you like my work! I have written a Red/Black and a Splay Tree Implementation as part of the forest repository but I wasen't satisfied enough with those so I removed them. I am planning to implement more stuff in the future so stay tuned!
- Ciberth 7y agoOhn it would have been cool to have a look. I have some start questions and code from a few years back at uni but I really disliked the courses, prof and way of programming. If you would be interested I can share them to gain some insights or motivations on how to (maybe not) do it :)
- xorz57 7y agoI feel you.
- deleted 7y ago[deleted]
- jstimpfle 7y agoI've implemented a red-black tree a while ago and wrote a post about it: http://jstimpfle.de/blah/rbtree/main.html http://jstimpfle.de/blah/rbtree/main.html 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 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.
- imedadel 7y agoOn a side note, I recently started competitive programming in my college, and while preparing for the upcoming xCPC competitions, I was wondering if I should use "auto" and a more functional approach in C++ (instead of using int, double, etc. and OOP). What do you think?
- mehrdadn 7y agoYou mean for competitions, or in general? For competitions, go with whatever is faster/reduces your typing. In general, I think a lot of people would the same thing, but I'm in the (apparently small?) camp that thinks auto is massively overused. I use typedefs liberally instead of using auto all over the place. It prevents some implicit casts from being inhibited (which are rare, but which can cause correctness issues), and it documents things better. The cost is more typing, which in my view is just something you have to learn C++ is not intended to minimize.
- imedadel 7y agoI think typing isn't my issue (so far), but rather the performance. On one hand, it's one less thing to think about while figuring out a problem, but on the other hand, it might reduce the performance of my solution, and in that case, going back and refactoring the code to use the correct types would be a waste of time...
- mehrdadn 7y agoOh interesting. Why do you think auto would affect run-time performance? Could you describe an example?
- xorz57 7y agoI think auto won't have any run-time performance since type deduction happens at compile-time. Also read this https://stackoverflow.com/questions/19618759/c-11-auto-compile-time-or-runtime https://stackoverflow.com/questions/19618759/c-11-auto-compi...
- xorz57 7y agoThis implementation lacks operations like clear() or remove(). I could create a repository if you would like to contribute.
- deleted 7y ago[deleted]
- panda88888 7y agoI would love to contribute. Ping me if you get the repo setup.
- xorz57 7y agoSure!
- xorz57 7y agoI will probably include this implementation in a repository of mine called "forest". You can check it out here https://github.com/xorz57/forest https://github.com/xorz57/forest Or you could copy paste it and open a pull request with additional features!
- codr7 7y agoLike someone else mentioned, there's no need for Node pointers at all here, storing Nodes by value cuts away a decent chunk of complexity and should run plenty faster (especially when threads are linked). 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.
- psurge 7y agoI don't think Node can contain a std::vector<Node>, since STL containers cannot have incomplete value types. But maybe I'm misunderstanding you? 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_map-and-abslflat_hash_set https://abseil.io/docs/cpp/guides/container#abslflat_hash_ma...
- psurge 7y agoAren't the second and third lines of the insert/search implementations superfluous? Casting root to a boolean will never return false, since it is initialized. The insert implementation doesn't update root, so if root were nullptr, insert would be throwing away its work.
- xorz57 7y agoYes, indeed!