为什么std::set是一个关联式容器？

Question

我查看了各种文本。唯一得到的东西就是set是一个包含排序和独特键的关联容器。现在如果没有值使用键进行映射，那么集合中的关联在哪里。

- cbinder

---

有趣的问题，我以前从未这样想过。集合中的条目与什么相关联？？我想是它们自己的存在。 - Neil Kirk

或许对于一个“集合（set）”，键和值是相同的？ - PaulMcKenzie

@PaulMcKenzie 你不喜欢 void 吗？ - Deduplicator

我喜欢认为“关联”是容器元素和其值之间的关系。相比之下，在序列容器中，元素是按其插入顺序进行标识的。 - Kerrek SB

@Kerrek SB，这就是我所想的...它在内部被存储为平衡二叉搜索树，需要logn时间进行搜索...所以我猜它只是一个列表的BST表示形式，只是为了获得logn的搜索时间。 - cbinder

@cbinder：我认为考虑实现是误导性的，没有帮助。关键在于，在关联容器中，容器成员资格由值确定，在序列容器中则由位置确定。 - Kerrek SB

Answer 1

一个容器是用于存储其他对象并负责管理其内含对象的内存使用的对象。

一个关联容器是一种有序容器，它能够根据键快速查找对象。

std::set 是一种关联容器，它包含一组按 Key 值排序的唯一对象。

那么什么使其成为关联容器？事实上，集合中的元素是通过其键而不是在容器中的绝对位置进行引用。当然，这个键就是元素本身。可以把它想象成一个地图，其中键和值是相等的，并且，在这种情况下消除了相同内容的重复副本。

那么无序集合呢？ std::unordered_set 符合容器、AllocatorAwareContainer 和 UnorderedAssociativeContainer 的要求。

- Carl

---

查找集合和映射的时间复杂度是对数级别的，这表明它们是基于树结构实现的。而无序等价物的查找时间复杂度是常数级别的，这表明它们是基于哈希表实现的。所以，嗯，映射和集合之间的区别在于值是否作为键或者你提供了键和值。 - Carl

Answer 2

有许多不同的思考方式，其中一些经常导致典型的鸡生蛋问题。

以 std::map 为例，按其接口规范，它是一个直观的关联容器。然而，您可以将 std::map 视为一组成对的 key:data，比较函数仅考虑存储元素的 key 部分并忽略 data 部分。从那个角度来看，"set"（std::set 或 std::unordered_set）可以被视为比 "map"（std::map 或 std::unordered_map）更通用和更基本的数据结构。也就是说，"set" 的功能覆盖了典型的关联容器存储 key:data 对的功能。换句话说，"set" 是关联容器的父类，仅出于这个原因，它本身可以被视为一个关联容器。

当然，有人可以争论说可以使用“map”来轻松实现“set”（通过使用相同的值作为key和data），这意味着“map”可以被视为比“set”更基本的数据结构。这就是我之前所提到的先有鸡还是先有蛋的情况。

- AnT stands with Russia

Answer 3

如果您认为集合是一种独立的数据结构，它不符合关联数据结构的定义，因为没有映射值。然而，当将集合视为映射的特殊情况时，映射（“关联”）值与键相同，它适合被称为关联容器。请注意，与集合相比，映射被认为是一种更主要的数据结构，因为可以使用映射来实现集合，但反之则不行。

- Srikanth

Answer 4

我们可以假设有两种类型的容器，一种是链表，另一种是关联容器。我们可以通过键选择任何关联容器的值，例如在简单数组中，您可以通过其位置选择任何值，即 arr[position] = value。这里，position 是 key。但是，对于链表，您无法这样做。

- Sohag