多关联容器


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

多关联容器是关联容器的一种，其中可能存在多个具有相同键的元素。也就是说，它是一个关联容器，不具有唯一关联容器的限制。

无，除了由关联容器定义的那些类型。

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

名称	表达式	类型要求	返回类型
范围构造函数	X(i, j) X a(i, j);	`i`和`j`是输入迭代器，其值类型可转换为`T` [1]
插入元素	`a.insert(t)`		`X::iterator`
插入范围	`a.insert(i, j)`	`i`和`j`是输入迭代器，其值类型可转换为`X::value_type`.	`void`

名称	表达式	前提条件	语义	后置条件
范围构造函数	X(i, j) X a(i, j);	`[i,j)`是一个有效的范围。	创建一个包含范围中所有元素的关联容器`[i,j)`.	`size()`等于从`i`到`j`的距离。范围`[i, j)`中的每个元素都存在于容器中。
插入元素	`a.insert(t)`		插入`t`到`a`.	的大小增加`a`由`1`。的值`a.count(t)`由`a`.
插入范围	`a.insert(i, j)`	`[i, j)`是一个有效的范围。	等价于`a.insert(t)`对于范围中每个迭代器指向的`t`对象。`[i, j)`每个元素都插入到`a`.	的大小增加`a`由`j - i`.

插入元素的平均复杂度最多为对数。

插入范围的平均复杂度最多为O(N * log(size() + N))，其中N是j - i.

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