---
name: "std::Rb_tree"
section: "3"
platform: "linux"
package: "libstdc++5-3.3-doc"
version: "1:3.3.6-15"
release: "Debian 4.0 (Etch)"
platforms: ["linux"]
url: "https://new.carta.tech/std::Rb_tree"
---

# std::Rb\_tree(3)

## NAME

std::Rb\_tree -

## SYNOPSIS

Inherits **std::Rb\_tree\_base\< Val, Alloc \>**.

### Public Types

typedef Key **key\_type**\
 typedef Val **value\_type**\
 typedef **value\_type** \* **pointer**\
 typedef const **value\_type** \* **const\_pointer**\
 typedef **value\_type** & **reference**\
 typedef const **value\_type** & **const\_reference**\
 typedef **Rb\_tree\_node** \* **Link\_type**\
 typedef size\_t **size\_type**\
 typedef ptrdiff\_t **difference\_type**\
 typedef **Base::allocator\_type** **allocator\_type**\
 typedef **Rb\_tree\_iterator**\< **value\_type**, **reference**, **pointer** \> **iterator**\
 typedef **Rb\_tree\_iterator**\< **value\_type**, **const\_reference**, **const\_pointer** \> **const\_iterator**\
 typedef **std::reverse\_iterator**\< **const\_iterator** \> **const\_reverse\_iterator**\
 typedef **std::reverse\_iterator**\< **iterator** \> **reverse\_iterator**\

### Public Member Functions

**allocator\_type** **get\_allocator** () const\
 **Rb\_tree** ()\
 **Rb\_tree** (const Compare &comp)\
 **Rb\_tree** (const Compare &comp, const **allocator\_type** &a)\
 **Rb\_tree** (const **Rb\_tree**\< Key, Val, KeyOfValue, Compare, Alloc \> &x)\
 **~Rb\_tree** ()\
 **Rb\_tree**\< Key, Val, KeyOfValue, Compare, Alloc \> & **operator=** (const **Rb\_tree**\< Key, Val, KeyOfValue, Compare, Alloc \> &x)\
 Compare **key\_comp** () const\
 **iterator** **begin** ()\
 **const\_iterator** **begin** () const\
 **iterator** **end** ()\
 **const\_iterator** **end** () const\
 **reverse\_iterator** **rbegin** ()\
 **const\_reverse\_iterator** **rbegin** () const\
 **reverse\_iterator** **rend** ()\
 **const\_reverse\_iterator** **rend** () const\
 bool **empty** () const\
 **size\_type** **size** () const\
 **size\_type** **max\_size** () const\
 void **swap** (**Rb\_tree**\< Key, Val, KeyOfValue, Compare, Alloc \> &\_\_t)\
 **pair**\< **iterator**, bool \> **insert\_unique** (const **value\_type** &x)\
 **iterator** **insert\_equal** (const **value\_type** &x)\
 **iterator** **insert\_unique** (**iterator** position, const **value\_type** &x)\
 **iterator** **insert\_equal** (**iterator** position, const **value\_type** &x)\
 template\<typename InputIterator\> void **insert\_unique** (InputIterator first, InputIterator last)\
 template\<typename InputIterator\> void **insert\_equal** (InputIterator first, InputIterator last)\
 void **erase** (**iterator** position)\
 **size\_type** **erase** (const **key\_type** &x)\
 void **erase** (**iterator** first, **iterator** last)\
 void **erase** (const **key\_type** \*first, const **key\_type** \*last)\
 void **clear** ()\
 **iterator** **find** (const **key\_type** &x)\
 **const\_iterator** **find** (const **key\_type** &x) const\
 **size\_type** **count** (const **key\_type** &x) const\
 **iterator** **lower\_bound** (const **key\_type** &x)\
 **const\_iterator** **lower\_bound** (const **key\_type** &x) const\
 **iterator** **upper\_bound** (const **key\_type** &x)\
 **const\_iterator** **upper\_bound** (const **key\_type** &x) const\
 **pair**\< **iterator**, **iterator** \> **equal\_range** (const **key\_type** &x)\
 **pair**\< **const\_iterator**, **const\_iterator** \> **equal\_range** (const **key\_type** &x) const\
 bool **\_\_rb\_verify** () const\

### Protected Types

typedef **Rb\_tree\_node\_base** \* **Base\_ptr**\
 typedef **Rb\_tree\_node**\< Val \> **Rb\_tree\_node**\

### Protected Member Functions

**Link\_type** **M\_create\_node** (const **value\_type** &x)\
 **Link\_type** **M\_clone\_node** (**Link\_type** x)\
 void **destroy\_node** (**Link\_type** \_\_p)\
 **Link\_type** & **M\_root** () const\
 **Link\_type** & **M\_leftmost** () const\
 **Link\_type** & **M\_rightmost** () const\
 **Rb\_tree\_node**\< Type \> \* **M\_get\_node** ()\
 void **M\_put\_node** (**Rb\_tree\_node**\< Type \> \*\_\_p)\

### Static Protected Member Functions

static **Link\_type** & **S\_left** (**Link\_type** x)\
 static **Link\_type** & **S\_right** (**Link\_type** x)\
 static **Link\_type** & **S\_parent** (**Link\_type** x)\
 static **reference** **S\_value** (**Link\_type** x)\
 static const Key & **S\_key** (**Link\_type** x)\
 static **Rb\_tree\_color** & **S\_color** (**Link\_type** x)\
 static **Link\_type** & **S\_left** (**Base\_ptr** x)\
 static **Link\_type** & **S\_right** (**Base\_ptr** x)\
 static **Link\_type** & **S\_parent** (**Base\_ptr** x)\
 static **reference** **S\_value** (**Base\_ptr** x)\
 static const Key & **S\_key** (**Base\_ptr** x)\
 static **Rb\_tree\_color** & **S\_color** (**Base\_ptr** x)\
 static **Link\_type** **S\_minimum** (**Link\_type** x)\
 static **Link\_type** **S\_maximum** (**Link\_type** x)\

### Protected Attributes

**size\_type** **M\_node\_count**\
 Compare **M\_key\_compare**\
 **Alloc\_traits**\< **Rb\_tree\_node**\< Type \>, Alloc \>::**allocator\_type** **M\_node\_allocator**\
 **Rb\_tree\_node**\< Type \> \* **M\_header**\

### Private Types

typedef **Rb\_tree\_base**\< Val, Alloc \> **Base**\

### Private Member Functions

**iterator** **M\_insert** (**Base\_ptr** x, **Base\_ptr** y, const **value\_type** &\_\_v)\
 **Link\_type** **M\_copy** (**Link\_type** x, **Link\_type** \_\_p)\
 void **M\_erase** (**Link\_type** x)\
 void **M\_empty\_initialize** ()\

## 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 586 of file stl\_tree.h.

## Author

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