---
name: "__gnu_pbds::detail::rb_tree_map"
section: "3cxx"
platform: "linux"
package: "libstdc++-12-doc"
version: "12.4.0-5"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/__gnu_pbds::detail::rb_tree_map/3cxx"
---

# \_\_gnu\_pbds::detail::rb\_tree\_map(3cxx)

Red-Black tree.

## NAME

\_\_gnu\_pbds::detail::rb\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \> - Red-Black tree.

## SYNOPSIS

`#include <rb_tree_.hpp>`

Inherits \_\_gnu\_pbds::detail::bin\_search\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \>.

### Public Types

typedef \_Alloc **allocator\_type**\
 typedef Cmp\_Fn **cmp\_fn**\
 typedef **std::pair**\< size\_type, size\_type \> **comp\_hash**\
 typedef base\_type::const\_iterator **const\_iterator**\
 typedef base\_type::const\_pointer **const\_pointer**\
 typedef base\_type::const\_reference **const\_reference**\
 typedef base\_type::const\_reverse\_iterator **const\_reverse\_iterator**\
 typedef **rb\_tree\_tag** **container\_category**\
 typedef \_Alloc::difference\_type **difference\_type**\
 typedef base\_type::iterator **iterator**\
 typedef base\_type::key\_const\_pointer **key\_const\_pointer**\
 typedef base\_type::key\_const\_reference **key\_const\_reference**\
 typedef base\_type::key\_pointer **key\_pointer**\
 typedef base\_type::key\_reference **key\_reference**\
 typedef base\_type::key\_type **key\_type**\
 typedef base\_type::mapped\_const\_pointer **mapped\_const\_pointer**\
 typedef base\_type::mapped\_const\_reference **mapped\_const\_reference**\
 typedef base\_type::mapped\_pointer **mapped\_pointer**\
 typedef base\_type::mapped\_reference **mapped\_reference**\
 typedef base\_type::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**\
 typedef base\_type::node\_update **node\_update**\
 typedef base\_type::const\_iterator **point\_const\_iterator**\
 typedef base\_type::point\_iterator **point\_iterator**\
 typedef base\_type::pointer **pointer**\
 typedef base\_type::reference **reference**\
 typedef base\_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 **base\_type::value\_type** **value\_type**\

### Public Member Functions

**rb\_tree\_map** (const Cmp\_Fn &)\
 **rb\_tree\_map** (const Cmp\_Fn &, const node\_update &)\
 **rb\_tree\_map** (const **direct\_mask\_range\_hashing**\< Size\_Type \> &)\
 iterator **begin** ()\
 const\_iterator **begin** () const\
 void **clear** ()\
 template\<typename It \> void **copy\_from\_range** (It, It)\
 bool **empty** () const\
 iterator **end** ()\
 const\_iterator **end** () const\
 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\
 Cmp\_Fn & **get\_cmp\_fn** ()\
 const Cmp\_Fn & **get\_cmp\_fn** () const\
 **std::pair**\< point\_iterator, bool \> **insert** (const\_reference)\
 void **join** (**direct\_mask\_range\_hashing**\< Size\_Type \> &)\
 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, **direct\_mask\_range\_hashing**\< Size\_Type \> &)\
 void **swap** (**direct\_mask\_range\_hashing**\< Size\_Type \> &)\
 void **swap** (**tree\_order\_statistics\_node\_update**\< Node\_CItr, Node\_Itr, Cmp\_Fn, \_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 Types

typedef node\_alloc\_traits::value\_type **node**\
 typedef node\_alloc\_traits::allocator\_type **node\_allocator**\
 typedef traits\_type::null\_node\_update\_pointer **null\_node\_update\_pointer**\
 typedef **types\_traits**\< Key, Mapped, \_Alloc, false \> **traits\_base**\

### Protected Member Functions

void **actual\_erase\_node** (node\_pointer)\
 template\<typename Node\_Update\_ \> void **apply\_update** (node\_pointer, Node\_Update\_ \*)\
 void **apply\_update** (node\_pointer, null\_node\_update\_pointer)\
 **std::pair**\< node\_pointer, bool \> **erase** (node\_pointer)\
 node\_pointer **get\_new\_node\_for\_leaf\_insert** (const\_reference, false\_type)\
 node\_pointer **get\_new\_node\_for\_leaf\_insert** (const\_reference, true\_type)\
 void **initialize\_min\_max** ()\
 iterator **insert\_imp\_empty** (const\_reference)\
 **std::pair**\< point\_iterator, bool \> **insert\_leaf** (const\_reference)\
 iterator **insert\_leaf\_new** (const\_reference, node\_pointer, bool)\
 void **join\_finish** (**tree\_order\_statistics\_node\_update**\< Node\_CItr, Node\_Itr, Cmp\_Fn, \_Alloc \> &)\
 bool **join\_prep** (**tree\_order\_statistics\_node\_update**\< Node\_CItr, Node\_Itr, Cmp\_Fn, \_Alloc \> &)\
 size\_type **recursive\_count** (node\_pointer) const\
 void **rotate\_left** (node\_pointer)\
 void **rotate\_parent** (node\_pointer)\
 void **rotate\_right** (node\_pointer)\
 void **split\_finish** (**tree\_order\_statistics\_node\_update**\< Node\_CItr, Node\_Itr, Cmp\_Fn, \_Alloc \> &)\
 bool **split\_prep** (key\_const\_reference, **tree\_order\_statistics\_node\_update**\< Node\_CItr, Node\_Itr, Cmp\_Fn, \_Alloc \> &)\
 void **update\_min\_max\_for\_erased\_node** (node\_pointer)\
 template\<typename Node\_Update\_ \> void **update\_to\_top** (node\_pointer, Node\_Update\_ \*)\
 void **update\_to\_top** (node\_pointer, null\_node\_update\_pointer)\
 void **value\_swap** (**tree\_order\_statistics\_node\_update**\< Node\_CItr, Node\_Itr, Cmp\_Fn, \_Alloc \> &)\

### Static Protected Member Functions

static void **clear\_imp** (node\_pointer)\

### Protected Attributes

node\_pointer **m\_p\_head**\
 size\_type **m\_size**\

### Static Protected Attributes

static node\_allocator **s\_node\_allocator**\

## Detailed Description

### template\<typename Key, typename Mapped, typename Cmp\_Fn, typename Node\_And\_It\_Traits, typename \_Alloc\>

class \_\_gnu\_pbds::detail::rb\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \>"Red-Black tree.

This implementation uses an idea from the SGI STL (using a *header* node which is needed for efficient iteration).

## Member Function Documentation

### template\<typename Key , typename Mapped , typename Cmp\_Fn , typename Node\_And\_It\_Traits , typename \_Alloc \> node\_iterator \_\_gnu\_pbds::detail::bin\_search\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \>::node\_begin ()` [inline]`, ` [inherited]`

Returns a node\_iterator corresponding to the node at the root of the tree.

### template\<typename Key , typename Mapped , typename Cmp\_Fn , typename Node\_And\_It\_Traits , typename \_Alloc \> node\_const\_iterator \_\_gnu\_pbds::detail::bin\_search\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \>::node\_begin () const` [inline]`, ` [inherited]`

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

### template\<typename Key , typename Mapped , typename Cmp\_Fn , typename Node\_And\_It\_Traits , typename \_Alloc \> node\_iterator \_\_gnu\_pbds::detail::bin\_search\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \>::node\_end ()` [inline]`, ` [inherited]`

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

### template\<typename Key , typename Mapped , typename Cmp\_Fn , typename Node\_And\_It\_Traits , typename \_Alloc \> node\_const\_iterator \_\_gnu\_pbds::detail::bin\_search\_tree\_map\< Key, Mapped, Cmp\_Fn, Node\_And\_It\_Traits, \_Alloc \>::node\_end () const` [inline]`, ` [inherited]`

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.