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

Question

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

中的第k位置

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

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

但是，我们仍然可以像上面显示的 std::list 示例一样继续，即，将迭代器带到关联容器的 "first" 元素（例如，成员返回的迭代器function begin()) 然后将迭代器向前移动 k-1 次（例如，通过 std::next()）.

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

有没有办法明确定义关联容器的位置访问操作的语义？或者这样的访问操作对他们不适用？

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

^X 这与这样做所花费的运行时间无关（例如，对于 std::list 是线性的，而不是对于 std::vector) 或者是否没有专门的成员函数（例如 std::list 中缺少下标运算符）来实现它。

Answer 1

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

这并不意味着在这样的容器中通过 "position" 访问是无用的 - 因为 std::set 保持其元素排序，第 k^th 项在 std::set 中是集合中的第 k^th 个最小元素（尽管我确实想不出按位置访问 std::unordered_set 的任何目的 - 哈希通常不会'不会产生任何特别有用的排序¹).

除了这个概念上的区别，我看不出访问 std::list 的第 k^th 元素和对 std::set - 在这两种情况下，容器都不支持 "natively" 操作（例如，容器不支持 O(1) 随机访问），您必须一次遍历一个元素。即使在幕后，走一棵二叉树，例如 std::set 或 std::map 通常使用的二叉树，与跟随链表中的链接（例如 std::list 中的链接）并没有什么不同。

如果 std::hash 是一个密码散列，"whites" 出原始数据，它可能像 "accessing some element of a random permutation" 一样没有意义，但是 std::hash 是必需的在类型范围内很好地分布，例如整数 are often hashed as themselves - 不是特别有趣的排列。

Answer 2

正如您指向列表的那样，可以定义第 k^th 元素，即指针指向的元素，它紧挨着指向 k[=19 的指针=]th-1个元素.

您可能还会注意到，在数论中，数字也被定义为序列： 1是0旁边的数字，2是1旁边的数字，等等...

因此可以创建由指向容器元素的指针及其下一个操作形成的结构的同构，与 +1 操作的自然数结构：

p0:=begin()                               O
  |next                                   |increment
p1:=next(begin())   --isomorphic to-->    1:=increment(0)
  |next                                   |increment
p2:=next(next(begin()))                   2:=increment(increment(0))
  .                                       .
  .                                       .

这种同构可以用于任何容器，只要它们提供开始指针。所以，为了位置的概念，任何STL容器都是等价的。

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

Conceptually understanding positional access operations on containers

c++

containers

stl

terminology

data-structures