[Qt-interest] Qt Containers (or: why I must use STL)

[Thiago Macieira]

Em Terça-feira 13. Outubro 2009, às 11.06.22, Julien Cugnière escreveu:
> 2009/10/13 Thiago Macieira <thiago at kde.org>
> 
> > 1) use of "int" doesn't mean limitation to 2 GB. It limits to 2 billion
> > elements, which on a QList of small, movable items means 16 GB.
> 
> I'm curious how you get that 16 GB number. It was my understanding
> that if T is a small movable type, then a QList<T> is just an array of
> T.  So 2 billion elements would only mean sizeof(T) * 2 billion, just
> like a QVector. With sizeof(T) == 4, that's only 8 GB. Are you
> assuming sizeof(T) == 8, or is there something else ?

QList has an array of void*. So on a 64-bit system, that's 8 * 2 billion = 16 
GB.

QList stores small and movable elements directly in the void*. If the item is 
larger than the size of a pointer or not movable (i.e. static), then QList 
will new() each item and store the pointer to it instead.

See:
Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t)
{
    if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t);
    else if (QTypeInfo<T>::isComplex) new (n) T(t);
    else *reinterpret_cast<T*>(n) = t;
}

See the first and third branches of the function.

That's how QList manages to have a fast insertion system. In a QVector of 
complex elements, the reallocation forces the recreation of all elements and 
destruction of all old elements. In QList, it's still O(n), but it's basically 
one or two memcpy.

-- 
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
  Senior Product Manager - Nokia, Qt Development Frameworks
      PGP/GPG: 0x6EF45358; fingerprint:
      E067 918B B660 DBD1 105C  966C 33F5 F005 6EF4 5358

Qt Developer Days 2009 | Registration Now Open!
Munich, Germany: Oct 12 - 14     San Francisco, California: Nov 2 - 4
      http://qt.nokia.com/qtdevdays2009
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 190 bytes
Desc: This is a digitally signed message part.
Url : http://lists.qt-project.org/pipermail/qt-interest-old/attachments/20091013/1775f2cf/attachment.bin