---
name: "__gnu_cxx::rb_tree"
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_cxx::rb_tree"
---

# \_\_gnu\_cxx::rb\_tree(3)

## NAME

\_\_gnu\_cxx::rb\_tree\< \_Key, \_Value, \_KeyOfValue, \_Compare, \_Alloc \>

## SYNOPSIS

\#include \<rb\_tree\>

### Public Types

template\<typename \_Iter\> using **\_\_same\_value\_type**\
 typedef std::\_Rb\_tree\< \_Key, \_Value, \_KeyOfValue, \_Compare, \_Alloc \> **\_Base**\
 typedef \_Base::allocator\_type **allocator\_type**\
 typedef \_Node\_traits::\_Const\_iterator **const\_iterator**\
 typedef const value\_type \* **const\_pointer**\
 typedef const value\_type & **const\_reference**\
 typedef **std::reverse\_iterator**\< const\_iterator \> **const\_reverse\_iterator**\
 typedef ptrdiff\_t **difference\_type**\
 typedef \_Node\_traits::\_Iterator **iterator**\
 typedef \_Key **key\_type**\
 typedef value\_type \* **pointer**\
 typedef value\_type & **reference**\
 typedef **std::reverse\_iterator**\< iterator \> **reverse\_iterator**\
 typedef size\_t **size\_type**\
 typedef \_Val **value\_type**\

### Public Member Functions

**rb\_tree** (const \_Compare &\_\_comp=\_Compare(), const allocator\_type &\_\_a=allocator\_type())\
 bool **\_\_rb\_verify** () const\
 template\<typename \_Iterator\> void **\_M\_assign\_equal** (\_Iterator, \_Iterator)\
 template\<typename \_Iterator\> void **\_M\_assign\_unique** (\_Iterator, \_Iterator)\
 template\<typename... \_Args\> iterator **\_M\_emplace\_equal** (\_Args &&... \_\_args)\
 template\<typename... \_Args\> iterator **\_M\_emplace\_here** (bool \_\_place\_left, \_Base\_ptr \_\_node, \_Args &&... \_\_args)\
 template\<typename... \_Args\> iterator **\_M\_emplace\_hint\_equal** (const\_iterator \_\_pos, \_Args &&... \_\_args)\
 template\<typename... \_Args\> iterator **\_M\_emplace\_hint\_unique** (const\_iterator \_\_pos, \_Args &&... \_\_args)\
 template\<typename... \_Args\> **pair**\< iterator, bool \> **\_M\_emplace\_unique** (\_Args &&... \_\_args)\
 template\<typename \_Kt\> size\_type **\_M\_erase\_tr** (const \_Kt &\_\_x)\
 size\_type **\_M\_erase\_unique** (const key\_type &\_\_x)\
 **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_equal\_pos** (const key\_type &\_\_k)\
 **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_hint\_equal\_pos** (const\_iterator \_\_pos, const key\_type &\_\_k)\
 **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_hint\_unique\_pos** (const\_iterator \_\_pos, const key\_type &\_\_k)\
 template\<typename \_Kt\> **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_hint\_unique\_pos\_tr** (const\_iterator, const \_Kt &\_\_k)\
 **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_unique\_pos** (const key\_type &\_\_k)\
 template\<typename \_Kt\> **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_unique\_pos\_tr** (const \_Kt &\_\_k)\
 const \_Node\_allocator & **\_M\_get\_Node\_allocator** () const noexcept\
 \_Node\_allocator & **\_M\_get\_Node\_allocator** () noexcept\
 template\<typename \_Arg\> iterator **\_M\_insert\_equal** (\_Arg &&\_\_x)\
 template\<typename \_Arg\> iterator **\_M\_insert\_equal\_** (const\_iterator \_\_pos, \_Arg &&\_\_x)\
 template\<typename \_Arg, typename \_NodeGen\> iterator **\_M\_insert\_equal\_** (const\_iterator \_\_pos, \_Arg &&\_\_x, \_NodeGen &)\
 template\<typename \_InputIterator\> \_\_enable\_if\_t\<!\_\_same\_value\_type\< \_InputIterator \>::value \> **\_M\_insert\_range\_equal** (\_InputIterator \_\_first, \_InputIterator \_\_last)\
 template\<typename \_InputIterator\> \_\_enable\_if\_t\< \_\_same\_value\_type\< \_InputIterator \>::value \> **\_M\_insert\_range\_equal** (\_InputIterator \_\_first, \_InputIterator \_\_last)\
 template\<typename \_InputIterator\> \_\_enable\_if\_t\<!\_\_same\_value\_type\< \_InputIterator \>::value \> **\_M\_insert\_range\_unique** (\_InputIterator \_\_first, \_InputIterator \_\_last)\
 template\<typename \_InputIterator\> \_\_enable\_if\_t\< \_\_same\_value\_type\< \_InputIterator \>::value \> **\_M\_insert\_range\_unique** (\_InputIterator \_\_first, \_InputIterator \_\_last)\
 template\<typename \_Arg\> **pair**\< typename \_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::iterator, bool \> **\_M\_insert\_unique** (\_Arg &&\_\_v)\
 template\<typename \_Arg\> **pair**\< iterator, bool \> **\_M\_insert\_unique** (\_Arg &&\_\_x)\
 template\<typename \_Arg\> iterator **\_M\_insert\_unique\_** (const\_iterator \_\_pos, \_Arg &&\_\_x)\
 template\<typename \_Arg, typename \_NodeGen\> iterator **\_M\_insert\_unique\_** (const\_iterator \_\_pos, \_Arg &&\_\_x, \_NodeGen &)\
 const\_iterator **begin** () const noexcept\
 iterator **begin** () noexcept\
 void **clear** () noexcept\
 size\_type **count** (const key\_type &\_\_k) const\
 bool **empty** () const noexcept\
 const\_iterator **end** () const noexcept\
 iterator **end** () noexcept\
 **pair**\< iterator, iterator \> **equal\_range** (const key\_type &\_\_k)\
 **pair**\< const\_iterator, const\_iterator \> **equal\_range** (const key\_type &\_\_k) const\
 size\_type **erase** (const key\_type &\_\_x)\
 iterator **erase** (const\_iterator \_\_first, const\_iterator \_\_last)\
 iterator **erase** (const\_iterator \_\_position)\
 iterator **erase** (iterator \_\_position)\
 iterator **find** (const key\_type &\_\_k)\
 const\_iterator **find** (const key\_type &\_\_k) const\
 allocator\_type **get\_allocator** () const noexcept\
 \_Compare **key\_comp** () const\
 iterator **lower\_bound** (const key\_type &\_\_k)\
 const\_iterator **lower\_bound** (const key\_type &\_\_k) const\
 size\_type **max\_size** () const noexcept\
 const\_reverse\_iterator **rbegin** () const noexcept\
 reverse\_iterator **rbegin** () noexcept\
 const\_reverse\_iterator **rend** () const noexcept\
 reverse\_iterator **rend** () noexcept\
 size\_type **size** () const noexcept\
 void **swap** (\_Rb\_tree &\_\_t) noexcept(/\*conditional \*/)\
 iterator **upper\_bound** (const key\_type &\_\_k)\
 const\_iterator **upper\_bound** (const key\_type &\_\_k) const\

### Protected Types

typedef \_Node\_traits::\_Base\_ptr **\_Base\_ptr**\
 typedef \_Node\_traits::\_Header\_t **\_Header\_t**\
 typedef \_Node\_traits::\_Node\_ptr **\_Node\_ptr**\

### Protected Member Functions

\_Base\_ptr **\_M\_begin** () const noexcept\
 \_Node\_ptr **\_M\_begin\_node** () const noexcept\
 template\<bool \_MoveValue, typename \_NodeGen\> \_Node\_ptr **\_M\_clone\_node** (\_Node\_ptr \_\_x, \_NodeGen &\_\_node\_gen)\
 template\<typename... \_Args\> void **\_M\_construct\_node** (\_Node\_ptr \_\_node, \_Args &&... \_\_args)\
 template\<typename... \_Args\> \_Node\_ptr **\_M\_create\_node** (\_Args &&... \_\_args)\
 void **\_M\_destroy\_node** (\_Node\_ptr \_\_p) noexcept\
 void **\_M\_drop\_node** (\_Node\_ptr \_\_p) noexcept\
 \_Base\_ptr **\_M\_end** () const noexcept\
 \_Node\_ptr **\_M\_get\_node** ()\
 template\<typename \_Key1, typename \_Key2\> bool **\_M\_key\_compare** (const \_Key1 &\_\_k1, const \_Key2 &\_\_k2) const\
 \_Base\_ptr **\_M\_leftmost** () const noexcept\
 \_Base\_ptr & **\_M\_leftmost** () noexcept\
 void **\_M\_put\_node** (\_Node\_ptr \_\_p) noexcept\
 \_Base\_ptr **\_M\_rightmost** () const noexcept\
 \_Base\_ptr & **\_M\_rightmost** () noexcept\
 \_Base\_ptr **\_M\_root** () const noexcept\
 \_Base\_ptr & **\_M\_root** () noexcept\

### Static Protected Member Functions

static const \_Key & **\_S\_key** (\_Base\_ptr \_\_x)\
 static const \_Key & **\_S\_key** (\_Node\_ptr \_\_x)\
 static const \_Key & **\_S\_key** (const \_Node &\_\_node)\
 static \_Base\_ptr **\_S\_left** (\_Base\_ptr \_\_x) noexcept\
 static \_Node\_ptr **\_S\_left** (\_Node\_ptr \_\_x)\
 static \_Base\_ptr **\_S\_right** (\_Base\_ptr \_\_x) noexcept\
 static \_Node\_ptr **\_S\_right** (\_Node\_ptr \_\_x) noexcept\

### Protected Attributes

\_Rb\_tree\_impl\< \_Compare \> **\_M\_impl**\

## Detailed Description

### template\<class \_Key, class \_Value, class \_KeyOfValue, class \_Compare, class \_Alloc = std::allocator\<\_Value\>\>

struct \_\_gnu\_cxx::rb\_tree\< \_Key, \_Value, \_KeyOfValue, \_Compare, \_Alloc \>"This is an SGI extension.

**Todo**

Needs documentation! See http://gcc.gnu.org/onlinedocs/libstdc++/manual/documentation\_style.html

## Author

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