Simple Trie Implementation in C++11 (xorz57.netlify.com)

Yes, 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.

What 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)?.

Do you mean using an array instead of map for storing pointer to the next node? Conceptually, an array is just a map that uses an integer and identity function and the hashing function.

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).

I have shipped a trie into production that used std::unordered_map to store children and it performed quite well.

I 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;
}

  trie<char16_t> trie;

  trie.insert(u"a");
  trie.search(u"ab");
  trie.insert(u"ab");

I 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!

I've implemented a red-black tree a while ago and wrote a post about it: 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 . 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.

You 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.

I don't like auto over int, and other primitives. But auto in for loops or with iterators seems the way to go and is a bless!

  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
   }
  }

Personally, I use auto only when I have to write a long typename (ex. Iterators).

I usually explicitly type my integer constants based on the problem description (e.g. if N < 1e9 I would use int_fast32_t) and then let auto/decltype do most of the work after that.

I would love to contribute. Ping me if you get the repo setup.

I 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).

   struct example {
     std::vector<example> xs;
   };

Yes `unique_ptr` would be better!

I 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_ma...

I did a quick re-implementation [0] taking these ideas into account. It also avoids assuming anything about inputs except iterating the key type and moves most functionality into Node to support more use cases.

[0] https://github.com/codr7/stash/blob/master/trie.cpp

Yes, indeed!