时间圣使·凡 @ 2023-07-10 20:55:27
RT 我用vector超时，童靴说要用链式前向星，为啥链式前向星更快捏？
by catandcode @ 2023-07-10 21:31:47
可以看一下这篇文章
by reveal @ 2023-07-10 21:48:36
@catandcode 你在扯淡
by catandcode @ 2023-07-10 21:59:03
@reveal 对不起，如果有错误欢迎指出，我的了解也不太多。
by reveal @ 2023-07-10 22:20:54
@catandcode 关于链式前向星与 vector 的存图的一些测试可见 UOJ。
一般而言，vector 的顺序遍历性能要优于非连续存储的链式结构，其性能问题在于 push_back 的动态扩张。其采取的是倍增扩张以保证均摊
一般而言，对 vector 进行恰当的 resize 与 reserve 可以避免其动态扩张（在 OI 范围内，简单而言，“恰当”定义为应使得 vector 后不应再进行任何扩张），之后其性能与静态数组无异（汇编码相同）。
值得注意的是，多维 vector 的效率是极差的，因为第二维的各个 vector 之间内存并不连续。
cppreference
by catandcode @ 2023-07-11 06:59:11
@reveal 我理解浅薄了，感谢。@时间圣使·凡 对 lz 的错误指导表示抱歉
by 时间圣使·凡 @ 2023-07-11 18:10:49
@reveal @catandcode 阿里嘎多