Introduction

There is no single best autocomplete data structure for every C or C++ program. The right choice depends on how many terms you store, how often the data changes, and whether results must be ranked by popularity or only matched by prefix.

For most in-memory autocomplete systems, a trie or a compressed trie is the default answer because prefix lookups line up naturally with the structure. That said, a sorted array plus binary search can beat a trie when memory use and implementation simplicity matter more than fast updates.

Choosing The Core Structure

Trie

A trie stores one character per edge and one node per prefix. If the user types app, you walk the tree through a, then p, then p, and the subtree below that node contains all completions.

The benefits are strong. Prefix lookup cost depends on prefix length rather than on the total number of words. Insert and delete operations are straightforward. You can also cache ranking data at each node for fast top-k suggestions.

The main downside is memory usage. A naive trie with a full child array per node wastes space when the alphabet is sparse.

Ternary Search Tree

A ternary search tree stores one character per node with low, equal, and high branches. It usually uses less memory than a naive trie and still supports prefix search efficiently. This is a good option in C or C++ when you want trie-like behavior without paying for many empty pointers.

Sorted Vector

If the dictionary is mostly static, keep the words in a sorted std::vector<std::string> and use std::lower_bound to find the prefix range. This approach is cache-friendly and often faster than expected for medium-sized datasets.

The tradeoff is update cost. Inserting into a sorted vector is expensive compared with updating a tree-based structure.

A Practical C++ Trie Example

The example below stores lowercase words and keeps a frequency score at terminal nodes. After finding the prefix node, it runs a depth-first search to collect matches and sorts them by score.

1#include <algorithm>
2#include <array>
3#include <iostream>
4#include <string>
5#include <vector>
6
7struct Node {
8    std::array<Node*, 26> child{};
9    bool isWord = false;
10    int frequency = 0;
11};
12
13void insert(Node* root, const std::string& word, int frequency) {
14    Node* cur = root;
15    for (char ch : word) {
16        int idx = ch - 'a';
17        if (!cur->child[idx]) {
18            cur->child[idx] = new Node();
19        }
20        cur = cur->child[idx];
21    }
22    cur->isWord = true;
23    cur->frequency = frequency;
24}
25
26Node* findPrefix(Node* root, const std::string& prefix) {
27    Node* cur = root;
28    for (char ch : prefix) {
29        int idx = ch - 'a';
30        if (!cur->child[idx]) {
31            return nullptr;
32        }
33        cur = cur->child[idx];
34    }
35    return cur;
36}
37
38void collect(Node* node, std::string current,
39             std::vector<std::pair<std::string, int>>& out) {
40    if (!node) return;
41    if (node->isWord) {
42        out.push_back({current, node->frequency});
43    }
44    for (int i = 0; i < 26; ++i) {
45        if (node->child[i]) {
46            collect(node->child[i], current + char('a' + i), out);
47        }
48    }
49}
50
51int main() {
52    Node root;
53    insert(&root, "apple", 30);
54    insert(&root, "app", 50);
55    insert(&root, "application", 10);
56    insert(&root, "apply", 20);
57
58    std::vector<std::pair<std::string, int>> matches;
59    Node* start = findPrefix(&root, "app");
60    collect(start, "app", matches);
61
62    std::sort(matches.begin(), matches.end(),
63              [](const auto& a, const auto& b) {
64                  return a.second > b.second;
65              });
66
67    for (const auto& [word, score] : matches) {
68        std::cout << word << " (" << score << ")\n";
69    }
70}

This is a solid baseline, but production systems often cache the best suggestions at each prefix node so they do not have to traverse the whole subtree on every keystroke.

Ranking Matters As Much As Lookup

Autocomplete is not just a prefix problem. It is also a ranking problem. If you have ten thousand matches for a prefix, the user only sees a few, so you need a ranking signal such as frequency, recency, or domain-specific priority.

A practical design combines a prefix structure with a ranking policy. The data structure finds candidates. The ranking layer decides which candidates are worth showing first.

Common Pitfalls

The first mistake is asking for the best data structure without considering ranking. A trie that returns matches quickly is not enough if the most useful suggestions are buried deep in the subtree.

Another mistake is overcommitting to a naive trie with one pointer slot per alphabet character. That design is easy to code but can become memory-heavy. For larger datasets, compress the trie, use sparse child storage, or switch to a ternary search tree.

A final pitfall is ignoring normalization. If the input can contain uppercase text, punctuation, accents, or Unicode, define a normalization policy before building the index. Otherwise, lookup and stored data drift apart.

Summary

• A trie is the standard choice when you need fast prefix lookup and frequent updates.
• A ternary search tree is a strong middle ground when memory pressure matters.
• A sorted vector plus binary search is often best for static dictionaries.
• Good autocomplete requires ranking, not just prefix matching.
• Normalize input consistently before inserting or searching terms.