Struct template trie

Struct template trie_map

boost::text::trie_map

Synopsis

// In header: <boost/text/trie_map.hpp>

template<typename Key, typename Value, typename Compare> 
struct trie_map {
  // types
  typedef Key                                                      key_type;              
  typedef Value                                                    mapped_type;           
  typedef trie_element< Key, Value >                               value_type;            
  typedef Compare                                                  key_compare;           
  typedef typename Key::value_type                                 key_element_type;      
  typedef value_type &                                             reference;             
  typedef value_type const &                                       const_reference;       
  typedef trie_map_iterator< key_type, mapped_type >               iterator;              
  typedef const_trie_map_iterator< key_type, mapped_type >         const_iterator;        
  typedef reverse_trie_map_iterator< key_type, mapped_type >       reverse_iterator;      
  typedef const_reverse_trie_map_iterator< key_type, mapped_type > const_reverse_iterator;
  typedef std::ptrdiff_t                                           size_type;             
  typedef std::ptrdiff_t                                           difference_type;       
  typedef trie_range< iterator >                                   range;                 
  typedef const_trie_range< const_iterator >                       const_range;           
  typedef trie_insert_result< iterator >                           insert_result;         
  typedef trie_match_result                                        match_result;          

  // construct/copy/destruct
  trie_map();
  trie_map(Compare const &);
  template<typename Iter, typename Sentinel> 
    trie_map(Iter, Sentinel, Compare const & = Compare());
  template<typename Range> 
    explicit trie_map(Range, Compare const & = Compare());
  template<std::size_t KeySize> 
    explicit trie_map(boost::text::trie< Key, Value, Compare, KeySize > const &);
  trie_map(std::initializer_list< value_type >);
  trie_map & operator=(std::initializer_list< value_type >);

  // public member functions
  bool empty() const;
  size_type size() const;
  size_type max_size() const;
  const_iterator begin() const;
  const_iterator end() const;
  const_iterator cbegin() const;
  const_iterator cend() const;
  const_reverse_iterator rbegin() const;
  const_reverse_iterator rend() const;
  const_reverse_iterator crbegin() const;
  const_reverse_iterator crend() const;
  template<typename KeyRange> bool contains(KeyRange const &) const;
  template<typename KeyRange> const_iterator find(KeyRange const &) const;
  template<typename KeyRange> 
    const_iterator lower_bound(KeyRange const &) const;
  template<typename KeyRange> 
    const_iterator upper_bound(KeyRange const &) const;
  template<typename KeyRange> const_range equal_range(KeyRange const &) const;
  template<typename KeyIter, typename Sentinel> 
    match_result longest_subsequence(KeyIter, Sentinel) const;
  template<typename KeyRange> 
    match_result longest_subsequence(KeyRange const &) const;
  template<typename KeyIter, typename Sentinel> 
    match_result longest_match(KeyIter, Sentinel) const;
  template<typename KeyRange> 
    match_result longest_match(KeyRange const &) const;
  template<typename KeyElementT> 
    match_result extend_subsequence(match_result, KeyElementT) const;
  template<typename KeyIter, typename Sentinel> 
    match_result extend_subsequence(match_result, KeyIter, Sentinel) const;
  template<typename KeyElementT> 
    match_result extend_match(match_result, KeyElementT) const;
  template<typename KeyIter, typename Sentinel> 
    match_result extend_match(match_result, KeyIter, Sentinel) const;
  template<typename OutIter> 
    OutIter copy_next_key_elements(match_result, OutIter) const;
  template<typename KeyRange> 
    optional_ref< mapped_type const > operator[](KeyRange const &) const;
  optional_ref< mapped_type const > operator[](match_result) const;
  iterator begin();
  iterator end();
  reverse_iterator rbegin();
  reverse_iterator rend();
  void clear();
  template<typename KeyRange> iterator find(KeyRange const &);
  template<typename KeyRange> iterator lower_bound(KeyRange const &);
  template<typename KeyRange> iterator upper_bound(KeyRange const &);
  template<typename KeyRange> range equal_range(KeyRange const &);
  template<typename KeyRange> 
    optional_ref< mapped_type > operator[](KeyRange const &);
  optional_ref< mapped_type > operator[](match_result);
  template<typename KeyIter, typename Sentinel> 
    insert_result insert(KeyIter, Sentinel, Value);
  template<typename KeyRange> insert_result insert(KeyRange const &, Value);
  template<typename Char, std::size_t N> 
    insert_result insert(Char const (&), Value);
  insert_result insert(value_type);
  template<typename Iter, typename Sentinel> void insert(Iter, Sentinel);
  template<typename Range> insert_result insert(Range const &);
  void insert(std::initializer_list< value_type >);
  template<typename KeyIter, typename Sentinel> 
    insert_result insert_or_assign(KeyIter, Sentinel, Value);
  template<typename KeyRange> 
    insert_result insert_or_assign(KeyRange const &, Value);
  template<typename Char, std::size_t N> 
    insert_result insert_or_assign(Char const (&), Value);
  template<typename KeyRange> bool erase(KeyRange const &);
  iterator erase(iterator);
  iterator erase(iterator, iterator);
  void swap(trie_map &);
};

Description

An associative container similar to std::map, built upon a trie, or prefix-tree. A trie_map contains a set of keys, each of which is a sequence, and a set of values, each associated with some key. Each node in the trie_map represents some prefix found in at least one member of the set of values contained in the trie_map. If a certain node represents the end of one of the keys, it has an associated value. Such a node may or may not have children.

Complexity of lookups is always O(M), where M is the size of the Key being lookep up. Note that this implies that lookup complexity is independent of the size of the trie_map.

`trie_map` public construct/copy/destruct

```
trie_map();
```
```
trie_map(Compare const & comp);
```

template<typename Iter, typename Sentinel> 
  trie_map(Iter first, Sentinel last, Compare const & comp = Compare());

template<typename Range> 
  explicit trie_map(Range r, Compare const & comp = Compare());

template<std::size_t KeySize> 
  explicit trie_map(boost::text::trie< Key, Value, Compare, KeySize > const & trie);

trie_map(std::initializer_list< value_type > il);

trie_map & operator=(std::initializer_list< value_type > il);

`trie_map` public member functions

```
bool empty() const;
```
```
size_type size() const;
```
```
size_type max_size() const;
```
```
const_iterator begin() const;
```
```
const_iterator end() const;
```
```
const_iterator cbegin() const;
```
```
const_iterator cend() const;
```
```
const_reverse_iterator rbegin() const;
```
```
const_reverse_iterator rend() const;
```
```
const_reverse_iterator crbegin() const;
```
```
const_reverse_iterator crend() const;
```

template<typename KeyRange> bool contains(KeyRange const & key) const;

Returns true if key is found in *this.

```
template<typename KeyRange> const_iterator find(KeyRange const & key) const;
```
Returns the iterator pointing to the key/value pair associated with key, if key is found in *this. Returns end() otherwise.
```
template<typename KeyRange> 
  const_iterator lower_bound(KeyRange const & key) const;
```
Returns the iterator pointing to the first key/value pair whose key is not less than key. Returns end() if no such key can be found.
```
template<typename KeyRange> 
  const_iterator upper_bound(KeyRange const & key) const;
```
Returns the iterator pointing to the first key/value pair whose key is not greater than key. Returns end() if no such key can be found.

template<typename KeyRange> 
  const_range equal_range(KeyRange const & key) const;

Returns the const_range(lower_bound(key), upper_bound(key)).

template<typename KeyIter, typename Sentinel> 
  match_result longest_subsequence(KeyIter first, Sentinel last) const;

Returns the longest subsequence of [first, last) found in *this, whether or not it is a match.

template<typename KeyRange> 
  match_result longest_subsequence(KeyRange const & key) const;

Returns the longest subsequence of key found in *this, whether or not it is a match.

template<typename KeyIter, typename Sentinel> 
  match_result longest_match(KeyIter first, Sentinel last) const;

Returns the longest matching subsequence of [first, last) found in *this.

template<typename KeyRange> 
  match_result longest_match(KeyRange const & key) const;

Returns the longest matching subsequence of key found in this.

template<typename KeyElementT> 
  match_result extend_subsequence(match_result prev, KeyElementT e) const;

Returns the result of extending prev by one element, e.

template<typename KeyIter, typename Sentinel> 
  match_result 
  extend_subsequence(match_result prev, KeyIter first, Sentinel last) const;

Returns the result of extending prev by the longest subsequence of [first, last) found in *this.

```
template<typename KeyElementT> 
  match_result extend_match(match_result prev, KeyElementT e) const;
```
Returns the result of extending prev by one element, e, if that would form a match, and prev otherwise. prev must be a match.
```
template<typename KeyIter, typename Sentinel> 
  match_result 
  extend_match(match_result prev, KeyIter first, Sentinel last) const;
```
Returns the result of extending prev by the longest subsequence of [first, last) found in *this, if that would form a match, and prev otherwise. prev must be a match.
```
template<typename OutIter> 
  OutIter copy_next_key_elements(match_result prev, OutIter out) const;
```
Writes the sequence of elements that would advance prev by one element to out, and returns the final value of out after the writes.

template<typename KeyRange> 
  optional_ref< mapped_type const > operator[](KeyRange const & key) const;

Returns an optional reference to the const value associated with key in *this (if any).

```
optional_ref< mapped_type const > operator[](match_result match) const;
```
Returns an optional reference to the const value associated with match in *this (if any).
```
iterator begin();
```
```
iterator end();
```
```
reverse_iterator rbegin();
```
```
reverse_iterator rend();
```
```
void clear();
```
```
template<typename KeyRange> iterator find(KeyRange const & key);
```
Returns the iterator pointing to the key/value pair associated with key, if key is found in *this. Returns end() otherwise.
```
template<typename KeyRange> iterator lower_bound(KeyRange const & key);
```
Returns the iterator pointing to the first key/value pair whose key is not less than key. Returns end() if no such key can be found.
```
template<typename KeyRange> iterator upper_bound(KeyRange const & key);
```
Returns the iterator pointing to the first key/value pair whose key is not greater than key. Returns end() if no such key can be found.

template<typename KeyRange> range equal_range(KeyRange const & key);

Returns the const_range(lower_bound(key), upper_bound(key)).

template<typename KeyRange> 
  optional_ref< mapped_type > operator[](KeyRange const & key);

Returns an optional reference to the value associated with key in *this (if any).

```
optional_ref< mapped_type > operator[](match_result match);
```
Returns an optional reference to the value associated with match in *this (if any).
```
template<typename KeyIter, typename Sentinel> 
  insert_result insert(KeyIter first, Sentinel last, Value value);
```
Inserts the key/value pair [first, last), value into *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
template<typename KeyRange> 
  insert_result insert(KeyRange const & key, Value value);
```
Inserts the key/value pair key, value into *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.

template<typename Char, std::size_t N> 
  insert_result insert(Char const (&) chars, Value value);

```
insert_result insert(value_type e);
```
Inserts the key/value pair e into *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
template<typename Iter, typename Sentinel> 
  void insert(Iter first, Sentinel last);
```
Inserts the sequence of key/value pairs [first, last) into this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
template<typename Range> insert_result insert(Range const & r);
```
Inserts the sequence of key/value pairs r into *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
void insert(std::initializer_list< value_type > il);
```
Inserts the sequence of key/value pairs il into this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
template<typename KeyIter, typename Sentinel> 
  insert_result insert_or_assign(KeyIter first, Sentinel last, Value value);
```
Inserts the key/value pair [first, last), value into *this, or assigns value over the existing value associated with [first, last), if this key is already found in *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
template<typename KeyRange> 
  insert_result insert_or_assign(KeyRange const & key, Value value);
```
Inserts the key/value pair key, value into *this, or assigns value over the existing value associated with key, if key is already found in *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.

template<typename Char, std::size_t N> 
  insert_result insert_or_assign(Char const (&) chars, Value value);

```
template<typename KeyRange> bool erase(KeyRange const & key);
```
Erases the key/value pair associated with key from this. Returns true if the key is found in *this, false otherwise.
```
iterator erase(iterator it);
```
Erases the key/value pair pointed to by it from *this. Returns an iterator to the next key/value pair in this.
```
iterator erase(iterator first, iterator last);
```
Erases the sequence of key/value pairs pointed to by [first, last) from *this. Returns an iterator to the next key/value pair in *this.
```
void swap(trie_map & other);
```