# Container Concepts

## Vector

#### Description

A Vector describes common aspects of dense, packed and sparse vectors.

#### Refinement of

Vector Expression.

#### Associated types

Value type | `value_type` | The type of the vector.
Distance type | `difference_type` | A signed integral type used to represent the distance between two of the vector's iterators.
Size type | `size_type` | An unsigned integral type that can represent any nonnegative value of the vector's distance type.

#### Notation

`V` | A type that is a model of Vector
`v` | Objects of type `V`
`n, i` | Objects of a type convertible to `size_type`
`t` | Object of a type convertible to `value_type`

#### Definitions

#### Valid expressions

In addition to the expressions defined in Vector Expression the following expressions must be valid.

Name | Expression | Type requirements | Return type
--- | --- | --- | ---
Sizing constructor | `V v (n)` |  | `V`
Insert | `v.insert (i, t)` | `v` is mutable. | `void`
Erase | `v.erase (i)` | `v` is mutable. | `void`
Clear | `v.clear ()` | `v` is mutable. | `void`
Resize | `v.resize (n)` | `v` is mutable. | `void`

#### Expression semantics

Semantics of an expression is defined only where it differs from, or is not defined in Vector Expression.

Name | Expression | Precondition | Semantics | Postcondition
--- | --- | --- | --- | ---
Sizing constructor | `V v (n)` | `n >= 0` | Creates a vector of `n` elements. | `v.size () == n`.
Insert | `v.insert (i, t)` | `0 <= i < v.size ()` and `v (i)` is a copy of `value_type ()`. | A copy of `t` is inserted in `v`. | `v (i)` is a copy of `t`.
Erase | `v.erase (i)` | `0 <= i < v.size ()` | Destroys the element `v (i)` and replaces it with `value_type ()`. | `v (i)` is a copy of `value_type ()`.
Clear | `v.clear ()` |  | Equivalent to `for (i = 0; i < v.size (); ++ i)` `v.erase (i);` |
Resize | `v.resize (n)` |  | Modifies the vector so that it can hold `n` elements. | `v.size () == n`.

#### Complexity guarantees

The run-time complexity of the sizing constructor is linear in the vector's size.

The run-time complexity of insert and erase is specific for the vector.

#### Invariants

#### Models

- `vector<T, A>`
- `unit_vector<T>`
- `zero_vector<T>`
- `sparse_vector<T, A>`

## Matrix

#### Description

A Matrix describes common aspects of dense, packed and sparse matrices.

#### Refinement of

Matrix Expression.

#### Associated types

Value type | `value_type` | The type of the matrix.
Distance type | `difference_type` | A signed integral type used to represent the distance between two of the matrix's iterators.
Size type | `size_type` | An unsigned integral type that can represent any nonnegative value of the matrix's distance type.

#### Notation

`M` | A type that is a model of Matrix
`m` | Objects of type `M`
`n1, n2, i, j` | Objects of a type convertible to `size_type`
`t` | Object of a type convertible to `value_type`

#### Definitions

#### Valid expressions

In addition to the expressions defined in Matrix Expression the following expressions must be valid.

Name | Expression | Type requirements | Return type
--- | --- | --- | ---
Sizing constructor | `M m (n1, n2)` |  | `M`
Insert | `m.insert (i, j, t)` | `m` is mutable. | `void`
Erase | `m.erase (i, j)` | `m` is mutable. | `void`
Clear | `m.clear ()` | `m` is mutable. | `void`
Resize | `m.resize (n1, n2)` | `m` is mutable. | `void`

#### Expression semantics

Semantics of an expression is defined only where it differs from, or is not defined in Matrix Expression.

Name | Expression | Precondition | Semantics | Postcondition
--- | --- | --- | --- | ---
Sizing constructor | `M m (n1, n2)` | `n1 >= 0` and`n2 >= 0` | Creates a matrix of `n1` rows and `n2` columns. | `m.size1 () == n1` and `m.size2 () == n2`.
Insert | `m.insert (i, j, t)` | `0 <= i < m.size1 ()`, `0 <= j < m.size2 ()`and `m (i, j)` is a copy of `value_type ()`. | A copy of `t` is inserted in `m`. | `m (i, j)` is a copy of `t`.
Erase | `m.erase (i, j)` | `0 <= i < m.size1 ()`and `0 <= j < m.size2` | Destroys the element `m (i, j)` and replaces it with `value_type ()`. | `m (i, j)` is a copy of `value_type ()`.
Clear | `m.clear ()` |  | Equivalent to `for (i = 0; i < m.size1 (); ++ i)` `for (j = 0; j < m.size2 (); ++ j)` `m.erase (i, j);` |
Resize | `m.resize (n1, n2)` |  | Modifies the vector so that it can hold `n1` rows and `n2` columns. | `m.size1 () == n1` and `m.size2 () == n2`.

#### Complexity guarantees

The run-time complexity of the sizing constructor is quadratic in the matrix's size.

The run-time complexity of insert and erase is specific for the matrix.

#### Invariants

#### Models

- `matrix<T, F, A>`
- `identity_matrix<T>`
- `zero_matrix<T>`
- `triangular_matrix<T, F1, F2, A>`
- `symmetric_matrix<T, F1, F2, A>`
- `banded_matrix<T, F, A>`
- `sparse_matrix<T, F, A>`

Copyright (©) 2000-2002 Joerg Walter, Mathias Koch
Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided ``as is'' without express or implied warranty, and with no claim as to its suitability for any purpose.

Last revised: 8/3/2002