LLVM: llvm::RadixTree< KeyType, T > Class Template Reference (original) (raw)
A Radix Tree implementation. More...
#include "[llvm/ADT/RadixTree.h](RadixTree%5F8h%5Fsource.html)"
| Public Types | |
|---|---|
| using | key_type = KeyType |
| using | mapped_type = T |
| using | value_type = std::pair<const KeyType, mapped_type> |
| using | prefix_iterator = IteratorImpl<value_type> |
| using | const_prefix_iterator = IteratorImpl<const value_type> |
| using | iterator = typename ContainerType::iterator |
| using | const_iterator = typename ContainerType::const_iterator |
| Public Member Functions | |
|---|---|
| RadixTree ()=default | |
| RadixTree (RadixTree &&)=default | |
| RadixTree & | operator= (RadixTree &&)=default |
| bool | empty () const |
| Returns true if the tree is empty. | |
| size_t | size () const |
| Returns the number of elements in the tree. | |
| size_t | countNodes () const |
| Returns the number of nodes in the tree. | |
| iterator | begin () |
| Returns an iterator to the first element. | |
| const_iterator | begin () const |
| iterator | end () |
| Returns an iterator to the end of the tree. | |
| const_iterator | end () const |
| template<typename... Ts> | |
| std::pair< iterator, bool > | emplace (key_type &&Key, Ts &&...Args) |
| Constructs and inserts a new element into the tree. | |
| iterator_range< const_prefix_iterator > | find_prefixes (const key_type &Key) const |
| Finds all elements whose keys are prefixes of the given Key. |
template<typename KeyType, typename T>
class llvm::RadixTree< KeyType, T >
A Radix Tree implementation.
A Radix Tree (also known as a compact prefix tree or radix trie) is a data structure that stores a dynamic set or associative array where keys are strings and values are associated with these keys. Unlike a regular trie, the edges of a radix tree can be labeled with sequences of characters as well as single characters. This makes radix trees more efficient for storing sparse data sets, where many nodes in a regular trie would have only one child.
This implementation supports arbitrary key types that can be iterated over (e.g., std::string, std::vector, ArrayRef). The key type must provide begin() and end() for iteration.
The tree stores std::pair<const KeyType, T> as its value type.
Example usage:
Tree.emplace("apple", 1);
Tree.emplace("grapefruit", 2);
Tree.emplace("grape", 3);
for (const auto &[Key, Value] : Tree.find_prefixes("grapefruit juice")) {
}
for (const auto &[Key, Value] : Tree)
A Radix Tree implementation.
iterator_range< const_prefix_iterator > find_prefixes(const key_type &Key) const
Finds all elements whose keys are prefixes of the given Key.
std::pair< iterator, bool > emplace(key_type &&Key, Ts &&...Args)
Constructs and inserts a new element into the tree.
LLVM Value Representation.
LLVM_ABI raw_fd_ostream & outs()
This returns a reference to a raw_fd_ostream for standard output.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
Note
The RadixTree takes ownership of the KeyType and T objects inserted into it. When an element is removed or the tree is destroyed, these objects will be destructed. However, if KeyType is a reference-like type, e.g., StringRef or range, the user must guarantee that the referenced data has a lifetime longer than the tree.
Definition at line 71 of file RadixTree.h.
◆ const_iterator
template<typename KeyType, typename T>
◆ const_prefix_iterator
template<typename KeyType, typename T>
◆ iterator
template<typename KeyType, typename T>
using llvm::RadixTree< KeyType, T >::iterator = typename ContainerType::iterator
◆ key_type
template<typename KeyType, typename T>
◆ mapped_type
template<typename KeyType, typename T>
◆ prefix_iterator
template<typename KeyType, typename T>
◆ value_type
template<typename KeyType, typename T>
template<typename KeyType, typename T>
Referenced by operator=(), and RadixTree().
◆ RadixTree() [2/2]
template<typename KeyType, typename T>
References RadixTree().
◆ begin() [1/2]
template<typename KeyType, typename T>
Returns an iterator to the first element.
Definition at line 290 of file RadixTree.h.
◆ begin() [2/2]
template<typename KeyType, typename T>
◆ countNodes()
template<typename KeyType, typename T>
Returns the number of nodes in the tree.
This function counts all internal nodes in the tree. It can be useful for understanding the memory footprint or complexity of the tree structure.
Definition at line 287 of file RadixTree.h.
◆ emplace()
template<typename KeyType, typename T>
template<typename... Ts>
Constructs and inserts a new element into the tree.
This function constructs an element in place within the tree. If an element with the same key already exists, the insertion fails and the function returns an iterator to the existing element along with false. Otherwise, the new element is inserted and the function returns an iterator to the new element along with true.
Parameters
| Key | The key of the element to construct. |
|---|---|
| Args | Arguments to forward to the constructor of the mapped_type. |
Returns
A pair consisting of an iterator to the inserted element (or to the element that prevented insertion) and a boolean value indicating whether the insertion took place.
Definition at line 311 of file RadixTree.h.
References llvm::HasValue(), llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key, and T.
◆ empty()
template<typename KeyType, typename T>
Returns true if the tree is empty.
Definition at line 278 of file RadixTree.h.
◆ end() [1/2]
template<typename KeyType, typename T>
Returns an iterator to the end of the tree.
Definition at line 294 of file RadixTree.h.
◆ end() [2/2]
template<typename KeyType, typename T>
◆ find_prefixes()
template<typename KeyType, typename T>
Finds all elements whose keys are prefixes of the given Key.
This function returns an iterator range over all elements in the tree whose keys are prefixes of the provided Key. For example, if the tree contains "abcde", "abc", "abcdefgh", and Key is "abcde", this function would return iterators to "abcde" and "abc".
Parameters
| Key | The key to search for prefixes of. |
|---|
Returns
An iterator_range of const_prefix_iterators, allowing iteration over the found prefix elements.
Note
The returned iterators reference the Key provided by the caller. The caller must ensure that Key remains valid for the lifetime of the iterators.
Definition at line 342 of file RadixTree.h.
References llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key.
◆ operator=()
template<typename KeyType, typename T>
References RadixTree().
◆ size()
template<typename KeyType, typename T>
Returns the number of elements in the tree.
Definition at line 281 of file RadixTree.h.
The documentation for this class was generated from the following file:
- include/llvm/ADT/RadixTree.h