C语言大数组能否仅遍历已赋值元素且无需辅助数组？

完全不修改原数组内容、不使用任何额外辅助存储，就想精准找出10亿个int数组里你赋值过的那1000个元素——这在标准C语言里根本做不到。

道理很简单：C语言对栈上、malloc堆上申请的数组，从来不会给“未初始化的位置”打任何固定标记，这些位置存的全是随机遗留的垃圾值。你靠遍历看到的每个值，分不出来哪个是你特意赋值的，哪个是内存里本来就乱的垃圾值。

你说的稀疏矩阵方案，本质是把“哪个位置赋值过”的信息存在单独的辅助数组里——但要记录“哪些位置是已赋值的”，至少每个位置需要1bit的状态信息，这部分信息不一定非要放在独立的辅助数组里，完全可以藏在原数组的存储空间里，实现出来就完全不会有你提到的“要维护第二个辅助数组、要记辅助数组长度”的麻烦：

两个完全不需要辅助数组的实现思路 #

• 哨兵值标记法
  找一个你的业务逻辑里绝对不可能用到的特殊整数值，比如INT_MIN或者业务上根本不会出现的极值，当“没赋值”的标记。
  申请完10亿大小的数组，第一行代码就用memset把整个数组全刷成这个哨兵值；之后你给目标位置赋业务值的时候，自然就把对应位置的哨兵覆盖了。遍历的时候只要碰到等于哨兵值的位置直接跳过，剩下的就是你赋值过的元素。
  全程你只需要定义一个哨兵常量，不需要开存索引的辅助数组，也不需要记什么辅助数组的长度，扫原数组就行。
  唯一的限制：如果你的业务要用到int的全部取值范围，根本找不到一个完全不会用到的特殊值，这个方法就用不了。
• 元素高位复用当标记
  如果你实际要存的业务值占不满int的全部位，比如业务值都是小于2^28的整数，或者根本不会用到int的最高符号位，那就直接把每个int的最高4位/1位拿出来当“已赋值标记”。
  赋值的时候先把高位打上固定标记，再把实际业务值拼上去存；遍历的时候先检查每个元素的高位有没有标记，有标记的就把高位的掩码去掉，拿剩下的低位存的业务值处理。
  这个方法的所有状态信息都存在原数组自己的空间里，半点儿额外内存都不占，更不需要维护什么外部列表。
  同样有个限制：必须能从每个int的位宽里抠出至少1bit来当标记，要是你把int的32位全用来存业务数据，一点富余的位都没有，这个方法就实现不了。

千万不要碰的投机歪路 #

有些人想当然去读malloc在内存块头部存的元数据，想靠这个判断哪些位置写过值——这东西每个libc的实现都不一样，根本没有C语言标准保障，换个系统、换个编译器版本就直接坏了，写出来的东西根本没法上线。

内容的提问来源于stack exchange，提问作者Erwin Zangwill