排序和 nsTArray

std::sort 及其相关函数

鉴于排序很复杂，为了将最难的部分留给其他人，我们基于 std::sort 及其相关函数实现 nsTArray 的排序函数。

标准排序函数被实现为类型安全的模板，允许进行积极的编译器优化（主要是内联）。标准库提供了三种不同的排序实现

std::sort 或 nsTArray<T>::Sort

优点

• 它提供了快速平均性能和（渐近）最佳的最坏情况性能。

注意事项

• 它可能会对完全相同的元素调用比较函数，并期望在这种情况下返回 false（“a 不小于 a”）；

• 被认为相等的元素的顺序可能会相对于初始状态发生变化。

• 它最终使用在元素类上定义的移动赋值/构造运算符，如果它们不是平凡的，则可能会产生意外的副作用。

std::make/sort_heap

我们没有在 nsTArray 中为堆排序提供包装器。假设 std::sort 始终是更好的选择。

std::stable_sort 或 nsTArray<T>::StableSort

优点

• 它保留了排序前和排序后相等元素的顺序。

注意事项

• 可能会尝试（不可靠地）分配额外的临时内存以减少其开销。

• 可能很慢，如果无法使用额外内存，则为 O(N·(log(N)²))。

一些实现说明

需要说明的是，不同的使用场景可能仍然需要不同的方法。虽然 std::sort 的 O(n*log(n)) 从算法的角度来看是最佳的，但使用的元素类的设计或调用 Sort 本身的频率会显着影响性能，特别是对于较高的 N。让我们看看一些典型用例。

如果列表始终保持排序状态

• 如果项目的追加是稀疏的 - 使用 InsertElementSorted，它具有 O(log(N)) 的复杂度来确定位置，但在每次插入时最终可能需要最多 N-1 个元素移动（或等效的 memmove）。

• 如果您改为批量添加 N 个项目，则应在之后只排序一次。检查外部循环，这些循环可能仍会导致多次调用 Sort 而在两次调用之间从未读取数组。

• 如果更改频率高且随机 - 考虑从 nsTArray 切换到 LinkedList。

如果我们只是偶尔需要一个短暂的排序表示

• 元素小而简单 - 只需在需要时对数组本身进行排序。

• 否则，使用包含 T* 或 RefPtr<T> 或原始数组索引的临时列表，并对其进行排序。

如果项目仅由列表持有

• 列表的项目 T 非常庞大且/或复杂 - 考虑使用 UniquePtr<T> 列表，并在每次插入时显式创建对象。如果对列表的更改频率不高，则单个分配和删除的开销可能可以承受（并且与 LinkedList 相当）。

如果比较函数代价很高

• 有一种简单的方法可以将计算转换为标量 - 预先计算它，并为此信息提供一个额外的字段或一个额外的数组。

如果排序预计是稳定的

• 由比较器认为相等的元素预计会保持其相对顺序 - 不要尝试自己向比较器添加聪明的条件，而是使用 nsTArray<T>::StableSort（或 std::stable_sort）以获得最佳性能。

请记住：排序条件必须在各方面保持稳定

std::sort 对不稳定的条件反应非常糟糕。比较器必须

• 在移动数组中的条目之前和之后产生相同的结果。

• 如果输入元素只是交换，则产生相反的结果（除了相等）。

• 能够容忍被调用来比较完全相同的元素本身。

• 比较函数本身不得以可能影响比较结果的方式更改任何元素的状态。

• 在排序执行期间，没有其他线程应以可能影响比较结果的方式更改数组中或元素引用的对象。

请记住：对 nsTArray 的修改操作不是原子的

当然，这对于 Sort 和 StableSort 也是如此。如果您想从不同的线程使用相同的 nsTArray 实例，则需要自行确保同步。