Interestingly, the code for word sequence insertion is shorter and simpler than the code for looking up a given word sequence in a subtrie. So, let's first have a look at the insertion code:

template <typename It>
void trie::insert(It it, It end_it) {
    if (it == end_it) { return; }
    tries[*it].insert(next(it), end_it);
}

The pair of iterators, it and end_it, represent the word sequence to be inserted. The tries[*it] element looks up the first word in the sequence in the subtrie, and then, .insert(next(it), end_it) restarts the same function on that lower subtrie, with the iterator one word further advanced. The if (it == end_it) { return; } line just aborts the recursion. The empty return statement does nothing, which is a bit weird at first. All the insertion happens in the tries[*it] statement. The bracket operator [] of std::map either returns an existing item for the given key or it creates one with that key. The associated value (the mapped type is a trie in this recipe) is constructed from its default constructor. This way, we are implicitly creating a new trie branch whenever we are looking up unknown words.

Looking up in a subtrie looks more complicated because we were not able to hide so much in implicit code:

template <typename It>
optional<reference_wrapper<const trie>> 
subtrie(It it, It end_it) const {
    if (it == end_it) { return ref(*this); }
    auto found (tries.find(*it));
    if (found == end(tries)) { return {}; }

    return found->second.subtrie(next(it), end_it);
}

This code basically revolves around the auto found (tries.find(*it)); statement. Instead of looking up the next deeper trie node using the bracket operator ([]), we use find. If we use the [] operator for lookups, the trie will create missing items for us, which is not what we want when just looking up whether an item exists! (By the way, try doing that. The class method is const, so this will not even be possible. This can be quite a life saver, which helps us in preventing bugs.)

Another scary looking detail is the return type, optional<reference_wrapper<const trie>>. We chose std::optional as the wrapper because it is possible that there is no such subtrie for the input sequence we are looking for. If we only inserted "hello my friend", there will be no "goodbye my friend" sequence to look up. In such cases, we just return {}, which gives the caller an empty optional object. This still does not explain why we use reference_wrapper instead of just writing optional<const trie &>. The point here is that an optional instance with a member variable of the trie& type is not reassignable and hence would not compile. Implementing a reference using reference_wrapper leads to reassignable objects.