**Category**: containers

**Component type**: concept

A Unique Sorted Associative Container is a Sorted Associative Container that is also a Unique Associative Container. That is, it is a Sorted Associative Container with the property that no two elements in the container have the same key.

Sorted Associative Container, Unique Associative Container

None, except for those described in the Sorted Associative Container Unique Associative Container requirements.

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

`a` | Object of type `X` |

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

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

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

`c` | Object of type `X::key_compare` |

In addition to the expressions defined in Sorted Associative Container and Unique Associative Container, the following expressions must be valid.

Name | Expression | Type requirements | Return type |
---|---|---|---|

Range constructor | X(i, j) X a(i, j); | `i` and `j` are Input Iterators whose value type is convertible to `T` [1]. | |

Range constructor with compare | X(i, j, c) X a(i, j, c); | `i` and `j` are Input Iterators whose value type is convertible to `T` [1]. `c` is an object of type `key_compare` . | |

Insert with hint | `a.insert(p, t)` | `iterator` | |

Insert range | `a.insert(i, j)` | `i` and `j` are Input Iterators whose value type is convertible to `X::value_type` . [1] | `void` |

Name | Expression | Precondition | Semantics | Postcondition |
---|---|---|---|---|

Range constructor | X(i, j) X a(i, j); | `[i,j)` is a valid range. | Creates an associative container that contains all of the elements in the range `[i,j)` that have unique keys. The comparison object used by the container is `key_compare()` . | `size()` is less than or equal to the distance from `i` to `j` . |

Range constructor with compare | X(i, j, c) X a(i, j, c); | `[i,j)` is a valid range. | Creates an associative container that contains all of the elements in the range `[i,j)` that have unique keys. The comparison object used by the container is `c` . | `size()` is less than or equal to the distance from `i` to `j` . |

Insert with hint | `a.insert(p, t)` | `p` is a nonsingular iterator in `a` . | Inserts `t` into `a` if and only if `a` does not already contain an element whose key is equivalent to `t` 's key. The argument `p` is a hint: it points to the location where the search will begin. The return value is a dereferenceable iterator that points to the element with a key that is equivalent to that of `t` . | `a` contains an element whose key is the same as that of `t` . The size of `a` is incremented by either `1` or `0` . |

Insert range | `a.insert(i, j)` | `[i, j)` is a valid range. | Equivalent to `a.insert(t)` for each object `t` that is pointed to by an iterator in the range `[i, j)` . Each element is inserted into `a` if and only if `a` does not already contain an element with an equivalent key. | The size of `a` is incremented by at most `j - i` . |

The range constructor, and range constructor with compare, are in general `O(N * log(N))`

, where `N`

is the size of the range. However, they are linear in `N`

if the range is already sorted by `value_comp()`

.

Insert with hint is logarithmic in general, but it is amortized constant time if `t`

is inserted immediately before `p`

.

Insert range is in general `O(N * log(N))`

, where `N`

is the size of the range. However, it is linear in `N`

if the range is already sorted by `value_comp()`

.

Strictly ascending order | The elements in a Unique Sorted Associative Container are always arranged in strictly ascending order by key. That is, if `a` is a Unique Sorted Associative Container, then `is_sorted(a.begin(), a.end(), a.value_comp())` is always `true` . Furthermore, if `i` and `j` are dereferenceable iterators in `a` such that `i` precedes `j` , then `a.value_comp()(*i, *j)` is always `true` . [2] |

- SkipList
- SSkipList
- KeyedSkipList
- KeyedSSkipList
- AutoSkipList
- AutoSSkipList
- AutoKeyedSkipList
- AutoKeyedSSkipList
- AccessSkipList
- AccessSSkipList
- AutoAccessSkipList
- AutoAccessSSkipList

[1] At present (early 1998), not all compilers support "member templates". If your compiler supports member templates then `i`

and `j`

may be of any type that conforms to the Input Iterator requirements. If your compiler does not yet support member templates, however, then `i`

and `j`

must be of type `const T*`

or of type `X::const_iterator`

.

[2] This is a more stringent invariant than that of Sorted Associative Container. In a Sorted Associative Container we merely know that every element is less than or equal to its successor; in a Unique Sorted Associative Container, however, we know that it must be less than its successor.

Associative Container, Sorted Associative Container, Multiple Sorted Associative Container,

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