c++ – Template Trie Container

This is a C++ template-based trie class. (Basically it is analagous to std::map<std::string, T> but by keeping all the strings in the tree, lookups are O(n) where n is the length of the string, as opposed to O(n log m) where m is the number of elements. The tradeoff is that it uses a lot of memory. I understand that std::map is more than good enough for 99% of situations, so feel free to assume this is an academic exercise.)

The idea is that you predefine a valid alphabet to somewhat limit the memory consumption, e.g. if you’re dealing with alphanumeric strings you only add 62 children per node.

It seems to work fine, I’m just curious if it can be made cleaner, or I goofed somewhere in the C++ stuff.

static const int TrieNChild = 67;

class TrieCharMap {
    int m(256);

    TrieCharMap() {
        int k = 0;
        for (int x = '0'; x <= '9'; x++) m(x) = k++;
        for (int x = 'A'; x <= 'Z'; x++) m(x) = k++;
        for (int x = 'a'; x <= 'z'; x++) m(x) = k++;
        m('.') = k++;
        m('-') = k++;
        m('+') = k++;
        m('_') = k++;
        m('/') = k++;
        assert(k == TrieNChild);
    }
    TrieCharMap(const TrieCharMap& o) {};
    void operator = (const TrieCharMap& o) {}

public:
    static TrieCharMap& Instance() {
        static TrieCharMap x;
        return x;
    }

    inline int operator () (char x) { return m(int(((unsigned char)(x)))); }

};

template <class T>
class Trie {
    struct node {
        node* p(TrieNChild) {};
        T z{};
    };

    node root;

    Trie() {}
    Trie(const Trie& o) {}
    void operator = (const Trie& o) {}

public:
    void add(const char* s, T value) {
        node* x = &root;
        for (; *s; s++) {
            int i = TrieCharMap::Instance()(*s);
            if (!x->p(i)) x->p(i) = new node;
            x = x->p(i);
        }
        x->z = value;
    }

    T search(const char* s, char delim=0) {
        node* x = &root;
        for (; x && *s && *s!=delim; s++) {
            int i = TrieCharMap::Instance()(*s);
            x = x->p(i);
        }
        if (x) return x->z;
        return T{};
    }

    T operator ()(const char* s) { return search(s); }
};

Here is a basic usage example:

void test_trie() {
    Trie<int> t;

    t.add("Hello", 3);
    t.add("hello", 4);
    t.add("/serv/potato", 5);

    for (const char* s : { "hi", "hello", "Hell", "Hello", 
                "/serv/potat", "/serv/potato", "oeua",  "/serv/potato?a=3", "/serv/potat?a=3" })
    {
        cerr << "Query result for " << s << " is " << t.search(s, '?') << endl;
    }
}