---
name: "__gnu_pbds::detail::pat_trie_map"
section: "3"
platform: "linux"
package: "gcc"
version: "16.2.1+r23+gd564253eb6c8-1"
release: "Arch Linux 2026-11-01"
platforms: ["linux"]
url: "https://new.carta.tech/__gnu_pbds::detail::pat_trie_map"
---

# \_\_gnu\_pbds::detail::pat\_trie\_map(3)

PATRICIA trie.

## NAME

\_\_gnu\_pbds::detail::pat\_trie\_map\< Key, Mapped, Node\_And\_It\_Traits, \_Alloc \> - PATRICIA trie.

## SYNOPSIS

\#include \<pat\_trie\_.hpp\>

Inherits , and .

### 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** }\
 Three types of nodes.  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** ()\
 Returns a node\_iterator corresponding to the node at the root of the tree.  node\_const\_iterator **node\_begin** () const\
 Returns a const node\_iterator corresponding to the node at the root of the tree.  node\_iterator **node\_end** ()\
 Returns a node\_iterator corresponding to a node just after a leaf of the tree.  node\_const\_iterator **node\_end** () const\
 Returns a const node\_iterator corresponding to a node just after a leaf of the tree.  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.

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

## Member Enumeration Documentation

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

## 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\_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\> 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.

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

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

## Author

Generated automatically by Doxygen for libstdc++ from the source code.