**Category**: containers

**Component type**: concept

A Pair Associative Container is an Associative Container that associates a key with some other object. The value type of a Pair Associative Container is `pair<const key_type, data_type>`

. [1]

One new type is introduced, in addition to the types defined in the Associative Container requirements. Additionally, Pair Associative Container introduces one new type restriction.

Key type | `X::key_type` | The type of the key associated with `X::value_type` . |

Data type | `X::data_type` | The type of the data associated with `X::value_type` . A Pair Associative Container can be thought of as a mapping from `key_type` to `data_type` . |

Value type | `X::value_type` | The type of object stored in the container. The value type is required to be `pair<const key_type, data_type>` . |

All SkipLists have additional typedefs that specify the content of each element. When defining Keyed SkipLists, the X::value_type is a `pair<const key_type, data_type>`

. All other Skiplists have `X::value_type`

identical to T. The following types always specify the actual content (rather than a pair or other compound types).

`X::mapped_type`

is identical to `X::data_type`

in a Pair Associative Container.

`X::mapped_type`

is identical to `X::value_type`

in all other skiplist containers.

Mapped type | `X::mapped_type` | In keyed SkipLists, identical to `X::data_type` . Otherwise, identical to `X::value_type` . |

Const mapped type | `X::const_mapped_type` | Const version of `X::mapped_type` |

Mapped reference | `X::mapped_type_reference` | Reference version of `X::mapped_type` |

Cosnt mapped reference | `X::const_mapped_type_reference` | Const reference version of `X::mapped_type` |

`X` | A type that is a model of Pair Associative Container |

`a` | Object of type `X` |

`t` | Object of type `X::value_type` |

`d` | Object of type `X::data_type` |

`k` | Object of type `X::key_type` |

`p` , `q` | Object of type `X::iterator` |

None, except for those defined in the Associative Container requirements.

- KeyedSkipList
- KeyedSSkipList
- AutoKeyedSkipList
- AutoKeyedSSkipList
- MultiKeyedSkipList
- MultiKeyedSSkipList
- MultiAutoKeyedSkipList
- MultiAutoKeyedSSkipList

[1] The value type must be `pair<const key_type, data_type>`

, rather than `pair<key_type, data_type>`

, because of the Associative Container invariant of key immutability. The `data_type`

part of an object in a Pair Associative Container may be modified, but the `key_type`

part may not be. Note the implication of this fact: a Pair Associative Container cannot provide mutable iterators (as defined in the Trivial Iterator requirements), because the value type of a mutable iterator must be Assignable, and `pair<const key_type, data_type>`

is not Assignable. However, a Pair Associative Container can provide iterators that are not completely constant: iterators such that the expression `(*i).second = d`

is valid.

Associative Container, Simple Associative Container, Access Associative Container

Generated on Thu Jan 6 2011 15:52:41 for SkipList Library by 1.7.3