|
QVector 介绍
QVector类是一个提供动态数组的模板类。
QVector<T>是Qt普通容器类的一种。它将自己的每一个对象存储在连续的内存中，可以使用索引号来快速访问它们。QList<T>、QLinkedList<T>和 QVarLengthArray<T>也提供了相似的功能，它们使用方法如下：
l QList一般用得最多，它能满足我们绝大部分需求。像prepend()和insert()这样的操作通常比QVector要快些，这是由于QList存储它的对象的方式（Algorithmic Complexity）不同。还有它基于索引的API比QLinkedList的基于迭代器的API更方便使用。最后，执行程序时它的代码扩展量更少些。
l QLinkedList，当你需要使用一个真正的链表，要求在恒定的时间内将对象插入到列表的中间，你更想用迭代器而不是索引号来访问对象，这个时候就使用QLinkedList吧！
l QVector，如果你想要在连续的内存上存储你的对象，你的对象比指针还要大，你想避免单独地把对象插入到堆的头部时，使用QVector。
l QVarLengthArray，如果你想要一个低层次的可变大小的容器，QVarLengthArray就足够了，它的优点是速度快！
下面是使用QVector存放整型值和QString的例子：
QVector<int> integerVector;
QVector<QString> stringVector;
QVector保存对象的向量容器，通常是使用初始大小来创建向量容器。举例，下面的代码构造了一个拥有200个元素的QVector：
QVector<QString> vector(200);
如果所创建的向量容器对象没有赋初值，就会被使用这个向量容器的类的默认构造函数进行初始化。基本类型和指针类型都会被初始化为0，如果想使用其它的初值来初始化对象时，可以在初始化时再添加一个参数：
QVector<QString> vector(200,"Pass");
你也可以调用fill()函数在任何时候填充向量容器。
就像C++的数组一样，QVector的索引号也是从0开始的。使用索引号来访问对象时，可以这样operator[]()
if (vector[0] == "Liz")
vector[0] ="Elizabeth";
如果只是读取向量容器的对象，可以调用at()函数来访问对象
for (int i = 0; i < vector.size(); ++i)
{
if (vector.at(i) =="Alfonso")
cout << "FoundAlfonso at position " << i << endl;
}
调用at()函数来读取对象会比使用operator[]()读取速度更快，因为这不会使用深度复制（deep copy）。
调用data()函数也可以访问保存在QVector的数据。这个函数会返回指向向量容器的第一个对象的指针。这样，你就可以使用指针来访问和修改向量容器内的对象。你可以使用指针将一个QVector向量容器传递给接收普通C++数组的函数。
你可以使用indexOf()和lastIndexOf()来查找某个对象出现的次数。前者从给定的位置向前搜索，后者是向后搜索。如果查找到了它们就返回相应的索引号，否则就返回-1，举例：
int i = vector.indexOf("Harumi");
if (i != -1)
cout << "Firstoccurrence of Harumi is at position " << i << endl;
contains()函数是用来查找向量容器内是否含有某个对象。
count()函数可以找出某个对象出现的次数。
insert(), replace(), remove(), prepend(), append()可以用来添加，移动和删除某个对象。对于体积较大的向量容器，除了append()和replace()这两个函数外，其它函数会比较慢，因为在内存中移动一个位置时，这些函数会使向量容器内的对象要移动许多次！如果你想要一个能够在中部快速插入和删除的容器时，可以使用QList或者QLinkedList。
resize()函数可以在任何时候改变QVector向量容器的体积。如果新的向量容器体积比以前的要大，QVector也许需要重新分配整个向量容器。QVector会预先分配两倍于实际数据的大小空间，从而减少再分配的次数。
reserve()函数，如果你事先知道向量容器大概包含多少个对象，你可以调用这个函数来预先分配一定的内存大小空间。
capacity()函数会告诉你向量容器所占内存的实际大小空间。
提醒：使用常量运算符和函数时会使QVector进行深度复制，这是隐含共享机制造成的。QVector的值的类型必须是可分配数据类型（assignable data type）。大多数数据类型都是这种类型。但是编译器不会让你存储一个QWidget，但是你可以存储QWidget指针啊！少数函数有额外的要求，比如indexOf()和lastIndexOf()期望值的类型可以支持operator==()，这些特殊要求在相关函数的文档上都有记录。
就像其它容器类一样，QVector支持Jave风格（QVectorIterator和QMutableVectorIterator）和STL风格的迭代器，实际上这些都很少使用，你可以使用索引号啊！
QVector不能插入、添加、替换一个QVector，否则你的应用程序就会报错！
QVector的内存分配策略
我们都知道 STL std::vector 作为动态数组在所分配的内存被填满时，如果继续添加数据，std::vector 会另外申请一个大小当前容量两倍的区域(如果 n > size 则申请 n+当前容量 的空间)，然后把当前内容拷贝到新的内存，以达到动态扩容的效果：
size_type
_M_check_len(size_type __n, const char* __s) const
{
if (max_size() - size() < __n)
__throw_length_error(__N(__s));
const size_type __len = size() + std::max(size(), __n);
return (__len < size() || __len > max_size()) ? max_size() : __len;
}
最直观的方式是写个客户程序看看：
vector<int> ve(4, 8);
cout << "size : " << ve.size() << " capacity : " << ve.capacity() << endl;
for ( int i = 0; i < 14; ++i )
{
ve.push_back(9);
ve.push_back(0);
cout << "size : " << ve.size() << " capacity : " << ve.capacity() << endl;
}输出如下，capacity 每次扩张为之前容量的两倍： 
类似的，Qt在其 QTL 中也实现了类似的QVector，为了更方便地服务为 Qt 应用服务，它提供了隐式共享，写时复制等机制，并同时提供了 Java Style 和 C++ Style 的接口，相同功能的接口也就是换了个名字而已：
inline void push_back(const T &t) { append(t); }
那么，在 QVector 所分配的内存被填满时，它的内存又是以何种方式扩充的呢？我们可以在源码中一探究竟：
先看看 QVector::append()：
const bool isTooSmall = uint(d->size + 1) > d->alloc;
if (!isDetached() || isTooSmall) {
QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
reallocData(d->size, isTooSmall ? d->size + 1 : d->alloc, opt);
}
isDetached()调用一个引用计数，用来判断该QVector是否独立(未被隐式共享)。如果该 QVector 是被共享的，那么我们此时想要在这个已被我们“复制”的 QVector 上调用 append() 时，当然需要真正分配一段新的内存并在该内存上进行添加元素的操作，也就是所谓的“写时复制”。
isTooSmall 则告诉我们当前szie加 1 之后是否超出了当前容量(d->alloc)，如果是同样需要调用 reallocData 开始申请内存。由于内存分配可能是由写时复制策略调用，因此根据 isTooSmall 参数的不同，reallocData()的参数也不同。
QVector::reallocData()函数调用了QTypedArrayData::allocate()，前者执行了begin(),end()等指针的重新指向，原内存释放等工作，后者实际调用了 QArrayData::allocate()，其函数原型为：
static QTypedArrayData *allocate(size_t capacity,
AllocationOptions options = Default) Q_REQUIRED_RESULT
{
Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
return static_cast<QTypedArrayData *>(QArrayData::allocate(sizeof(T),
Q_ALIGNOF(AlignmentDummy), capacity, options));
}
这里的 Q_ALIGNOF(AlignmentDummy) 十分关键，AlignmentDummy是下面这样的一个class：
class AlignmentDummy { QArrayData header; T data; };
QArrayData 是 Qt 所有连续型容器实际存放数据的地方，包含以下几个数据成员，也就是说，sizeof(QArrayData)为16个字节长度：
QtPrivate::RefCount ref;
int size;
uint alloc : 31;
uint capacityReserved : 1;
qptrdiff offset; // in bytes from beginning of header
而 Q_ALIGNOF 在 gcc 下是 __alignof__ 的别名，而在MSVC下则为 __alignof，用来获得 AlignmentDummy 的内存对齐大小，由上面的数据成员可以知道 Q_ALIGNOF(QArrayData) 的值为4。当 Q_ALIGNOF(AlignmentDummy) 大于4 时，意味着该 QArrayData 的成员变量所占内存空间与实际 T 型数据间由于内存对齐将会存在间隙(padding)，因此我们需要额外多申请 padding 的空间才能保证所有数据都能够被正确安放。
理解这一点后，我们就可以来看看QArrayData::allocate()
QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment,
size_t capacity, AllocationOptions options)
{
// 检测aligment是否为2的阶数倍
Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData)
&& !(alignment & (alignment - 1)));
...
// 获取 QArrayData 类为空时的大小
size_t headerSize = sizeof(QArrayData);
// 申请额外的 alignment-Q_ALIGNOF(QArrayData)大小的 padding 字节数
// 这样就能将数据放在合适的位置上
if (!(options & RawData))
headerSize += (alignment - Q_ALIGNOF(QArrayData));
// 如果数组长度超出容量则申请新的内存
if (options & Grow)
capacity = qAllocMore(int(objectSize * capacity), int(headerSize)) / int(objectSize);
//一共需要申请的字节数
size_t allocSize = headerSize + objectSize * capacity;
QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize));
if (header) {
...
}
return header;
}
qAllocMore() 实现在 qbyteArray.cpp 文件中，这个函数返回一个整型数，返回数据内容所需的字节数：
int qAllocMore(int alloc, int extra)
{
Q_ASSERT(alloc >= 0 && extra >= 0);
Q_ASSERT_X(alloc < (1 << 30) - extra, "qAllocMore", "Requested size is too large!");
unsigned nalloc = alloc + extra;
// Round up to next power of 2
// Assuming container is growing, always overshoot
//--nalloc;
nalloc |= nalloc >> 1;
nalloc |= nalloc >> 2;
nalloc |= nalloc >> 4;
nalloc |= nalloc >> 8;
nalloc |= nalloc >> 16;
++nalloc;
Q_ASSERT(nalloc > unsigned(alloc + extra));
return nalloc - extra;
}
函数开头告诉我们如果申请字节不能超过 2^30 - extra。注意这里的 extra 就是我们在上面求到的 sizeof(QArrayData) + sizeof(padding)。alloc是我们存放实际数据区域的大小，nalloc即为我们总共需要的新内存容量。
下面的几排移位算法如果大家眼熟的话应该知道得到的 nalloc 的新值为比其原值大的一个最近的 2 的阶乘数，比如输入20，经过最后一步 ++nalloc 操作后，nalloc将变成 32。
拨开云雾见青天的时候终于要到了，回到我们最初的问题：QVector 在满容量之后继续插入，其内存增长策略如何？
按照我们前面所看到的，大家心里也许有了答案：QVector的容量按照 2^n 增长，也就是 2, 4, 8, 16, 32...OK，写测试代码的时候到了：
QVector<int> ve(2, 8);
qDebug() << "size : " << ve.size() << " capacity : " << ve.capacity();
for ( int i = 0; i < 20; ++i )
{
ve.append(9);
qDebug() << "size : " << ve.size() << " capacity : " << ve.capacity();
}
输入如下：
似乎有些奇怪，容量并不是 2 的 n 次方？还记得QArrayData类中的数据成员所占用的 sizeof(QArrayData) = 16 吗，正是这 16 个字节占用了我们这个QVector<int>的 4 个容量，也就是说，这个QVector<int>实际的容量应该为：
现在我们再考虑带有 padding 的情况，当我们创建一个 QVector<quint64> 时，由于内存对齐的关系，QArrayData的数据成员与实际存储数据之间应该存在间隙，导致不可用的空间超过 16 字节：
可以看到，实际空间占用比容量大了 3*8 = 24bytes，其中 16bytes 为headerSize，余下 8bytes 则为间隙了。
这样应该很清晰了吧(●'◡'●)
那么，这个分配策略和 STL std::vector 的差异主要在哪呢，不也是每次翻倍吗？
使用int作为数组数据类型，直接给个输出结果哈： 
同样向 100 个容量的满数组中添加一个数据，QVector扩容将申请 128*4 (16字节headerSize) 个字节，而 std::vector 将申请 200*4 个字节。
|
