[翻译]理解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隐性转换。

(未完待续、、、)

14 thoughts on “[翻译]理解Qt容器:STL VS QTL(一)——特性总览”

Leave a Reply to 李阳博客 Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.