本文介绍了一种名为“段数组”的数据结构，适用于替代动态数组，具有稳定的指针特性，并能与内存池分配器良好配合。其核心思想是将数据存储在多个连续段中，每段长度是前一段的两倍，仅在需要时分配新段，并将指针保存在固定大小的数组中。该结构不仅适用于C语言，也可用于Zig、Rust或C++等其他语言。

标题：C语言中的一种快速、可增长且具有稳定指针的数组

主要内容：

本文介绍了一种名为“段数组”（Segment Array）的数据结构，它可以替代动态数组，具有稳定的指针，并且与arena allocators兼容。这种数据结构在不同的编程语言中都有应用，如Zig、Rust或C++。

核心概念： 段数组将数据存储在多个连续的段中，每个段的长度是前一个段的两倍。新段仅在需要时分配，其指针保存在一个固定大小的数组中。与标准数组不同，段数组中的指针始终有效，因为数据项不会被移动。这种布局还允许在常数时间内访问任何索引。

实现细节： 段数组的实现包括一个C结构体，其中包含段的数量、已使用的段数和一个固定大小的段指针数组。段的大小通常是2的幂次方，这使得计算索引时可以使用快速的位移操作。段数组的容量可以通过调整第一个段的大小来保持为2的幂次方。

使用示例： 段数组提供了一个简洁的API，可以方便地添加、获取和遍历数据项。例如，可以创建一个存储结构体的段数组，并通过宏来获取和遍历数据项。

与其他数据结构的比较： 段数组在可增长性、与arena allocator的兼容性、随机访问和连续性方面与其他数据结构（如固定大小数组、动态数组、分块链表、混合方法和虚拟内存数组）有不同的权衡。段数组的平均内存效率为75%。

结论： 段数组是一种快速、可增长、稳定且与arena allocator兼容的数据结构，可以在不到120行的代码中实现。作者提供了单头文件的库实现，并鼓励读者使用和反馈问题。

参考链接： - 段数组实现 - Arena Allocator

评论内容主要围绕数据结构的实现、优缺点以及替代方案展开，以下是主要观点总结：

1. 数据结构的连续性问题：

   • 评论5和评论10指出，该数据结构不连续，可能影响缓存预取和迭代性能。
     • "Can we really call it an array if it's not contiguous?"（评论5）
     • "One frequent reason to use an array is to iterate the items. In those cases, non-contiguous memory layout is not ideal."（评论10）

2. 命名与语义争议：

   • 评论9认为应将其称为“列表”而非“数组”，因为其行为不符合数组的语义。
     • "This is really clever but better to call this a list rather than an array."（评论9）

3. 实现细节与优化：

   • 评论6提到宏的使用过于复杂，且clz指令未出现在反汇编中，可能被编译器优化。
     • "The level of 'trickery' with the macros becomes a bit much."（评论6）
   • 评论4建议增加最小段大小的构造函数参数，以优化缓存行为。
     • "I do wonder if it would be useful to be able to skip even more smaller segments."（评论4）

4. 替代方案与类似结构：

   • 评论2、评论8和评论14分别推荐了plf::colony、Zig的std.SegmentedList和Rope数据结构作为替代方案。
     • "Readers might also find plf::colony interesting."（评论2）
     • "Zig has this as std.SegmentedList, but it can resize the segment array dynamically."（评论8）
     • "Another similar data structure which has a balanced tree is the Rope."（评论14）

5. 潜在问题与局限性：

   • 评论12质疑指数级分段大小的适用性，认为可能导致大量空间浪费。
     • "Under what conditions is exponential segment sizing preferable to fixed size segments?"（评论12）
   • 评论13指出该结构在哈希表中的应用可能存在问题，因为需要重新哈希所有元素。
     • "The hash table won't provide stable pointers, given that you would need to rehash every element as the table grows."（评论13）

6. 编译与兼容性问题：

   • 评论7和评论11提到示例代码无法编译，且该项目仅支持C23。
     • "The example code doesn't seem to compile."（评论7）
     • "It's c23 only tho (bc of typeof)?"（评论11）

7. 虚拟内存的应用：

   • 评论3和评论9提到可以利用虚拟内存实现可调整大小的向量，并确保指针稳定。
     • "You can also use virtual memory for a stable resizable vector implementation."（评论3）
     • "I've abused virtual memory systems to block off a bunch of pages after my array."（评论9）

总结：评论中既有对该数据结构创新性的认可，也对其连续性、命名、实现细节和适用性提出了质疑，同时推荐了多种替代方案。