6. 有序数组

在很多场景下，我们需要数组元素是有序的。对于这类需求，有两种满足的方法：

  1. 让数组保持无序；在需要时，临时进行（部分）排序；

  2. 让数组本身保持有序；

排序需要时间。而数组排序时，大对象在数组空间内的拷贝/移动也代价高昂。因而，无论是临时性的排序，还是 让数组本身保持有序，都有两种选择：

  1. 对于小对象，可以让对象自身进行移动；

  2. 对于大对象，则最好使用索引进行排序。

对于元素本身保持无序，需要时临时进行排序的数组，可以通过 Sort 或者 SortObject 进行排序； 而对于自身需要维持有序的数组而言，本库提供了以简单 插入排序 为算法的有序数组。

6.1. OrderedObjectArray

OrderedObjectArray<T,N,COMPARE> 是一种维持数组元素自身有序的一种数组。

模版的第三个参数 COMPARE ，决定了数组元素的顺序。其本身的默认实现为 T::operator< ，但你可以 指定任何一种对比类型，比如：

struct Foo {
     int a;
     explicit Foo(int a) : a{a} {}
     ~Foo() { a = 10; }
 };

 auto FooLess = [](Foo const& l, Foo const& r) {
     return l.a > r.a;
 };

 OrderedObjectArray<Foo, 10, decltype(FooLess)> array;

6.2. IndexedOrderedArray

IndexedOrderedArray<T,N,COMPARE> 通过 索引 来维持数组元素顺序， 而数组元素本身是完全 无序的，甚至是非连续的。这样保证了数组元素一旦在某个 slot 上创建，在整个生命周期存在期间，完全不会 移动位置（无论是删除操作，还是 Replace 相关操作）。取而代之，变化和移动的，是数组元素的索引。

因而，IndexedOrderedArray 要比 OrderedObjectArray 耗费更多的空间（索引所需的空间，以及空间占用位图）， 但在维持有序方面，性能更高。

注意

事实上，ObjectArray 也有它的索引版本 : IndexedArray 。它们都是将 ScatteredArray 当作一个 数组空间分配器，并通过索引数组来保持 Contiguous 属性。

这样的做法，可以让需要频繁修改，比如进行 Append , Erase , Sort , Rotate 等操作，但同时对象 的 move 成本又比较大的数组，具备性能优势。

6.3. 自动选择

上述两种有序数组，提供了完全一致的接口。程序员拥有根据需要自主选择的权利。

但如果你有选择困难症，则可以使用 OrderedArray<T,N,COMPARE> ，它会根据一定的条件，自动从二者之中选择一个（而条件是可以集中进行统一维护）。

6.4. 接口

对于有序数组而言，由于本身已经有序，因而不再提供 Sort 相关的任何接口，也不能创建 SortObject 。除此 之外，它们拥有与普通数组完全一致的接口。