什么是随机访问??

时间:2022-07-11 17:39:23
我看书上写,链表没有提供对元素的随机访问,但是向量和双端队列提供随机访问。。这个随机访问是什么意思??

5 个解决方案

#1


例如vector
iterator i = v.begin() + N;
得到v中第N + 1个元素的迭代器。
vector的迭代器是随机访问的迭代器。因此可以直接通过+N的方法。

而list不是随机访问的,同样得到第N+1个元素的话就不能用+N的方法。
iterator i = l.begin();
std::advance(i, N);

#2


引用 1 楼 Jinhao 的回复:
例如vector
iterator i = v.begin() + N;
得到v中第N + 1个元素的迭代器。
vector的迭代器是随机访问的迭代器。因此可以直接通过+N的方法。

而list不是随机访问的,同样得到第N+1个元素的话就不能用+N的方法。
iterator i = l.begin();
std::advance(i, N);

那+N和advance()在具体实现上,有什么区别?

#3


随机访问是说你可以随意访问该数据结构中的任意一个节点,假设该数据结构有10个节点,你可以随意访问第1个到第10个节点。
对于列表而言,如果其存在10个节点,如果你要访问第5个节点,你只能从列表的头或者尾,依次遍历相邻的每一个节点;
对于vector而言,你可以直接利用[]操作符,直接访问[4],不需要遍历其他的节点。
这就是随机访问。

#4


一步直接得到该数据的首地址

#5


比如first是第一个元素的地址,现在想访问第N个元素。

随机访问:直接first+N,便可以得到第N个元素的地址,因为这些相邻元素是按顺序连续存储的。
比如普通数组就是可随机访问的。

而链表不支持随机访问,链表存储的元素,它们的存储地址也不是连续的,是随机的。
要想访问第N个元素,只能从second = first->next遍历第2个元素,然后再three = first->next遍历第3个元素... 这样一直到第N个元素。所以这样的访问速度就没有随机访问快。

#1


例如vector
iterator i = v.begin() + N;
得到v中第N + 1个元素的迭代器。
vector的迭代器是随机访问的迭代器。因此可以直接通过+N的方法。

而list不是随机访问的,同样得到第N+1个元素的话就不能用+N的方法。
iterator i = l.begin();
std::advance(i, N);

#2


引用 1 楼 Jinhao 的回复:
例如vector
iterator i = v.begin() + N;
得到v中第N + 1个元素的迭代器。
vector的迭代器是随机访问的迭代器。因此可以直接通过+N的方法。

而list不是随机访问的,同样得到第N+1个元素的话就不能用+N的方法。
iterator i = l.begin();
std::advance(i, N);

那+N和advance()在具体实现上,有什么区别?

#3


随机访问是说你可以随意访问该数据结构中的任意一个节点,假设该数据结构有10个节点,你可以随意访问第1个到第10个节点。
对于列表而言,如果其存在10个节点,如果你要访问第5个节点,你只能从列表的头或者尾,依次遍历相邻的每一个节点;
对于vector而言,你可以直接利用[]操作符,直接访问[4],不需要遍历其他的节点。
这就是随机访问。

#4


一步直接得到该数据的首地址

#5


比如first是第一个元素的地址,现在想访问第N个元素。

随机访问:直接first+N,便可以得到第N个元素的地址,因为这些相邻元素是按顺序连续存储的。
比如普通数组就是可随机访问的。

而链表不支持随机访问,链表存储的元素,它们的存储地址也不是连续的,是随机的。
要想访问第N个元素,只能从second = first->next遍历第2个元素,然后再three = first->next遍历第3个元素... 这样一直到第N个元素。所以这样的访问速度就没有随机访问快。