Struct template trie

boost::text::trie

Synopsis

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

template<typename Key, typename Value, typename Compare, std::size_t KeySize> 
struct trie {
  // types
  typedef Key                      key_type;        
  typedef 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 std::ptrdiff_t           size_type;       
  typedef std::ptrdiff_t           difference_type; 
  typedef trie_match_result        match_result;    

  // construct/copy/destruct
  trie();
  trie(Compare const &);
  template<typename Iter, typename Sentinel> 
    trie(Iter, Sentinel, Compare const & = Compare());
  template<typename Range> explicit trie(Range, Compare const & = Compare());
  trie(std::initializer_list< trie_element< key_type, value_type > >);
  trie & operator=(std::initializer_list< trie_element< key_type, value_type > >);

  // public member functions
  bool empty() const;
  size_type size() const;
  template<typename KeyRange> bool contains(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< value_type const > operator[](KeyRange const &) const;
  optional_ref< value_type const > operator[](match_result) const;
  void clear();
  template<typename KeyRange> 
    optional_ref< value_type > operator[](KeyRange const &);
  optional_ref< value_type > operator[](match_result);
  template<typename KeyIter, typename Sentinel> 
    bool insert(KeyIter, Sentinel, Value);
  template<typename KeyRange> bool insert(KeyRange const &, Value);
  template<typename Char, std::size_t N> bool insert(Char const (&), Value);
  template<typename Iter, typename Sentinel> void insert(Iter, Sentinel);
  bool insert(trie_element< key_type, value_type > const &);
  template<typename Range> bool insert(Range const &);
  void insert(std::initializer_list< trie_element< key_type, value_type > >);
  template<typename KeyIter, typename Sentinel> 
    void insert_or_assign(KeyIter, Sentinel, Value);
  template<typename KeyRange> void insert_or_assign(KeyRange const &, Value);
  template<typename KeyRange> bool erase(KeyRange const &);
  bool erase(match_result);
  void swap(trie &);
};

Description

A trie, or prefix-tree. A trie 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 represents some prefix found in at least one member of the set of values contained in the trie. 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.

	Note
	trie is not a C++ Container, according to the definition in the C++ standard, in part because it does not have any iterators. This allows trie to do slightly less work when it does insertions and erasures. If you need iterators, use trie_map or trie_set.

`trie` public construct/copy/destruct

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

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

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

trie(std::initializer_list< trie_element< key_type, value_type > > il);

trie & operator=(std::initializer_list< trie_element< key_type, value_type > > il);

`trie` public member functions

```
bool empty() const;
```
```
size_type size() const;
```

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

Returns true if key is found in *this.

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< value_type const > operator[](KeyRange const & key) const;

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

```
optional_ref< value_type const > operator[](match_result match) const;
```
Returns an optional reference to the const value associated with match in *this (if any).
```
void clear();
```

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

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

```
optional_ref< value_type > operator[](match_result match);
```
Returns an optional reference to the value associated with match in *this (if any).
```
template<typename KeyIter, typename Sentinel> 
  bool insert(KeyIter first, Sentinel last, Value value);
```
Inserts the key/value pair [first, last), value into *this. Returns false if the key already exists in *this, true otherwise.
```
template<typename KeyRange> bool insert(KeyRange const & key, Value value);
```
Inserts the key/value pair key, value into *this. Returns false if the key already exists in *this, true otherwise.

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

template<typename Iter, typename Sentinel> 
  void insert(Iter first, Sentinel last);

Inserts the sequence of key/value pairs [first, last) into this.

bool insert(trie_element< key_type, value_type > const & e);

Inserts the element e.key, e.value into *this.

template<typename Range> bool insert(Range const & r);

Inserts the sequence of key/value pairs r into this.

void insert(std::initializer_list< trie_element< key_type, value_type > > il);

Inserts the sequence of key/value pairs il into *this.

```
template<typename KeyIter, typename Sentinel> 
  void 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> 
  void 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 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.
```
bool erase(match_result match);
```
Erases the key/value pair associated with match from *this. Returns true if the key is found in *this, false otherwise.
```
void swap(trie & other);
```