@
raptor 可能你学得语言还是不够多;你的说法显然不对:C++ 自带的数组和“字典”(std::unordered_map) 都用 [] 操作符访问元素。
严格来讲,理解偏差完全就不该是 PHP 的锅;问题来自数组(array) 这个概念本身。
array 这玩意儿作为数据结构在早年( 1950 年代)就极其模糊,但硬要说一般的外延,就是所谓的关联数组(associative array) :一个 key 对应到作为数组元素的 value 的映射。
用类 ALGOL 语言的习惯来讲,就是能用 [] 的里面塞 key 的东西,所谓 subscritable 。
至于这个 key 是个整数,来使 [] 里面放 key 取得元素能有明确 O(1) 时间复杂度的随机访问,那是实现细节。用连续存储的线性表实现叫向量(vector) 。
特别地,向量一般具有确定的静态空间上界。不具有上界限制的线性表叫串(string) 。(虽然严格来讲,数学上的串不一定在乎复杂度要求,不过不少算法实际上隐含了要求。)
其它实现可以有不同的计算复杂度性质。
例如二叉搜索树(BST) 可以实现平均 O(log n) 的元素访问,同时在插入和删除元素上比向量更优化。这种索引结构在 C++ 中叫 map ,会跟数学上的映射(map) 产生歧义;之后的一些其它语言改叫字典(dictionary) 。
而散列表(hash table) 能实现平摊(amortized) O(1) 的访问和增删操作。
另外还有 Illffe vector 等特定于实现而不常被应用直接使用的数据结构。
向量因为早年机器实现的开销较小的关系曾经流行过,例如 B 语言自带支持。然而自从抄了 B 的 C 把向量硬叫做数组以后,到处都乱了。
C 的流行影响了很多语言,导致这些语言设计中的词汇表混乱——该叫向量的不叫向量而叫数组,别的就顺带乾坤大挪移了。典型的像 C++ ,vector 被用于原本叫做 string 的数据结构上,而 string 则用作特指混了 char_traits 这种二道贩子实现细节私货的特定实现。
以 C 为中心在另一方面也是无耻的;考虑 1957 年就开工的 APL ,(虽然代码模样不咋地)人家混饭吃的核心、不知比你 vector 屌多少倍的 array 就这样被偷换概念了,好意思不?
所以 PHP 这种设计反而是文艺复兴,恢复了 array 历史上应有的本来面目。
题外话:
1.其实向量的 O(1)也就是形式上的。所以广泛使用向量实现数组的语言嘛……
像 C 都没保证下标访问的复杂度,所以实际上也没禁止实现使用树或者散列表实现内建数组。
C++倒是隐含了随机访问迭代器 O(1)访问要求,考虑到和内建指针以及数组的关系,实现基本别无选择。但这也不是正经的限制。
更要命的是一旦放在主存上,主流环境根本无法严格实现。
典型的宿主(hosted) 实现,不保证实时性,自然不直接提供这种物理上保证 O(1)的例程——比如程序跑一半可能切出去调度了。
即便不考虑那么流氓的情况,现代 CPU 上的缺页中断里可以允许用户编码明显不 O(1)的非平凡程序,现实也很可能一个程序跑一半换页了结果一个访问突然卡上几百万倍;或者可能有更倒霉的,比如正好放 swap 的机械硬盘有坏道但宿主系统装作系统完整可用的情况——实际上也根本没保证可终止,更别说 O(1)了。
2.如果忽略修改之类的副作用而只允许构造和访问元素,一元函数(更确切地,映射)和 subscritable 形式的数组同构,都可以用 → 类型构造器表达的类型为其定型(typing) 。所以纯函数式语言不强调数组,是根本不需要。