Android Utils 之 Vector 学习笔记（二）—— SortedVectorImpl 代码分析
卫昊东
上一篇笔记中，分析了最底层的抽象类 VectorImpl 中的几个重点函数实现方法。可以看到在那个类中，基本上所有 Vector 应有的操作都已经实现好了。
而 SortedVectorImpl 则基于此，又针对 Sorted 这一特性而增加了一些底层操作，接下来就分析分析相关的代码实现。
相关文章
- Android Utils 之 Vector 学习笔记（一）—— VectorImpl 代码分析
- Android Utils 之 Vector 学习笔记（二）—— SortedVectorImpl 代码分析
- Android Utils 之 Vector 学习笔记（三）—— Vector 与 SortedVector 代码分析
- Android Utils 之 Vector 学习笔记（四，完结）—— KeyedVector 与 DefaultKeyedVector 代码分析
SortedVectorImpl
类定义
文件路径：system\core\libutils\include\utils\VectorImpl.h
概览：
indexOf（第 11 行）：用于查找指定元素的位置。orderOf（第 14 行）：用于确定元素应插入的位置。add（第 17 行）：用于将元素加入 Vector 中正确的位置（如果已经有了，则覆盖）。merge（第 20、21 行）：用于合并 Vector。remove（第 24 行）：用于删除指定元素。do_compare（第 27 行）：纯虚函数，留给子类实现，应是用于确定比较规则的函数。_indexOrderOf（第 30 行）：用于确定元素应插入的位置（orderOf的具体实现），其返回值表示元素所在位置（若无此元素则返回错误码），而参数order则返回所求的位置。- 第 34~45 行：定义了关于增删查找之类的基本操作，但注释有提到，这些函数不会进行实现，因为它们在
SortedVector这样的结构中不会提供给外部使用。
class SortedVectorImpl : public VectorImpl
{
public:
SortedVectorImpl(size_t itemSize, uint32_t flags);
explicit SortedVectorImpl(const VectorImpl& rhs);
virtual ~SortedVectorImpl();
SortedVectorImpl& operator = (const SortedVectorImpl& rhs);
//! finds the index of an item
ssize_t indexOf(const void* item) const;
//! finds where this item should be inserted
size_t orderOf(const void* item) const;
//! add an item in the right place (or replaces it if there is one)
ssize_t add(const void* item);
//! merges a vector into this one
ssize_t merge(const VectorImpl& vector);
ssize_t merge(const SortedVectorImpl& vector);
//! removes an item
ssize_t remove(const void* item);
protected:
virtual int do_compare(const void* lhs, const void* rhs) const = 0;
private:
ssize_t _indexOrderOf(const void* item, size_t* order = 0) const;
// these are made private, because they can't be used on a SortedVector
// (they don't have an implementation either)
ssize_t add();
void pop();
void push();
void push(const void* item);
ssize_t insertVectorAt(const VectorImpl& vector, size_t index);
ssize_t appendVector(const VectorImpl& vector);
ssize_t insertArrayAt(const void* array, size_t index, size_t length);
ssize_t appendArray(const void* array, size_t length);
ssize_t insertAt(size_t where, size_t numItems = 1);
ssize_t insertAt(const void* item, size_t where, size_t numItems = 1);
ssize_t replaceAt(size_t index);
ssize_t replaceAt(const void* item, size_t index);
};具体实现
文件路径：system\core\libutils\VectorImpl.cpp
这个类的实现部分内容比较少，也比较简单。
我认为此处值得关注的是：
- 位置查找函数：
_indexOrderOf - Vector 合并函数：
merge
查找函数分析
查找逻辑：由于元素已经是排好序的，所以可以直接采用二分法进行查找。若查找不到指定元素，则将最终位置通过 order 返回，且函数返回值为错误码 NAME_NOT_FOUND。若查找到元素，则返回其位置。
代码分析：
- 第 8 行：变量
err作为函数最终的返回值。 - 第 9 行：变量
l表示当前需查找的区间的下界。 - 第 10 行：变量
h表示当前需查找的区间的上界，此处size是父类函数，用于返回当前 Vector 的大小。而由于 Vector 下标从0开始，size - 1才是其真正上界。 - 第 11 行：变量
mid表示当前查找区间的中值。 - 第 12 行：指针
a指向当前 Vector 的首地址（通过父类函数arrayImpl获取）。 - 第 13 行：变量
s表示单个元素的大小（通过父类函数itemSize获取）； - 第 14~26 行：这部分是二分查找的具体实现。
- 进入的循环条件为，当前下界小于等于上界。
- 当前中值的计算公式为
mid = l + (h - l) / 2，除法应是向下取整，如果区间元素数量为偶数，则计算出的中值应偏向下界。 - 指针
curr指向中值所对应的元素地址。 - 通过
do_compare（该函数由子类具体实现）比较curr与传入的指定元素item，这里分为三种情况。 - 若
curr = item，则查找成功，将变量l与err都赋值为mid（即成功查找时的下标）。 - 若
curr < item，则需要继续往上界方向查找（修改当前下界l = mid + 1）。 - 若
curr > item，则需要继续往下界方向查找（修改当前上界h = mid - 1）。
- 第 27 行：若传入的参数
order非空（当不需要这个位置信息时，可以设置为空，或者令其缺省为空），则让其记录最终找到的位置。
ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
{
if (order) *order = 0;
if (isEmpty()) {
return NAME_NOT_FOUND;
}
// binary search
ssize_t err = NAME_NOT_FOUND;
ssize_t l = 0;
ssize_t h = size()-1;
ssize_t mid;
const void* a = arrayImpl();
const size_t s = itemSize();
while (l <= h) {
mid = l + (h - l)/2;
const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
const int c = do_compare(curr, item);
if (c == 0) {
err = l = mid;
break;
} else if (c < 0) {
l = mid + 1;
} else {
h = mid - 1;
}
}
if (order) *order = l;
return err;
}合并函数分析
在看合并函数之前，可以先看看用于加入元素的 add 函数的实现：
- 第 4 行：调用
_indexOrderOf函数，获取待加入元素应插入的位置。 - 第 5~9 行：这里分成两种情况。
- 若
index < 0，表示原 Vector 中没有与item相同（怎样才算相同，取决于do_compare的具体实现）的元素，则在order指定的位置插入元素即可，Vector 保持已排序状态。 - 若
index >= 0，表示已经存在与item相同的元素，则用当前item把对应元素覆盖掉（以 Key-Value 形式的 Vector 为例，比较函数是通过 Key 进行比较的，则item对应的 Key-Value1 就会覆盖掉原来的 Key_Value0）。
- 若
- 第 10 行：该函数返回的是元素的最终位置。
ssize_t SortedVectorImpl::add(const void* item)
{
size_t order;
ssize_t index = _indexOrderOf(item, &order);
if (index < 0) {
index = VectorImpl::insertAt(item, order, 1);
} else {
index = VectorImpl::replaceAt(item, index);
}
return index;
}合并函数有两个，一个是针对一般的 VectorImpl 类型的 Vector，另一个是针对 SortedVectorImpl 类型的 Vector。
代码分析：
- 第 4~14 行：简单合并，遍历入参
vector中的每个元素，并通过add函数将其加入到当前 Vector 中。 - 第 24~31 行：与另一个排序好的数组进行合并，这就有三种情况。
- 若入参
vector的最后一个元素小于等于当前 Vector 的第一个元素，则在当前 Vector 的开头位置将其插入即可（通过调用父类函数insertVectorAt实现）。 - 若入参
vector的第一个元素大于等于当前 Vector 的最后一个元素，则往当前 Vector 末端将其加入即可（通过调用父类函数appendVector实现）。 - 若非以上两种情况，则表明入参
vector的区间与当前 Vector 有重叠，此时就直接调用简单合并函数，依次将元素插入即可。
- 若入参
ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
{
// naive merge...
if (!vector.isEmpty()) {
const void* buffer = vector.arrayImpl();
const size_t is = itemSize();
size_t s = vector.size();
for (size_t i=0 ; i<s ; i++) {
ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
if (err<0) {
return err;
}
}
}
return NO_ERROR;
}
ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
{
// we've merging a sorted vector... nice!
ssize_t err = NO_ERROR;
if (!vector.isEmpty()) {
// first take care of the case where the vectors are sorted together
if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
} else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
} else {
// this could be made a little better
err = merge(static_cast<const VectorImpl&>(vector));
}
}
return err;
}小结
VectorImpl 与 SortedVectorImpl 这两个抽象类都已经分析了一遍，接下来就要看看它们的子类 Vector 与 SortedVector 有哪些需要注意的了。实际上要关注的内容很少，因为各种功能都在抽象类中实现好了。
类似资料：