唯一已排序关联容器


类别: 容器	组件类型: 概念

说明

唯一已排序关联容器是一款已排序关联容器，同时也是一款唯一关联容器。换句话说，它是一款具有以下特性的已排序关联容器：容器中的元素没有两个的键相同。

细化

已排序关联容器、唯一关联容器

关联类型

无，除了那些在已排序关联容器和唯一关联容器需求中描述的类型。

符号

`X`	唯一已排序关联容器类型的模型
`a`	类型对象`X`
`t`	类型对象`X::value_type`
`k`	类型对象`X::key_type`
`p`, `q`	类型对象`X::iterator`
`c`	类型对象`X::key_compare`

定义

有效表达式

除了已排序关联容器和唯一关联容器中定义的表达式以外，以下表达式必须有效。

名称	表达式	类型需求	返回类型
范围构造函数	X(i, j) X a(i, j);	`i`和`j`是其值类型可转换为`T` [1].
具有比较的范围构造函数	X(i, j, c) X a(i, j, c);	`i`和`j`是其值类型可转换为`T` [1]. `c`是类型对象`key_compare`.
提示插入	`a.insert(p, t)`		`迭代器`
插入范围	`a.insert(i, j)`	`i`和`j`是其值类型可转换为`X::value_type`. [1]	`void`

表达式语义

名称	表达式	前置条件	语义	后置条件
范围构造函数	X(i, j) X a(i, j);	`[i,j)`是有效范围。	创建含有范围中的所有元素且这些元素拥有唯一键的关联容器。`[i,j)`容器使用的比较对象为`key_compare()`.	`size()`小于等于从`i`到`j`.
具有比较的范围构造函数	X(i, j, c) X a(i, j, c);	`[i,j)`是有效范围。	创建含有范围中的所有元素且这些元素拥有唯一键的关联容器。`[i,j)`容器使用的比较对象为`c`.	`size()`小于等于从`i`到`j`.
提示插入	`a.insert(p, t)`	`p`在`a`.	中是一个非奇异迭代器。`t`插入`a`仅当且仅当`a`不包含其键等同于`t`的键的元素时。`p`参数`t`.	`a`是一个提示：它指向搜索开始的位置。返回值是一个可取消引用的迭代器，它指向的元素具有与`t`包含一个其键与`a`的键相同的元素时。`1`的大小将递增`0`.
插入范围	`a.insert(i, j)`	`或`是有效范围。	[i, j)`等同于`a.insert(t)`t`针对由范围中的迭代器指向的每个对象`或`。每个元素都被插入到`a`仅当且仅当`a`不包含具有等效键的元素。	的大小`a`最多增加`j - i`.

复杂性保证

范围构造函数和带有比较函数的范围构造函数通常为O(N * log(N))，其中N是范围的大小。但是，如果范围按Nvalue_comp()排序，则范围呈线性增长。.

带有提示的插入操作通常呈对数增长，但在t之前立即插入后变为平均恒定时间。p.

插入范围通常为O(N * log(N))，其中N是范围的大小。但是，如果范围按Nvalue_comp()排序，则范围呈线性增长。.

不变条件

严格的升序唯一的已排序关联容器中的元素始终按键严格按照升序排列。即，如果a是唯一的已排序关联容器，则is_sorted(a.begin(), a.end(), a.value_comp())始终为true。此外，如果i和j是a中的可解引用迭代器，使得i在j之前，则a.value_comp()(*i, *j)始终为true. [2]

模型

map
set

注释

[1] 目前（1998年初），并非所有编译器都支持“成员模板”。如果您的编译器支持成员模板，则i和j可以为符合输入迭代器要求的任何类型。但是，如果您的编译器尚不支持成员模板，则i和j必须为以下类型const T*或以下类型X::const_iterator.

[2] 这是一个比已排序关联容器更严格的不变条件。在已排序关联容器中，我们仅知道每个元素小于或等于其后继元素；但在唯一的已排序关联容器中，我们知道元素必须小于其后继元素。

另请参阅

关联容器、已排序关联容器、多重已排序关联容器、哈希关联容器