排序关联容器


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

排序关联容器是一种关联容器。排序关联容器在其键上使用排序关系；如果两个键都不小于另一个，则认为它们是等价的。（例如，如果排序关系是不区分大小写的字符串比较，则键“abcde”和“aBcDe”是等价的。）

排序关联容器保证大多数操作的复杂度永远不会比对数更差[1]，并且它们还保证其元素始终按键升序排序。

除了在关联容器和可逆容器需求中定义的类型外，还引入了两种新类型。

`X::key_compare`	用于比较键的严格弱排序的类型。其参数类型必须是`X::key_type`.
`X::value_compare`	用于比较值的严格弱排序的类型。其参数类型必须是`X::value_type`，并且它通过将与这些对象关联的键传递给类型为`value_type`的两个对象的比较`key_compare`.

除了在关联容器和可逆容器中定义的表达式外，以下表达式必须有效。

名称	表达式	返回类型
默认构造函数	X() X a;
带比较器的构造函数	X(c) X a(c);
键比较	`a.key_comp()`	`X::key_compare`
值比较	`a::value_compare()`	`X::value_compare`
下界	`a.lower_bound(k)`	`迭代器`如果`a`是可变的，否则`const_iterator`.
上界	`a.upper_bound(k)`	`迭代器`如果`a`是可变的，否则`const_iterator`.
相等范围	`a.equal_range(k)`	`pair<iterator, iterator>`如果`a`是可变的，否则`pair<const_iterator, const_iterator>`.

名称	表达式	语义	后置条件
默认构造函数	X() X a;	创建一个空容器，使用`key_compare()`作为比较对象。	容器的大小为`0`.
带比较器的构造函数	X(c) X a(c);	创建一个空容器，使用`c`作为比较对象。	容器的大小为`0`. `key_comp()`返回一个与`c`.
键比较	`a.key_comp()`	返回由`a`.
值比较	`a::value_compare()`	返回由`a`.	如果`t1`和`t2`是类型为`value_type`的对象，并且`k1`和`k2`是与其关联的键，则`a.value_comp()(t1, t2)`等价于`a.key_comp()(k1, k2)`.
下界	`a.lower_bound(k)`	返回一个指向键不小于`k`的第一个元素的迭代器。如果不存在这样的元素，则返回`a.end()`。	如果`a`包含任何与`k`具有相同键的元素，则`lower_bound`的返回值指向第一个这样的元素。
上界	`a.upper_bound(k)`	返回一个指向键大于`k`的第一个元素的迭代器。如果不存在这样的元素，则返回`a.end()`。	如果`a`包含任何与`k`具有相同键的元素，则`upper_bound`的第一个元素的迭代器，指向最后一个这样的元素的下一个位置。
相等范围	`a.equal_range(k)`	返回一个对，其第一个元素是`a.lower_bound(k)`，其第二个元素是`a.upper_bound(k)`.

key_comp()和value_comp()是常数时间。

删除元素是常数时间。

删除键是O(log(size()) + count(k)). [1]

删除范围是O(log(size()) + N)，其中N是范围的长度。[1]

查找是对数的。[1]

计数是O(log(size()) + count(k)). [1]

下界、上界和相等范围是对数的。[1]

的定义`value_comp`	如果`t1`和`t2`是类型为`X::value_type`和`k1`和`k2`是与这些对象关联的键，则`a.value_comp()`返回一个函数对象，使得`a.value_comp()(t1, t2)`等价于`a.key_comp()(k1, k2)`.
升序	排序关联容器中的元素始终按键升序排列。也就是说，如果`a`是排序关联容器，则`is_sorted(a.begin(), a.end(), a.value_comp())`始终为`true`.

[1] 这是比关联容器提供的保证强得多的保证。关联容器中的保证仅适用于平均复杂度；允许最坏情况复杂度更大。但是，排序关联容器提供了对最坏情况复杂度的上限。

[2] 此定义与关联容器中描述的语义一致。不过，它是一个更强的条件：如果a不包含任何具有键k的元素，则a.equal_range(k)返回一个空范围，指示如果这些元素存在则它们将位于的位置。关联容器需求仅声明返回值是任意空范围。