C.2. 自定义增长策略

为了定义自定义增长策略，需要实现 Growth 特性。实现很简单。该特性包含两个方法。以下方法是必需的

fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> usize

请注意，它接受所有已分配的片段作为参数，并需要决定新片段的容量。

第二个方法 fn get_fragment_and_inner_indices<T>(&self, vec_len: usize, fragments: &[Fragment<T>], element_index: usize) -> Option<(usize, usize)> 有默认实现，如果策略允许高效地计算索引，则可以重写。

D. 示例

D.1. 与 std::vec::Vec 相似的使用

use orx_split_vec::*;

let mut vec = SplitVec::new();

vec.push(0);
vec.extend_from_slice(&[1, 2, 3]);
assert_eq!(vec, &[0, 1, 2, 3]);

vec[0] = 10;
assert_eq!(10, vec[0]);

vec.remove(0);
vec.insert(0, 0);

assert_eq!(6, vec.iter().sum());

assert_eq!(vec.clone(), vec);

let std_vec: Vec<_> = vec.into();
assert_eq!(&std_vec, &[0, 1, 2, 3]);

D.2. SplitVec 特定操作

use orx_split_vec::*;

#[derive(Clone)]
struct MyCustomGrowth;

impl Growth for MyCustomGrowth {
    fn new_fragment_capacity_from(&self, fragment_capacities: impl ExactSizeIterator<Item = usize>) -> usize {
        fragment_capacities.last().map(|f| f + 1).unwrap_or(4)
    }
}

impl PseudoDefault for MyCustomGrowth {
  fn pseudo_default() -> Self {
    MyCustomGrowth
  }
}

// set the growth explicitly
let vec: SplitVec<i32, Linear> = SplitVec::with_linear_growth(4);
let vec: SplitVec<i32, Doubling> = SplitVec::with_doubling_growth();
let vec: SplitVec<i32, MyCustomGrowth> = SplitVec::with_growth(MyCustomGrowth);

// methods revealing fragments
let mut vec = SplitVec::with_doubling_growth();
vec.extend_from_slice(&[0, 1, 2, 3]);

assert_eq!(4, vec.capacity());
assert_eq!(1, vec.fragments().len());

vec.push(4);
assert_eq!(vec, &[0, 1, 2, 3, 4]);

assert_eq!(2, vec.fragments().len());
assert_eq!(4 + 8, vec.capacity());

// SplitVec is not contagious; instead a collection of contagious fragments
// so it might or might not return a slice for a given range

let slice: SplitVecSlice<_> = vec.try_get_slice(1..3);
assert_eq!(slice, SplitVecSlice::Ok(&[1, 2]));

let slice = vec.try_get_slice(3..5);
// the slice spans from fragment 0 to fragment 1
assert_eq!(slice, SplitVecSlice::Fragmented(0, 1));

let slice = vec.try_get_slice(3..7);
assert_eq!(slice, SplitVecSlice::OutOfBounds);

// or the slice can be obtained as a vector of slices
let slices = vec.slices(0..3);
assert_eq!(1, slices.len());
assert_eq!(slices[0], &[0, 1, 2]);

let slices = vec.slices(3..5);
assert_eq!(2, slices.len());
assert_eq!(slices[0], &[3]);
assert_eq!(slices[1], &[4]);

let slices = vec.slices(0..vec.len());
assert_eq!(2, slices.len());
assert_eq!(slices[0], &[0, 1, 2, 3]);
assert_eq!(slices[1], &[4]);

D.3. 固定元素

除非从向量中删除元素，否则已推送到 SplitVec 的元素的内存位置 永远不会 改变，除非明确更改。

use orx_split_vec::*;

let mut vec = SplitVec::new(); // Doubling growth as the default strategy

// split vec with 1 item in 1 fragment
vec.push(42usize);

assert_eq!(&[42], &vec);
assert_eq!(1, vec.fragments().len());
assert_eq!(&[42], &vec.fragments()[0]);

// let's get a pointer to the first element
let addr42 = &vec[0] as *const usize;

// let's push 3 + 8 + 16 new elements to end up with 3 fragments
for i in 1..(3 + 8 + 16) {
    vec.push(i);
}

for (i, elem) in vec.iter().enumerate() {
    assert_eq!(if i == 0 { 42 } else { i }, *elem);
}

// now the split vector is composed of 11 fragments each with a capacity of 10
assert_eq!(3, vec.fragments().len());

// the memory location of the first element remains intact
assert_eq!(addr42, &vec[0] as *const usize);

// we can safely dereference it and read the correct value
// dereferencing is still unsafe for SplitVec,
// but the underlying guarantee will be used by wrappers such as ImpVec or SelfRefCol
assert_eq!(unsafe { *addr42 }, 42);

E. 性能测试

回想一下，使用分割向量的动机是为了从固定元素中获得好处，并在特定情况下避免标准向量的内存复制；而不是作为替代品。性能优化和基准测试的目的是确保关键操作的性能保持在期望范围内。似乎 SplitVec 满足这一点。经过优化，内置增长策略在增长、串行访问和随机访问基准测试中似乎与 std::vec::Vec 的性能相似，在追加基准测试中表现更好。

您可以在以下子节中找到每个基准测试的详细信息。下面表格中的所有数字都表示以毫秒为单位的时间。

E.1. 增长

您可以在 benches/grow.rs 中看到基准测试。

该基准通过逐个推送元素来比较向量的构建时间。基线是通过std::vec::Vec::with_capacity创建的向量，它对要推送的元素数量有完美的信息。比较的变体是没有关于容量先验知识的向量：std::vec::Vec::new，SplitVec<_, Linear>和SplitVec<_, Doubling>。

基线std_vec_with_capacity的性能比没有容量信息的std_vec_new快1.5到2.0倍，后者在增长时需要复制。如前所述，SplitVec的增长保证无复制，确保推送的元素保持固定。因此，预计其性能介于两者之间。然而，其性能几乎与std_vec_with_capacity相当，有时甚至更快。

由于Recursive策略的行为与Doubling策略完全相同，因此在此省略。关于其差异，请参阅随机访问和追加基准。

E.2. 随机访问

您可以在benches/random_access.rs中查看基准。

在此基准中，我们以随机顺序通过索引访问向量元素。这里基线再次是使用Vec::with_capacity创建的标准向量，它被与Linear和Doubling增长策略的SplitVec进行比较，这些策略专门针对随机访问进行了优化。此外，还包括了不提供常数时间随机访问操作的Recursive增长策略。

请注意，Recursive使用Growth特质的默认get_fragment_and_inner_indices实现，因此反映了没有专用访问方法的自定义增长策略的预期随机访问性能。

我们可以看到，Linear比Doubling慢。与标准向量相比，Doubling的随机访问性能最多慢50%，并且随着元素大小或元素数量的增加，差异趋于减小。