- Generated by
1.9.8
|
BDE 4.39.x Production Release
|
#include <ball_categorymanager_radixtree.h>
This class template implements a space-efficient associative container that maps string keys to values of the specified t_VALUE type. The container uses a radix tree (compressed trie) data structure, which shares common prefixes among keys. The container provides O(k) insertion, lookup, and removal operations, where k is the key length.
Public Types | |
| typedef bsl::allocator | allocator_type |
| typedef t_VALUE | value_type |
| typedef bsl::size_t | size_type |
| typedef bsl::optional< bsl::reference_wrapper< t_VALUE > > | OptValueRef |
| typedef bsl::optional< bsl::reference_wrapper< const t_VALUE > > | OptValueCRef |
| typedef bsl::pair< bool, bsl::reference_wrapper< t_VALUE > > | EmplaceResult |
Friends | |
| template<class t_TYPE > | |
| bool | operator== (const CategoryManager_RadixTree< t_TYPE > &, const CategoryManager_RadixTree< t_TYPE > &) |
| template<class t_TYPE > | |
| void | swap (CategoryManager_RadixTree< t_TYPE > &a, CategoryManager_RadixTree< t_TYPE > &b) |
| typedef bsl::allocator ball::CategoryManager_RadixTree< t_VALUE >::allocator_type |
| typedef bsl::pair<bool, bsl::reference_wrapper<t_VALUE> > ball::CategoryManager_RadixTree< t_VALUE >::EmplaceResult |
The return type of adding a value to the tree with emplace(). It is not the usual insert return type, because this data structure does not provide an iterator. The .first boolean is true if an element was inserted, and the .second data member is a reference to the (possibly newly created) value. Notice that if the value existed (.first == false) the reference wrapper will still give access to the value of that node; the .second is always a valid mutable reference to the value belonging to the key used in the emplace call.
| typedef bsl::optional<bsl::reference_wrapper<const t_VALUE> > ball::CategoryManager_RadixTree< t_VALUE >::OptValueCRef |
Type for immutable access to the optional value. Used also as return type for immutable finders where empty optional signifies "not found".
| typedef bsl::optional<bsl::reference_wrapper< t_VALUE> > ball::CategoryManager_RadixTree< t_VALUE >::OptValueRef |
Type for mutable access to the optional value. Used also as return type for mutable finders where empty optional signifies "not found".
| typedef bsl::size_t ball::CategoryManager_RadixTree< t_VALUE >::size_type |
| typedef t_VALUE ball::CategoryManager_RadixTree< t_VALUE >::value_type |
|
inline |
Create an empty CategoryManager_RadixTree. Optionally specify an allocator (e.g., the address of a bslma::Allocator object) to supply memory; otherwise, the default allocator is used.
|
inlineexplicit |
|
inline |
Create a CategoryManager_RadixTree having the same value as the specified original object. Optionally specify an allocator (e.g., the address of a bslma::Allocator object) to supply memory; otherwise, the default allocator is used.
|
inline |
Create a CategoryManager_RadixTree having the same value as the specified original object by moving (in amortized constant time) the contents of original to the newly-created object. The allocator associated with original is propagated for use in the newly-created object. original is left in a valid but unspecified state.
|
inline |
Create a CategoryManager_RadixTree having the same value as the specified original object that uses the specified allocator to supply memory. The contents of original are moved (in amortized constant time) to the newly-created object if allocator == original.get_allocator(), and are move-inserted (in linear time) using allocator otherwise. original is left in a valid but unspecified state.
|
default |
Destroy this object.
|
inline |
Remove all entries from this tree. After this call empty() will return true. After this call the tree will have 0 nodes.
|
inline |
Return true if this tree contains an entry for the specified key, and false otherwise.
| CategoryManager_RadixTree< t_VALUE >::size_type ball::CategoryManager_RadixTree< t_VALUE >::countNodes | ( | ) | const |
Return the total number of nodes in this tree, including internal nodes without values.
size() that tells the actual number of entries with values. | CategoryManager_RadixTree< t_VALUE >::EmplaceResult ball::CategoryManager_RadixTree< t_VALUE >::emplace | ( | const bsl::string_view & | key, |
| Args &&... | args | ||
| ) |
Insert into this tree an entry with the specified key and a newly created t_VALUE object, constructed by forwarding get_allocator() (if required) and the specified (variable number of) args to the corresponding constructor of t_VALUE. Return a pair consisting of a reference to the value associated with key (whether newly inserted or already existing) and a boolean indicating whether insertion took place (true if the key was not already present, false otherwise). This method requires that t_VALUE be emplace-constructible from args.
|
inline |
Return true if this tree contains no entries, and false otherwise.
| bool ball::CategoryManager_RadixTree< t_VALUE >::erase | ( | const bsl::string_view & | key | ) |
Remove from this tree the entry with the specified key. Return true if the entry was removed (key existed), and false otherwise.
| CategoryManager_RadixTree< t_VALUE >::size_type ball::CategoryManager_RadixTree< t_VALUE >::eraseChildrenOfPrefix | ( | const bsl::string_view & | prefix | ) |
Remove all children of the entry matching the specified prefix, but not the entry with the prefix itself. If unused (no value, no children) nodes remain remove those, too. If no entry exists for prefix remove nothing. Return the number of entries removed.
| CategoryManager_RadixTree< t_VALUE >::size_type ball::CategoryManager_RadixTree< t_VALUE >::erasePrefix | ( | const bsl::string_view & | prefix | ) |
Remove from this tree all entries with keys that have the specified prefix, including the entry for the prefix itself if it exists. Return the number of entries removed.
prefix, not just those that have a value. | CategoryManager_RadixTree< t_VALUE >::OptValueRef ball::CategoryManager_RadixTree< t_VALUE >::find | ( | const bsl::string_view & | key | ) |
Return an optional containing a reference to the modifiable value associated with the specified key, or an empty optional if the key is not found. The returned reference remains valid until the tree is modified.
| CategoryManager_RadixTree< t_VALUE >::OptValueCRef ball::CategoryManager_RadixTree< t_VALUE >::find | ( | const bsl::string_view & | key | ) | const |
Return an optional containing a reference to the non-modifiable value associated with the specified key, or an empty optional if the key is not found. The returned reference remains valid until the tree is modified.
|
inline |
Return the longest prefix of the specified key that has an associated value in this tree, or an empty string view if no such prefix exists. If the optionally specified value is not null, load into *value a reference to the value associated with the returned prefix.
|
inline |
Return the longest prefix of the specified key that has an associated value in this tree, or an empty string view if no such prefix exists. If the optionally specified value is not null, load into *value a reference to the value associated with the returned prefix.
| void ball::CategoryManager_RadixTree< t_VALUE >::forEach | ( | const t_FUNCTOR & | functor | ) |
Call the specified functor for each key-value pair in this tree. The functor should be a callable object that accepts two parameters: const bsl::string_view& for the key and t_VALUE& for the value. The order of visitation is unspecified. Noteice that the functor is able to modify the value.
| void ball::CategoryManager_RadixTree< t_VALUE >::forEach | ( | const t_FUNCTOR & | functor | ) | const |
Call the specified functor for each key-value pair in this tree. The functor should be a callable object that accepts two parameters: const bsl::string_view& for the key and const t_VALUE& for the value. The order of visitation is unspecified. See also the manipulator variation that allows the functor to modify the value.
| CategoryManager_RadixTree< t_VALUE >::size_type ball::CategoryManager_RadixTree< t_VALUE >::forEachPrefix | ( | const bsl::string_view & | prefix, |
| const t_FUNCTOR & | functor | ||
| ) |
Call the specified functor for each key-value pair whose key starts with the specified prefix. The functor should be a callable object that accepts two parameters: const bsl::string_view& for the key and t_VALUE& for the value. Return the number of times the functor was called. The order of visitation is unspecified. Noteice that the functor is able to modify the value.
| CategoryManager_RadixTree< t_VALUE >::size_type ball::CategoryManager_RadixTree< t_VALUE >::forEachPrefix | ( | const bsl::string_view & | prefix, |
| const t_FUNCTOR & | functor | ||
| ) | const |
Call the specified functor for each key-value pair whose key starts with the specified prefix. The functor should be a callable object that accepts two parameters: const bsl::string_view& for the key and const t_VALUE& for the value. Return the number of times the functor was called. The order of visitation is unspecified. See also the manipulator variation that allows the functor to modify the value.
|
inline |
Return the allocator used by this object to supply memory.
|
inline |
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object. The contents of rhs are moved (in amortized constant time) to this object if get_allocator() == rhs.get_allocator(); otherwise, all elements in this object are either destroyed or move-assigned to, and each additional element in rhs is move-inserted into this object. rhs is left in a valid but unspecified state.
|
inline |
Assign to this object the value of the specified rhs object, and return a reference providing modifiable access to this object.
| bsl::ostream & ball::CategoryManager_RadixTree< t_VALUE >::printNodes | ( | bsl::ostream & | stream, |
| int | level = 0, |
||
| int | spacesPerLevel = 4 |
||
| ) | const |
Write the value of this object to the specified output stream in a human-readable format, and return a non-const reference to stream. Optionally specify an initial indentation level, whose absolute value is incremented recursively for nested objects. If level is specified, optionally specify spacesPerLevel, whose absolute value indicates the number of spaces per indentation level for this and all of its nested objects. If level is negative, suppress indentation of the first line. If spacesPerLevel is negative, format the entire output on one line, suppressing all but the initial indentation (as governed by level). If stream is not valid on entry, this operation has no effect.
|
inline |
Return the number of entries in this tree.
|
inline |
Efficiently exchange the value of this object with the value of the specified other object. This method provides the no-throw exception-safety guarantee.
other.
|
friend |
|
friend |
1.9.8