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

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. More...

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.

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.


Member Function Documentation

template<typename Key , typename Mapped , typename Node_And_It_Traits , typename _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.

template<typename Key , typename Mapped , typename Node_And_It_Traits , typename _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.

template<typename Key , typename Mapped , typename Node_And_It_Traits , typename _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.

template<typename Key , typename Mapped , typename Node_And_It_Traits , typename _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.


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