libstdc++
__gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > Class Template Reference
Inheritance diagram for __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc >:

List of all members.

Public Types

Public Member Functions

Public Attributes

Protected Member Functions


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 102 of file pat_trie_.hpp.


Member Enumeration Documentation

Three types of nodes.

Definition at line 54 of file pat_trie_base.hpp.


Member Function Documentation

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 101 of file pat_trie_.hpp.

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 107 of file pat_trie_.hpp.

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 113 of file pat_trie_.hpp.

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 119 of file pat_trie_.hpp.


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