[翻译]理解Qt容器：STL VS QTL（一）——特性总览

注：此文为翻译大牛的文章，原文地址：http://marcmutz.wordpress.com/effective-qt/containers/ (需翻墙)，原文较长，我E文不是很好，而且个人时间安排，我就分段翻译发出了，这是第一篇，余下的我会慢慢补齐的。

容器类是面向对象编程的一个重要的部分，是一个而非常重要的，帮助我们去管理内存的工具。

Qt有它自己实现的容器类，十分像STL，但是还是有些差异的，一些是Qt做的补充，还有一些不能对应。作为一个Qt开发者，是非常重要的去理解什么时候去使用哪一个Qt容器类，和一些时候，你去用STL去替换QTL。

QTL 和STL对照表

下面表格主要对比了顺序和关联容器中QTL和STL的对应。大多数时候，我们忽略字符串类，虽然技术上来说，它也属于容器。

QTL	STL
顺序容器
QVector	std::vector
—-	std::deque
QList	———
QLinkedList	std::list
—————-	std::forward_list
关联容器
QMap	std::map
QMultiMap	std::multimap
———————-	std::set
———————	std::multiset
QHash	std::unordered_map
QMultiHash	std::unordered_multimap
QSet	std::unordered_set
———————	std::unordered_multiset

如你所看到的一样，没有QTL与 std::deque, std::forward_list 和 std::{multi,}set,对应，也没有STL与QList对应。有两个容易误导的地方：QList和std::list是不一样的，QSet和std::set也是不一样的。还有一些原因，没有QTL没有QMultiSet的。

提示：谨记QList和std::list是不一样的，QSet和std::set也是不一样的

 

 

QTL和STL的大致区别：

他们有一些少量的区别是存在所有的容器类中的。

赋值 API：（Duplicated API）

首先，还是重要的：QTL有”Qt-ish” 和 “STL-compatible”两种赋值api，。他们是 append() 和push_back(); count() 和 size();  isEmpty() 和 empty()。根据你的Qt使用范围和习惯，你应该优先一种或者同时使用两种api。全部使用Qt的程序去使用Qt-ish API，当做分层程序时，为与项目中其他地方使用的 STL 容器的一致性，你应该去用STL-compatible API。 如果有疑问，那就去用STL API吧——对于Qt5也是这样。

提示：了解Qt的两种API，”Qt-ish” 和 “STL-compatible”。并尽量避免在一个程序中同时使用两种API。

 

 

QTL中缺失的一些STL的特性

STL容器也有几个乍一看很深奥的特性

• 大多数STL容器都rbegin()/rend()函数，它返回一个反向迭代器

const std::vector<int> v = { 1, 2, 4, 8 };
for ( auto it = v.rbegin(), end = v.rend() ; it != end ; ++it )
   std::cout << *it << std::endl; // prints 8 4 2 1

 

在QTL中，你就必须用正常的迭代器和相减的效果来实现相同的功能：

const QVector<int> v = ...;
auto it = v.end(), end = v.begin();
while ( it != end ) {
    --it;
   std::cout << *it << std::endl;
}

或者使用JAVA风格的迭代器（见下面）：

QVectorIterator it( v );
it.toBack();
while ( it.hasPrevious() )
    std::cout << it.previous() << std::endl;

 

• 所有 STL 容器也都有范围插入、 范围构造和分配，以及范围擦除。all but the last templated so that you can fill—say—a std::vectorfrom a pair of iterators to—say—a std::set(这句我没读懂):

const std::set<T> s = ...;
std::vector<S> v( s.begin(), s.end() ) ; // 'T' needs to be convertible to 'S'

 

这样就省去使用 qCopy()/std::copy() 算法函数了。

QTL只提供了范围删除

• 所有的 STL 容器有内存分配器（Allocator）的模板参数。虽然相当晦涩，分配器允许放置到 STL 容器的元素到共享内存，或将他们分配到内存池分。

QTL你不能用特殊的内存分配方法，所以，他们的元素（还有扩充和他们自己）不能分配到共享内存里去。

• 最后，单并非不重要，我应该提及，几乎任何 STL 都有很好的可用性的调试模式。这些调试模式可以查找 bug 在运行时不需要调试模式就可以显示崩溃或未定义的行为。可以STL 调试模式发现的缺陷：
  • 推进一个迭代器，超出其有效范围。
  • 比较指向不同容器的迭代器。
  • 除了将分配给他们的任何方式使用无效的迭代器。
  • 无效或超出范围的迭代器。

请参阅您的编译器的手册，了解如何启用 STL 调试模式。你会感谢你自己。

QTL中不存在那些类别。

（注：STL调试模式我也没用过，很多也没不大看懂，您可以去查看原文。）

提示：是自己熟悉STL和它提供的额外的特性。

 

Copy-On-Write（写入时复制）：

在好的方面，QTL都是隐式共享，所以其副本都是浅复制。与QTL相反，除了std:string外的所有STL容器都是深度复制，虽然看起来有点资源浪费。标准委员会正在评估Copy-On-Write是不是一个更好的优化。

 

在任何情况下，明智地使用 swap() 成员函数的 （也可在 QTL中当 qt 版本 ≥ 4.7） 和 C + + 11 移动语义优化实际上复制容器内容的需要：

Container c;
// populate 'c'
m_container = c; // wrong: copy
m_container.swap( c ); // correct: C++98 move by swapping
m_container = std::move( c ); // correct: C++11 move

 

从函数返回一个集合，应该无需这么做。因为大多数编译器已经进行了返回值优化。

顺便说一句，这是怎么移动一个元素到容器在C++98标准下：

// the item to move-append:
Type item = ...;
// the container to move-append it to:
Container c = ...;
// make space in the container
// (assumes that a default-constructed Type is efficient to create)
c.resize( c.size() + 1 ); // or: c.push_back( Type() );
// then move 'item' into the new position using swap:
c.back().swap( item );

在C++11下：

c.push_back( std::move( item ) );

 

指南：如果您的编译器支持C++11，相对于交换分配，优先使用明确的移动语义，用C++11的右值移动。

 

还有，有一种情况下，我推荐优先使用QTL：并行读或写访问，通过Copy-On-Write，在QT互斥锁下，Qt容器可以减少花费时间。例如一个交易基础的方法：

// global shared data:
QVector<Data> g_data;
QMutex g_mutex;
void reader() {
    QMutexLocker locker( &g_mutex );
    // make a (shallow) copy under mutex protection:
    const QVector<Data> copy = g_data;
    // can already unlock the mutex again:
    locker.unlock();
    // work on 'copy'
}
void writer() {
try_again:
    QMutexLocker locker( &g_mutex );
    // make a (shallow) copy under mutex protection:
    QVector<Data> copy = g_data;
    // remember the d-pointer of g_data (QVector lacks the usual data_ptr() member):
    const void * const g_data_data = reinterpret_cast<void*>(g_data);
    // can already unlock the mutex again:
    locker.unlock();
    // modify 'copy' (will detach, but _outside_ critical section!)
    // lock the mutex again in order to commit the result:
    locker.relock();
    // check that no-one else has modified g_data:
    // (only necessary if this isn't the only possible writer thread):
    if ( g_data_data == reinterpret_cast<void*>(g_data) )
        g_data.swap( copy ); // commit (member-swap requires Qt >= 4.8)
    else
        goto try_again;      // oops, someone else was faster, do the whole thing again
}

 

对于STL，这是不可能的。

指导：如果你能更好的利用Copy-On-Write，优先使用QTL。

 

警告：COW的所有操作都是隐藏操作的。在容器发生变化的时候（写的时候）必须保证这是独一无二的数据拷贝（也就是没有其他容器共享此数据），这样才能在此容器变化的时候不影响其他容器。如果在写的时候，有其他容器与此容器共享，这样就会进行数据的深拷贝还获取独一无二的副本，这是十分有必要的。当然，这种拷贝的数目会在保证读数据唯一性下按照最少拷贝原则的。

然而，一些操作在什么情况下都会被必须被检测是否写。例如：索引操作operator[]( int )。在所有支持索引的容器中，它们都会重载这个索引符号。

T & operator[]( int idx ); // mutable
const T & operator[]( int idx ) const; // const

第一种重载可以用在写容器这个操作：

c[1] = T();

或者，当仅仅读的时候，你能用第二种操作：

T t = c[1];

 

在进行上面第一种操作的时候，容器一定会分离（深拷贝），在第二种情况，它不应该。然而，用operator[]( int )从容器中获取一个元素引用的时候，是通过这个容器写还是读是没法确定的，它不得不做最坏的打算，去事先分离容器。我们也能选择，它可以返回一个用户明确定义的类型，好过于一个单独的引用，来让只有用户写入的时候再分离。如果您感兴趣的话，可以去看下 QCharRef QString::operator[]( int ) 或者 QByteRef  QByteArray::operator[]( int ),为实现这一方案的定义。这俩是Qt中唯一实现这一方案的容器。

还有另外一个问题：迭代器。和易变（潜在可变）的 operator[]操作一样，所以begin()/end()也一样，除非返回的迭代器足够智能去区分读和写，但是从Qt源码来看，没有那么智能。

对于我们使用容器来说，这对应着什么呢？首先，在STL容器（除了std::string）中，没有使用COW技术，所以也不存在我们上面说的这么多。对于Qt容器，不管怎么，你都应该注意不用可变的迭代器去执行只读的遍历。但是说来容易，做着难，然而，当我们用潜在易变的begin()/end()函数去赋给一个const 迭代器：

QString str = ...;
const QString cstr = ...;
for ( QString::const_iterator it = str.begin(), end = str.end() ; it != end ; ++it ) // detaches
    ...;
for ( QString::const_iterator it = cstr.begin(), end = cstr.end() ; it != end ; ++it ) // doesn't
    ...;

 

我们在两个迭代操作中都使用了const_iterator ，但是第一个是从QString::begin() (non-const) 返回的iterator 转换过来的，其实在转换之前，分离（深拷贝）就已经发生了。

一个解决办法是，对容器申请一个const 的引用，并使用这个引用去遍历：

const QString & crstr = str;
for ( QString::const_iterator it = crstr.begin(), end = crstr.end() ; it != end ; ++it ) // no detach
    ...;

另外：所有的Qt容器都提供了 constBegin()/constEnd()函数，他们总是返回const_iterator，即使是容器是可变的（非const）。

for ( QString::const_iterator it = str.constBegin(), end = str.constEnd() ; it != end ; ++it ) // no detach
    ...;

 

这对于QT容器来说是重要的，防止分离。对于STL容器，在C++11中也给了我们类似于constBegin()/constEnd()的，叫做 cbegin()/cend()。我们可以预测Qt APIs 马上就会添加上。（注：Qt5中已经添加上了）。

提示：永远使用constBegin()/constEnd() (cbegin()/cend())去获取一个const_iterator.

 

你也可以预定义QT_STRICT_ITERATORS来让iterator 到 const_iterator隐性转换。

（未完待续、、、）