std::variant and recursive data in C++: JSON values, trees and visitors
Model a value that is one of several types with std::variant, handle each case with std::visit, build recursive types like JSON values and trees, and walk them safely.
Parsers and trees need one type that can hold "a number, or a string, or a list of more of these".
C++17's std::variant is the tool for the first part, and containers of the type itself handle
the second.
One of several types: std::variant
using Token = std::variant<double, char, std::string>; // number, operator, name
Token t = 3.5;
t = '+'; // now holds a char
if (std::holds_alternative<char>(t)) { char op = std::get<char>(t); }
if (auto* name = std::get_if<std::string>(&t)) { /* *name */ }A variant always holds exactly one of its alternatives. std::get with the wrong type throws
std::bad_variant_access; std::get_if returns nullptr instead.
std::visit: one branch per case
std::visit calls a function with whatever the variant holds. With a set of lambdas, you get a
type-checked switch:
template <class... Fs> struct Overloaded : Fs... { using Fs::operator()...; };
template <class... Fs> Overloaded(Fs...) -> Overloaded<Fs...>;
std::string describe(const Token& t) {
return std::visit(Overloaded{
[](double d) { return "number " + std::to_string(d); },
[](char c) { return std::string("operator ") + c; },
[](const std::string& s) { return "name " + s; },
}, t);
}Forget a case and it doesn't compile. That's the main advantage over a hand-written enum plus
fields.
Recursive types: a JSON value
A JSON value is null, a boolean, a number, a string, an array of values or an object of values. It refers to itself, so wrap the variant in a struct:
struct Value;
using Array = std::vector<Value>; // OK with an incomplete type
using Object = std::vector<std::pair<std::string, Value>>; // keeps the key order
struct Value {
std::variant<std::nullptr_t, bool, double, std::string, Array, Object> data;
};std::vector of an incomplete type is allowed since C++17. std::map<std::string, Value> isn't
guaranteed to compile with an incomplete type, which is one reason to use a vector of pairs (the
other: it keeps the order the keys appeared in). Build it in
a JSON parser for Configo.
Trees with unique_ptr children
For nodes that own their children, use std::unique_ptr:
struct TrieNode {
std::map<char, std::unique_ptr<TrieNode>> children; // sorted, so walks are alphabetical
int weight = 0; // > 0 if a word ends here
};Destroying the root destroys the whole tree, with no delete anywhere. To remove a branch, erase
its entry from the parent's map. See search suggestions for Findly
and smart pointers.
Walking a tree recursively
Recursive data invites recursive functions: a function that handles one node and calls itself for the children.
void collect(const TrieNode& node, std::string& prefix, std::vector<std::string>& out) {
if (node.weight > 0) out.push_back(prefix);
for (const auto& [ch, child] : node.children) {
prefix.push_back(ch);
collect(*child, prefix, out);
prefix.pop_back(); // undo, so the caller's prefix is unchanged
}
}Each call uses stack space, and the stack is small (often 1–8 MB). Input from outside, such as a
JSON file of 100,000 nested [, can crash a recursive parser. Add a depth limit and report a
clean error when it's exceeded: see
depth limits in parsing.
Questions and answers
- When should I use std::variant instead of inheritance?
- When the set of alternatives is fixed and known up front, like the six kinds of JSON value. A variant keeps values on the stack, needs no virtual functions, and std::visit makes the compiler check you handled every case. Inheritance fits better when other code must be able to add new types.
- How can a type contain itself, like a JSON array of values?
- Through a container or pointer that doesn't need the full type yet: std::vector<Value> is allowed with an incomplete type since C++17, and std::unique_ptr<Node> always is. A Value can't contain a Value directly, because its size would be infinite.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Configo
A JSON parser for Configo
Write the strict, dependency-free JSON parser at the heart of Configo: exact error positions, Unicode escapes, depth limits, compact output and path lookups.
- recursive descent
- recursive data types
- Unicode and UTF-8
- defensive parsing
Sheetwise
A formula engine for Sheetwise
Write the formula engine behind Sheetwise's cells: a tokenizer and a recursive-descent parser with correct precedence, precise error positions, cell references and functions.
- tokenizers
- recursive descent
- operator precedence
- error reporting
Findly
Search suggestions for Findly
Build the autocomplete behind Findly's search box with a trie, then add 'did you mean' suggestions using edit distance computed along the trie.
- tries
- tree ownership
- edit distance
- dynamic programming
Sieve Mail
A safe regex engine for Sieve Mail
Write the regular-expression engine behind Sieve Mail's filter rules: a parser, Thompson's NFA construction and a simulation that runs in linear time, so no rule can hang the mail servers.
- parsing
- automata
- Thompson's construction
- worst-case complexity
Read next
- Recursive descent parsing: tokenizers, grammars and precedence
How to parse formulas, JSON and patterns by hand: split input into tokens, write the grammar down, turn each rule into a function, handle precedence, and report exact error positions.