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

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

## NAME

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

## SYNOPSIS

`#include <rb_tree>`

Inherits std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>.

### Public Types

template\<typename \_Iter \> using **\_\_same\_value\_type** = is\_same\< value\_type, typename iterator\_traits\< \_Iter \>::value\_type \>\
 typedef std::\_Rb\_tree\< \_Key, \_Value, \_KeyOfValue, \_Compare, \_Alloc \> **\_Base**\
 template\<typename \_Compare2 \> using **\_Compatible\_tree** = \_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare2, \_Alloc \>\
 typedef \_Base::allocator\_type **allocator\_type**\
 typedef \_Rb\_tree\_const\_iterator\< value\_type \> **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**\
 using **insert\_return\_type** = \_Node\_insert\_return\< \_\_conditional\_t\< is\_same\_v\< \_Key, \_Val \>, const\_iterator, iterator \>, **node\_type** \>\
 typedef \_Rb\_tree\_iterator\< value\_type \> **iterator**\
 typedef \_Key **key\_type**\
 using **node\_type** = \_Node\_handle\< \_Key, \_Val, \_Node\_allocator \>\
 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 \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> size\_type **\_M\_count\_tr** (const \_Kt &\_\_k) const\
 template\<typename... \_Args\> iterator **\_M\_emplace\_equal** (\_Args &&... \_\_args)\
 template\<typename... \_Args\> auto **\_M\_emplace\_equal** (\_Args &&... \_\_args) -\> iterator\
 template\<typename... \_Args\> iterator **\_M\_emplace\_hint\_equal** (const\_iterator \_\_pos, \_Args &&... \_\_args)\
 template\<typename... \_Args\> auto **\_M\_emplace\_hint\_equal** (const\_iterator \_\_pos, \_Args &&... \_\_args) -\> iterator\
 template\<typename... \_Args\> iterator **\_M\_emplace\_hint\_unique** (const\_iterator \_\_pos, \_Args &&... \_\_args)\
 template\<typename... \_Args\> auto **\_M\_emplace\_hint\_unique** (const\_iterator \_\_pos, \_Args &&... \_\_args) -\> iterator\
 template\<typename... \_Args\> **pair**\< iterator, bool \> **\_M\_emplace\_unique** (\_Args &&... \_\_args)\
 template\<typename... \_Args\> auto **\_M\_emplace\_unique** (\_Args &&... \_\_args) -\> **pair**\< iterator, bool \>\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> **pair**\< iterator, iterator \> **\_M\_equal\_range\_tr** (const \_Kt &\_\_k)\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> **pair**\< const\_iterator, const\_iterator \> **\_M\_equal\_range\_tr** (const \_Kt &\_\_k) const\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> iterator **\_M\_find\_tr** (const \_Kt &\_\_k)\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> const\_iterator **\_M\_find\_tr** (const \_Kt &\_\_k) const\
 **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)\
 **pair**\< \_Base\_ptr, \_Base\_ptr \> **\_M\_get\_insert\_unique\_pos** (const **key\_type** &\_\_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 &)\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> iterator **\_M\_lower\_bound\_tr** (const \_Kt &\_\_k)\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> const\_iterator **\_M\_lower\_bound\_tr** (const \_Kt &\_\_k) const\
 template\<typename \_Compare2 \> void **\_M\_merge\_equal** (**\_Compatible\_tree**\< \_Compare2 \> &\_\_src) noexcept\
 Merge from a compatible container into one with equivalent keys.  template\<typename \_Compare2 \> void **\_M\_merge\_unique** (**\_Compatible\_tree**\< \_Compare2 \> &\_\_src) noexcept\
 Merge from a compatible container into one with unique keys.  iterator **\_M\_reinsert\_node\_equal** (**node\_type** &&\_\_nh)\
 Re-insert an extracted node.  iterator **\_M\_reinsert\_node\_hint\_equal** (const\_iterator \_\_hint, **node\_type** &&\_\_nh)\
 Re-insert an extracted node.  iterator **\_M\_reinsert\_node\_hint\_unique** (const\_iterator \_\_hint, **node\_type** &&\_\_nh)\
 Re-insert an extracted node.  **insert\_return\_type** **\_M\_reinsert\_node\_unique** (**node\_type** &&\_\_nh)\
 Re-insert an extracted node.  template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> iterator **\_M\_upper\_bound\_tr** (const \_Kt &\_\_k)\
 template\<typename \_Kt , typename \_Req  = \_\_has\_is\_transparent\_t\<\_Compare, \_Kt\>\> const\_iterator **\_M\_upper\_bound\_tr** (const \_Kt &\_\_k) const\
 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)\
 \_GLIBCXX\_ABI\_TAG\_CXX11 iterator **erase** (const\_iterator \_\_first, const\_iterator \_\_last)\
 \_GLIBCXX\_ABI\_TAG\_CXX11 iterator **erase** (const\_iterator \_\_position)\
 \_GLIBCXX\_ABI\_TAG\_CXX11 iterator **erase** (iterator \_\_position)\
 **node\_type** **extract** (const **key\_type** &\_\_k)\
 Extract a node.  **node\_type** **extract** (const\_iterator \_\_pos)\
 Extract a node.  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 \_Rb\_tree\_node\_base \* **\_Base\_ptr**\
 typedef const \_Rb\_tree\_node\_base \* **\_Const\_Base\_ptr**\
 typedef const \_Rb\_tree\_node\< \_Val \> \* **\_Const\_Link\_type**\
 typedef \_Rb\_tree\_node\< \_Val \> \* **\_Link\_type**\

### Protected Member Functions

\_Const\_Link\_type **\_M\_begin** () const noexcept\
 \_Link\_type **\_M\_begin** () noexcept\
 template\<bool \_MoveValue, typename \_NodeGen \> \_Link\_type **\_M\_clone\_node** (\_Link\_type \_\_x, \_NodeGen &\_\_node\_gen)\
 template\<typename... \_Args\> void **\_M\_construct\_node** (\_Link\_type \_\_node, \_Args &&... \_\_args)\
 template\<typename... \_Args\> \_Link\_type **\_M\_create\_node** (\_Args &&... \_\_args)\
 void **\_M\_destroy\_node** (\_Link\_type \_\_p) noexcept\
 void **\_M\_drop\_node** (\_Link\_type \_\_p) noexcept\
 \_Const\_Base\_ptr **\_M\_end** () const noexcept\
 \_Base\_ptr **\_M\_end** () noexcept\
 \_Link\_type **\_M\_get\_node** ()\
 \_Const\_Base\_ptr **\_M\_leftmost** () const noexcept\
 \_Base\_ptr & **\_M\_leftmost** () noexcept\
 \_Link\_type **\_M\_mbegin** () const noexcept\
 void **\_M\_put\_node** (\_Link\_type \_\_p) noexcept\
 \_Const\_Base\_ptr **\_M\_rightmost** () const noexcept\
 \_Base\_ptr & **\_M\_rightmost** () noexcept\
 \_Const\_Base\_ptr **\_M\_root** () const noexcept\
 \_Base\_ptr & **\_M\_root** () noexcept\

### Static Protected Member Functions

static const \_Key & **\_S\_key** (\_Const\_Base\_ptr \_\_x)\
 static const \_Key & **\_S\_key** (\_Const\_Link\_type \_\_x)\
 static \_Link\_type **\_S\_left** (\_Base\_ptr \_\_x) noexcept\
 static \_Const\_Link\_type **\_S\_left** (\_Const\_Base\_ptr \_\_x) noexcept\
 static \_Base\_ptr **\_S\_maximum** (\_Base\_ptr \_\_x) noexcept\
 static \_Const\_Base\_ptr **\_S\_maximum** (\_Const\_Base\_ptr \_\_x) noexcept\
 static \_Base\_ptr **\_S\_minimum** (\_Base\_ptr \_\_x) noexcept\
 static \_Const\_Base\_ptr **\_S\_minimum** (\_Const\_Base\_ptr \_\_x) noexcept\
 static \_Link\_type **\_S\_right** (\_Base\_ptr \_\_x) noexcept\
 static \_Const\_Link\_type **\_S\_right** (\_Const\_Base\_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

## Member Function Documentation

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> template\<typename \_Compare2 \> void std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::\_M\_merge\_equal (\_Compatible\_tree\< \_Compare2 \> & \_\_src)` [inline]`, ` [noexcept]`, ` [inherited]`

Merge from a compatible container into one with equivalent keys.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> template\<typename \_Compare2 \> void std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::\_M\_merge\_unique (\_Compatible\_tree\< \_Compare2 \> & \_\_src)` [inline]`, ` [noexcept]`, ` [inherited]`

Merge from a compatible container into one with unique keys.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> iterator std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::\_M\_reinsert\_node\_equal (node\_type && \_\_nh)` [inline]`, ` [inherited]`

Re-insert an extracted node.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> iterator std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::\_M\_reinsert\_node\_hint\_equal (const\_iterator \_\_hint, node\_type && \_\_nh)` [inline]`, ` [inherited]`

Re-insert an extracted node.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> iterator std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::\_M\_reinsert\_node\_hint\_unique (const\_iterator \_\_hint, node\_type && \_\_nh)` [inline]`, ` [inherited]`

Re-insert an extracted node.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> insert\_return\_type std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::\_M\_reinsert\_node\_unique (node\_type && \_\_nh)` [inline]`, ` [inherited]`

Re-insert an extracted node.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> node\_type std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::extract (const key\_type & \_\_k)` [inline]`, ` [inherited]`

Extract a node.

### template\<typename \_Key , typename \_Val , typename \_KeyOfValue , typename \_Compare , typename \_Alloc = allocator\<\_Val\>\> node\_type std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>::extract (const\_iterator \_\_pos)` [inline]`, ` [inherited]`

Extract a node.

## Author

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