注意

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

概述

简化版 (C++98 起)

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

详细

常规版 (C++98 起)

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

多态版 (C++17 起)

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

std::set 是一个有序的关联容器，存储唯一的对象，默认按升序排列。

技术细节

set 的技术定义

std::set 是一个关联容器，包含一个排序的唯一 Key 类型对象的集合。排序使用键比较函数 Compare 完成。搜索、删除和插入操作具有对数复杂度。

集合通常实现为红黑树。

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

std::set 满足 Container、AllocatorAwareContainer、AssociativeContainer 和 ReversibleContainer 的要求。

std::set

定义于

set

模板参数

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

类型名称

公有	key_type	Key
公有	value_type	Key
公有	size_type	无符号整型（通常为 std::size_t ).
公有	difference_type	有符号整型（通常为 std::ptrdiff_t ).
公有	key_compare	Compare
公有	value_compare	Compare
公有	allocator_type	Allocator
公有	reference	value_type&
公有	const_reference	const value_type&
公有	pointer	Allocator::pointer(C++11 以前) std::allocator_traits<Allocator>::pointer(C++11 起)
公有	const_pointer	Allocator::const_pointer(C++11 以前) std::allocator_traits<Allocator>::const_pointer(C++11 起)
公有	iterator ❗	指向 value_type 的常量 LegacyBidirectionalIterator
公有	const_iterator ❗	指向 const value_type 的 LegacyBidirectionalIterator
公有	reverse_iterator	std::reverse_iterator<iterator>
公有	const_reverse_iterator	std::reverse_iterator<const_iterator>
公有	node_type (C++17 起)	节点句柄的一个特化，表示一个容器节点。
公有	insert_return_type (C++17起)	描述插入 node_type 结果的类型，它是 template < class Iter, class NodeType > struct /* unspecified */ { Iter position; bool inserted; NodeType node; }; 使用模板参数 iterator 和 node_type 实例化的特化。

Set 的迭代器

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

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

成员函数

公有	(构造函数)	构造一个新的 set。
公有	（析构函数）	销毁一个 set。
公有	operator=	将一个 set 赋值给另一个 set。
公有	get_allocator	返回关联的分配器。

迭代器

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

容量

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

修饰符

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

查找

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

观察器

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

非成员函数

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

推导指南 (C++17 起)

点击展开

推导指南

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

// (2)
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>>
set(InputIt, InputIt, Comp = Comp(), Alloc = Alloc())
  -> set<typename std::iterator_traits<InputIt>::value_type, Comp, Alloc>;

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

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

// (4)
template<class Key, class Alloc>
set(std::initializer_list<Key>, Alloc)
  -> set<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::set<int> unique_item_id = {3, 3, 1};

  unique_item_id.insert(12);
  unique_item_id.insert(12);

  std::cout << "Unique items id's:\n";
  for (const auto elem : unique_item_id)
    std::cout << elem << '\n';

  return 0;
}

结果

Unique items id's:
1
3
12

#include <iostream>
#include <set>

int main() {
  std::set<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::set<char> letters = {'A', 'C', 'B'};
  std::set<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 D E
C