动态数组.

Presentation on theme: "动态数组."— Presentation transcript:

1 动态数组

2 动态数组 引言 这部分要解决 固定长度数组类 动态数组类对于操纵那些无法预知需要分配多少内存的数据集合是很有用的
动态数组随着元素增加而扩展，并且不需要创建成固定长度 这部分要解决 Symbian OS 提供的两类动态数组类 固定长度数组类 和标准 C++ [] 数组很相似

3 Symbian OS中的动态数组 基本掌握Symbian OS 中的动态数组 (CArrayX 和 RArray 系列)
掌握Symbian OS中动态数组的不同类型，注意内存分配 (平的(flat) 或者 分段 (segmented)), 对象存储 (在数组中或者别处), 对象长度(定长或者不定长)和对 象的所以权 区别在什么环境下使用基于段的缓冲区数组类而不是使用平数组类

4 Symbian OS中的动态数组 数组的逻辑设计 动态数组的实现： 就象向量一样 或者使用单独的堆单元，作为 “平坦” 缓冲区来保存数组元素
或者将数组缓冲区分成很多段，再用双向链表来管理这些一段一段的堆内存

5 Symbian OS中的动态数组 使用分段缓冲区更好 平坦缓冲区典型用于 典型的，插入和删除用分段缓冲区比平坦缓冲区更有效
对于那些数组大小会频繁变化的情况 有很多元素频繁插入或者从数组中删除的情况 重复再分配单个平坦缓冲区可能导致堆内存抖动和复制 平坦缓冲区典型用于 高速的指针查找被作为重要考虑 数组大小的改变不是很频繁 典型的，插入和删除用分段缓冲区比平坦缓冲区更有效 因为它不要求修改点后面的所有元素都重新移动到一个新的地方

6 Symbian OS中的动态数组 Symbian OS 提供 有许多不同类型的动态数组类 RArray 和 RPointerArray 类
创建和访问动态数组的两个不同的类家族 早期的Symbian OS数组类是 C 类 有许多不同类型的动态数组类 所有类名字以“CArray” 为前缀。例如 CArrayFixFlat, CArrayFixSeg 和 CArrayVarSeg 他们被统称为 “CArrayX” RArray 和 RPointerArray 类 后来引入它们来提高效率

7 CArrayX 类 CArrayX 类的数目 使数组类家族十分灵活 但是有明显的性能开销 (随后讨论) 不推荐使用

8 CArrayX 类 每个以 CArray 为前缀的类名后面会有如下字符串： Fix 意味着数组中的元素是等长的
而且是可以被复制的，所以他们可以保存在数组缓冲区内 Var 代表数组中元素是变长的 每个元素被保存在自己的堆中，数组缓冲区包含的是指向这些元素的指针 Pak 表明这是拥有变长元素的压缩数组（packed array） 数组元素被复制到数组缓冲区中，每个元素前面都有它的长度信息 Ptr 代表指向CBase派生类对象的指针数组

9 CArrayX 类 在 Fix,Var,Pak和Ptr之后，类名以以下字符结尾： Flat Seg
例如 CArrayFixFlat，表明该类的动态内存在底层使用的是平坦缓冲区 Seg 例如 CArrayPtrSeg ，表明其使用的是段缓冲区

10 CArrayX 类 CArrayX 类的继承层次是很容易理解的 每个类是瘦模板的特例化 所有类是C类，最终从CBase 派生
数组的基类是下面类中的一个： CArrayVarBase CArrayPakBase CArrayFixBase

11 CArrayX 类 CArrayVarSeg<class T> 和 CArrayVarFlat<class T>
派生自 CArrayVar<class T> 是CArrayVarBase 的模板特例化 CArrayVarBase 拥有一个对象 有一个动态缓冲区基类 CBufBase 的派生对象 用来存储数组元素 对象是下面类的具体实例 CBufFlat 是平坦动态存储缓冲区 CBufSeg 是分段动态缓冲区

12 动态数组的内存结构 12 5 6 Fix Var 或者 Ptr Pak 元素长度 平坦缓冲区 被有效元素占用的堆内存 未被占用的元素
粒度 = 4 双向链表 分段缓冲区

13 可用的CArrayX 类 数组类 描述 清除行为 CArrayFixFlat
数组元素的大小是固定的并且包含在数组自身中。数组在内存中占用一块独立的空间。 数组元素为数组所拥有，并且由数组销毁。 CArrayFixSeg 数组元素的大小是固定的并且包含在数组自身中。数组在内存中占用许多块(段)空间。 CArrayVarFlat 数组元素的大小可变，每个元素分别存在于堆上，数组元素由指向他们的指针组成。数组在内存中占用一块独立的空间。

14 可能用到的CArrayX 类 数组类 描述 清除的行为 CArrayVarSeg
数组元素的大小可变，每个元素分别存在于堆上，数组元素由指向他们的指针组成。数组在内存中占据很多块空间(段)。 数组元素为数组所拥有，并且由数组销毁。 CArrayPtrFlat 数组元素是指向派生自CBase的对象。数组在内存中占用一块独立的空间。 在销毁数组之前，数组元素必须被分别销毁，这可以调用ResetAndDestroy()函数实现 CArrayPtrSeg 数组元素是指向派生自CBase的对象。数组在内存中占据很多块空间(段)。

15 RArray 和 RPointerArray
RArray和 RPointerArray 都是 R 类 表明这是持有资源的类，这些资源就是它们所分配到的、用于保存数组的堆内存 RArray<class T> 是RArrayBase 类的一个瘦模版特例化 它保存具有相同大小的元素 它使用平坦的、类似向量的堆内存块来保存元素，在必要时还可以调整大小

16 RArray RArray 对象 RArray::Close() RArray::Reset() 可以调用 Reset()
是可以基于栈也可以基于堆的 对象使用完毕后调用 Close() 或者Reset()函数进行清除，也就是说释放那些为数组分配的内存 RArray::Close() 释放用于存储数组的内存并且关闭它 RArray::Reset() 释放与数组有关的内存 重置内部状态，从而可以让数组被重新使用 可以调用 Reset() 在对象离开作用域之前 因为所有与对象相关的堆内存将会被清除

17 RPointerArray RPointerArray<class T> 如果对象被其他组件持有 如果对象只被数组持有
派生于RPointerArrayBase的一个瘦模版类 由指针元素组成简单数组，使用平坦的线性内存 每个指针元素可以寻址存储在对象的对象 当销毁数组时，必须考虑这些对象的所有权 如果对象被其他组件持有 调用Close() 或者 Reset() 来清除与数组相关的内存就足够了 如果对象只被数组持有 当清除数组时它们不会自动销毁 作为清除的一部分, 调用ResetAndDestroy()来删除与数组中每个指针元素相关联的堆对 象

18 RArray, RPointerArray还是CArrayX?
了解RArrayX比CArrayX更好的原因, 以及CArrayX 类是更好选择的例外情况

19 RArray, RPointerArray 还是CArrayX?
原始CArrayX 类使用CBufBase 基类来访问分配给数组的内存 CBufBase 使用字节缓冲区，并且对于每个数组访问都要创建一个TPtr8 对象 这就使得对于一个包含固定元素的简单平坦数组，也会有很大的开销

20 RArray, RPointerArray还是CArrayX?
更进一步的 对于每个访问数组的方法，即使在发行版本中，也至少有两个断言来检查参数。 例如，访问CArrayFixX 数组中的一个位置 operator[]调用了 CArrayFixBase::At() CArrayFixBase::At() 使用了 __ASSERT_ALWAYS对索引值进行范围检查 CArrayFixBase::At() 调用CBufFlat::Ptr() CBufFlat::Ptr() 也对数组缓冲区内指定的位置进行判断

21 RArray, RPointerArray还是CArrayX?
第二个问题 CArrayX中的很多数组操纵函数，如AppendL()在没有足够的内存来调整数组缓冲区大小时 都可能发生异常退出 在内核使用动态数组的情况下 或者在不会发生异常退出的函数中必须调用动态数组的情况 可异常退出函数必须在TRAP宏中调用以捕获所有异常退出 如前所述，TRAP宏具有关联的性能开销，而这在使用TRAP宏时是不合需要的

22 RArray, RPointerArray还是CArrayX?
增加这两个类使得Symbian OS能提供更有效的简单平坦内存数组 比较 RArray 和 CArrayFixFlat RPointerArray 和 CArrayPtrFlat 比CArrayX 类性能更优 RArray 和 RPointerArray 所以当向数组中插入或添加数组元素时不需要使用TRAP 机制来确保安全退出操作 因此在内核模式和用户模式下都可以有效使用 (随后再讨论)

23 RArray, RPointerArray还是CArrayX?
R 类为C类有更低的开销，因为它们不需要C类的特性： 分配时以零填充 虚函数表指针 强制在堆上创建对象 排序和查找函数 RArray 类比原有的类更加的优化

24 RArray, RPointerArray 还是 CArrayX?
只要数组有如下特征时，RArray 或者 RPointerArray 就应该比 CArrayFixFlat 和 CArrayPtrFlat 类被优先使用： 数组元素的大小有限制 RArray 的当前实现使用的上限是640 bytes 向数组插入元素是不频繁的 RArray 或者RPointerArray 不是基于分段内存- 两个类都是定长的而不是使用分段内存

25 RArray, RPointerArray 还是 CArrayX?
当由于性能原因需要使用分段内存 (例如， 频繁调整大小的数组) 可能使用动态数组的CArrayX 家族更合适 由于这个原因 CArrayFixSeg 和 CArrayPtrSeg 是比RArray 和RPointerArray更好的选择

26 实现时注意 由于性能原因 这意味着 RArray在数组中存储对象是以字(4-byte)对齐的
当硬件要求强制对齐时可能发生未处理的异常

27 实现时注意 影响到的函数有： 构造函数 RArray(TInt, T*, TInt) Append(const T&)
Insert(const T&, TInt) Operator [], 如果返回的指针被用作数组遍历，就像C语言的数组那样

28   数组粒度 了解数组粒度和容量的定义 了解怎样合适选择数组粒度

29 数组粒度 动态数组的容量 当容量充满时 所有的动态容器类 是数组在当前已分配的缓冲区空间中能容纳的元素的个数
当插入一个新元素时，数组就再分配堆内存从而动态改变自身大小 为缓冲区分配额外元素的数目是由粒度决定的，这个值是在构造时指定的。 所有的动态容器类 无论是分段内存结构还是平坦内存结构，都有一个再分配的粒度。

30 数组粒度 选择一个与数组预期适用模式相一致的粒度是很重要的 例如，一个数组通常存有8 到10个对象 如果通常有11个对象
取值太小，那么当大量元素加入数组中时，就会因为多次额外分配内存而引发一些开销 如果选择的粒度太大，那么数组会浪费许多存储空间 例如，一个数组通常存有8 到10个对象 选择粒度为10就是明智的 选择粒度为100 就不必要了。 如果通常有11个对象 取粒度为10就会造成9个对象的内存浪费。 取粒度为1也很愚蠢，因为会导致多次再分配

31 数组排序和查找 示范对动态数组中怎样排序和查找的理解
知道RArray, RPointerArray 和 CArrayX 家族都可以的排序,但是CArrayX 类 不是很高效

32 数组排序和查找 对于CArrayX 类 例如 基于优先级的关键值 基于名字的关键值
数组的关键字可以用来定义数组元素的属性，通过这个可以对整个数组进行排序和查找 例如 以任务为元素的数组可以有一个整型的优先级值和一个字符串类型的名字 基于优先级的关键值 可用于根据优先级的顺序进行排序 基于名字的关键值 可用于搜索特定的名字

33 数组排序和查找 抽象基类 如下的关键字来自于不同类型的数组： 数组的关键字是 TKey TKeyArrayFix 固定长度的数组
TKeyArrayVar元素长度可变的数组 TKeyArrayPak元素长度可变的压缩数组

34 数组排序和查找 基于关键字访问元素需要合适的 对象被传递到 TKeyArrayFix TKeyArrayVar TKeyArrayPak
Sort() InsertIsqL() Find() 或者FindIsq() 数组类成员函数

35 数组排序和查找 查找元素 顺序查找 二分查找 两个函数 例如，如下两种基于关键字的查找方式： 从第一个元素开始使用Find()成员函数查找
使用FindIsq() 成员函数 假设数组元素已经按关键字值有序排好 两个函数 指出查找成功或者失败，如果查找成功，则返回该元素在数组中的位置

36 数组排序和查找 RArray 类提供的查找和排序方法 对象 典型的，这些类 传递 请参看ASD Primer中的例子以了解如何实现排序功能
比CArrayX 类的对应方法更高效更方便 对象 包含在RArray和RPointerArray 中的对象可能已经有序 使用作为元素的类提供的比较函数 典型的，这些类 为对象排序提供了方法 传递 给InsertInOrder() 或者Sort() 方法的对象被包装在TLinearOrder<class T> 包中 请参看ASD Primer中的例子以了解如何实现排序功能 The primer contains a detailed example at this point Section 8.4 p141 (UK version )

37 数组排序和查找 也可能 RArray 类 该对象包裹了一个函数 请看ASD Primer上的例子理解如果实现查找功能
在RArray 和 RPointerArray类中以相似的方式执行查找操作 RArray 类 有许多 Find() 方法 其中一个被重载成使用TIdentityRelation<class T>对象作为参数 该对象包裹了一个函数 该函数通常是由元素类提供的 它决定了两个T类型的对象是否匹配 请看ASD Primer上的例子理解如果实现查找功能 The primer contains a detailed example at this point Section 8.4 p141 (UK version )

38 TFixedArray 认识到当不是必须使用动态数组时， TFixedArray数组类的使用要优于 C++ 数 组，因为它提供边界检查 (仅调试版本中或者在调试和发行版本中)

39 TFixedArray TFixedArray 是动态数组的一个替代 TFixedArray 类
在编译时可以知道数组元素个数的情况下，该类很有用 TFixedArray 类包装了标准C++的固定长度数组 增加边界检查来阻止越界访问 TFixedArray 类 可以被当作CBase 类的成员在堆上使用 或者在栈上时，因为它是T类

40 TFixedArray 访问时自动进行边界检查 在产品代码中需要运行时的效率 如果调用At()函数，那么对发行版本和调试版本都进行边界检查
operator[]可以取代 At() ，因此只在调试版本中进行边界检查 如果试图使用超出范围的数组索引，那么将会产生一个致命错误

41 TFixedArray 一旦 TFixedArray 被分配空间 因为分配已经完成 这意味着 不能动态改变大小，这是这个类的缺点
在运行时向数组边界内插入元素可以确保成功 这意味着 不需要检查内存不足错误或者数组插入中的异常退出 在发行版本中访问数组也很快

42 TFixedArray 使用固定长度数组的最大缺点是： 向数组中添加任何元素都必须在数组末尾 TFixedArray不支持排序和匹配

43 TFixedArray TFixedArray类还有一些有用的其他函数，它们扩展了一般的 C++数组，这些函数包括：
Begin() 和 End()，用于数组导航 Count() ，返回数组中的元素个数 Length() ，以字节为单位返回数组元素大小 DeleteAll()， 对数组中每个元素调用delete Reset()， 清除数组，将每个元素置为零

44 动态数组 Symbian OS中的动态数组 RArray,RPointerArray 还是CArrayX? 数组粒度 数组排序和查找
TFixedArray