Struct template trie

Struct template trie_set

boost::text::trie_set

Synopsis

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

template<typename Key, typename Compare> 
struct trie_set {
  // types
  typedef Key                                         key_type;              
  typedef Key                                         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_set_iterator< key_type >               iterator;              
  typedef const_trie_set_iterator< key_type >         const_iterator;        
  typedef reverse_trie_set_iterator< key_type >       reverse_iterator;      
  typedef const_reverse_trie_set_iterator< key_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_set();
  trie_set(Compare const &);
  template<typename Iter, typename Sentinel> 
    trie_set(Iter, Sentinel, Compare const & = Compare());
  template<typename Range> 
    explicit trie_set(Range, Compare const & = Compare());
  trie_set(std::initializer_list< value_type >);
  trie_set & 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;
  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 KeyIter, typename Sentinel> auto insert(KeyIter, Sentinel);
  template<typename KeyRange> insert_result insert(KeyRange const &);
  insert_result insert(Key const &);
  template<typename Iter, typename Sentinel> auto insert(Iter, Sentinel);
  void insert(std::initializer_list< value_type >);
  template<typename KeyRange> bool erase(KeyRange const &);
  iterator erase(iterator);
  iterator erase(iterator, iterator);
  void swap(trie_set &);
};

Description

An associative container similar to std::set, built upon a trie, or prefix-tree. A trie_set contains a set of keys. Each node in the trie_set represents some prefix found in at least one member of the set of values contained in the trie_set. If a certain node represents the end of one of the keys, it represents that key in the trie_set. 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_set.

`trie_set` public construct/copy/destruct

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

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

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

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

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

`trie_set` 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, 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 that 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 that is 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.
```
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, 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 that 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 that is 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 KeyIter, typename Sentinel> 
  auto insert(KeyIter first, Sentinel last);
```
Inserts the key [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 KeyRange> insert_result insert(KeyRange const & key);
```
Inserts the key key into *this. The inserted field of the result will be true if the operation resulted in a new insertion, or false otherwise.
```
insert_result insert(Key const & key);
```
Inserts the ke key 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> 
  auto insert(Iter first, Sentinel last);
```
Inserts the the sequence of keys [first, last) 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 the sequence of keys 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 KeyRange> bool erase(KeyRange const & key);
```
Erases key from *this. Returns true if the key is found in this, false otherwise.
```
iterator erase(iterator it);
```
Erases the key pointed to by it from *this. Returns an iterator to the next key in *this.
```
iterator erase(iterator first, iterator last);
```
Erases the sequence of keys pointed to by [first, last) from this. Returns an iterator to the next key in *this.
```
void swap(trie_set & other);
```