Map Trie
(string/map_trie.hpp)

View this file on GitHub
Last update: 2026-08-11 13:50:43+09:00
Include: #include "string/map_trie.hpp"

Overview

m1une::string::MapTrie is a multiset trie whose outgoing edges are stored in std::map. It is useful when symbols come from a large, sparse, or non-integral alphabet for which allocating one transition per possible symbol is wasteful.

It supports duplicate insertion, deletion, exact lookup, prefix counting, and enumerating stored sequences that are prefixes of a query. Nodes are kept in a contiguous vector, while each node allocates only the transitions it uses.

Template Parameters

Symbol: Key type stored on each edge.
Compare: Strict weak ordering for Symbol. Defaults to std::less<Symbol> and must be default-constructible.

The input to an operation may be any iterable sequence whose elements can be used to search for and construct Symbol values. Examples include strings, integer vectors, and vectors of coordinate pairs with a suitable comparator.

Methods

For a sequence of length $L$, let $d_i$ be the number of outgoing transitions at the node visited before its $i$-th symbol, and let $K$ be the allocated node count. The bounds below assume that comparing two symbols takes $O(1)$ time; otherwise, multiply the logarithmic terms by the comparison cost.

Method	Description	Complexity
`MapTrie()`	Constructs an empty trie.	$O(1)$
`int size() const`	Returns the number of stored sequences including duplicates.	$O(1)$
`int distinct_size() const`	Returns the number of distinct stored sequences.	$O(1)$
`bool empty() const`	Returns whether no sequences are stored.	$O(1)$
`node_id root() const`	Returns the root node handle.	$O(1)$
`node_id find(const Sequence& sequence) const`	Returns the node reached by an active path, or `null_node` if absent.	$O(\sum_i \log(d_i + 1))$
`const Node& node(node_id id) const`	Returns a read-only node view.	$O(1)$
`size_t node_count() const`	Returns allocated nodes, including the root.	$O(1)$
`void reserve(size_t n)`	Reserves vector storage for approximately `n` nodes.	$O(K)$
`void clear()`	Removes all sequences and returns to one root node.	$O(K)$
`node_id insert(const Sequence& sequence, int multiplicity = 1)`	Inserts copies and returns the endpoint node handle.	$O(\sum_i \log(d_i + 1))$
`int count(const Sequence& sequence) const`	Returns the sequence multiplicity.	$O(\sum_i \log(d_i + 1))$
`bool contains(const Sequence& sequence) const`	Returns whether the sequence is stored.	$O(\sum_i \log(d_i + 1))$
`int prefix_count(const Sequence& prefix) const`	Counts stored sequences beginning with `prefix`, including duplicates.	$O(\sum_i \log(d_i + 1))$
`bool starts_with(const Sequence& prefix) const`	Returns whether a stored sequence begins with `prefix`.	$O(\sum_i \log(d_i + 1))$
`bool erase_one(const Sequence& sequence)`, `bool erase(const Sequence& sequence)`	Erases one copy and reports success.	$O(\sum_i \log(d_i + 1))$
`int erase_all(const Sequence& sequence)`	Erases all copies and returns the number erased.	$O(\sum_i \log(d_i + 1))$
`void for_each_prefix(const Sequence& sequence, Callback callback) const`	Calls `callback(length, multiplicity)` for every stored prefix.	$O(\sum_i \log(d_i + 1))$ plus callback time
`int longest_prefix(const Sequence& sequence) const`	Returns the longest stored prefix length, or `-1` if none exists.	$O(\sum_i \log(d_i + 1))$

Each Node exposes child, subtree_count, and terminal_count. The child member has type std::map<Symbol, node_id, Compare>. Node handles remain valid across insertions and erasures and may index user-owned metadata. References returned by node() can be invalidated by insertion, reserve(), or clear().

Erasing does not reclaim nodes or transitions. clear() invalidates all old handles except the root. The empty sequence is supported and is reported by for_each_prefix with length 0 when stored.

For a small contiguous character alphabet, prefer m1une::string::Trie: its array transitions give lower constants and $O(L)$ operations.

Example

#include "string/map_trie.hpp"

#include <iostream>
#include <vector>

int main() {
    m1une::string::MapTrie<int> trie;

    std::vector<int> first;
    first.push_back(1000000000);
    first.push_back(-7);
    std::vector<int> second = first;
    second.push_back(42);

    trie.insert(first, 2);
    trie.insert(second);

    std::cout << trie.count(first) << "\n";        // 2
    std::cout << trie.prefix_count(first) << "\n"; // 3
    std::cout << trie.longest_prefix(second) << "\n"; // 3
}

Required by

String Algorithms Bundle (string/all.hpp)

Verified with

Code

#ifndef M1UNE_STRING_MAP_TRIE_HPP
#define M1UNE_STRING_MAP_TRIE_HPP 1

#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <map>
#include <vector>

namespace m1une {
namespace string {

// A multiset trie whose outgoing edges are stored in ordered maps.
template <class Symbol, class Compare = std::less<Symbol>>
struct MapTrie {
    using node_id = int;
    static constexpr node_id null_node = -1;

    struct Node {
        std::map<Symbol, node_id, Compare> child;
        int subtree_count = 0;
        int terminal_count = 0;
    };

   private:
    std::vector<Node> _nodes;
    int _distinct_size;

    node_id new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    template <class Sequence>
    node_id find_node(const Sequence& sequence) const {
        node_id node = 0;
        for (const auto& symbol : sequence) {
            auto iterator = _nodes[node].child.find(symbol);
            if (iterator == _nodes[node].child.end()) return null_node;
            node = iterator->second;
            if (_nodes[node].subtree_count == 0) return null_node;
        }
        return node;
    }

   public:
    MapTrie() : _nodes(1), _distinct_size(0) {}

    int size() const {
        return _nodes[0].subtree_count;
    }

    int distinct_size() const {
        return _distinct_size;
    }

    bool empty() const {
        return size() == 0;
    }

    node_id root() const {
        return 0;
    }

    const Node& node(node_id id) const {
        assert(0 <= id && std::size_t(id) < _nodes.size());
        return _nodes[id];
    }

    template <class Sequence>
    node_id find(const Sequence& sequence) const {
        return find_node(sequence);
    }

    std::size_t node_count() const {
        return _nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        _nodes.reserve(node_capacity);
    }

    void clear() {
        _nodes.clear();
        _nodes.emplace_back();
        _distinct_size = 0;
    }

    template <class Sequence>
    node_id insert(const Sequence& sequence, int multiplicity = 1) {
        assert(0 < multiplicity);
        node_id node = 0;
        _nodes[node].subtree_count += multiplicity;
        for (const auto& symbol : sequence) {
            auto iterator = _nodes[node].child.find(symbol);
            node_id child;
            if (iterator == _nodes[node].child.end()) {
                child = new_node();
                _nodes[node].child.emplace(symbol, child);
            } else {
                child = iterator->second;
            }
            node = child;
            _nodes[node].subtree_count += multiplicity;
        }
        if (_nodes[node].terminal_count == 0) _distinct_size++;
        _nodes[node].terminal_count += multiplicity;
        return node;
    }

    template <class Sequence>
    int count(const Sequence& sequence) const {
        node_id node = find_node(sequence);
        return node == null_node ? 0 : _nodes[node].terminal_count;
    }

    template <class Sequence>
    bool contains(const Sequence& sequence) const {
        return count(sequence) != 0;
    }

    // Returns the number of stored sequences beginning with prefix.
    template <class Sequence>
    int prefix_count(const Sequence& prefix) const {
        node_id node = find_node(prefix);
        return node == null_node ? 0 : _nodes[node].subtree_count;
    }

    template <class Sequence>
    bool starts_with(const Sequence& prefix) const {
        return prefix_count(prefix) != 0;
    }

    template <class Sequence>
    bool erase_one(const Sequence& sequence) {
        node_id terminal = find_node(sequence);
        if (terminal == null_node || _nodes[terminal].terminal_count == 0) {
            return false;
        }

        node_id node = 0;
        _nodes[node].subtree_count--;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child.find(symbol)->second;
            _nodes[node].subtree_count--;
        }
        _nodes[node].terminal_count--;
        if (_nodes[node].terminal_count == 0) _distinct_size--;
        return true;
    }

    template <class Sequence>
    bool erase(const Sequence& sequence) {
        return erase_one(sequence);
    }

    template <class Sequence>
    int erase_all(const Sequence& sequence) {
        int multiplicity = count(sequence);
        if (multiplicity == 0) return 0;

        node_id node = 0;
        _nodes[node].subtree_count -= multiplicity;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child.find(symbol)->second;
            _nodes[node].subtree_count -= multiplicity;
        }
        _nodes[node].terminal_count = 0;
        _distinct_size--;
        return multiplicity;
    }

    // Calls callback(length, multiplicity) for every stored prefix.
    // The empty prefix is reported with length 0 when it is stored.
    template <class Sequence, class Callback>
    void for_each_prefix(const Sequence& sequence, Callback callback) const {
        node_id node = 0;
        if (_nodes[node].terminal_count != 0) {
            callback(0, _nodes[node].terminal_count);
        }

        int length = 0;
        for (const auto& symbol : sequence) {
            auto iterator = _nodes[node].child.find(symbol);
            if (iterator == _nodes[node].child.end()) return;
            node = iterator->second;
            if (_nodes[node].subtree_count == 0) return;
            length++;
            if (_nodes[node].terminal_count != 0) {
                callback(length, _nodes[node].terminal_count);
            }
        }
    }

    // Returns the length of the longest stored sequence that is a prefix.
    // Returns -1 when no stored prefix exists.
    template <class Sequence>
    int longest_prefix(const Sequence& sequence) const {
        int result = _nodes[0].terminal_count == 0 ? -1 : 0;
        for_each_prefix(sequence, [&result](int length, int) {
            result = length;
        });
        return result;
    }
};

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_MAP_TRIE_HPP

#line 1 "string/map_trie.hpp"



#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <map>
#include <vector>

namespace m1une {
namespace string {

// A multiset trie whose outgoing edges are stored in ordered maps.
template <class Symbol, class Compare = std::less<Symbol>>
struct MapTrie {
    using node_id = int;
    static constexpr node_id null_node = -1;

    struct Node {
        std::map<Symbol, node_id, Compare> child;
        int subtree_count = 0;
        int terminal_count = 0;
    };

   private:
    std::vector<Node> _nodes;
    int _distinct_size;

    node_id new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    template <class Sequence>
    node_id find_node(const Sequence& sequence) const {
        node_id node = 0;
        for (const auto& symbol : sequence) {
            auto iterator = _nodes[node].child.find(symbol);
            if (iterator == _nodes[node].child.end()) return null_node;
            node = iterator->second;
            if (_nodes[node].subtree_count == 0) return null_node;
        }
        return node;
    }

   public:
    MapTrie() : _nodes(1), _distinct_size(0) {}

    int size() const {
        return _nodes[0].subtree_count;
    }

    int distinct_size() const {
        return _distinct_size;
    }

    bool empty() const {
        return size() == 0;
    }

    node_id root() const {
        return 0;
    }

    const Node& node(node_id id) const {
        assert(0 <= id && std::size_t(id) < _nodes.size());
        return _nodes[id];
    }

    template <class Sequence>
    node_id find(const Sequence& sequence) const {
        return find_node(sequence);
    }

    std::size_t node_count() const {
        return _nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        _nodes.reserve(node_capacity);
    }

    void clear() {
        _nodes.clear();
        _nodes.emplace_back();
        _distinct_size = 0;
    }

    template <class Sequence>
    node_id insert(const Sequence& sequence, int multiplicity = 1) {
        assert(0 < multiplicity);
        node_id node = 0;
        _nodes[node].subtree_count += multiplicity;
        for (const auto& symbol : sequence) {
            auto iterator = _nodes[node].child.find(symbol);
            node_id child;
            if (iterator == _nodes[node].child.end()) {
                child = new_node();
                _nodes[node].child.emplace(symbol, child);
            } else {
                child = iterator->second;
            }
            node = child;
            _nodes[node].subtree_count += multiplicity;
        }
        if (_nodes[node].terminal_count == 0) _distinct_size++;
        _nodes[node].terminal_count += multiplicity;
        return node;
    }

    template <class Sequence>
    int count(const Sequence& sequence) const {
        node_id node = find_node(sequence);
        return node == null_node ? 0 : _nodes[node].terminal_count;
    }

    template <class Sequence>
    bool contains(const Sequence& sequence) const {
        return count(sequence) != 0;
    }

    // Returns the number of stored sequences beginning with prefix.
    template <class Sequence>
    int prefix_count(const Sequence& prefix) const {
        node_id node = find_node(prefix);
        return node == null_node ? 0 : _nodes[node].subtree_count;
    }

    template <class Sequence>
    bool starts_with(const Sequence& prefix) const {
        return prefix_count(prefix) != 0;
    }

    template <class Sequence>
    bool erase_one(const Sequence& sequence) {
        node_id terminal = find_node(sequence);
        if (terminal == null_node || _nodes[terminal].terminal_count == 0) {
            return false;
        }

        node_id node = 0;
        _nodes[node].subtree_count--;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child.find(symbol)->second;
            _nodes[node].subtree_count--;
        }
        _nodes[node].terminal_count--;
        if (_nodes[node].terminal_count == 0) _distinct_size--;
        return true;
    }

    template <class Sequence>
    bool erase(const Sequence& sequence) {
        return erase_one(sequence);
    }

    template <class Sequence>
    int erase_all(const Sequence& sequence) {
        int multiplicity = count(sequence);
        if (multiplicity == 0) return 0;

        node_id node = 0;
        _nodes[node].subtree_count -= multiplicity;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child.find(symbol)->second;
            _nodes[node].subtree_count -= multiplicity;
        }
        _nodes[node].terminal_count = 0;
        _distinct_size--;
        return multiplicity;
    }

    // Calls callback(length, multiplicity) for every stored prefix.
    // The empty prefix is reported with length 0 when it is stored.
    template <class Sequence, class Callback>
    void for_each_prefix(const Sequence& sequence, Callback callback) const {
        node_id node = 0;
        if (_nodes[node].terminal_count != 0) {
            callback(0, _nodes[node].terminal_count);
        }

        int length = 0;
        for (const auto& symbol : sequence) {
            auto iterator = _nodes[node].child.find(symbol);
            if (iterator == _nodes[node].child.end()) return;
            node = iterator->second;
            if (_nodes[node].subtree_count == 0) return;
            length++;
            if (_nodes[node].terminal_count != 0) {
                callback(length, _nodes[node].terminal_count);
            }
        }
    }

    // Returns the length of the longest stored sequence that is a prefix.
    // Returns -1 when no stored prefix exists.
    template <class Sequence>
    int longest_prefix(const Sequence& sequence) const {
        int result = _nodes[0].terminal_count == 0 ? -1 : 0;
        for_each_prefix(sequence, [&result](int length, int) {
            result = length;
        });
        return result;
    }
};

}  // namespace string
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Map Trie
(string/map_trie.hpp)

Overview

Template Parameters

Methods

Example

Required by

Verified with

Code

Map Trie (string/map_trie.hpp)

Overview

Template Parameters

Methods

Example

Required by

Verified with

Code

Map Trie
(string/map_trie.hpp)