c++ - 从概念上理解容器上的位置访问操作

Question

容器上的位置访问操作的定义^†对我来说对于std::来说似乎非常简单 vector 、std::deque、std::list 和 std::forward_list。也就是说，访问集合中的第 k 元素包括获取存储在第 k 位置的元素在集合中^X。

例如，表达式vec[k-1]访问std::vector中的k^th code>，而 *std::next(lst.begin(), k-1) 对应于它的 std::list 对应项。

但是，当涉及到 std::set 或 std::unordered_set 等关联容器时，我不太清楚谈论位置访问操作是否真的有意义，因为我没有找到一种直接的方法来确定此类容器中任意位置第 k^th 的位置。

但是，我们仍然可以像上面显示的 std::list 示例一样继续，即，将迭代器带到关联容器的“第一个”元素(例如，由成员函数 begin())，然后将迭代器向前移动 k-1 次(例如，通过 std::next() )。

我观察到容器 std::vector、std::deque、std::list 和 std::forward_list 都是使用线性数据结构实现的，而通常作为二叉树实现的 std::set 则不是。因此，也许这个问题与容器实现的底层数据结构的线性有关。

有什么方法可以清楚地定义关联容器的位置访问操作的语义吗？或者此类访问操作不适用于吗？

---

^† 不要混淆搜索和访问操作。在搜索操作中，您正在集合中查找具有给定键的元素。

---

^X 这与执行此操作所需的运行时间无关(例如，std::list 是线性的，而不是 std::vector)或者是否没有专用的成员函数(例如，std::list中缺少下标运算符)来实现这一点。

Answer 1

您提到的容器类别之间的最大区别在于，第一个是序列容器，其中容器的用户明确确定将元素放置在何处，而后者是关联容器，其中结果顺序是根据元素的某些属性隐式确定的，以便可以通过键访问它们(std::map/std::unordered_map)/value (std::set/std::unordered_set) 有效。

这并不意味着在此类容器中通过“位置”进行访问是无用的 - 因为 std::set 保持其元素排序，其中的第 k 项std::set 是集合中第 k 个最小元素(尽管我确实想不出访问 std::unordered_set 的任何目的> 按位置 - 哈希通常不会产生任何特别有用的排序¹)。

除了这种概念上的区别之外，我认为访问 std::list 的第 k 元素与在 std::list 上执行相同操作之间没有任何大的操作差异。 code>std::set - 在这两种情况下，该操作都不是容器“ native ”支持的(例如，容器不支持 O(1) 随机访问)，并且您必须遍历它一次时的元素。即使在底层，遍历二叉树(例如 std::set 或 std::map 通常使用的二叉树)与跟踪链表中的链接也没有什么不同(例如在 std::list 中)。

---

1. 如果 std::hash 是一个加密哈希，它会“白化”原始数据，那么“访问随机排列的某些元素”可能会有一些无力的意义，但是 std::hash 只需要在类型范围内良好分布，因此例如整数are often hashed as themselves - 不是一个特别有趣的排列。