Niente male anche le trie; con un'implementazione abbastanza povera (senza check che l'elemento sia un terminale e con payload su ogni nodo) ma con interi piccoli come indici e "frozen trie" con un vector come backend (dopo aver costruito il tutto con la deque per evitare riallocazioni del vettore durante il lookup) per guadagnare un 30% in prestazioni, il risultato è competitivo con la hashtable.

Trie:
codice:
template<typename T>
struct trie_node {
    uint16_t next[26] = {0};
    T payload = T();

    template<typename TCont>
    trie_node *lookup(const char *sz, bool add, TCont &alloc) {
        if(*sz==0) return this;
        uint16_t &n = next[*sz-'a'];
        if(n==0) {
            if(add) {
                n = alloc.size();
                alloc.push_back(trie_node());
            } else {
                return nullptr;
            }
        }
        return alloc[n].lookup(sz+1, add, alloc);
    }
};

template<typename T>
struct trie {
    std::deque<trie_node<T>> nodes;
    trie_node<T> *lookup(const char *sz, bool add) {
        return nodes[0].lookup(sz, add, nodes);
    }

    trie() {
        nodes.resize(1);
    }
};

template<typename T>
struct frozen_trie {
    std::vector<trie_node<T>> nodes;
    trie_node<T> *lookup(const char *sz) {
        return nodes[0].lookup(sz, false, nodes);
    }

    frozen_trie(trie<T> &orig) : nodes(orig.nodes.begin(), orig.nodes.end()) {}
};
Codice in coda al main:
codice:
    {
        std::cout<<"Trie\n";
        trie<unsigned> count_t;
        for(auto &sz: combs) {
            count_t.lookup(sz.c_str(), true);
        }
        frozen_trie<unsigned> count_t_frozen(count_t);
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            count_t_frozen.lookup(key.c_str())->payload++;
        }
        std::cout<<"Fine trie\n";
    }
Risultati:
codice:
[mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
0.000019 Lineare
33.315037 Fine lineare!
0.000230 Dicotomica
6.158021 Fine dicotomica
0.000079 Hashtable
1.610438 Fine hashtable
0.000084 Map
3.777893 Fine map
0.000089 Trie
2.120793 Fine trie