__GNU_PBDS::DETAIL::PAT_TRIE_MAP(3)

✨ NAME ✨

okay bestie, say hi to __gnu_pbds::detail::pat_trie_map< Key, Mapped, Node_And_It_Traits, _Alloc > — it's a PATRICIA trie. that's it, that's the name, she's a whole data structure 💅

this one lives in the Library Functions Manual (libstdc++ girlies, this is your section 3 moment).

---

🌸 SYNOPSIS 🌸

#include <pat_trie_.hpp>

she inherits , and . — no literally, that's all the source says, the blanks are blank, don't come for me 🙈

---

🎀 Public Types 🎀

• access_traits — traits_type::access_traits
• allocator_type — _Alloc
• comp_hash — std::pair< size_type, size_type >
• const_iterator — point_const_iterator
• const_pointer — traits_base::const_pointer
• const_reference — traits_base::const_reference
• const_reverse_iterator — traits_type::const_reverse_iterator
• container_category — pat_trie_tag
• difference_type — _Alloc::difference_type
• iterator — point_iterator
• key_const_pointer — traits_base::key_const_pointer
• key_const_reference — traits_base::key_const_reference
• key_pointer — traits_base::key_pointer
• key_reference — traits_base::key_reference
• key_type — traits_base::key_type
• mapped_const_pointer — traits_base::mapped_const_pointer
• mapped_const_reference — traits_base::mapped_const_reference
• mapped_pointer — traits_base::mapped_pointer
• mapped_reference — traits_base::mapped_reference
• mapped_type — traits_base::mapped_type
• no_throw_indicator — __nothrowcopy::indicator
• node_const_iterator — traits_type::node_const_iterator
• node_iterator — traits_type::node_iterator
• node_type — enum, and the values are i_node, leaf_node, head_node. three types of nodes, that's the whole vibe check
• node_update — traits_type::node_update
• point_const_iterator — traits_type::const_iterator
• point_iterator — traits_type::iterator
• pointer — traits_base::pointer
• reference — traits_base::reference
• reverse_iterator — traits_type::reverse_iterator
• size_type — _Alloc::size_type
• store_extra — integral_constant< int, Store_Hash >
• stored_data_type — stored_data< value_type, size_type, Store_Hash >
• value_type — traits_base::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 () — hands you a node_iterator pointing at the node at the root of the tree 🌱
• node_const_iterator node_begin () const — same energy but const: a const node_iterator for the root node
• node_iterator node_end () — a node_iterator for a node just after a leaf of the tree 🍃
• node_const_iterator node_end () const — the const version: a const node_iterator just after a leaf
• 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
• 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. she's iconic, she's a trie, she said what she said ✨

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

note the word loosely, bestie. that's the source's own word, not mine, and I'm not adding lore where there isn't any 💅

---

🎀 Member Enumeration Documentation 🎀

enum __gnu_pbds::detail::pat_trie_base::node_type [inherited]

three types of nodes, periodt. i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head. that's the whole taxonomy, slay 👑

---

⭐ Member Function Documentation ⭐

node_begin () [inline]

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 ()

returns a node_iterator corresponding to the node at the root of the tree. the root. the main character. the head node energy. 🌳

node_begin () const [inline]

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

returns a const node_iterator corresponding to the node at the root of the tree. same root, but she's const now, respect her boundaries 🫶

node_end () [inline]

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 ()

returns a node_iterator corresponding to a node just after a leaf of the tree. like, one past the leaf. off the edge. end-of-range coded 🍂

node_end () const [inline]

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

returns a const node_iterator corresponding to a node just after a leaf of the tree. const version, same spot just past the leaf, no cap 💜

---

👑 Author 👑

generated automatically by Doxygen for libstdc++ from the source code. not a human author, just a robot doing her best 🧚

---

okay that's the whole page!! and for the little sign-off at the bottom: this beauty is a libstdc++ situation, and the footer is just the manual name — __gnu_pbds...s, _Alloc >(3) — printed next to it. no date in sight, so don't ask me for one, I'm not inventing dates bestie 😭💖

she ate, honestly. bye!! 🌸✨