libstdc++
Public Types | Public Member Functions | Public Attributes | Protected Member Functions | List of all members
__gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > Class Template Reference
Extensions » Policy-Based Data Structures » Containers » Branch-Based » Base and Policy Classes

#include <pat_trie_.hpp>

Inheritance diagram for __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >:
[legend]

Public Types

typedef traits_type::access_traits access_traits
 
typedef _Alloc allocator_type
 
typedef std::pair< size_type, size_type > comp_hash
 
typedef point_const_iterator const_iterator
 
typedef traits_base::const_pointer const_pointer
 
typedef traits_base::const_reference const_reference
 
typedef traits_type::const_reverse_iterator const_reverse_iterator
 
typedef pat_trie_tag container_category
 
typedef _Alloc::difference_type difference_type
 
typedef point_iterator iterator
 
typedef traits_base::key_const_pointer key_const_pointer
 
typedef traits_base::key_const_reference key_const_reference
 
typedef traits_base::key_pointer key_pointer
 
typedef traits_base::key_reference key_reference
 
typedef traits_base::key_type key_type
 
typedef traits_base::mapped_const_pointer mapped_const_pointer
 
typedef traits_base::mapped_const_reference mapped_const_reference
 
typedef traits_base::mapped_pointer mapped_pointer
 
typedef traits_base::mapped_reference mapped_reference
 
typedef traits_base::mapped_type mapped_type
 
typedef __nothrowcopy::indicator no_throw_indicator
 
typedef traits_type::node_const_iterator node_const_iterator
 
typedef traits_type::node_iterator node_iterator
 
enum  node_type { i_node , leaf_node , head_node }
 
typedef traits_type::node_update node_update
 
typedef traits_type::const_iterator point_const_iterator
 
typedef traits_type::iterator point_iterator
 
typedef traits_base::pointer pointer
 
typedef traits_base::reference reference
 
typedef traits_type::reverse_iterator reverse_iterator
 
typedef _Alloc::size_type size_type
 
typedef integral_constant< int, Store_Hash > store_extra
 
typedef stored_data< value_type, size_type, Store_Hash > stored_data_type
 
typedef traits_base::value_type value_type
 

Public Member Functions

 pat_trie_map (const access_traits &)
 
 pat_trie_map (const pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > &)
 
iterator begin ()
 
const_iterator begin () const
 
void clear ()
 
bool empty () const
 
iterator end ()
 
const_iterator end () const
 
const_iterator erase (const_iterator)
 
const_reverse_iterator erase (const_reverse_iterator)
 
iterator erase (iterator)
 
bool erase (key_const_reference)
 
reverse_iterator erase (reverse_iterator)
 
template<typename Pred>
size_type erase_if (Pred)
 
point_iterator find (key_const_reference)
 
point_const_iterator find (key_const_reference) const
 
access_traits & get_access_traits ()
 
const access_traits & get_access_traits () const
 
node_update & get_node_update ()
 
const node_update & get_node_update () const
 
std::pair< point_iterator, bool > insert (const_reference)
 
void join (pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > &)
 
point_iterator lower_bound (key_const_reference)
 
point_const_iterator lower_bound (key_const_reference) const
 
size_type max_size () const
 
node_iterator node_begin ()
 
node_const_iterator node_begin () const
 
node_iterator node_end ()
 
node_const_iterator node_end () const
 
mapped_reference operator[] (key_const_reference r_key)
 
reverse_iterator rbegin ()
 
const_reverse_iterator rbegin () const
 
reverse_iterator rend ()
 
const_reverse_iterator rend () const
 
size_type size () const
 
void split (key_const_reference, pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > &)
 
void swap (pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > &)
 
point_iterator upper_bound (key_const_reference)
 
point_const_iterator upper_bound (key_const_reference) const
 

Public Attributes

no_throw_indicator m_no_throw_copies_indicator
 
no_throw_indicator m_no_throw_copies_indicator
 
store_extra m_store_extra_indicator
 
store_extra m_store_extra_indicator
 

Protected Member Functions

template<typename It>
void copy_from_range (It, It)
 
node_pointer recursive_copy_node (node_const_pointer)
 
void value_swap (pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > &)
 

Detailed Description

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
class __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >

PATRICIA trie.

This implementation loosely borrows ideas from: 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 2) Ptset: Sets of integers implemented as Patricia trees, Jean-Christophe Filliatr, 2000

Definition at line 101 of file pat_trie_.hpp.

Member Typedef Documentation

◆ access_traits

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::access_traits __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::access_traits

Definition at line 259 of file pat_trie_.hpp.

◆ allocator_type

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef _Alloc __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::allocator_type

Definition at line 239 of file pat_trie_.hpp.

◆ comp_hash

typedef std::pair<size_type, size_type> __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::comp_hash
inherited

Definition at line 187 of file types_traits.hpp.

◆ const_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef point_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_iterator

Definition at line 262 of file pat_trie_.hpp.

◆ const_pointer

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::const_pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_pointer

Definition at line 255 of file pat_trie_.hpp.

◆ const_reference

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::const_reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_reference

Definition at line 257 of file pat_trie_.hpp.

◆ const_reverse_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::const_reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_reverse_iterator

Definition at line 266 of file pat_trie_.hpp.

◆ container_category

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef pat_trie_tag __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::container_category

Definition at line 238 of file pat_trie_.hpp.

◆ difference_type

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef _Alloc::difference_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::difference_type

Definition at line 241 of file pat_trie_.hpp.

◆ iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef point_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::iterator

Definition at line 263 of file pat_trie_.hpp.

◆ key_const_pointer

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::key_const_pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::key_const_pointer

Definition at line 245 of file pat_trie_.hpp.

◆ key_const_reference

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::key_const_reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::key_const_reference

Definition at line 247 of file pat_trie_.hpp.

◆ key_pointer

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::key_pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::key_pointer

Definition at line 244 of file pat_trie_.hpp.

◆ key_reference

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::key_reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::key_reference

Definition at line 246 of file pat_trie_.hpp.

◆ key_type

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::key_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::key_type

Definition at line 243 of file pat_trie_.hpp.

◆ mapped_const_pointer

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::mapped_const_pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::mapped_const_pointer

Definition at line 250 of file pat_trie_.hpp.

◆ mapped_const_reference

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::mapped_const_reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::mapped_const_reference

Definition at line 252 of file pat_trie_.hpp.

◆ mapped_pointer

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::mapped_pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::mapped_pointer

Definition at line 249 of file pat_trie_.hpp.

◆ mapped_reference

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::mapped_reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::mapped_reference

Definition at line 251 of file pat_trie_.hpp.

◆ mapped_type

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::mapped_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::mapped_type

Definition at line 248 of file pat_trie_.hpp.

◆ no_throw_indicator

typedef __nothrowcopy::indicator __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::no_throw_indicator
inherited

Definition at line 189 of file types_traits.hpp.

◆ node_const_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::node_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_const_iterator

Definition at line 267 of file pat_trie_.hpp.

◆ node_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::node_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_iterator

Definition at line 268 of file pat_trie_.hpp.

◆ node_update

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::node_update __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_update

Definition at line 269 of file pat_trie_.hpp.

◆ point_const_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_const_iterator

Definition at line 260 of file pat_trie_.hpp.

◆ point_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_iterator

Definition at line 261 of file pat_trie_.hpp.

◆ pointer

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::pointer

Definition at line 254 of file pat_trie_.hpp.

◆ reference

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::reference

Definition at line 256 of file pat_trie_.hpp.

◆ reverse_iterator

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_type::reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::reverse_iterator

Definition at line 265 of file pat_trie_.hpp.

◆ size_type

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef _Alloc::size_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::size_type

Definition at line 240 of file pat_trie_.hpp.

◆ store_extra

typedef integral_constant<int, Store_Hash> __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::store_extra
inherited

Definition at line 188 of file types_traits.hpp.

◆ stored_data_type

typedef stored_data<value_type, size_type, Store_Hash> __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::stored_data_type
inherited

Definition at line 181 of file types_traits.hpp.

◆ value_type

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
typedef traits_base::value_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::value_type

Definition at line 253 of file pat_trie_.hpp.

Member Enumeration Documentation

◆ node_type

enum __gnu_pbds::detail::pat_trie_base::node_type
inherited

Three types of nodes.

i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head.

Definition at line 58 of file pat_trie_base.hpp.

Constructor & Destructor Documentation

◆ pat_trie_map() [1/3]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
__gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::pat_trie_map ( )

Definition at line 57 of file pat_trie_.hpp.

◆ pat_trie_map() [2/3]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
__gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::pat_trie_map ( const access_traits & r_access_traits)

Definition at line 67 of file pat_trie_.hpp.

◆ pat_trie_map() [3/3]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
__gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::pat_trie_map ( const pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > & other)

Definition at line 78 of file pat_trie_.hpp.

◆ ~pat_trie_map()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
__gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::~pat_trie_map ( )

Definition at line 136 of file pat_trie_.hpp.

Member Function Documentation

◆ begin() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::begin ( )
inline

Definition at line 46 of file pat_trie_.hpp.

◆ begin() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::begin ( ) const
inline

Definition at line 52 of file pat_trie_.hpp.

◆ clear()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
void __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::clear ( )

Definition at line 130 of file pat_trie_.hpp.

◆ copy_from_range()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
template<typename It>
void __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::copy_from_range ( It first_it,
It last_it )
protected

Definition at line 158 of file pat_trie_.hpp.

◆ empty()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
bool __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::empty ( ) const
inlinenodiscard

Definition at line 47 of file pat_trie_.hpp.

◆ end() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::end ( )
inline

Definition at line 58 of file pat_trie_.hpp.

◆ end() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::end ( ) const
inline

Definition at line 64 of file pat_trie_.hpp.

◆ erase() [1/5]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::erase ( const_iterator it)
inline

Definition at line 170 of file pat_trie_.hpp.

◆ erase() [2/5]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::erase ( const_reverse_iterator it)
inline

Definition at line 207 of file pat_trie_.hpp.

◆ erase() [3/5]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::erase ( iterator it)
inline

Definition at line 189 of file pat_trie_.hpp.

◆ erase() [4/5]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
bool __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::erase ( key_const_reference r_key)
inline

Definition at line 46 of file pat_trie_.hpp.

◆ erase() [5/5]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::erase ( reverse_iterator it)
inline

Definition at line 226 of file pat_trie_.hpp.

◆ erase_if()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
template<typename Pred>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::size_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::erase_if ( Pred pred)
inline

Definition at line 246 of file pat_trie_.hpp.

◆ find() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::find ( key_const_reference r_key)
inline

Definition at line 46 of file pat_trie_.hpp.

◆ find() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::find ( key_const_reference r_key) const
inline

Definition at line 70 of file pat_trie_.hpp.

◆ get_access_traits() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::access_traits & __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::get_access_traits ( )

Definition at line 46 of file pat_trie_.hpp.

◆ get_access_traits() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
const pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::access_traits & __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::get_access_traits ( ) const

Definition at line 52 of file pat_trie_.hpp.

◆ get_node_update() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_update & __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::get_node_update ( )

Definition at line 58 of file pat_trie_.hpp.

◆ get_node_update() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
const pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_update & __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::get_node_update ( ) const

Definition at line 64 of file pat_trie_.hpp.

◆ insert()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
std::pair< typename pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::iterator, bool > __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::insert ( const_reference r_val)
inline

Definition at line 384 of file pat_trie_.hpp.

◆ join()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
void __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::join ( pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > & other)

Definition at line 46 of file pat_trie_.hpp.

◆ lower_bound() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::lower_bound ( key_const_reference r_key)
inline

Definition at line 162 of file pat_trie_.hpp.

◆ lower_bound() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::lower_bound ( key_const_reference r_key) const
inline

Definition at line 168 of file pat_trie_.hpp.

◆ max_size()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::size_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::max_size ( ) const
inline

Definition at line 59 of file pat_trie_.hpp.

◆ node_begin() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_begin ( )
inline

Returns a node_iterator corresponding to the node at the root of the tree.

Definition at line 108 of file pat_trie_.hpp.

◆ node_begin() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_begin ( ) const
inline

Returns a const node_iterator corresponding to the node at the root of the tree.

Definition at line 102 of file pat_trie_.hpp.

◆ node_end() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_end ( )
inline

Returns a node_iterator corresponding to a node just after a leaf of the tree.

Definition at line 120 of file pat_trie_.hpp.

◆ node_end() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_end ( ) const
inline

Returns a const node_iterator corresponding to a node just after a leaf of the tree.

Definition at line 114 of file pat_trie_.hpp.

◆ operator[]()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
mapped_reference __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::operator[] ( key_const_reference r_key)
inline

Definition at line 307 of file pat_trie_.hpp.

◆ rbegin() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::rbegin ( )
inline

Definition at line 80 of file pat_trie_.hpp.

◆ rbegin() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::rbegin ( ) const
inline

Definition at line 70 of file pat_trie_.hpp.

◆ recursive_copy_node()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::node_pointer __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::recursive_copy_node ( node_const_pointer p_ncp)
protected

Definition at line 167 of file pat_trie_.hpp.

◆ rend() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::rend ( )
inline

Definition at line 90 of file pat_trie_.hpp.

◆ rend() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::const_reverse_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::rend ( ) const
inline

Definition at line 96 of file pat_trie_.hpp.

◆ size()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::size_type __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::size ( ) const
inline

Definition at line 53 of file pat_trie_.hpp.

◆ split()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
void __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::split ( key_const_reference r_key,
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > & other )

Definition at line 46 of file pat_trie_.hpp.

◆ swap()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
void __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::swap ( pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > & other)

Definition at line 114 of file pat_trie_.hpp.

◆ upper_bound() [1/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::upper_bound ( key_const_reference r_key)
inline

Definition at line 176 of file pat_trie_.hpp.

◆ upper_bound() [2/2]

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::point_const_iterator __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::upper_bound ( key_const_reference r_key) const
inline

Definition at line 194 of file pat_trie_.hpp.

◆ value_swap()

template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc>
void __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >::value_swap ( pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > & other)
protected

Definition at line 127 of file pat_trie_.hpp.

Member Data Documentation

◆ m_no_throw_copies_indicator [1/2]

no_throw_indicator __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::m_no_throw_copies_indicator
inherited

Definition at line 192 of file types_traits.hpp.

◆ m_no_throw_copies_indicator [2/2]

no_throw_indicator __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::m_no_throw_copies_indicator
inherited

Definition at line 192 of file types_traits.hpp.

◆ m_store_extra_indicator [1/2]

store_extra __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::m_store_extra_indicator
inherited

Definition at line 191 of file types_traits.hpp.

◆ m_store_extra_indicator [2/2]

store_extra __gnu_pbds::detail::types_traits< Key, Mapped, _Alloc, Store_Hash >::m_store_extra_indicator
inherited

Definition at line 191 of file types_traits.hpp.

The documentation for this class was generated from the following file: