---
name: "std::_Rb_tree"
section: "3"
platform: "linux"
package: "libstdc++6-4.1-doc"
version: "4.1.1-21"
release: "Debian 4.0 (Etch)"
platforms: ["linux"]
url: "https://new.carta.tech/std::_Rb_tree"
---

# std::\_Rb\_tree(3)

## NAME

std::\_Rb\_tree -

## SYNOPSIS

## Detailed Description

### template\<typename \_Key, typename \_Val, typename \_KeyOfValue, typename \_Compare, typename \_Alloc = allocator\<\_Val\>\> class std::\_Rb\_tree\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \>

Definition at line 328 of file stl\_tree.h.

### Public Types

typedef const **\_Rb\_tree\_node** \* **\_Const\_Link\_type**\
 typedef **\_Rb\_tree\_node** \* **\_Link\_type**\
 typedef \_Alloc **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**\
 typedef **\_Rb\_tree\_iterator**\< **value\_type** \> **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

bool **\_\_rb\_verify** () const\
 **\_Rb\_tree** (const **\_Rb\_tree**\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \> &\_\_x)\
 **\_Rb\_tree** (const \_Compare &\_\_comp, const **allocator\_type** &\_\_a)\
 **\_Rb\_tree** (const \_Compare &\_\_comp)\
 **\_Rb\_tree** ()\
 **const\_iterator** **begin** () const\
 **iterator** **begin** ()\
 void **clear** ()\
 **size\_type** **count** (const **key\_type** &\_\_x) const \
 bool **empty** () const\
 **const\_iterator** **end** () const\
 **iterator** **end** ()\
 **pair**\< **const\_iterator**, **const\_iterator** \> **equal\_range** (const **key\_type** &\_\_x) const \
 **pair**\< **iterator**, **iterator** \> **equal\_range** (const **key\_type** &\_\_x)\
 void **erase** (const **key\_type** \*\_\_first, const **key\_type** \*\_\_last)\
 void **erase** (**const\_iterator** \_\_first, **const\_iterator** \_\_last)\
 void **erase** (**iterator** \_\_first, **iterator** \_\_last)\
 **size\_type** **erase** (const **key\_type** &\_\_x)\
 void **erase** (**const\_iterator** \_\_position)\
 void **erase** (**iterator** \_\_position)\
 **const\_iterator** **find** (const **key\_type** &\_\_x) const \
 **iterator** **find** (const **key\_type** &\_\_x)\
 **allocator\_type** **get\_allocator** () const\
 template\<typename \_InputIterator\> void **insert\_equal** (\_InputIterator \_\_first, \_InputIterator \_\_last)\
 **const\_iterator** **insert\_equal** (**const\_iterator** \_\_position, const **value\_type** &\_\_x)\
 **iterator** **insert\_equal** (**iterator** \_\_position, const **value\_type** &\_\_x)\
 **iterator** **insert\_equal** (const **value\_type** &\_\_x)\
 template\<typename \_InputIterator\> void **insert\_unique** (\_InputIterator \_\_first, \_InputIterator \_\_last)\
 **const\_iterator** **insert\_unique** (**const\_iterator** \_\_position, const **value\_type** &\_\_x)\
 **iterator** **insert\_unique** (**iterator** \_\_position, const **value\_type** &\_\_x)\
 **pair**\< **iterator**, bool \> **insert\_unique** (const **value\_type** &\_\_x)\
 \_Compare **key\_comp** () const\
 **const\_iterator** **lower\_bound** (const **key\_type** &\_\_x) const \
 **iterator** **lower\_bound** (const **key\_type** &\_\_x)\
 **size\_type** **max\_size** () const\
 **\_Rb\_tree**\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \> & **operator=** (const **\_Rb\_tree**\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \> &\_\_x)\
 **const\_reverse\_iterator** **rbegin** () const\
 **reverse\_iterator** **rbegin** ()\
 **const\_reverse\_iterator** **rend** () const\
 **reverse\_iterator** **rend** ()\
 **size\_type** **size** () const\
 void **swap** (**\_Rb\_tree**\< \_Key, \_Val, \_KeyOfValue, \_Compare, \_Alloc \> &\_\_t)\
 **const\_iterator** **upper\_bound** (const **key\_type** &\_\_x) const \
 **iterator** **upper\_bound** (const **key\_type** &\_\_x)\
 **~\_Rb\_tree** ()\

### Protected Types

typedef **\_Rb\_tree\_node\_base** \* **\_Base\_ptr**\
 typedef const **\_Rb\_tree\_node\_base** \* **\_Const\_Base\_ptr**\
 typedef **\_Rb\_tree\_node**\< \_Val \> **\_Rb\_tree\_node**\

### Protected Member Functions

**\_Const\_Link\_type** **\_M\_begin** () const\
 **\_Link\_type** **\_M\_begin** ()\
 **\_Link\_type** **\_M\_clone\_node** (**\_Const\_Link\_type** \_\_x)\
 **\_Link\_type** **\_M\_create\_node** (const **value\_type** &\_\_x)\
 **\_Const\_Link\_type** **\_M\_end** () const\
 **\_Link\_type** **\_M\_end** ()\
 **\_Rb\_tree\_node** \* **\_M\_get\_node** ()\
 **\_Const\_Base\_ptr** **\_M\_leftmost** () const\
 **\_Base\_ptr** & **\_M\_leftmost** ()\
 void **\_M\_put\_node** (**\_Rb\_tree\_node** \*\_\_p)\
 **\_Const\_Base\_ptr** **\_M\_rightmost** () const\
 **\_Base\_ptr** & **\_M\_rightmost** ()\
 **\_Const\_Base\_ptr** **\_M\_root** () const\
 **\_Base\_ptr** & **\_M\_root** ()\
 void **destroy\_node** (**\_Link\_type** \_\_p)\

### Static Protected Member Functions

static const \_Key & **\_S\_key** (**\_Const\_Base\_ptr** \_\_x)\
 static const \_Key & **\_S\_key** (**\_Const\_Link\_type** \_\_x)\
 static **\_Const\_Link\_type** **\_S\_left** (**\_Const\_Base\_ptr** \_\_x)\
 static **\_Link\_type** **\_S\_left** (**\_Base\_ptr** \_\_x)\
 static **\_Const\_Base\_ptr** **\_S\_maximum** (**\_Const\_Base\_ptr** \_\_x)\
 static **\_Base\_ptr** **\_S\_maximum** (**\_Base\_ptr** \_\_x)\
 static **\_Const\_Base\_ptr** **\_S\_minimum** (**\_Const\_Base\_ptr** \_\_x)\
 static **\_Base\_ptr** **\_S\_minimum** (**\_Base\_ptr** \_\_x)\
 static **\_Const\_Link\_type** **\_S\_right** (**\_Const\_Base\_ptr** \_\_x)\
 static **\_Link\_type** **\_S\_right** (**\_Base\_ptr** \_\_x)\
 static **const\_reference** **\_S\_value** (**\_Const\_Base\_ptr** \_\_x)\
 static **const\_reference** **\_S\_value** (**\_Const\_Link\_type** \_\_x)\

### Protected Attributes

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

### Classes

struct **\_Rb\_tree\_impl**\
 struct **\_Rb\_tree\_impl\< \_Key\_compare, true \>**\

## Author

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