注意

请注意，本文尚未完成！您可以通过编辑此文档页面来提供帮助。

概述

简化版 (C++98 起)

template< class Key, /* ... */ >
class multiset;

详细

常规版 (C++98 起)

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
>
class multiset;

多态版 (C++17 起)

namespace pmr {
    template <class Key, class Compare = std::less<Key>>
    using multiset = std::multiset<Key, Compare,
                                   std::pmr::polymorphic_allocator<Key>>;
}

std::multiset 是一个已排序的关联容器，它包含一组已排序的对象。与 set 不同，它允许具有等效值的多个键。

技术细节

集合的技术定义

std::multiset 是一个关联容器，它包含一组已排序的 Key 类型对象。与 set 不同，它允许具有等效值的多个键。排序使用键比较函数 Compare 完成。

搜索、插入和删除操作具有对数复杂度 (O(size()))。

在标准库中使用 Compare 要求的所有地方，等效性是通过使用 Compare 中描述的等价关系来确定的。不精确地说，如果两个对象 a 和 b 都不小于另一个，则它们被认为是等效的：!comp(a, b) && !comp(b, a)。

自 C++11 起

比较等效的元素的顺序是插入顺序，并且不会改变。

std::multiset 符合 Container、AllocatorAwareContainer、AssociativeContainer 和 ReversibleContainer 的要求。

std::multiset

定义于

set

模板参数

pub	Key	存储键的类型。
pub	Compare	一个满足 Compare 的比较器类型。
pub	Allocator	负责分配和释放内存的分配器类型。必须满足 Allocator。

类型名称

pub	key_type	Key
pub	value_type	Key
pub	size_type	无符号整型（通常为 std::size_t ).
pub	difference_type	有符号整型（通常为 std::ptrdiff_t ).
pub	key_compare	Compare
pub	value_compare	Compare
pub	allocator_type	Allocator
pub	reference	value_type&
pub	const_reference	const value_type&
pub	pointer	Allocator::pointer(C++11 以前) std::allocator_traits<Allocator>::pointer(C++11 起)
pub	const_pointer	Allocator::const_pointer(C++11 以前) std::allocator_traits<Allocator>::const_pointer(C++11 起)
pub	iterator ❗	指向 value_type 的常量 LegacyBidirectionalIterator
pub	const_iterator ❗	指向 const value_type 的 LegacyBidirectionalIterator
pub	reverse_iterator	std::reverse_iterator<iterator>
pub	const_reverse_iterator	std::reverse_iterator<const_iterator>
pub	node_type (C++17 起)	节点句柄的一个特化，表示一个容器节点。

多重集的迭代器

iterator 被称为常量，因为无法修改它指向的值。这是因为修改迭代器指向的值可能会使多重集的内部结构失效，从而导致各种不正确和意外的行为。

成员类型别名 iterator 和 const_iterator 可能相同。这完全取决于实现。这意味着任何仅在迭代器类型上不同的重载函数/特化可能不正确，并可能导致ODR 违规。

成员函数

pub	(构造函数)	构造一个新集合。
pub	（析构函数）	析构一个集合。
pub	operator=	将一个集合赋值给另一个。
pub	get_allocator	返回关联的分配器。

迭代器

pub	begin cbegin (C++11 起)	返回指向开头的迭代器。
pub	end cend (C++11 起)	返回指向末尾的迭代器。
pub	rbegin crbegin (C++11 起)	返回指向开头的反向迭代器。
pub	rend crend (C++11 起)	返回指向末尾的反向迭代器。

容量

pub	empty	如果 set 为空则返回 true，否则返回 false。
pub	size	返回集合中的元素数量。
pub	max_size	返回最大可能的元素数量。

修饰符

pub	clear	清除集合的内容。
pub	insert	插入元素或节点（使用 .extract() 提取的）(C++17 起)。
pub	emplace (C++11 起)	就地构造新元素。
pub	emplace_hint (C++11 起)	使用提示（迭代器）就地构造元素。
pub	erase	擦除元素。
pub	swap	交换两个集合。
pub	extract (C++17 起)	从集合中提取节点（稍后可以插入到其他地方）。
pub	merge (C++17 起)	将两个集合合并在一起。

查找

pub	count	返回与特定键匹配的元素数量。
pub	find	搜索元素并返回指向该元素的迭代器，如果未找到则返回末尾迭代器。
pub	contains (C++20 起)	如果元素在 set 中则返回 true，否则返回 false。
pub	equal_range	返回与特定键匹配的元素范围。
pub	lower_bound	返回指向第一个不小于给定键的元素的迭代器。
pub	upper_bound	返回指向第一个大于给定键的元素的迭代器。

观察器

pub	key_comp	返回一个比较键的内部函数对象。
pub	value_comp	返回一个内部函数对象，该对象比较 value_type 类型对象中的键。

非成员函数

pub	operator== operator!= (C++20 中移除) operator< (C++20 中移除) operator> (C++20 中移除) operator<= (C++20 中移除) operator>= (C++20 中移除) operator<=> (C++20 起)	按字典顺序比较集合中的值。
pub	std::swap (std::multiset)	std::swap 算法的重载。
pub	std::erase_if (std::multiset) (自 C++20 起)	std::erase_if 算法的重载。

推导指南 (C++17 起)

点击展开

推导指南

// (1)
template<class InputIt,
         class Comp = std::less<typename std::iterator_traits<InputIt>::value_type>,
         class Alloc = std::allocator<typename std::iterator_traits<InputIt>::value_type>>
multiset(InputIt, InputIt, Comp = Comp(), Alloc = Alloc())
  -> multiset<typename std::iterator_traits<InputIt>::value_type, Comp, Alloc>;

// (2)
template<class InputIt, class Alloc>
multiset(InputIt, InputIt, Alloc)
  -> multiset<typename std::iterator_traits<InputIt>::value_type,
           std::less<typename std::iterator_traits<InputIt>::value_type>, Alloc>;

(1) 和 (2) 允许从迭代器范围进行推导

// (3)
template<class Key, class Comp = std::less<Key>, class Alloc = std::allocator<Key>>
multiset(std::initializer_list<Key>, Comp = Comp(), Alloc = Alloc())
  -> multiset<Key, Comp, Alloc>;

// (4)
template<class Key, class Alloc>
multiset(std::initializer_list<Key>, Alloc)
  -> multiset<Key, std::less<Key>, Alloc>;

(3) 和 (4) 允许从 std::initializer_list 进行推导

重载决议

为了使任何推导指南参与重载决议，必须满足以下要求

• InputIt 满足 LegacyInputIterator
• Alloc 满足 Allocator
• Comp 不满足 Allocator

注意

库确定类型不满足 LegacyInputIterator 的程度是未指定的，但至少

• 整型不符合输入迭代器的条件。

同样，它确定类型不满足 Allocator 的程度是未指定的，但至少

• 成员类型 Alloc::value_type 必须存在。
• 当作为未求值操作数处理时，表达式 std::declval<Alloc&>().allocate(std::size_t{}) 必须是格式良好的。

更多示例

基本操作

#include <iostream>
#include <set>

int main() {
  std::multiset<int> items = {3, 3, 1};

  items.insert(12);
  items.insert(12);

  std::cout << "Items: \n";
  for (const auto elem : items)
    std::cout << elem << '\n';

  return 0;
}

结果

Items: 1
3
3
12
12

#include <iostream>
#include <set>

int main() {
  std::multiset<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};

  for (auto i = numbers.begin(); i != numbers.end();) {
    if (*i % 2 == 0)
      i = numbers.erase(i);
    else
      ++i;
  }

  for (const auto i : numbers)
    std::cout << i << std::endl;

  return 0;
}

结果

1
3
5
7
9

#include <iostream>
#include <set>

int main() {
  std::multiset<char> letters = {'A', 'C', 'B'};
  std::multiset<char> letters2 = {'E', 'D', 'C'};

  letters.merge(letters2);

  for (const auto i : letters)
    std::cout << i << ' ';

  std::cout << '\n';

  for (const auto i : letters2)
    std::cout << i << ' ';

  return 0;
}

结果

A B C C D E