ruby 数组是如何在内部实现的(主要是在 CRuby 中，但欢迎任何其他信息)？
它们是像 C++ 向量那样可增长的数组还是基于列表？ shift/unshift 和按索引访问元素的复杂性如何？
最佳答案
它们是“在最后增长”的可增长数组。
shift 是 O(1)，unshift 是 O(n) 并且通过索引访问是 O(1)。据我所知，这适用于所有 ruby 实现，但它绝对适用于 MRI。
更新:最初写完这个答案后，Ruby 是 enhanced使 unshift 摊销 O(1)。增强数组在Ruby 2.0.0之后，shift、unshift、push 和 pop 都是 O(1) 或摊销 O(1)。
关于ruby 数组内部结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7310015/