代码之家 › 专栏 › 技术社区 › jfMR

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

terminology containers stl data-structures c++

jfMR · 技术社区 · 6 年前

什么定义的一个 位置访问操作 ^阿西在一个容器上可以看起来,似乎是非常直接的,当谈到 std::vector , std::deque , std::list 和 std::forward_list . 这就是说, 访问K ^钍要素 在一个集合中包含 获取存储的元素 在位置K ^钍 在集合中 ^X .

例如,表达式 vec[k-1] 访问 k ^钍在一个 STD::载体 而 *std::next(lst.begin(), k-1) 对应于其 STD::列表 对应的。

然而,当涉及到 关联容器 喜欢 std::set 或 std::unordered_set 我不太清楚 位置访问操作 实际上是有道理的,因为我找不到一个直接的方法来确定任意位置k的位置。 ^钍在这样的容器中。

但是,我们仍然可以继续 STD::列表 上面所示的示例,即,将迭代器带到关联容器的“first”元素(例如,成员函数返回的迭代器 begin() )然后向前移动迭代器 K-1 时间(例如,通过 std::next() )

我注意到集装箱 STD::载体 , 性病:德克 , STD::列表 和 标准::转发列表 都是用 线性的 数据结构,而 STD::设置 通常实现为二叉树,而不是。所以,也许这个问题与 线性度 容器实现的基础数据结构。

是否有任何方法可以清楚地定义关联容器的位置访问操作的语义?或者是这样的访问操作 不适用 对他们?

^阿西不要混淆搜索和接近操作。在搜索操作中,您将在集合中查找具有给定键的元素。

^X 这与运行时间无关(例如,线性 STD::列表 而不是 STD::载体 )或者是否没有专用的成员函数(例如,在 STD::列表 )为了实现这一点。

2 回复 | 直到 6 年前

Matteo Italia 6 年前

你提到的集装箱类别的最大区别在于序列容器,容器的用户明确地确定元素的放置位置,而后者是 联想的 容器,其中的结果顺序是通过元素的某些属性隐式确定的,以便可以通过键访问它们。( std::map / std::unordered_map /值 std::set / std::unordered_set )有效。

这并不意味着在这样的容器中通过“位置”访问是无用的-作为 STD::设置 保持元素排序,k ^钍 A中的项目 STD::设置 是K ^钍集合中最小的元素(尽管实际上我无法想到访问 std::无序集 按位置-哈希通常不会产生任何特别有用的排序 ^一 )

除了这个概念上的区别,我看不到访问k之间有什么大的操作上的区别。 ^钍 A的元素 std::list 在一个 STD::设置 -在这两种情况下,操作都不是由容器“本机”支持的(如中所述,容器不支持O(1)随机访问),您必须一次遍历一个元素。即使在引擎盖下,也要走一棵二叉树,就像那些通常被 STD::设置 或 STD::地图 与跟踪链接列表中的链接(如 STD::列表 )

如果 std::hash 是一个密码散列,它“清空”原始数据,它可能有一些弱的意义,如“访问某个随机排列的元素”,但是 STD::哈希 只是需要在类型范围内均匀分布,例如整数 are often hashed as themselves -不是特别有趣的排列。

Oliv 6 年前

如您所指的列表,可以定义k ^钍元素,指针指向K的指针旁边的指针指向的元素。 ^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容器都是等效的。