# Reversible Container

Category: containers | Component type: concept

### Description

A Reversible Container is a Forward Container whose iterators are Bidirectional Iterators. It allows backwards iteration through the container.

### Refinement of

Forward Container

### Associated types

Two new types are introduced. In addition, the iterator type and the const iterator type must satisfy a more stringent requirement than for a Forward Container. The iterator and reverse iterator types must be Bidirectional Iterators, not merely Forward Iterators.

Reverse iterator type | `X::reverse_iterator` | A Reverse Iterator adaptor whose base iterator type is the container's iterator type. Incrementing an object of type `reverse_iterator` moves backwards through the container: the Reverse Iterator adaptor maps `operator++` to `operator--`.
Const reverse iterator type | `X::const_reverse_iterator` | A Reverse Iterator adaptor whose base iterator type is the container's const iterator type. [1]

### Notation

`X` | A type that is a model of Reversible Container
`a`, `b` | Object of type `X`

### Definitions

### Valid expressions

In addition to the expressions defined in Forward Container, the following expressions must be valid.

Name | Expression | Type requirements | Return type
--- | --- | --- | ---
Beginning of range | `a.rbegin()` |  | `reverse_iterator` if `a` is mutable, `const_reverse_iterator` otherwise [1]
End of range | `a.rend()` |  | `reverse_iterator` if `a` is mutable, `const_reverse_iterator` otherwise [1]

### Expression semantics

Semantics of an expression is defined only where it is not defined in Forward Container, or where there is additional information.

Name | Expression | Precondition | Semantics | Postcondition
--- | --- | --- | --- | ---
Beginning of reverse range | `a.rbegin()` |  | Equivalent to `X::reverse_iterator(a.end())`. | `a.rbegin()` is dereferenceable or past-the-end. It is past-the-end if and only if `a.size() == 0`.
End of reverse range | `a.rend()` |  | Equivalent to `X::reverse_iterator(a.begin())`. | `a.end()` is past-the-end.

### Complexity guarantees

The run-time complexity of `rbegin()` and `rend()` is amortized constant time.

### Invariants

Valid range | `[a.rbegin(), a.rend())` is a valid range.
Equivalence of ranges | The distance from `a.begin()` to `a.end()` is the same as the distance from `a.rbegin()` to `a.rend()`.

### Models

- vector
- list
- deque

### Notes

[1] A Container's iterator type and const iterator type may be the same type: a container need not provide mutable iterators. It follows from this that the reverse iterator type and the const reverse iterator type may also be the same.

### See also

The Iterator overview, Bidirectional Iterator, Sequence

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation