summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools')
-rw-r--r--src/corelib/tools/qarraydata.cpp111
-rw-r--r--src/corelib/tools/qarraydata.h231
-rw-r--r--src/corelib/tools/qarraydataops.h413
-rw-r--r--src/corelib/tools/qarraydatapointer.h169
-rw-r--r--src/corelib/tools/qbitarray.cpp32
-rw-r--r--src/corelib/tools/qbitarray.h4
-rw-r--r--src/corelib/tools/qcontainerfwd.h2
-rw-r--r--src/corelib/tools/qcontiguouscache.h5
-rw-r--r--src/corelib/tools/qeasingcurve.cpp5
-rw-r--r--src/corelib/tools/qeasingcurve.h7
-rw-r--r--src/corelib/tools/qflatmap_p.h982
-rw-r--r--src/corelib/tools/qhash.h25
-rw-r--r--src/corelib/tools/qlinkedlist.h3
-rw-r--r--src/corelib/tools/qlist.cpp2025
-rw-r--r--src/corelib/tools/qlist.h1151
-rw-r--r--src/corelib/tools/qmap.h36
-rw-r--r--src/corelib/tools/qrefcount.h25
-rw-r--r--src/corelib/tools/qset.h33
-rw-r--r--src/corelib/tools/qvector.h1221
-rw-r--r--src/corelib/tools/qvector_msvc.cpp7
-rw-r--r--src/corelib/tools/tools.pri2
21 files changed, 2136 insertions, 4353 deletions
diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp
index 3879b48cbb..497eae1f7f 100644
--- a/src/corelib/tools/qarraydata.cpp
+++ b/src/corelib/tools/qarraydata.cpp
@@ -153,18 +153,16 @@ QT_WARNING_PUSH
QT_WARNING_DISABLE_GCC("-Wmissing-field-initializers")
const QArrayData QArrayData::shared_null[2] = {
- { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared null
+ { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }, // shared null
/* zero initialized terminator */};
-static const QArrayData qt_array[3] = {
- { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared empty
- { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, sizeof(QArrayData) }, // unsharable empty
+static const QArrayData emptyNotNullShared[2] = {
+ { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }, // shared empty
/* zero initialized terminator */};
QT_WARNING_POP
-static const QArrayData &qt_array_empty = qt_array[0];
-static const QArrayData &qt_array_unsharable_empty = qt_array[1];
+static const QArrayData &qt_array_empty = emptyNotNullShared[0];
static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, size_t headerSize,
uint options)
@@ -172,7 +170,7 @@ static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, siz
// Calculate the byte size
// allocSize = objectSize * capacity + headerSize, but checked for overflow
// plus padded to grow in size
- if (options & QArrayData::Grow) {
+ if (options & QArrayData::GrowsForward) {
auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize);
capacity = r.elementCount;
return r.size;
@@ -181,91 +179,104 @@ static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, siz
}
}
+static QArrayData *allocateData(size_t allocSize, uint options)
+{
+ QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize));
+ if (header) {
+ header->ref_.storeRelaxed(1);
+ header->flags = options;
+ header->alloc = 0;
+ }
+ return header;
+}
+
static QArrayData *reallocateData(QArrayData *header, size_t allocSize, uint options)
{
header = static_cast<QArrayData *>(::realloc(header, allocSize));
if (header)
- header->capacityReserved = bool(options & QArrayData::CapacityReserved);
+ header->flags = options;
return header;
}
-QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment,
- size_t capacity, AllocationOptions options) noexcept
+void *QArrayData::allocate(QArrayData **dptr, size_t objectSize, size_t alignment,
+ size_t capacity, ArrayOptions options) noexcept
{
+ Q_ASSERT(dptr);
// Alignment is a power of two
- Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData)
+ Q_ASSERT(alignment >= alignof(QArrayData)
&& !(alignment & (alignment - 1)));
- // Don't allocate empty headers
- if (!(options & RawData) && !capacity) {
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- if (options & Unsharable)
- return const_cast<QArrayData *>(&qt_array_unsharable_empty);
-#endif
- return const_cast<QArrayData *>(&qt_array_empty);
+ if (capacity == 0) {
+ // optimization for empty headers
+ *dptr = const_cast<QArrayData *>(&qt_array_empty);
+ return sharedNullData();
}
size_t headerSize = sizeof(QArrayData);
- // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we
- // can properly align the data array. This assumes malloc is able to
- // provide appropriate alignment for the header -- as it should!
- // Padding is skipped when allocating a header for RawData.
- if (!(options & RawData))
- headerSize += (alignment - Q_ALIGNOF(QArrayData));
+ if (alignment > alignof(QArrayData)) {
+ // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we
+ // can properly align the data array. This assumes malloc is able to
+ // provide appropriate alignment for the header -- as it should!
+ headerSize += alignment - alignof(QArrayData);
+ }
if (headerSize > size_t(MaxAllocSize))
return nullptr;
size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
- QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize));
+ options |= AllocatedDataType | MutableData;
+ options &= ~ImmutableHeader;
+ QArrayData *header = allocateData(allocSize, options);
+ quintptr data = 0;
if (header) {
- quintptr data = (quintptr(header) + sizeof(QArrayData) + alignment - 1)
+ // find where offset should point to so that data() is aligned to alignment bytes
+ data = (quintptr(header) + sizeof(QArrayData) + alignment - 1)
& ~(alignment - 1);
-
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- header->ref.atomic.storeRelaxed(bool(!(options & Unsharable)));
-#else
- header->ref.atomic.storeRelaxed(1);
-#endif
- header->size = 0;
- header->alloc = capacity;
- header->capacityReserved = bool(options & CapacityReserved);
- header->offset = data - quintptr(header);
+ header->alloc = uint(capacity);
}
+ *dptr = header;
+ return reinterpret_cast<void *>(data);
+}
+
+QArrayData *QArrayData::prepareRawData(ArrayOptions options) Q_DECL_NOTHROW
+{
+ QArrayData *header = allocateData(sizeof(QArrayData), (options & ~DataTypeBits) | RawDataType);
+ if (header)
+ header->alloc = 0;
return header;
}
-QArrayData *QArrayData::reallocateUnaligned(QArrayData *data, size_t objectSize, size_t capacity,
- AllocationOptions options) noexcept
+QPair<QArrayData *, void *>
+QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer,
+ size_t objectSize, size_t capacity, ArrayOptions options) noexcept
{
Q_ASSERT(data);
Q_ASSERT(data->isMutable());
- Q_ASSERT(!data->ref.isShared());
+ Q_ASSERT(!data->isShared());
size_t headerSize = sizeof(QArrayData);
size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
- QArrayData *header = static_cast<QArrayData *>(reallocateData(data, allocSize, options));
- if (header)
- header->alloc = capacity;
- return header;
+ qptrdiff offset = reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data);
+ options |= AllocatedDataType | MutableData;
+ QArrayData *header = reallocateData(data, allocSize, options);
+ if (header) {
+ header->alloc = uint(capacity);
+ dataPointer = reinterpret_cast<char *>(header) + offset;
+ }
+ return qMakePair(static_cast<QArrayData *>(header), dataPointer);
}
void QArrayData::deallocate(QArrayData *data, size_t objectSize,
size_t alignment) noexcept
{
// Alignment is a power of two
- Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData)
+ Q_ASSERT(alignment >= alignof(QArrayData)
&& !(alignment & (alignment - 1)));
Q_UNUSED(objectSize) Q_UNUSED(alignment)
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- if (data == &qt_array_unsharable_empty)
- return;
-#endif
-
- Q_ASSERT_X(data == nullptr || !data->ref.isStatic(), "QArrayData::deallocate",
+ Q_ASSERT_X(data == nullptr || !data->isStatic(), "QArrayData::deallocate",
"Static data cannot be deleted");
::free(data);
}
diff --git a/src/corelib/tools/qarraydata.h b/src/corelib/tools/qarraydata.h
index dcd95924c1..483f6d5edb 100644
--- a/src/corelib/tools/qarraydata.h
+++ b/src/corelib/tools/qarraydata.h
@@ -1,6 +1,7 @@
/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2019 Intel Corporation.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
@@ -40,32 +41,64 @@
#ifndef QARRAYDATA_H
#define QARRAYDATA_H
-#include <QtCore/qrefcount.h>
+#include <QtCore/qpair.h>
+#include <QtCore/qatomic.h>
#include <string.h>
QT_BEGIN_NAMESPACE
+template <class T> struct QTypedArrayData;
+
struct Q_CORE_EXPORT QArrayData
{
- QtPrivate::RefCount ref;
- int size;
- uint alloc : 31;
- uint capacityReserved : 1;
+ enum ArrayOption {
+ RawDataType = 0x0001, //!< this class is really a QArrayData
+ AllocatedDataType = 0x0002, //!< this class is really a QArrayAllocatedData
+ DataTypeBits = 0x000f,
+
+ CapacityReserved = 0x0010, //!< the capacity was reserved by the user, try to keep it
+ GrowsForward = 0x0020, //!< allocate with eyes towards growing through append()
+ GrowsBackwards = 0x0040, //!< allocate with eyes towards growing through prepend()
+ MutableData = 0x0080, //!< the data can be changed; doesn't say anything about the header
+ ImmutableHeader = 0x0100, //!< the header is static, it can't be changed
+
+ /// this option is used by the Q_ARRAY_LITERAL and similar macros
+ StaticDataFlags = RawDataType | ImmutableHeader,
+ /// this option is used by the allocate() function
+ DefaultAllocationFlags = MutableData,
+ /// this option is used by the prepareRawData() function
+ DefaultRawFlags = 0
+ };
+ Q_DECLARE_FLAGS(ArrayOptions, ArrayOption)
- qptrdiff offset; // in bytes from beginning of header
+ QBasicAtomicInt ref_;
+ uint flags;
+ uint alloc;
+
+ inline size_t allocatedCapacity()
+ {
+ return alloc;
+ }
+
+ inline size_t constAllocatedCapacity() const
+ {
+ return alloc;
+ }
- void *data()
+ /// Returns true if sharing took place
+ bool ref()
{
- Q_ASSERT(size == 0
- || offset < 0 || size_t(offset) >= sizeof(QArrayData));
- return reinterpret_cast<char *>(this) + offset;
+ if (!isStatic())
+ ref_.ref();
+ return true;
}
- const void *data() const
+ /// Returns false if deallocation is necessary
+ bool deref()
{
- Q_ASSERT(size == 0
- || offset < 0 || size_t(offset) >= sizeof(QArrayData));
- return reinterpret_cast<const char *>(this) + offset;
+ if (isStatic())
+ return true;
+ return ref_.deref();
}
// This refers to array data mutability, not "header data" represented by
@@ -73,57 +106,93 @@ struct Q_CORE_EXPORT QArrayData
// follow COW principles.
bool isMutable() const
{
- return alloc != 0;
+ return flags & MutableData;
}
- enum AllocationOption {
- CapacityReserved = 0x1,
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- Unsharable = 0x2,
-#endif
- RawData = 0x4,
- Grow = 0x8,
+ bool isStatic() const
+ {
+ return flags & ImmutableHeader;
+ }
- Default = 0
- };
+ bool isShared() const
+ {
+ return ref_.loadRelaxed() != 1;
+ }
- Q_DECLARE_FLAGS(AllocationOptions, AllocationOption)
+ // Returns true if a detach is necessary before modifying the data
+ // This method is intentionally not const: if you want to know whether
+ // detaching is necessary, you should be in a non-const function already
+ bool needsDetach()
+ {
+ // requires two conditionals
+ return !isMutable() || isShared();
+ }
size_t detachCapacity(size_t newSize) const
{
- if (capacityReserved && newSize < alloc)
- return alloc;
+ if (flags & CapacityReserved && newSize < constAllocatedCapacity())
+ return constAllocatedCapacity();
return newSize;
}
- AllocationOptions detachFlags() const
+ ArrayOptions detachFlags() const
{
- AllocationOptions result;
- if (capacityReserved)
+ ArrayOptions result = DefaultAllocationFlags;
+ if (flags & CapacityReserved)
result |= CapacityReserved;
return result;
}
- AllocationOptions cloneFlags() const
+ ArrayOptions cloneFlags() const
{
- AllocationOptions result;
- if (capacityReserved)
+ ArrayOptions result = DefaultAllocationFlags;
+ if (flags & CapacityReserved)
result |= CapacityReserved;
return result;
}
- Q_REQUIRED_RESULT static QArrayData *allocate(size_t objectSize, size_t alignment,
- size_t capacity, AllocationOptions options = Default) noexcept;
+ Q_REQUIRED_RESULT
+#if defined(Q_CC_GNU)
+ __attribute__((__malloc__))
+#endif
+ static void *allocate(QArrayData **pdata, size_t objectSize, size_t alignment,
+ size_t capacity, ArrayOptions options = DefaultAllocationFlags) noexcept;
Q_REQUIRED_RESULT static QArrayData *reallocateUnaligned(QArrayData *data, size_t objectSize,
- size_t newCapacity, AllocationOptions newOptions = Default) noexcept;
+ size_t newCapacity, ArrayOptions newOptions = DefaultAllocationFlags) noexcept;
+ Q_REQUIRED_RESULT static QPair<QArrayData *, void *> reallocateUnaligned(QArrayData *data, void *dataPointer,
+ size_t objectSize, size_t newCapacity, ArrayOptions newOptions = DefaultAllocationFlags) Q_DECL_NOTHROW;
+ Q_REQUIRED_RESULT static QArrayData *prepareRawData(ArrayOptions options = ArrayOptions(RawDataType))
+ Q_DECL_NOTHROW;
static void deallocate(QArrayData *data, size_t objectSize,
size_t alignment) noexcept;
static const QArrayData shared_null[2];
static QArrayData *sharedNull() noexcept { return const_cast<QArrayData*>(shared_null); }
+ static void *sharedNullData()
+ {
+ QArrayData *const null = const_cast<QArrayData *>(&shared_null[1]);
+ return null;
+ }
+};
+
+Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::ArrayOptions)
+
+template <class T, size_t N>
+struct QStaticArrayData
+{
+ // static arrays are of type RawDataType
+ QArrayData header;
+ T data[N];
};
-Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::AllocationOptions)
+// Support for returning QArrayDataPointer<T> from functions
+template <class T>
+struct QArrayDataPointerRef
+{
+ QTypedArrayData<T> *ptr;
+ T *data;
+ uint size;
+};
template <class T>
struct QTypedArrayData
@@ -205,51 +274,45 @@ struct QTypedArrayData
typedef const T* const_iterator;
#endif
- T *data() { return static_cast<T *>(QArrayData::data()); }
- const T *data() const { return static_cast<const T *>(QArrayData::data()); }
-
- iterator begin(iterator = iterator()) { return data(); }
- iterator end(iterator = iterator()) { return data() + size; }
- const_iterator begin(const_iterator = const_iterator()) const { return data(); }
- const_iterator end(const_iterator = const_iterator()) const { return data() + size; }
- const_iterator constBegin(const_iterator = const_iterator()) const { return data(); }
- const_iterator constEnd(const_iterator = const_iterator()) const { return data() + size; }
-
class AlignmentDummy { QArrayData header; T data; };
- Q_REQUIRED_RESULT static QTypedArrayData *allocate(size_t capacity,
- AllocationOptions options = Default)
+ Q_REQUIRED_RESULT static QPair<QTypedArrayData *, T *> allocate(size_t capacity,
+ ArrayOptions options = DefaultAllocationFlags)
{
Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
- return static_cast<QTypedArrayData *>(QArrayData::allocate(sizeof(T),
- Q_ALIGNOF(AlignmentDummy), capacity, options));
+ QArrayData *d;
+ void *result = QArrayData::allocate(&d, sizeof(T), alignof(AlignmentDummy), capacity, options);
+#if (defined(Q_CC_GNU) && Q_CC_GNU >= 407) || QT_HAS_BUILTIN(__builtin_assume_aligned)
+ result = __builtin_assume_aligned(result, Q_ALIGNOF(AlignmentDummy));
+#endif
+ return qMakePair(static_cast<QTypedArrayData *>(d), static_cast<T *>(result));
}
- static QTypedArrayData *reallocateUnaligned(QTypedArrayData *data, size_t capacity,
- AllocationOptions options = Default)
+ static QPair<QTypedArrayData *, T *>
+ reallocateUnaligned(QTypedArrayData *data, T *dataPointer, size_t capacity,
+ ArrayOptions options = DefaultAllocationFlags)
{
Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
- return static_cast<QTypedArrayData *>(QArrayData::reallocateUnaligned(data, sizeof(T),
- capacity, options));
+ QPair<QArrayData *, void *> pair =
+ QArrayData::reallocateUnaligned(data, dataPointer, sizeof(T), capacity, options);
+ return qMakePair(static_cast<QTypedArrayData *>(pair.first), static_cast<T *>(pair.second));
}
static void deallocate(QArrayData *data)
{
Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
- QArrayData::deallocate(data, sizeof(T), Q_ALIGNOF(AlignmentDummy));
+ QArrayData::deallocate(data, sizeof(T), alignof(AlignmentDummy));
}
- static QTypedArrayData *fromRawData(const T *data, size_t n,
- AllocationOptions options = Default)
+ static QArrayDataPointerRef<T> fromRawData(const T *data, size_t n,
+ ArrayOptions options = DefaultRawFlags)
{
Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
- QTypedArrayData *result = allocate(0, options | RawData);
- if (result) {
- Q_ASSERT(!result->ref.isShared()); // No shared empty, please!
-
- result->offset = reinterpret_cast<const char *>(data)
- - reinterpret_cast<const char *>(result);
- result->size = int(n);
+ QArrayDataPointerRef<T> result = {
+ static_cast<QTypedArrayData *>(prepareRawData(options)), const_cast<T *>(data), uint(n)
+ };
+ if (result.ptr) {
+ Q_ASSERT(!result.ptr->isShared()); // No shared empty, please!
}
return result;
}
@@ -266,38 +329,13 @@ struct QTypedArrayData
return allocate(/* capacity */ 0);
}
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- static QTypedArrayData *unsharableEmpty()
+ static T *sharedNullData()
{
Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData));
- return allocate(/* capacity */ 0, Unsharable);
+ return static_cast<T *>(QArrayData::sharedNullData());
}
-#endif
-};
-
-template <class T, size_t N>
-struct QStaticArrayData
-{
- QArrayData header;
- T data[N];
-};
-
-// Support for returning QArrayDataPointer<T> from functions
-template <class T>
-struct QArrayDataPointerRef
-{
- QTypedArrayData<T> *ptr;
};
-#define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size, offset) \
- { Q_REFCOUNT_INITIALIZE_STATIC, size, 0, 0, offset } \
- /**/
-
-#define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(type, size) \
- Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size,\
- ((sizeof(QArrayData) + (Q_ALIGNOF(type) - 1)) & ~(Q_ALIGNOF(type) - 1) )) \
- /**/
-
////////////////////////////////////////////////////////////////////////////////
// Q_ARRAY_LITERAL
@@ -333,15 +371,16 @@ struct QArrayDataPointerRef
Q_ARRAY_LITERAL_CHECK_LITERAL_TYPE(Type); \
\
/* Portable compile-time array size computation */ \
- Q_CONSTEXPR Type data[] = { __VA_ARGS__ }; Q_UNUSED(data); \
+ static Type const data[] = { __VA_ARGS__ }; \
enum { Size = sizeof(data) / sizeof(data[0]) }; \
\
- static const QStaticArrayData<Type, Size> literal = { \
- Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(Type, Size), { __VA_ARGS__ } }; \
+ static const QArrayData literal = { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }; \
\
QArrayDataPointerRef<Type> ref = \
{ static_cast<QTypedArrayData<Type> *>( \
- const_cast<QArrayData *>(&literal.header)) }; \
+ const_cast<QArrayData *>(&literal)), \
+ const_cast<Type *>(data), \
+ Size }; \
/**/
namespace QtPrivate {
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 8e19525f07..0d2be5d51c 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -1,6 +1,7 @@
/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2016 Intel Corporation.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
@@ -41,12 +42,15 @@
#define QARRAYDATAOPS_H
#include <QtCore/qarraydata.h>
+#include <QtCore/qcontainertools_impl.h>
#include <new>
#include <string.h>
QT_BEGIN_NAMESPACE
+template <class T> struct QArrayDataPointer;
+
namespace QtPrivate {
QT_WARNING_PUSH
@@ -56,48 +60,67 @@ QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
template <class T>
struct QPodArrayOps
- : QTypedArrayData<T>
+ : public QArrayDataPointer<T>
{
+ typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
+
void appendInitialize(size_t newSize)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(newSize > uint(this->size));
- Q_ASSERT(newSize <= this->alloc);
+ Q_ASSERT(newSize <= this->allocatedCapacity());
::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T));
this->size = int(newSize);
}
+ template<typename iterator>
+ void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true)
+ {
+ Q_ASSERT(this->isMutable() || b == e);
+ Q_ASSERT(!this->isShared() || b == e);
+ Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size);
+
+ T *iter = this->end();
+ for (; b != e; ++iter, ++b) {
+ new (iter) T(*b);
+ ++this->size;
+ }
+ }
+
void copyAppend(const T *b, const T *e)
{
- Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
- Q_ASSERT(b < e);
- Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+ Q_ASSERT(this->isMutable() || b == e);
+ Q_ASSERT(!this->isShared() || b == e);
+ Q_ASSERT(b <= e);
+ Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b),
(e - b) * sizeof(T));
this->size += e - b;
}
- void copyAppend(size_t n, const T &t)
+ void moveAppend(T *b, T *e)
+ { copyAppend(b, e); }
+
+ void copyAppend(size_t n, parameter_type t)
{
- Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
- Q_ASSERT(n <= this->alloc - uint(this->size));
+ Q_ASSERT(this->isMutable() || n == 0);
+ Q_ASSERT(!this->isShared() || n == 0);
+ Q_ASSERT(n <= uint(this->allocatedCapacity() - this->size));
T *iter = this->end();
const T *const end = iter + n;
for (; iter != end; ++iter)
- ::memcpy(iter, &t, sizeof(T));
+ *iter = t;
this->size += int(n);
}
void truncate(size_t newSize)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(newSize < size_t(this->size));
this->size = int(newSize);
@@ -106,7 +129,7 @@ struct QPodArrayOps
void destroyAll() // Call from destructors, ONLY!
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(this->ref.atomic.loadRelaxed() == 0);
+ Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
// As this is to be called only from destructor, it doesn't need to be
// exception safe; size not updated.
@@ -115,11 +138,11 @@ struct QPodArrayOps
void insert(T *where, const T *b, const T *e)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
- Q_ASSERT(b < e);
+ Q_ASSERT(b <= e);
Q_ASSERT(e <= where || b > this->end()); // No overlap
- Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+ Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
::memmove(static_cast<void *>(where + (e - b)), static_cast<void *>(where),
(static_cast<const T*>(this->end()) - where) * sizeof(T));
@@ -127,43 +150,97 @@ struct QPodArrayOps
this->size += (e - b);
}
+ void insert(T *where, size_t n, parameter_type t)
+ {
+ Q_ASSERT(!this->isShared());
+ Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
+ Q_ASSERT(this->allocatedCapacity() - this->size >= n);
+
+ ::memmove(static_cast<void *>(where + n), static_cast<void *>(where),
+ (static_cast<const T*>(this->end()) - where) * sizeof(T));
+ this->size += int(n); // PODs can't throw on copy
+ while (n--)
+ *where++ = t;
+ }
+
+ void insert(T *where, T &&t)
+ {
+ Q_ASSERT(!this->isShared());
+ Q_ASSERT(where >= this->begin() && where <= this->end());
+ Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
+
+ ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where),
+ (static_cast<const T*>(this->end()) - where) * sizeof(T));
+ this->size += 1;
+ new (where) T(std::move(t));
+ }
+
+
void erase(T *b, T *e)
{
Q_ASSERT(this->isMutable());
Q_ASSERT(b < e);
Q_ASSERT(b >= this->begin() && b < this->end());
- Q_ASSERT(e > this->begin() && e < this->end());
+ Q_ASSERT(e > this->begin() && e <= this->end());
::memmove(static_cast<void *>(b), static_cast<void *>(e),
(static_cast<T *>(this->end()) - e) * sizeof(T));
this->size -= (e - b);
}
+
+ void assign(T *b, T *e, parameter_type t)
+ {
+ Q_ASSERT(b <= e);
+ Q_ASSERT(b >= this->begin() && e <= this->end());
+
+ while (b != e)
+ ::memcpy(static_cast<void *>(b++), static_cast<const void *>(&t), sizeof(T));
+ }
+
+ bool compare(const T *begin1, const T *begin2, size_t n) const
+ {
+ // only use memcmp for fundamental types or pointers.
+ // Other types could have padding in the data structure or custom comparison
+ // operators that would break the comparison using memcmp
+ if (QArrayDataPointer<T>::pass_parameter_by_value)
+ return ::memcmp(begin1, begin2, n * sizeof(T)) == 0;
+ const T *end1 = begin1 + n;
+ while (begin1 != end1) {
+ if (*begin1 == *begin2)
+ ++begin1, ++begin2;
+ else
+ return false;
+ }
+ return true;
+ }
};
QT_WARNING_POP
template <class T>
struct QGenericArrayOps
- : QTypedArrayData<T>
+ : public QArrayDataPointer<T>
{
+ typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
+
void appendInitialize(size_t newSize)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(newSize > uint(this->size));
- Q_ASSERT(newSize <= this->alloc);
+ Q_ASSERT(newSize <= this->allocatedCapacity());
- T *const begin = this->begin();
+ T *const b = this->begin();
do {
- new (begin + this->size) T;
+ new (b + this->size) T;
} while (uint(++this->size) != newSize);
}
- void copyAppend(const T *b, const T *e)
+ template<typename iterator>
+ void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true)
{
- Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
- Q_ASSERT(b < e);
- Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+ Q_ASSERT(this->isMutable() || b == e);
+ Q_ASSERT(!this->isShared() || b == e);
+ Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size);
T *iter = this->end();
for (; b != e; ++iter, ++b) {
@@ -172,11 +249,37 @@ struct QGenericArrayOps
}
}
- void copyAppend(size_t n, const T &t)
+ void copyAppend(const T *b, const T *e)
{
- Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
- Q_ASSERT(n <= this->alloc - uint(this->size));
+ Q_ASSERT(this->isMutable() || b == e);
+ Q_ASSERT(!this->isShared() || b == e);
+ Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size);
+
+ T *iter = this->end();
+ this->size += e - b;
+ for (; b != e; ++iter, ++b)
+ new (iter) T(*b);
+ }
+
+ void moveAppend(T *b, T *e)
+ {
+ Q_ASSERT(this->isMutable() || b == e);
+ Q_ASSERT(!this->isShared() || b == e);
+ Q_ASSERT(b <= e);
+ Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
+
+ T *iter = this->end();
+ for (; b != e; ++iter, ++b) {
+ new (iter) T(std::move(*b));
+ ++this->size;
+ }
+ }
+
+ void copyAppend(size_t n, parameter_type t)
+ {
+ Q_ASSERT(this->isMutable() || n == 0);
+ Q_ASSERT(!this->isShared() || n == 0);
+ Q_ASSERT(n <= size_t(this->allocatedCapacity() - this->size));
T *iter = this->end();
const T *const end = iter + n;
@@ -189,7 +292,7 @@ struct QGenericArrayOps
void truncate(size_t newSize)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(newSize < size_t(this->size));
const T *const b = this->begin();
@@ -204,7 +307,7 @@ struct QGenericArrayOps
// As this is to be called only from destructor, it doesn't need to be
// exception safe; size not updated.
- Q_ASSERT(this->ref.atomic.loadRelaxed() == 0);
+ Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
const T *const b = this->begin();
const T *i = this->end();
@@ -216,11 +319,11 @@ struct QGenericArrayOps
void insert(T *where, const T *b, const T *e)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
- Q_ASSERT(b < e);
+ Q_ASSERT(b <= e);
Q_ASSERT(e <= where || b > this->end()); // No overlap
- Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+ Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
// Array may be truncated at where in case of exceptions
@@ -279,25 +382,139 @@ struct QGenericArrayOps
}
}
+ void insert(T *where, size_t n, parameter_type t)
+ {
+ Q_ASSERT(!this->isShared());
+ Q_ASSERT(where >= this->begin() && where <= this->end());
+ Q_ASSERT(this->allocatedCapacity() - this->size >= n);
+
+ // Array may be truncated at where in case of exceptions
+ T *const end = this->end();
+ const T *readIter = end;
+ T *writeIter = end + n;
+
+ const T *const step1End = where + qMax<size_t>(n, end - where);
+
+ struct Destructor
+ {
+ Destructor(T *&it)
+ : iter(&it)
+ , end(it)
+ {
+ }
+
+ void commit()
+ {
+ iter = &end;
+ }
+
+ ~Destructor()
+ {
+ for (; *iter != end; --*iter)
+ (*iter)->~T();
+ }
+
+ T **iter;
+ T *end;
+ } destroyer(writeIter);
+
+ // Construct new elements in array
+ do {
+ --readIter, --writeIter;
+ new (writeIter) T(*readIter);
+ } while (writeIter != step1End);
+
+ while (writeIter != end) {
+ --n, --writeIter;
+ new (writeIter) T(t);
+ }
+
+ destroyer.commit();
+ this->size += destroyer.end - end;
+
+ // Copy assign over existing elements
+ while (readIter != where) {
+ --readIter, --writeIter;
+ *writeIter = *readIter;
+ }
+
+ while (writeIter != where) {
+ --n, --writeIter;
+ *writeIter = t;
+ }
+ }
+
+ void insert(T *where, T &&t)
+ {
+ Q_ASSERT(!this->isShared());
+ Q_ASSERT(where >= this->begin() && where <= this->end());
+ Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
+
+ // Array may be truncated at where in case of exceptions
+ T *const end = this->end();
+
+ if (where != end) {
+ // Move elements in array
+ T *readIter = end - 1;
+ T *writeIter = end;
+ new (writeIter) T(std::move(*readIter));
+ while (readIter > where) {
+ --readIter;
+ --writeIter;
+ *writeIter = std::move(*readIter);
+ }
+ *where = std::move(t);
+ } else {
+ new (where) T(std::move(t));
+ }
+
+ ++this->size;
+ }
+
void erase(T *b, T *e)
{
Q_ASSERT(this->isMutable());
Q_ASSERT(b < e);
Q_ASSERT(b >= this->begin() && b < this->end());
- Q_ASSERT(e > this->begin() && e < this->end());
+ Q_ASSERT(e > this->begin() && e <= this->end());
const T *const end = this->end();
- do {
+ // move (by assignment) the elements from e to end
+ // onto b to the new end
+ while (e != end) {
*b = *e;
++b, ++e;
- } while (e != end);
+ }
+ // destroy the final elements at the end
+ // here, b points to the new end and e to the actual end
do {
(--e)->~T();
--this->size;
} while (e != b);
}
+
+ void assign(T *b, T *e, parameter_type t)
+ {
+ Q_ASSERT(b <= e);
+ Q_ASSERT(b >= this->begin() && e <= this->end());
+
+ while (b != e)
+ *b++ = t;
+ }
+
+ bool compare(const T *begin1, const T *begin2, size_t n) const
+ {
+ const T *end1 = begin1 + n;
+ while (begin1 != end1) {
+ if (*begin1 == *begin2)
+ ++begin1, ++begin2;
+ else
+ return false;
+ }
+ return true;
+ }
};
template <class T>
@@ -308,15 +525,16 @@ struct QMovableArrayOps
// using QGenericArrayOps<T>::copyAppend;
// using QGenericArrayOps<T>::truncate;
// using QGenericArrayOps<T>::destroyAll;
+ typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
void insert(T *where, const T *b, const T *e)
{
Q_ASSERT(this->isMutable());
- Q_ASSERT(!this->ref.isShared());
+ Q_ASSERT(!this->isShared());
Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
- Q_ASSERT(b < e);
+ Q_ASSERT(b <= e);
Q_ASSERT(e <= where || b > this->end()); // No overlap
- Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+ Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
// Provides strong exception safety guarantee,
// provided T::~T() nothrow
@@ -376,12 +594,79 @@ struct QMovableArrayOps
this->size += (e - b);
}
+ void insert(T *where, size_t n, parameter_type t)
+ {
+ Q_ASSERT(!this->isShared());
+ Q_ASSERT(where >= this->begin() && where <= this->end());
+ Q_ASSERT(this->allocatedCapacity() - this->size >= n);
+
+ // Provides strong exception safety guarantee,
+ // provided T::~T() nothrow
+
+ struct ReversibleDisplace
+ {
+ ReversibleDisplace(T *start, T *finish, size_t diff)
+ : begin(start)
+ , end(finish)
+ , displace(diff)
+ {
+ ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
+ (end - begin) * sizeof(T));
+ }
+
+ void commit() { displace = 0; }
+
+ ~ReversibleDisplace()
+ {
+ if (displace)
+ ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
+ (end - begin) * sizeof(T));
+ }
+
+ T *const begin;
+ T *const end;
+ size_t displace;
+
+ } displace(where, this->end(), n);
+
+ struct CopyConstructor
+ {
+ CopyConstructor(T *w) : where(w) {}
+
+ void copy(size_t count, parameter_type proto)
+ {
+ n = 0;
+ while (count--) {
+ new (where + n) T(proto);
+ ++n;
+ }
+ n = 0;
+ }
+
+ ~CopyConstructor()
+ {
+ while (n)
+ where[--n].~T();
+ }
+
+ T *const where;
+ size_t n;
+ } copier(where);
+
+ copier.copy(n, t);
+ displace.commit();
+ this->size += int(n);
+ }
+
+ // use moving insert
+ using QGenericArrayOps<T>::insert;
+
void erase(T *b, T *e)
{
Q_ASSERT(this->isMutable());
Q_ASSERT(b < e);
Q_ASSERT(b >= this->begin() && b < this->end());
- Q_ASSERT(e > this->begin() && e < this->end());
+ Q_ASSERT(e > this->begin() && e <= this->end());
struct Mover
{
@@ -405,11 +690,51 @@ struct QMovableArrayOps
int &size;
} mover(e, this->end(), this->size);
+ // destroy the elements we're erasing
do {
// Exceptions or not, dtor called once per instance
(--e)->~T();
} while (e != b);
}
+
+ void moveAppend(T *b, T *e)
+ {
+ Q_ASSERT(this->isMutable());
+ Q_ASSERT(!this->isShared());
+ Q_ASSERT(b <= e);
+ Q_ASSERT(e <= this->begin() || b > this->end()); // No overlap
+ Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
+
+ // Provides strong exception safety guarantee,
+ // provided T::~T() nothrow
+
+ struct CopyConstructor
+ {
+ CopyConstructor(T *w) : where(w) {}
+
+ void copy(T *src, const T *const srcEnd)
+ {
+ n = 0;
+ for (; src != srcEnd; ++src) {
+ new (where + n) T(std::move(*src));
+ ++n;
+ }
+ n = 0;
+ }
+
+ ~CopyConstructor()
+ {
+ while (n)
+ where[--n].~T();
+ }
+
+ T *const where;
+ size_t n;
+ } copier(this->end());
+
+ copier.copy(b, e);
+ this->size += (e - b);
+ }
};
template <class T, class = void>
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h
index af5173c9ad..a17cf4a101 100644
--- a/src/corelib/tools/qarraydatapointer.h
+++ b/src/corelib/tools/qarraydatapointer.h
@@ -41,6 +41,7 @@
#define QARRAYDATAPOINTER_H
#include <QtCore/qarraydataops.h>
+#include <QtCore/qcontainertools_impl.h>
QT_BEGIN_NAMESPACE
@@ -52,30 +53,40 @@ private:
typedef QArrayDataOps<T> DataOps;
public:
+ typedef typename Data::iterator iterator;
+ typedef typename Data::const_iterator const_iterator;
+ enum { pass_parameter_by_value = std::is_fundamental<T>::value || std::is_pointer<T>::value };
+
+ typedef typename std::conditional<pass_parameter_by_value, T, const T &>::type parameter_type;
+
QArrayDataPointer() noexcept
- : d(Data::sharedNull())
+ : d(Data::sharedNull()), ptr(Data::sharedNullData()), size(0)
{
}
- QArrayDataPointer(const QArrayDataPointer &other)
- : d(other.d->ref.ref()
- ? other.d
- : other.clone(other.d->cloneFlags()))
+ QArrayDataPointer(const QArrayDataPointer &other) noexcept
+ : d(other.d), ptr(other.ptr), size(other.size)
{
+ other.d->ref();
}
- explicit QArrayDataPointer(QTypedArrayData<T> *ptr)
- : d(ptr)
+ QArrayDataPointer(Data *header, T *adata, size_t n = 0) noexcept
+ : d(header), ptr(adata), size(int(n))
{
- Q_CHECK_PTR(ptr);
}
- QArrayDataPointer(QArrayDataPointerRef<T> ref)
- : d(ref.ptr)
+ explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> adata, size_t n = 0)
+ : d(adata.first), ptr(adata.second), size(int(n))
{
+ Q_CHECK_PTR(d);
}
- QArrayDataPointer &operator=(const QArrayDataPointer &other)
+ QArrayDataPointer(QArrayDataPointerRef<T> dd) noexcept
+ : d(dd.ptr), ptr(dd.data), size(dd.size)
+ {
+ }
+
+ QArrayDataPointer &operator=(const QArrayDataPointer &other) noexcept
{
QArrayDataPointer tmp(other);
this->swap(tmp);
@@ -83,9 +94,11 @@ public:
}
QArrayDataPointer(QArrayDataPointer &&other) noexcept
- : d(other.d)
+ : d(other.d), ptr(other.ptr), size(other.size)
{
other.d = Data::sharedNull();
+ other.ptr = Data::sharedNullData();
+ other.size = 0;
}
QArrayDataPointer &operator=(QArrayDataPointer &&other) noexcept
@@ -95,114 +108,142 @@ public:
return *this;
}
- DataOps &operator*() const
+ DataOps &operator*() noexcept
{
Q_ASSERT(d);
- return *static_cast<DataOps *>(d);
+ return *static_cast<DataOps *>(this);
}
- DataOps *operator->() const
+ DataOps *operator->() noexcept
{
Q_ASSERT(d);
- return static_cast<DataOps *>(d);
+ return static_cast<DataOps *>(this);
}
- ~QArrayDataPointer()
+ const DataOps &operator*() const noexcept
{
- if (!d->ref.deref()) {
- if (d->isMutable())
- (*this)->destroyAll();
- Data::deallocate(d);
- }
+ Q_ASSERT(d);
+ return *static_cast<const DataOps *>(this);
}
- bool isNull() const
+ const DataOps *operator->() const noexcept
{
- return d == Data::sharedNull();
+ Q_ASSERT(d);
+ return static_cast<const DataOps *>(this);
}
- Data *data() const
+ ~QArrayDataPointer()
{
- return d;
+ if (!deref()) {
+ if (isMutable())
+ (*this)->destroyAll();
+ Data::deallocate(d);
+ }
}
- bool needsDetach() const
+ bool isNull() const noexcept
{
- return (!d->isMutable() || d->ref.isShared());
+ return d == Data::sharedNull();
}
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- void setSharable(bool sharable)
- {
- if (needsDetach()) {
- Data *detached = clone(sharable
- ? d->detachFlags() & ~QArrayData::Unsharable
- : d->detachFlags() | QArrayData::Unsharable);
- QArrayDataPointer old(d);
- d = detached;
- } else {
- d->ref.setSharable(sharable);
- }
- }
+ T *data() noexcept { return ptr; }
+ const T *data() const noexcept { return ptr; }
- bool isSharable() const { return d->isSharable(); }
-#endif
+ iterator begin(iterator = iterator()) noexcept { return data(); }
+ iterator end(iterator = iterator()) noexcept { return data() + size; }
+ const_iterator begin(const_iterator = const_iterator()) const noexcept { return data(); }
+ const_iterator end(const_iterator = const_iterator()) const noexcept { return data() + size; }
+ const_iterator constBegin(const_iterator = const_iterator()) const noexcept { return data(); }
+ const_iterator constEnd(const_iterator = const_iterator()) const noexcept { return data() + size; }
void swap(QArrayDataPointer &other) noexcept
{
qSwap(d, other.d);
+ qSwap(ptr, other.ptr);
+ qSwap(size, other.size);
}
- void clear()
+ void clear() Q_DECL_NOEXCEPT_EXPR(std::is_nothrow_destructible<T>::value)
{
- QArrayDataPointer tmp(d);
- d = Data::sharedNull();
+ QArrayDataPointer tmp;
+ swap(tmp);
}
bool detach()
{
- if (needsDetach()) {
- Data *copy = clone(d->detachFlags());
- QArrayDataPointer old(d);
- d = copy;
+ if (d->needsDetach()) {
+ QPair<Data *, T *> copy = clone(d->detachFlags());
+ QArrayDataPointer old(d, ptr, size);
+ d = copy.first;
+ ptr = copy.second;
return true;
}
return false;
}
-private:
- Q_REQUIRED_RESULT Data *clone(QArrayData::AllocationOptions options) const
+ // forwards from QArrayData
+ size_t allocatedCapacity() noexcept { return d->allocatedCapacity(); }
+ size_t constAllocatedCapacity() const noexcept { return d->constAllocatedCapacity(); }
+ int refCounterValue() const noexcept { return d->refCounterValue(); }
+ bool ref() noexcept { return d->ref(); }
+ bool deref() noexcept { return d->deref(); }
+ bool isMutable() const noexcept { return d->isMutable(); }
+ bool isStatic() const noexcept { return d->isStatic(); }
+ bool isShared() const noexcept { return d->isShared(); }
+ bool isSharedWith(const QArrayDataPointer &other) const noexcept { return d && d == other.d; }
+ bool needsDetach() const noexcept { return d->needsDetach(); }
+ size_t detachCapacity(size_t newSize) const noexcept { return d->detachCapacity(newSize); }
+ typename Data::ArrayOptions &flags() noexcept { return reinterpret_cast<typename Data::ArrayOptions &>(d->flags); }
+ typename Data::ArrayOptions flags() const noexcept { return typename Data::ArrayOption(d->flags); }
+ typename Data::ArrayOptions detachFlags() const noexcept { return d->detachFlags(); }
+ typename Data::ArrayOptions cloneFlags() const noexcept { return d->cloneFlags(); }
+
+ void reallocate(uint alloc, typename Data::ArrayOptions options)
{
- Data *x = Data::allocate(d->detachCapacity(d->size), options);
- Q_CHECK_PTR(x);
- QArrayDataPointer copy(x);
+ auto pair = Data::reallocateUnaligned(d, ptr, alloc, options);
+ d = pair.first;
+ ptr = pair.second;
+ }
+ Data *d_ptr() { return d; }
- if (d->size)
- copy->copyAppend(d->begin(), d->end());
+private:
+ Q_REQUIRED_RESULT QPair<Data *, T *> clone(QArrayData::ArrayOptions options) const
+ {
+ QPair<Data *, T *> pair = Data::allocate(d->detachCapacity(size),
+ options);
+ Q_CHECK_PTR(pair.first);
+ QArrayDataPointer copy(pair.first, pair.second, 0);
+ if (size)
+ copy->copyAppend(begin(), end());
- Data *result = copy.d;
+ pair.first = copy.d;
copy.d = Data::sharedNull();
- return result;
+ return pair;
}
+protected:
Data *d;
+ T *ptr;
+
+public:
+ int size;
};
template <class T>
-inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs)
+inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept
{
- return lhs.data() == rhs.data();
+ return lhs.data() == rhs.data() && lhs.size == rhs.size;
}
template <class T>
-inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs)
+inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept
{
- return lhs.data() != rhs.data();
+ return lhs.data() != rhs.data() || lhs.size != rhs.size;
}
template <class T>
-inline void swap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2)
+inline void qSwap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept
{
p1.swap(p2);
}
diff --git a/src/corelib/tools/qbitarray.cpp b/src/corelib/tools/qbitarray.cpp
index f0b81cce66..a1dd537d4d 100644
--- a/src/corelib/tools/qbitarray.cpp
+++ b/src/corelib/tools/qbitarray.cpp
@@ -342,6 +342,38 @@ QBitArray QBitArray::fromBits(const char *data, qsizetype size)
return result;
}
+/*!
+ \since 6.0
+
+ Returns the array of bit converted to an int. The conversion is based on \a endianness.
+ Converts up to the first 32 bits of the array to \c quint32 and returns it,
+ obeying \a endianness. If \a ok is not a null pointer, and the array has more
+ than 32 bits, \a ok is set to false and this function returns zero; otherwise,
+ it's set to true.
+*/
+quint32 QBitArray::toUInt32(QSysInfo::Endian endianness, bool *ok) const noexcept
+{
+ const qsizetype _size = size();
+ if (_size > 32) {
+ if (ok)
+ *ok = false;
+ return 0;
+ }
+
+ if (ok)
+ *ok = true;
+
+ quint32 factor = 1;
+ quint32 total = 0;
+ for (qsizetype i = 0; i < _size; ++i, factor *= 2) {
+ const auto index = endianness == QSysInfo::Endian::LittleEndian ? i : (_size - i - 1);
+ if (testBit(index))
+ total += factor;
+ }
+
+ return total;
+}
+
/*! \fn bool QBitArray::isDetached() const
\internal
diff --git a/src/corelib/tools/qbitarray.h b/src/corelib/tools/qbitarray.h
index 9b0e931aca..ac3a8771d9 100644
--- a/src/corelib/tools/qbitarray.h
+++ b/src/corelib/tools/qbitarray.h
@@ -105,8 +105,10 @@ public:
const char *bits() const { return isEmpty() ? nullptr : d.constData() + 1; }
static QBitArray fromBits(const char *data, qsizetype len);
+ quint32 toUInt32(QSysInfo::Endian endianness, bool *ok = nullptr) const noexcept;
+
public:
- typedef QByteArray::DataPtr DataPtr;
+ typedef QByteArray::DataPointer DataPtr;
inline DataPtr &data_ptr() { return d.data_ptr(); }
};
diff --git a/src/corelib/tools/qcontainerfwd.h b/src/corelib/tools/qcontainerfwd.h
index 532b4c95ce..f6efa99b6a 100644
--- a/src/corelib/tools/qcontainerfwd.h
+++ b/src/corelib/tools/qcontainerfwd.h
@@ -50,7 +50,6 @@ template <class Key, class T> class QHash;
#ifndef QT_NO_LINKED_LIST
template <class T> class QLinkedList;
#endif
-template <class T> class QList;
template <class Key, class T> class QMap;
template <class Key, class T> class QMultiHash;
template <class Key, class T> class QMultiMap;
@@ -60,6 +59,7 @@ template <class T> class QSet;
template <class T> class QStack;
template<class T, int Prealloc = 256> class QVarLengthArray;
template <class T> class QVector;
+template<typename T> using QList = QVector<T>;
QT_END_NAMESPACE
diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h
index 7b74b4f526..8cae7d1651 100644
--- a/src/corelib/tools/qcontiguouscache.h
+++ b/src/corelib/tools/qcontiguouscache.h
@@ -102,9 +102,6 @@ public:
inline void detach() { if (d->ref.loadRelaxed() != 1) detach_helper(); }
inline bool isDetached() const { return d->ref.loadRelaxed() == 1; }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
-#endif
QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other) noexcept
@@ -166,7 +163,7 @@ private:
}
int alignOfTypedData() const
{
- return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
+ return qMax<int>(sizeof(void*), alignof(Data));
}
};
diff --git a/src/corelib/tools/qeasingcurve.cpp b/src/corelib/tools/qeasingcurve.cpp
index 7f9b6ef39f..0ec51aa4d3 100644
--- a/src/corelib/tools/qeasingcurve.cpp
+++ b/src/corelib/tools/qeasingcurve.cpp
@@ -1382,11 +1382,6 @@ void QEasingCurve::addTCBSegment(const QPointF &nextPoint, qreal t, qreal c, qre
}
/*!
- \fn QList<QPointF> QEasingCurve::cubicBezierSpline() const
- \obsolete Use toCubicSpline() instead.
- */
-
-/*!
\since 5.0
Returns the cubicBezierSpline that defines a custom easing curve.
diff --git a/src/corelib/tools/qeasingcurve.h b/src/corelib/tools/qeasingcurve.h
index d3a468bb22..81833a758f 100644
--- a/src/corelib/tools/qeasingcurve.h
+++ b/src/corelib/tools/qeasingcurve.h
@@ -46,10 +46,6 @@ QT_REQUIRE_CONFIG(easingcurve);
#include <QtCore/qobjectdefs.h>
#include <QtCore/qvector.h>
-#if QT_DEPRECATED_SINCE(5, 0)
-# include <QtCore/qlist.h>
-# include <QtCore/qpoint.h>
-#endif
QT_BEGIN_NAMESPACE
@@ -105,9 +101,6 @@ public:
void addCubicBezierSegment(const QPointF & c1, const QPointF & c2, const QPointF & endPoint);
void addTCBSegment(const QPointF &nextPoint, qreal t, qreal c, qreal b);
QVector<QPointF> toCubicSpline() const;
-#if QT_DEPRECATED_SINCE(5, 0)
- QT_DEPRECATED QList<QPointF> cubicBezierSpline() const { return toCubicSpline().toList(); }
-#endif
Type type() const;
void setType(Type type);
diff --git a/src/corelib/tools/qflatmap_p.h b/src/corelib/tools/qflatmap_p.h
new file mode 100644
index 0000000000..590b0d942f
--- /dev/null
+++ b/src/corelib/tools/qflatmap_p.h
@@ -0,0 +1,982 @@
+/****************************************************************************
+**
+** Copyright (C) 2020 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QFLATMAP_P_H
+#define QFLATMAP_P_H
+
+//
+// W A R N I N G
+// -------------
+//
+// This file is not part of the Qt API. It exists for the convenience
+// of a number of Qt sources files. This header file may change from
+// version to version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include "qvector.h"
+
+#include <algorithm>
+#include <functional>
+#include <initializer_list>
+#include <iterator>
+#include <numeric>
+#include <type_traits>
+#include <utility>
+
+QT_BEGIN_NAMESPACE
+
+/*
+ QFlatMap provides an associative container backed by sorted sequential
+ containers. By default, QVector is used.
+
+ Keys and values are stored in two separate containers. This provides improved
+ cache locality for key iteration and makes keys() and values() fast
+ operations.
+
+ One can customize the underlying container type by passing the KeyContainer
+ and MappedContainer template arguments:
+ QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>>
+*/
+
+namespace Qt {
+
+struct OrderedUniqueRange_t {};
+constexpr OrderedUniqueRange_t OrderedUniqueRange = {};
+
+} // namespace Qt
+
+template <class Key, class T, class Compare>
+class QFlatMapValueCompare : protected Compare
+{
+public:
+ QFlatMapValueCompare() = default;
+ QFlatMapValueCompare(const Compare &key_compare)
+ : Compare(key_compare)
+ {
+ }
+
+ using value_type = std::pair<const Key, T>;
+ static constexpr bool is_comparator_noexcept = noexcept(
+ std::declval<Compare>()(std::declval<Key>(), std::declval<Key>()));
+
+ bool operator()(const value_type &lhs, const value_type &rhs) const
+ noexcept(is_comparator_noexcept)
+ {
+ return Compare::operator()(lhs.first, rhs.first);
+ }
+};
+
+template <class Key, class T,
+ class Compare = std::less<Key>,
+ class KeyContainer = QVector<Key>,
+ class MappedContainer = QVector<T>>
+class QFlatMap : private QFlatMapValueCompare<Key, T, Compare>
+{
+ using full_map_t = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>;
+
+ template <class U>
+ class mock_pointer
+ {
+ U ref;
+ public:
+ mock_pointer(U r)
+ : ref(r)
+ {
+ }
+
+ U *operator->()
+ {
+ return &ref;
+ }
+ };
+
+public:
+ using key_type = Key;
+ using mapped_type = T;
+ using value_compare = QFlatMapValueCompare<Key, T, Compare>;
+ using value_type = typename value_compare::value_type;
+ using key_container_type = KeyContainer;
+ using mapped_container_type = MappedContainer;
+ using size_type = typename key_container_type::size_type;
+ using key_compare = Compare;
+
+ struct containers
+ {
+ key_container_type keys;
+ mapped_container_type values;
+ };
+
+ class iterator
+ {
+ public:
+ using difference_type = ptrdiff_t;
+ using value_type = std::pair<const Key, T>;
+ using reference = std::pair<const Key &, T &>;
+ using pointer = mock_pointer<reference>;
+ using iterator_category = std::random_access_iterator_tag;
+
+ iterator() = default;
+
+ iterator(containers *ac, size_type ai)
+ : c(ac), i(ai)
+ {
+ }
+
+ reference operator*()
+ {
+ return { c->keys[i], c->values[i] };
+ }
+
+ pointer operator->()
+ {
+ return { operator*() };
+ }
+
+ bool operator==(const iterator &o) const
+ {
+ return c == o.c && i == o.i;
+ }
+
+ bool operator!=(const iterator &o) const
+ {
+ return !operator==(o);
+ }
+
+ iterator &operator++()
+ {
+ ++i;
+ return *this;
+ }
+
+ iterator operator++(int)
+ {
+
+ iterator r = *this;
+ i++;
+ return r;
+ }
+
+ iterator &operator--()
+ {
+ --i;
+ return *this;
+ }
+
+ iterator operator--(int)
+ {
+ iterator r = *this;
+ i--;
+ return r;
+ }
+
+ iterator &operator+=(size_type n)
+ {
+ i += n;
+ return *this;
+ }
+
+ friend iterator operator+(size_type n, const iterator a)
+ {
+ iterator ret = a;
+ return ret += n;
+ }
+
+ friend iterator operator+(const iterator a, size_type n)
+ {
+ return n + a;
+ }
+
+ iterator &operator-=(size_type n)
+ {
+ i -= n;
+ return *this;
+ }
+
+ friend iterator operator-(const iterator a, size_type n)
+ {
+ iterator ret = a;
+ return ret -= n;
+ }
+
+ friend difference_type operator-(const iterator b, const iterator a)
+ {
+ return b.i - a.i;
+ }
+
+ reference operator[](size_type n)
+ {
+ size_type k = i + n;
+ return { c->keys[k], c->values[k] };
+ }
+
+ bool operator<(const iterator &other) const
+ {
+ return i < other.i;
+ }
+
+ bool operator>(const iterator &other) const
+ {
+ return i > other.i;
+ }
+
+ bool operator<=(const iterator &other) const
+ {
+ return i <= other.i;
+ }
+
+ bool operator>=(const iterator &other) const
+ {
+ return i >= other.i;
+ }
+
+ const Key &key() const { return c->keys[i]; }
+ T &value() { return c->values[i]; }
+
+ private:
+ containers *c = nullptr;
+ size_type i = 0;
+ friend full_map_t;
+ };
+
+ class const_iterator
+ {
+ public:
+ using difference_type = ptrdiff_t;
+ using value_type = std::pair<const Key, const T>;
+ using reference = std::pair<const Key &, const T &>;
+ using pointer = mock_pointer<reference>;
+ using iterator_category = std::random_access_iterator_tag;
+
+ const_iterator() = default;
+
+ const_iterator(const containers *ac, size_type ai)
+ : c(ac), i(ai)
+ {
+ }
+
+ const_iterator(iterator o)
+ : c(o.c), i(o.i)
+ {
+ }
+
+ reference operator*()
+ {
+ return { c->keys[i], c->values[i] };
+ }
+
+ pointer operator->()
+ {
+ return { operator*() };
+ }
+
+ bool operator==(const const_iterator &o) const
+ {
+ return c == o.c && i == o.i;
+ }
+
+ bool operator!=(const const_iterator &o) const
+ {
+ return !operator==(o);
+ }
+
+ const_iterator &operator++()
+ {
+ ++i;
+ return *this;
+ }
+
+ const_iterator operator++(int)
+ {
+
+ const_iterator r = *this;
+ i++;
+ return r;
+ }
+
+ const_iterator &operator--()
+ {
+ --i;
+ return *this;
+ }
+
+ const_iterator operator--(int)
+ {
+ const_iterator r = *this;
+ i--;
+ return r;
+ }
+
+ const_iterator &operator+=(size_type n)
+ {
+ i += n;
+ return *this;
+ }
+
+ friend const_iterator operator+(size_type n, const const_iterator a)
+ {
+ const_iterator ret = a;
+ return ret += n;
+ }
+
+ friend const_iterator operator+(const const_iterator a, size_type n)
+ {
+ return n + a;
+ }
+
+ const_iterator &operator-=(size_type n)
+ {
+ i -= n;
+ return *this;
+ }
+
+ friend const_iterator operator-(const const_iterator a, size_type n)
+ {
+ const_iterator ret = a;
+ return ret -= n;
+ }
+
+ friend difference_type operator-(const const_iterator b, const const_iterator a)
+ {
+ return b.i - a.i;
+ }
+
+ reference operator[](size_type n)
+ {
+ size_type k = i + n;
+ return { c->keys[k], c->values[k] };
+ }
+
+ bool operator<(const const_iterator &other) const
+ {
+ return i < other.i;
+ }
+
+ bool operator>(const const_iterator &other) const
+ {
+ return i > other.i;
+ }
+
+ bool operator<=(const const_iterator &other) const
+ {
+ return i <= other.i;
+ }
+
+ bool operator>=(const const_iterator &other) const
+ {
+ return i >= other.i;
+ }
+
+ const Key &key() const { return c->keys[i]; }
+ const T &value() { return c->values[i]; }
+
+ private:
+ const containers *c = nullptr;
+ size_type i = 0;
+ friend full_map_t;
+ };
+
+private:
+ template <class, class = void>
+ struct is_marked_transparent_type : std::false_type { };
+
+ template <class X>
+ struct is_marked_transparent_type<X, typename X::is_transparent> : std::true_type { };
+
+ template <class X>
+ using is_marked_transparent = typename std::enable_if<
+ is_marked_transparent_type<X>::value>::type *;
+
+ template <typename It>
+ using is_compatible_iterator = typename std::enable_if<
+ std::is_same<value_type, typename std::iterator_traits<It>::value_type>::value>::type *;
+
+public:
+ QFlatMap() = default;
+
+ explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values)
+ : c{keys, values}
+ {
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values)
+ {
+ c.keys = std::move(keys);
+ c.values = values;
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values)
+ {
+ c.keys = keys;
+ c.values = std::move(values);
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values)
+ {
+ c.keys = std::move(keys);
+ c.values = std::move(values);
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(std::initializer_list<value_type> lst)
+ : QFlatMap(lst.begin(), lst.end())
+ {
+ }
+
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ explicit QFlatMap(InputIt first, InputIt last)
+ {
+ initWithRange(first, last);
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
+ const mapped_container_type &values)
+ {
+ c.keys = keys;
+ c.values = values;
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
+ const mapped_container_type &values)
+ {
+ c.keys = std::move(keys);
+ c.values = values;
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
+ mapped_container_type &&values)
+ {
+ c.keys = keys;
+ c.values = std::move(values);
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
+ mapped_container_type &&values)
+ {
+ c.keys = std::move(keys);
+ c.values = std::move(values);
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst)
+ : QFlatMap(lst.begin(), lst.end())
+ {
+ }
+
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last)
+ {
+ initWithRange(first, last);
+ }
+
+ explicit QFlatMap(const Compare &compare)
+ : value_compare(compare)
+ {
+ }
+
+ explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values,
+ const Compare &compare)
+ : value_compare(compare), c{keys, values}
+ {
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values,
+ const Compare &compare)
+ : value_compare(compare), c{std::move(keys), values}
+ {
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values,
+ const Compare &compare)
+ : value_compare(compare), c{keys, std::move(values)}
+ {
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values,
+ const Compare &compare)
+ : value_compare(compare), c{std::move(keys), std::move(values)}
+ {
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(std::initializer_list<value_type> lst, const Compare &compare)
+ : QFlatMap(lst.begin(), lst.end(), compare)
+ {
+ }
+
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ explicit QFlatMap(InputIt first, InputIt last, const Compare &compare)
+ : value_compare(compare)
+ {
+ initWithRange(first, last);
+ ensureOrderedUnique();
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
+ const mapped_container_type &values, const Compare &compare)
+ : value_compare(compare), c{keys, values}
+ {
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
+ const mapped_container_type &values, const Compare &compare)
+ : value_compare(compare), c{std::move(keys), values}
+ {
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
+ mapped_container_type &&values, const Compare &compare)
+ : value_compare(compare), c{keys, std::move(values)}
+ {
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
+ mapped_container_type &&values, const Compare &compare)
+ : value_compare(compare), c{std::move(keys), std::move(values)}
+ {
+ }
+
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst,
+ const Compare &compare)
+ : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end(), compare)
+ {
+ }
+
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last, const Compare &compare)
+ : value_compare(compare)
+ {
+ initWithRange(first, last);
+ }
+
+ size_type count() const noexcept { return c.keys.size(); }
+ size_type size() const noexcept { return c.keys.size(); }
+ size_type capacity() const noexcept { return c.keys.capacity(); }
+ bool isEmpty() const noexcept { return c.keys.empty(); }
+ bool empty() const noexcept { return c.keys.empty(); }
+ containers extract() && { return std::move(c); }
+ const key_container_type &keys() const noexcept { return c.keys; }
+ const mapped_container_type &values() const noexcept { return c.values; }
+
+ void reserve(size_type s)
+ {
+ c.keys.reserve(s);
+ c.values.reserve(s);
+ }
+
+ void clear()
+ {
+ c.keys.clear();
+ c.values.clear();
+ }
+
+ bool remove(const Key &key)
+ {
+ auto it = binary_find(key);
+ if (it != end()) {
+ c.keys.erase(toKeysIterator(it));
+ c.values.erase(toValuesIterator(it));
+ return true;
+ }
+ return false;
+ }
+
+ iterator erase(iterator it)
+ {
+ c.values.erase(toValuesIterator(it));
+ return fromKeysIterator(c.keys.erase(toKeysIterator(it)));
+ }
+
+ T take(const Key &key)
+ {
+ auto it = binary_find(key);
+ if (it != end()) {
+ T result = std::move(it.value());
+ erase(it);
+ return result;
+ }
+ return {};
+ }
+
+ bool contains(const Key &key) const
+ {
+ return binary_find(key) != end();
+ }
+
+ T value(const Key &key, const T &defaultValue) const
+ {
+ auto it = binary_find(key);
+ return it == end() ? defaultValue : it.value();
+ }
+
+ T value(const Key &key) const
+ {
+ auto it = binary_find(key);
+ return it == end() ? T() : it.value();
+ }
+
+ T &operator[](const Key &key)
+ {
+ auto it = lower_bound(key);
+ if (it == end() || key_compare::operator()(key, it.key())) {
+ c.keys.insert(toKeysIterator(it), key);
+ return *c.values.insert(toValuesIterator(it), T());
+ }
+ return it.value();
+ }
+
+ T &operator[](Key &&key)
+ {
+ auto it = lower_bound(key);
+ if (it == end() || key_compare::operator()(key, it.key())) {
+ c.keys.insert(toKeysIterator(it), key);
+ return *c.values.insert(toValuesIterator(it), T());
+ }
+ return it.value();
+ }
+
+ T operator[](const Key &key) const
+ {
+ return value(key);
+ }
+
+ std::pair<iterator, bool> insert(const Key &key, const T &value)
+ {
+ auto it = lower_bound(key);
+ if (it == end() || key_compare::operator()(key, it.key())) {
+ c.values.insert(toValuesIterator(it), value);
+ auto k = c.keys.insert(toKeysIterator(it), key);
+ return { fromKeysIterator(k), true };
+ } else {
+ it.value() = value;
+ return {it, false};
+ }
+ }
+
+ std::pair<iterator, bool> insert(Key &&key, const T &value)
+ {
+ auto it = lower_bound(key);
+ if (it == end() || key_compare::operator()(key, it.key())) {
+ c.values.insert(toValuesIterator(it), value);
+ return { c.keys.insert(it, std::move(key)), true };
+ } else {
+ *toValuesIterator(it) = value;
+ return {it, false};
+ }
+ }
+
+ std::pair<iterator, bool> insert(const Key &key, T &&value)
+ {
+ auto it = lower_bound(key);
+ if (it == end() || key_compare::operator()(key, it.key())) {
+ c.values.insert(toValuesIterator(it), std::move(value));
+ return { c.keys.insert(it, key), true };
+ } else {
+ *toValuesIterator(it) = std::move(value);
+ return {it, false};
+ }
+ }
+
+ std::pair<iterator, bool> insert(Key &&key, T &&value)
+ {
+ auto it = lower_bound(key);
+ if (it == end() || key_compare::operator()(key, it.key())) {
+ c.values.insert(toValuesIterator(it), std::move(value));
+ return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true };
+ } else {
+ *toValuesIterator(it) = std::move(value);
+ return {it, false};
+ }
+ }
+
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ void insert(InputIt first, InputIt last)
+ {
+ insertRange(first, last);
+ }
+
+ // ### Merge with the templated version above
+ // once we can use std::disjunction in is_compatible_iterator.
+ void insert(const value_type *first, const value_type *last)
+ {
+ insertRange(first, last);
+ }
+
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ void insert(Qt::OrderedUniqueRange_t, InputIt first, InputIt last)
+ {
+ insertOrderedUniqueRange(first, last);
+ }
+
+ // ### Merge with the templated version above
+ // once we can use std::disjunction in is_compatible_iterator.
+ void insert(Qt::OrderedUniqueRange_t, const value_type *first, const value_type *last)
+ {
+ insertOrderedUniqueRange(first, last);
+ }
+
+ iterator begin() { return { &c, 0 }; }
+ const_iterator begin() const { return { &c, 0 }; }
+ const_iterator cbegin() const { return begin(); }
+ const_iterator constBegin() const { return cbegin(); }
+ iterator end() { return { &c, c.keys.size() }; }
+ const_iterator end() const { return { &c, c.keys.size() }; }
+ const_iterator cend() const { return end(); }
+ const_iterator constEnd() const { return cend(); }
+ std::reverse_iterator<iterator> rbegin() { return std::reverse_iterator<iterator>(end()); }
+ std::reverse_iterator<const_iterator> rbegin() const
+ {
+ return std::reverse_iterator<const_iterator>(end());
+ }
+ std::reverse_iterator<const_iterator> crbegin() const { return rbegin(); }
+ std::reverse_iterator<iterator> rend() {
+ return std::reverse_iterator<iterator>(begin());
+ }
+ std::reverse_iterator<const_iterator> rend() const
+ {
+ return std::reverse_iterator<const_iterator>(begin());
+ }
+ std::reverse_iterator<const_iterator> crend() const { return rend(); }
+
+ iterator lower_bound(const Key &key)
+ {
+ auto cit = const_cast<const full_map_t *>(this)->lower_bound(key);
+ return { &c, cit.i };
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ iterator lower_bound(const X &key)
+ {
+ auto cit = const_cast<const full_map_t *>(this)->lower_bound(key);
+ return { &c, cit.i };
+ }
+
+ const_iterator lower_bound(const Key &key) const
+ {
+ return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp()));
+ }
+
+ template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
+ const_iterator lower_bound(const X &key) const
+ {
+ return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp()));
+ }
+
+ iterator find(const key_type &k)
+ {
+ return binary_find(k);
+ }
+
+ const_iterator find(const key_type &k) const
+ {
+ return binary_find(k);
+ }
+
+ key_compare key_comp() const noexcept
+ {
+ return static_cast<key_compare>(*this);
+ }
+
+ value_compare value_comp() const noexcept
+ {
+ return static_cast<value_compare>(*this);
+ }
+
+private:
+ template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
+ void initWithRange(InputIt first, InputIt last)
+ {
+ QtPrivate::reserveIfForwardIterator(this, first, last);
+ while (first != last) {
+ c.keys.push_back(first->first);
+ c.values.push_back(first->second);
+ ++first;
+ }
+ }
+
+ iterator fromKeysIterator(typename key_container_type::iterator kit)
+ {
+ return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) };
+ }
+
+ const_iterator fromKeysIterator(typename key_container_type::const_iterator kit) const
+ {
+ return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) };
+ }
+
+ typename key_container_type::iterator toKeysIterator(iterator it)
+ {
+ return c.keys.begin() + it.i;
+ }
+
+ typename mapped_container_type::iterator toValuesIterator(iterator it)
+ {
+ return c.values.begin() + it.i;
+ }
+
+ template <class InputIt>
+ void insertRange(InputIt first, InputIt last)
+ {
+ size_type i = c.keys.size();
+ c.keys.resize(i + std::distance(first, last));
+ c.values.resize(c.keys.size());
+ for (; first != last; ++first, ++i) {
+ c.keys[i] = first->first;
+ c.values[i] = first->second;
+ }
+ ensureOrderedUnique();
+ }
+
+ class IndexedKeyComparator
+ {
+ public:
+ IndexedKeyComparator(const full_map_t *am)
+ : m(am)
+ {
+ }
+
+ bool operator()(size_type i, size_type k) const
+ {
+ return m->key_comp()(m->c.keys[i], m->c.keys[k]);
+ }
+
+ private:
+ const full_map_t *m;
+ };
+
+ template <class InputIt>
+ void insertOrderedUniqueRange(InputIt first, InputIt last)
+ {
+ const size_type s = c.keys.size();
+ c.keys.resize(s + std::distance(first, last));
+ c.values.resize(c.keys.size());
+ for (size_type i = s; first != last; ++first, ++i) {
+ c.keys[i] = first->first;
+ c.values[i] = first->second;
+ }
+
+ std::vector<size_type> p(size_t(c.keys.size()));
+ std::iota(p.begin(), p.end(), 0);
+ std::inplace_merge(p.begin(), p.begin() + s, p.end(), IndexedKeyComparator(this));
+ applyPermutation(p);
+ makeUnique();
+ }
+
+ iterator binary_find(const Key &key)
+ {
+ return { &c, const_cast<const full_map_t *>(this)->binary_find(key).i };
+ }
+
+ const_iterator binary_find(const Key &key) const
+ {
+ auto it = lower_bound(key);
+ if (it != end()) {
+ if (!key_compare::operator()(key, it.key()))
+ return it;
+ it = end();
+ }
+ return it;
+ }
+
+ void ensureOrderedUnique()
+ {
+ std::vector<size_type> p(size_t(c.keys.size()));
+ std::iota(p.begin(), p.end(), 0);
+ std::stable_sort(p.begin(), p.end(), IndexedKeyComparator(this));
+ applyPermutation(p);
+ makeUnique();
+ }
+
+ void applyPermutation(const std::vector<size_type> &p)
+ {
+ const size_type s = c.keys.size();
+ std::vector<bool> done(s);
+ for (size_type i = 0; i < s; ++i) {
+ if (done[i])
+ continue;
+ done[i] = true;
+ size_type j = i;
+ size_type k = p[i];
+ while (i != k) {
+ qSwap(c.keys[j], c.keys[k]);
+ qSwap(c.values[j], c.values[k]);
+ done[k] = true;
+ j = k;
+ k = p[j];
+ }
+ }
+ }
+
+ void makeUnique()
+ {
+ if (c.keys.size() < 2)
+ return;
+ auto k = std::end(c.keys) - 1;
+ auto i = k - 1;
+ for (;;) {
+ if (key_compare::operator()(*i, *k) || key_compare::operator()(*k, *i)) {
+ if (i == std::begin(c.keys))
+ break;
+ --i;
+ --k;
+ } else {
+ c.values.erase(std::begin(c.values) + std::distance(std::begin(c.keys), i));
+ i = c.keys.erase(i);
+ if (i == std::begin(c.keys))
+ break;
+ k = i + 1;
+ }
+ }
+ c.keys.shrink_to_fit();
+ c.values.shrink_to_fit();
+ }
+
+ containers c;
+};
+
+QT_END_NAMESPACE
+
+#endif // QFLATMAP_P_H
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 0b8a0b283d..c56324eef7 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -235,7 +235,7 @@ class QHash
return reinterpret_cast<Node *>(node);
}
- static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
+ static inline int alignOfNode() { return qMax<int>(sizeof(void*), alignof(Node)); }
public:
inline QHash() noexcept : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
@@ -290,9 +290,6 @@ public:
inline void detach() { if (d->ref.isShared()) detach_helper(); }
inline bool isDetached() const { return !d->ref.isShared(); }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; }
-#endif
bool isSharedWith(const QHash &other) const { return d == other.d; }
void clear();
@@ -376,13 +373,8 @@ public:
friend inline QT_DEPRECATED iterator operator+(int j, iterator k) { return k + j; }
#endif
-#ifndef QT_STRICT_ITERATORS
- public:
- inline bool operator==(const const_iterator &o) const
- { return i == o.i; }
- inline bool operator!=(const const_iterator &o) const
- { return i != o.i; }
-#endif
+ inline bool operator==(const const_iterator &o) const { return i == o.i; }
+ inline bool operator!=(const const_iterator &o) const { return i != o.i; }
};
friend class iterator;
@@ -408,11 +400,7 @@ public:
Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
explicit inline const_iterator(void *node)
: i(reinterpret_cast<QHashData::Node *>(node)) { }
-#ifdef QT_STRICT_ITERATORS
- explicit inline const_iterator(const iterator &o)
-#else
inline const_iterator(const iterator &o)
-#endif
{ i = o.i; }
inline const Key &key() const { return concrete(i)->key; }
@@ -453,13 +441,6 @@ public:
return k + j;
}
#endif
-
- // ### Qt 5: not sure this is necessary anymore
-#ifdef QT_STRICT_ITERATORS
- private:
- inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
- inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
-#endif
};
friend class const_iterator;
diff --git a/src/corelib/tools/qlinkedlist.h b/src/corelib/tools/qlinkedlist.h
index 8970d39be0..e3713d2c1c 100644
--- a/src/corelib/tools/qlinkedlist.h
+++ b/src/corelib/tools/qlinkedlist.h
@@ -107,9 +107,6 @@ public:
inline void detach()
{ if (d->ref.isShared()) detach_helper2(this->e); }
inline bool isDetached() const { return !d->ref.isShared(); }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QLinkedListData::shared_null) d->sharable = sharable; }
-#endif
inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
inline bool isEmpty() const { return d->size == 0; }
diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index 5d5da20752..62201fd5d6 100644
--- a/src/corelib/tools/qlist.cpp
+++ b/src/corelib/tools/qlist.cpp
@@ -63,2029 +63,4 @@ template class Q_CORE_EXPORT QVector<QPointF>;
template class Q_CORE_EXPORT QVector<QPoint>;
#endif
-
-/*
- QList as an array-list combines the easy-of-use of a random
- access interface with fast list operations and the low memory
- management overhead of an array. Accessing elements by index,
- appending, prepending, and removing elements from both the front
- and the back all happen in constant time O(1). Inserting or
- removing elements at random index positions \ai happens in linear
- time, or more precisly in O(min{i,n-i}) <= O(n/2), with n being
- the number of elements in the list.
-*/
-
-const QListData::Data QListData::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, { nullptr } };
-
-/*!
- * Detaches the QListData by allocating new memory for a list which will be bigger
- * than the copied one and is expected to grow further.
- * *idx is the desired insertion point and is clamped to the actual size of the list.
- * num is the number of new elements to insert at the insertion point.
- * Returns the old (shared) data, it is up to the caller to deref() and free().
- * For the new data node_copy needs to be called.
- *
- * \internal
- */
-QListData::Data *QListData::detach_grow(int *idx, int num)
-{
- Data *x = d;
- int l = x->end - x->begin;
- int nl = l + num;
- auto blockInfo = qCalculateGrowingBlockSize(nl, sizeof(void *), DataHeaderSize);
- Data* t = static_cast<Data *>(::malloc(blockInfo.size));
- Q_CHECK_PTR(t);
- t->alloc = int(uint(blockInfo.elementCount));
-
- t->ref.initializeOwned();
- // The space reservation algorithm's optimization is biased towards appending:
- // Something which looks like an append will put the data at the beginning,
- // while something which looks like a prepend will put it in the middle
- // instead of at the end. That's based on the assumption that prepending
- // is uncommon and even an initial prepend will eventually be followed by
- // at least some appends.
- int bg;
- if (*idx < 0) {
- *idx = 0;
- bg = (t->alloc - nl) >> 1;
- } else if (*idx > l) {
- *idx = l;
- bg = 0;
- } else if (*idx < (l >> 1)) {
- bg = (t->alloc - nl) >> 1;
- } else {
- bg = 0;
- }
- t->begin = bg;
- t->end = bg + nl;
- d = t;
-
- return x;
-}
-
-/*!
- * Detaches the QListData by allocating new memory for a list which possibly
- * has a different size than the copied one.
- * Returns the old (shared) data, it is up to the caller to deref() and free()
- * For the new data node_copy needs to be called.
- *
- * \internal
- */
-QListData::Data *QListData::detach(int alloc)
-{
- Data *x = d;
- Data* t = static_cast<Data *>(::malloc(qCalculateBlockSize(alloc, sizeof(void*), DataHeaderSize)));
- Q_CHECK_PTR(t);
-
- t->ref.initializeOwned();
- t->alloc = alloc;
- if (!alloc) {
- t->begin = 0;
- t->end = 0;
- } else {
- t->begin = x->begin;
- t->end = x->end;
- }
- d = t;
-
- return x;
-}
-
-void QListData::realloc(int alloc)
-{
- Q_ASSERT(!d->ref.isShared());
- Data *x = static_cast<Data *>(::realloc(d, qCalculateBlockSize(alloc, sizeof(void *), DataHeaderSize)));
- Q_CHECK_PTR(x);
-
- d = x;
- d->alloc = alloc;
- if (!alloc)
- d->begin = d->end = 0;
-}
-
-void QListData::realloc_grow(int growth)
-{
- Q_ASSERT(!d->ref.isShared());
- auto r = qCalculateGrowingBlockSize(d->alloc + growth, sizeof(void *), DataHeaderSize);
- Data *x = static_cast<Data *>(::realloc(d, r.size));
- Q_CHECK_PTR(x);
-
- d = x;
- d->alloc = int(uint(r.elementCount));
-}
-
-void QListData::dispose(Data *d)
-{
- Q_ASSERT(!d->ref.isShared());
- free(d);
-}
-
-// ensures that enough space is available to append n elements
-void **QListData::append(int n)
-{
- Q_ASSERT(!d->ref.isShared());
- int e = d->end;
- if (e + n > d->alloc) {
- int b = d->begin;
- if (b - n >= 2 * d->alloc / 3) {
- // we have enough space. Just not at the end -> move it.
- e -= b;
- ::memcpy(d->array, d->array + b, e * sizeof(void *));
- d->begin = 0;
- } else {
- realloc_grow(n);
- }
- }
- d->end = e + n;
- return d->array + e;
-}
-
-// ensures that enough space is available to append one element
-void **QListData::append()
-{
- return append(1);
-}
-
-// ensures that enough space is available to append the list
-void **QListData::append(const QListData& l)
-{
- return append(l.d->end - l.d->begin);
-}
-
-void **QListData::prepend()
-{
- Q_ASSERT(!d->ref.isShared());
- if (d->begin == 0) {
- if (d->end >= d->alloc / 3)
- realloc_grow(1);
-
- if (d->end < d->alloc / 3)
- d->begin = d->alloc - 2 * d->end;
- else
- d->begin = d->alloc - d->end;
-
- ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
- d->end += d->begin;
- }
- return d->array + --d->begin;
-}
-
-void **QListData::insert(int i)
-{
- Q_ASSERT(!d->ref.isShared());
- if (i <= 0)
- return prepend();
- int size = d->end - d->begin;
- if (i >= size)
- return append();
-
- bool leftward = false;
-
- if (d->begin == 0) {
- if (d->end == d->alloc) {
- // If the array is full, we expand it and move some items rightward
- realloc_grow(1);
- } else {
- // If there is free space at the end of the array, we move some items rightward
- }
- } else {
- if (d->end == d->alloc) {
- // If there is free space at the beginning of the array, we move some items leftward
- leftward = true;
- } else {
- // If there is free space at both ends, we move as few items as possible
- leftward = (i < size - i);
- }
- }
-
- if (leftward) {
- --d->begin;
- ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
- } else {
- ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
- (size - i) * sizeof(void *));
- ++d->end;
- }
- return d->array + d->begin + i;
-}
-
-void QListData::remove(int i)
-{
- Q_ASSERT(!d->ref.isShared());
- i += d->begin;
- if (i - d->begin < d->end - i) {
- if (int offset = i - d->begin)
- ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
- d->begin++;
- } else {
- if (int offset = d->end - i - 1)
- ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
- d->end--;
- }
-}
-
-void QListData::remove(int i, int n)
-{
- Q_ASSERT(!d->ref.isShared());
- i += d->begin;
- int middle = i + n/2;
- if (middle - d->begin < d->end - middle) {
- ::memmove(d->array + d->begin + n, d->array + d->begin,
- (i - d->begin) * sizeof(void*));
- d->begin += n;
- } else {
- ::memmove(d->array + i, d->array + i + n,
- (d->end - i - n) * sizeof(void*));
- d->end -= n;
- }
-}
-
-void QListData::move(int from, int to)
-{
- Q_ASSERT(!d->ref.isShared());
- if (from == to)
- return;
-
- from += d->begin;
- to += d->begin;
- void *t = d->array[from];
-
- if (from < to) {
- if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {
- ::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));
- } else {
- // optimization
- if (int offset = from - d->begin)
- ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
- if (int offset = d->end - (to + 1))
- ::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));
- ++d->begin;
- ++d->end;
- ++to;
- }
- } else {
- if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {
- ::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));
- } else {
- // optimization
- if (int offset = to - d->begin)
- ::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));
- if (int offset = d->end - (from + 1))
- ::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));
- --d->begin;
- --d->end;
- --to;
- }
- }
- d->array[to] = t;
-}
-
-void **QListData::erase(void **xi)
-{
- Q_ASSERT(!d->ref.isShared());
- int i = xi - (d->array + d->begin);
- remove(i);
- return d->array + d->begin + i;
-}
-
-/*! \class QList
- \inmodule QtCore
- \brief The QList class is a template class that provides lists.
-
- \ingroup tools
- \ingroup shared
-
- \reentrant
-
- QList\<T\> is one of Qt's generic \l{container classes}. It
- stores items in a list that provides fast index-based access
- and index-based insertions and removals.
-
- QList\<T\>, QLinkedList\<T\>, and QVector\<T\> provide similar
- APIs and functionality. They are often interchangeable, but there
- are performance consequences. Here is an overview of use cases:
-
- \list
- \li QVector should be your default first choice.
- QVector\<T\> will usually give better performance than QList\<T\>,
- because QVector\<T\> always stores its items sequentially in memory,
- where QList\<T\> will allocate its items on the heap unless
- \c {sizeof(T) <= sizeof(void*)} and T has been declared to be
- either a \c{Q_MOVABLE_TYPE} or a \c{Q_PRIMITIVE_TYPE} using
- \l {Q_DECLARE_TYPEINFO}. See the \l {Pros and Cons of Using QList}
- for an explanation.
- \li However, QList is used throughout the Qt APIs for passing
- parameters and for returning values. Use QList to interface with
- those APIs.
- \li If you need a real linked list, which guarantees
- \l {Algorithmic Complexity}{constant time} insertions mid-list and
- uses iterators to items rather than indexes, use QLinkedList.
- \endlist
-
- \note QVector and QVarLengthArray both guarantee C-compatible
- array layout. QList does not. This might be important if your
- application must interface with a C API.
-
- \note Iterators into a QLinkedList and references into
- heap-allocating QLists remain valid as long as the referenced items
- remain in the container. This is not true for iterators and
- references into a QVector and non-heap-allocating QLists.
-
- Internally, QList\<T\> is represented as an array of T if
- \c{sizeof(T) <= sizeof(void*)} and T has been declared to be
- either a \c{Q_MOVABLE_TYPE} or a \c{Q_PRIMITIVE_TYPE} using
- \l {Q_DECLARE_TYPEINFO}. Otherwise, QList\<T\> is represented
- as an array of T* and the items are allocated on the heap.
-
- The array representation allows very fast insertions and
- index-based access. The prepend() and append() operations are
- also very fast because QList preallocates memory at both
- ends of its internal array. (See \l{Algorithmic Complexity} for
- details.
-
- Note, however, that when the conditions specified above are not met,
- each append or insert of a new item requires allocating the new item
- on the heap, and this per item allocation will make QVector a better
- choice for use cases that do a lot of appending or inserting, because
- QVector can allocate memory for many items in a single heap allocation.
-
- Note that the internal array only ever gets bigger over the life
- of the list. It never shrinks. The internal array is deallocated
- by the destructor and by the assignment operator, when one list
- is assigned to another.
-
- Here's an example of a QList that stores integers and
- a QList that stores QDate values:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 0
-
- Qt includes a QStringList class that inherits QList\<QString\>
- and adds a few convenience functions, such as QStringList::join()
- and QStringList::filter(). QString::split() creates QStringLists
- from strings.
-
- QList stores a list of items. The default constructor creates an
- empty list. You can use the initializer-list constructor to create
- a list with elements:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 1a
-
- QList provides these basic functions to add, move, and remove
- items: insert(), replace(), removeAt(), move(), and swap(). In
- addition, it provides the following convenience functions:
- append(), \l{operator<<()}, \l{operator+=()}, prepend(), removeFirst(),
- and removeLast().
-
- \l{operator<<()} allows to conveniently add multiple elements to a list:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 1b
-
- QList uses 0-based indexes, just like C++ arrays. To access the
- item at a particular index position, you can use operator[](). On
- non-const lists, operator[]() returns a reference to the item and
- can be used on the left side of an assignment:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 2
-
- Because QList is implemented as an array of pointers for types
- that are larger than a pointer or are not movable, this operation
- requires (\l{Algorithmic Complexity}{constant time}). For read-only
- access, an alternative syntax is to use at():
-
- \snippet code/src_corelib_tools_qlistdata.cpp 3
-
- at() can be faster than operator[](), because it never causes a
- \l{deep copy} to occur.
-
- A common requirement is to remove an item from a list and do
- something with it. For this, QList provides takeAt(), takeFirst(),
- and takeLast(). Here's a loop that removes the items from a list
- one at a time and calls \c delete on them:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 4
-
- Inserting and removing items at either end of the list is very
- fast (\l{Algorithmic Complexity}{constant time} in most cases),
- because QList preallocates extra space on both sides of its
- internal buffer to allow for fast growth at both ends of the list.
-
- If you want to find all occurrences of a particular value in a
- list, use indexOf() or lastIndexOf(). The former searches forward
- starting from a given index position, the latter searches
- backward. Both return the index of a matching item if they find
- it; otherwise, they return -1. For example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 5
-
- If you simply want to check whether a list contains a particular
- value, use contains(). If you want to find out how many times a
- particular value occurs in the list, use count(). If you want to
- replace all occurrences of a particular value with another, use
- replace().
-
- QList's value type must be an \l{assignable data type}. This
- covers most data types that are commonly used, but the compiler
- won't let you, for example, store a QWidget as a value; instead,
- store a QWidget *. A few functions have additional requirements;
- for example, indexOf() and lastIndexOf() expect the value type to
- support \c operator==(). These requirements are documented on a
- per-function basis.
-
- Like the other container classes, QList provides \l{Java-style
- iterators} (QListIterator and QMutableListIterator) and
- \l{STL-style iterators} (QList::const_iterator and
- QList::iterator). In practice, these are rarely used, because you
- can use indexes into the QList. QList is implemented in such a way
- that direct index-based access is just as fast as using iterators.
-
- QList does \e not support inserting, prepending, appending or
- replacing with references to its own values. Doing so will cause
- your application to abort with an error message.
-
- To make QList as efficient as possible, its member functions don't
- validate their input before using it. Except for isEmpty(), member
- functions always assume the list is \e not empty. Member functions
- that take index values as parameters always assume their index
- value parameters are in the valid range. This means QList member
- functions can fail. If you define QT_NO_DEBUG when you compile,
- failures will not be detected. If you \e don't define QT_NO_DEBUG,
- failures will be detected using Q_ASSERT() or Q_ASSERT_X() with an
- appropriate message.
-
- To avoid failures when your list can be empty, call isEmpty()
- before calling other member functions. If you must pass an index
- value that might not be in the valid range, check that it is less
- than the value returned by size() but \e not less than 0.
-
- \section1 More Members
-
- If T is a QByteArray, this class has a couple more members that can be
- used. See the documentation for QByteArrayList for more information.
-
- If T is QString, this class has the following additional members:
- \l{QStringList::filter()}{filter},
- \l{QStringList::join()}{join},
- \l{QStringList::removeDuplicates()}{removeDuplicates},
- \l{QStringList::sort()}{sort}.
-
- \section1 More Information on Using Qt Containers
-
- For a detailed discussion comparing Qt containers with each other and
- with STL containers, see \l {Understand the Qt Containers}.
-
- \sa QListIterator, QMutableListIterator, QLinkedList, QVector
-*/
-
-/*!
- \fn template <class T> QList<T>::QList(QList<T> &&other)
-
- Move-constructs a QList instance, making it point at the same
- object that \a other was pointing to.
-
- \since 5.2
-*/
-
-/*! \fn template <class T> template<typename InputIterator> QList<T>::QList(InputIterator first, InputIterator last)
- \since 5.14
-
- Constructs a QList with the contents in the iterator range [\a first, \a last).
-
- The value type of \c InputIterator must be convertible to \c T.
-*/
-
-/*!
- \fn template <class T> QList<T> QList<T>::mid(int pos, int length) const
-
- Returns a sub-list which includes elements from this list,
- starting at position \a pos. If \a length is -1 (the default), all
- elements from \a pos are included; otherwise \a length elements (or
- all remaining elements if there are less than \a length elements)
- are included.
-*/
-
-/*! \fn template <class T> QList<T>::QList()
-
- Constructs an empty list.
-*/
-
-/*! \fn template <class T> QList<T>::QList(const QList<T> &other)
-
- Constructs a copy of \a other.
-
- This operation takes \l{Algorithmic Complexity}{constant time},
- because QList is \l{implicitly shared}. This makes returning a
- QList from a function very fast. If a shared instance is modified,
- it will be copied (copy-on-write), and that takes
- \l{Algorithmic Complexity}{linear time}.
-
- \sa operator=()
-*/
-
-/*! \fn template <class T> QList<T>::QList(std::initializer_list<T> args)
- \since 4.8
-
- Construct a list from the std::initializer_list specified by \a args.
-
- This constructor is only enabled if the compiler supports C++11 initializer
- lists.
-*/
-
-/*! \fn template <class T> QList<T>::~QList()
-
- Destroys the list. References to the values in the list and all
- iterators of this list become invalid.
-*/
-
-/*! \fn template <class T> QList<T> &QList<T>::operator=(const QList<T> &other)
-
- Assigns \a other to this list and returns a reference to this
- list.
-*/
-
-/*!
- \fn template <class T> QList &QList<T>::operator=(QList<T> &&other)
-
- Move-assigns \a other to this QList instance.
-
- \since 5.2
-*/
-
-/*! \fn template <class T> void QList<T>::swap(QList<T> &other)
- \since 4.8
-
- Swaps list \a other with this list. This operation is very
- fast and never fails.
-*/
-
-/*! \fn template <class T> bool QList<T>::operator==(const QList<T> &other) const
-
- Returns \c true if \a other is equal to this list; otherwise returns
- false.
-
- Two lists are considered equal if they contain the same values in
- the same order.
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- \sa operator!=()
-*/
-
-/*! \fn template <class T> bool QList<T>::operator!=(const QList<T> &other) const
-
- Returns \c true if \a other is not equal to this list; otherwise
- returns \c false.
-
- Two lists are considered equal if they contain the same values in
- the same order.
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- \sa operator==()
-*/
-
-/*! \fn template <class T> bool operator<(const QList<T> &lhs, const QList<T> &rhs)
- \since 5.6
- \relates QList
-
- Returns \c true if list \a lhs is
- \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
- {lexicographically less than} \a rhs; otherwise returns \c false.
-
- This function requires the value type to have an implementation
- of \c operator<().
-*/
-
-/*! \fn template <class T> bool operator<=(const QList<T> &lhs, const QList<T> &rhs)
- \since 5.6
- \relates QList
-
- Returns \c true if list \a lhs is
- \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
- {lexicographically less than or equal to} \a rhs; otherwise returns \c false.
-
- This function requires the value type to have an implementation
- of \c operator<().
-*/
-
-/*! \fn template <class T> bool operator>(const QList<T> &lhs, const QList<T> &rhs)
- \since 5.6
- \relates QList
-
- Returns \c true if list \a lhs is
- \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
- {lexicographically greater than} \a rhs; otherwise returns \c false.
-
- This function requires the value type to have an implementation
- of \c operator<().
-*/
-
-/*! \fn template <class T> bool operator>=(const QList<T> &lhs, const QList<T> &rhs)
- \since 5.6
- \relates QList
-
- Returns \c true if list \a lhs is
- \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
- {lexicographically greater than or equal to} \a rhs; otherwise returns \c false.
-
- This function requires the value type to have an implementation
- of \c operator<().
-*/
-
-/*!
- \fn template <class T> uint qHash(const QList<T> &key, uint seed = 0)
- \since 5.6
- \relates QList
-
- Returns the hash value for \a key,
- using \a seed to seed the calculation.
-
- This function requires qHash() to be overloaded for the value type \c T.
-*/
-
-/*!
- \fn template <class T> int QList<T>::size() const
-
- Returns the number of items in the list.
-
- \sa isEmpty(), count()
-*/
-
-/*! \fn template <class T> void QList<T>::detach()
-
- \internal
-*/
-
-/*! \fn template <class T> void QList<T>::detachShared()
-
- \internal
-
- like detach(), but does nothing if we're shared_null.
- This prevents needless mallocs, and makes QList more exception safe
- in case of cleanup work done in destructors on empty lists.
-*/
-
-/*! \fn template <class T> bool QList<T>::isDetached() const
-
- \internal
-*/
-
-/*! \fn template <class T> void QList<T>::setSharable(bool sharable)
-
- \internal
-*/
-
-/*! \fn template <class T> bool QList<T>::isSharedWith(const QList<T> &other) const
-
- \internal
-*/
-
-/*! \fn template <class T> bool QList<T>::isEmpty() const
-
- Returns \c true if the list contains no items; otherwise returns
- false.
-
- \sa size()
-*/
-
-/*! \fn template <class T> void QList<T>::clear()
-
- Removes all items from the list.
-
- \sa removeAll()
-*/
-
-/*! \fn template <class T> const T &QList<T>::at(int i) const
-
- Returns the item at index position \a i in the list. \a i must be
- a valid index position in the list (i.e., 0 <= \a i < size()).
-
- This function is very fast (\l{Algorithmic Complexity}{constant time}).
-
- \sa value(), operator[]()
-*/
-
-/*! \fn template <class T> T &QList<T>::operator[](int i)
-
- Returns the item at index position \a i as a modifiable reference.
- \a i must be a valid index position in the list (i.e., 0 <= \a i <
- size()).
-
- If this function is called on a list that is currently being shared, it
- will trigger a copy of all elements. Otherwise, this function runs in
- \l{Algorithmic Complexity}{constant time}. If you do not want to modify
- the list you should use QList::at().
-
- \sa at(), value()
-*/
-
-/*! \fn template <class T> const T &QList<T>::operator[](int i) const
-
- \overload
-
- Same as at(). This function runs in \l{Algorithmic Complexity}{constant time}.
-*/
-
-/*! \fn template <class T> void QList<T>::reserve(int alloc)
-
- Reserve space for \a alloc elements.
-
- If \a alloc is smaller than the current size of the list, nothing will happen.
-
- Use this function to avoid repetetive reallocation of QList's internal
- data if you can predict how many elements will be appended.
- Note that the reservation applies only to the internal pointer array.
-
- \since 4.7
-*/
-
-/*! \fn template <class T> void QList<T>::append(const T &value)
-
- Inserts \a value at the end of the list.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 6
-
- This is the same as list.insert(size(), \a value).
-
- If this list is not shared, this operation is typically
- very fast (amortized \l{Algorithmic Complexity}{constant time}),
- because QList preallocates extra space on both sides of its
- internal buffer to allow for fast growth at both ends of the list.
-
- \sa operator<<(), prepend(), insert()
-*/
-
-/*! \fn template <class T> void QList<T>::append(const QList<T> &value)
-
- \overload
-
- \since 4.5
-
- Appends the items of the \a value list to this list.
-
- \sa operator<<(), operator+=()
-*/
-
-/*! \fn template <class T> void QList<T>::prepend(const T &value)
-
- Inserts \a value at the beginning of the list.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 7
-
- This is the same as list.insert(0, \a value).
-
- If this list is not shared, this operation is typically
- very fast (amortized \l{Algorithmic Complexity}{constant time}),
- because QList preallocates extra space on both sides of its
- internal buffer to allow for fast growth at both ends of the list.
-
- \sa append(), insert()
-*/
-
-/*! \fn template <class T> void QList<T>::insert(int i, const T &value)
-
- Inserts \a value at index position \a i in the list.
-
- If \a i == 0, the value is prepended to the list. If \a i == size(),
- the value is appended to the list.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 8
-
- \sa append(), prepend(), replace(), removeAt()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::insert(iterator before, const T &value)
-
- \overload
-
- Inserts \a value in front of the item pointed to by the
- iterator \a before. Returns an iterator pointing at the inserted
- item. Note that the iterator passed to the function will be
- invalid after the call; the returned iterator should be used
- instead.
-*/
-
-/*! \fn template <class T> void QList<T>::replace(int i, const T &value)
-
- Replaces the item at index position \a i with \a value. \a i must
- be a valid index position in the list (i.e., 0 <= \a i < size()).
-
- \sa operator[](), removeAt()
-*/
-
-/*!
- \fn template <class T> int QList<T>::removeAll(const T &value)
-
- Removes all occurrences of \a value in the list and returns the
- number of entries removed.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 9
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- \sa removeOne(), removeAt(), takeAt(), replace()
-*/
-
-/*!
- \fn template <class T> bool QList<T>::removeOne(const T &value)
- \since 4.4
-
- Removes the first occurrence of \a value in the list and returns
- true on success; otherwise returns \c false.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 10
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- \sa removeAll(), removeAt(), takeAt(), replace()
-*/
-
-/*! \fn template <class T> void QList<T>::removeAt(int i)
-
- Removes the item at index position \a i. \a i must be a valid
- index position in the list (i.e., 0 <= \a i < size()).
-
- \sa takeAt(), removeFirst(), removeLast(), removeOne()
-*/
-
-/*! \fn template <class T> T QList<T>::takeAt(int i)
-
- Removes the item at index position \a i and returns it. \a i must
- be a valid index position in the list (i.e., 0 <= \a i < size()).
-
- If you don't use the return value, removeAt() is more efficient.
-
- \sa removeAt(), takeFirst(), takeLast()
-*/
-
-/*! \fn template <class T> T QList<T>::takeFirst()
-
- Removes the first item in the list and returns it. This is the
- same as takeAt(0). This function assumes the list is not empty. To
- avoid failure, call isEmpty() before calling this function.
-
- If this list is not shared, this operation takes
- \l {Algorithmic Complexity}{constant time}.
-
- If you don't use the return value, removeFirst() is more
- efficient.
-
- \sa takeLast(), takeAt(), removeFirst()
-*/
-
-/*! \fn template <class T> T QList<T>::takeLast()
-
- Removes the last item in the list and returns it. This is the
- same as takeAt(size() - 1). This function assumes the list is
- not empty. To avoid failure, call isEmpty() before calling this
- function.
-
- If this list is not shared, this operation takes
- \l {Algorithmic Complexity}{constant time}.
-
- If you don't use the return value, removeLast() is more
- efficient.
-
- \sa takeFirst(), takeAt(), removeLast()
-*/
-
-/*! \fn template <class T> void QList<T>::move(int from, int to)
-
- Moves the item at index position \a from to index position \a to.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 11
-
- This is the same as insert(\a{to}, takeAt(\a{from})).This function
- assumes that both \a from and \a to are at least 0 but less than
- size(). To avoid failure, test that both \a from and \a to are at
- least 0 and less than size().
-
- \sa swap(), insert(), takeAt()
-*/
-
-/*! \fn template <class T> void QList<T>::swap(int i, int j)
-
- \obsolete Use swapItemsAt()
-
- \sa move(), swapItemsAt()
-*/
-
-/*! \fn template <class T> void QList<T>::swapItemsAt(int i, int j)
- \since 5.13
-
- Exchange the item at index position \a i with the item at index
- position \a j. This function assumes that both \a i and \a j are
- at least 0 but less than size(). To avoid failure, test that both
- \a i and \a j are at least 0 and less than size().
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 12
-
- \sa move()
-*/
-
-/*! \fn template <class T> int QList<T>::indexOf(const T &value, int from = 0) const
-
- Returns the index position of the first occurrence of \a value in
- the list, searching forward from index position \a from. Returns
- -1 if no item matched.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 13
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- Note that QList uses 0-based indexes, just like C++ arrays. Negative
- indexes are not supported with the exception of the value mentioned
- above.
-
- \sa lastIndexOf(), contains()
-*/
-
-/*! \fn template <class T> int QList<T>::lastIndexOf(const T &value, int from = -1) const
-
- Returns the index position of the last occurrence of \a value in
- the list, searching backward from index position \a from. If \a
- from is -1 (the default), the search starts at the last item.
- Returns -1 if no item matched.
-
- Example:
- \snippet code/src_corelib_tools_qlistdata.cpp 14
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- Note that QList uses 0-based indexes, just like C++ arrays. Negative
- indexes are not supported with the exception of the value mentioned
- above.
-
- \sa indexOf()
-*/
-
-/*! \fn template <class T> bool QList<T>::contains(const T &value) const
-
- Returns \c true if the list contains an occurrence of \a value;
- otherwise returns \c false.
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- \sa indexOf(), count()
-*/
-
-/*! \fn template <class T> int QList<T>::count(const T &value) const
-
- Returns the number of occurrences of \a value in the list.
-
- This function requires the value type to have an implementation of
- \c operator==().
-
- \sa contains(), indexOf()
-*/
-
-/*! \fn template <class T> bool QList<T>::startsWith(const T &value) const
- \since 4.5
-
- Returns \c true if this list is not empty and its first
- item is equal to \a value; otherwise returns \c false.
-
- \sa isEmpty(), contains()
-*/
-
-/*! \fn template <class T> bool QList<T>::endsWith(const T &value) const
- \since 4.5
-
- Returns \c true if this list is not empty and its last
- item is equal to \a value; otherwise returns \c false.
-
- \sa isEmpty(), contains()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::begin()
-
- Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
- the list.
-
- \sa constBegin(), end()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::begin() const
-
- \overload
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::cbegin() const
- \since 5.0
-
- Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
- in the list.
-
- \sa begin(), cend()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::constBegin() const
-
- Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
- in the list.
-
- \sa begin(), constEnd()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::end()
-
- Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
- after the last item in the list.
-
- \sa begin(), constEnd()
-*/
-
-/*! \fn template <class T> const_iterator QList<T>::end() const
-
- \overload
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::cend() const
- \since 5.0
-
- Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
- item after the last item in the list.
-
- \sa cbegin(), end()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::constEnd() const
-
- Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
- item after the last item in the list.
-
- \sa constBegin(), end()
-*/
-
-/*! \fn template <class T> QList<T>::reverse_iterator QList<T>::rbegin()
- \since 5.6
-
- Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
- item in the list, in reverse order.
-
- \sa begin(), crbegin(), rend()
-*/
-
-/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::rbegin() const
- \since 5.6
- \overload
-*/
-
-/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::crbegin() const
- \since 5.6
-
- Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
- item in the list, in reverse order.
-
- \sa begin(), rbegin(), rend()
-*/
-
-/*! \fn template <class T> QList<T>::reverse_iterator QList<T>::rend()
- \since 5.6
-
- Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past
- the last item in the list, in reverse order.
-
- \sa end(), crend(), rbegin()
-*/
-
-/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::rend() const
- \since 5.6
- \overload
-*/
-
-/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::crend() const
- \since 5.6
-
- Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one
- past the last item in the list, in reverse order.
-
- \sa end(), rend(), rbegin()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::erase(iterator pos)
-
- Removes the item associated with the iterator \a pos from the
- list, and returns an iterator to the next item in the list (which
- may be end()).
-
- \sa insert(), removeAt()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::erase(iterator begin, iterator end)
-
- \overload
-
- Removes all the items from \a begin up to (but not including) \a
- end. Returns an iterator to the same item that \a end referred to
- before the call.
-*/
-
-/*! \typedef QList::Iterator
-
- Qt-style synonym for QList::iterator.
-*/
-
-/*! \typedef QList::ConstIterator
-
- Qt-style synonym for QList::const_iterator.
-*/
-
-/*!
- \typedef QList::size_type
-
- Typedef for int. Provided for STL compatibility.
-*/
-
-/*!
- \typedef QList::value_type
-
- Typedef for T. Provided for STL compatibility.
-*/
-
-/*!
- \typedef QList::difference_type
-
- Typedef for ptrdiff_t. Provided for STL compatibility.
-*/
-
-/*!
- \typedef QList::pointer
-
- Typedef for T *. Provided for STL compatibility.
-*/
-
-/*!
- \typedef QList::const_pointer
-
- Typedef for const T *. Provided for STL compatibility.
-*/
-
-/*!
- \typedef QList::reference
-
- Typedef for T &. Provided for STL compatibility.
-*/
-
-/*!
- \typedef QList::const_reference
-
- Typedef for const T &. Provided for STL compatibility.
-*/
-
-/*! \typedef QList::reverse_iterator
- \since 5.6
-
- The QList::reverse_iterator typedef provides an STL-style non-const
- reverse iterator for QList.
-
- It is simply a typedef for \c{std::reverse_iterator<iterator>}.
-
- \warning Iterators on implicitly shared containers do not work
- exactly like STL-iterators. You should avoid copying a container
- while iterators are active on that container. For more information,
- read \l{Implicit sharing iterator problem}.
-
- \sa QList::rbegin(), QList::rend(), QList::const_reverse_iterator, QList::iterator
-*/
-
-/*! \typedef QList::const_reverse_iterator
- \since 5.6
-
- The QList::const_reverse_iterator typedef provides an STL-style const
- reverse iterator for QList.
-
- It is simply a typedef for \c{std::reverse_iterator<const_iterator>}.
-
- \warning Iterators on implicitly shared containers do not work
- exactly like STL-iterators. You should avoid copying a container
- while iterators are active on that container. For more information,
- read \l{Implicit sharing iterator problem}.
-
- \sa QList::rbegin(), QList::rend(), QList::reverse_iterator, QList::const_iterator
-*/
-
-/*! \fn template <class T> int QList<T>::count() const
-
- Returns the number of items in the list. This is effectively the
- same as size().
-*/
-
-/*! \fn template <class T> int QList<T>::length() const
- \since 4.5
-
- This function is identical to count().
-
- \sa count()
-*/
-
-/*! \fn template <class T> T& QList<T>::first()
-
- Returns a reference to the first item in the list. The list must
- not be empty. If the list can be empty, call isEmpty() before
- calling this function.
-
- \sa constFirst(), last(), isEmpty()
-*/
-
-/*! \fn template <class T> const T& QList<T>::first() const
-
- \overload
-*/
-
-/*! \fn template <class T> const T& QList<T>::constFirst() const
- \since 5.6
-
- Returns a const reference to the first item in the list. The list must
- not be empty. If the list can be empty, call isEmpty() before
- calling this function.
-
- \sa constLast(), isEmpty(), first()
-*/
-
-/*! \fn template <class T> T& QList<T>::last()
-
- Returns a reference to the last item in the list. The list must
- not be empty. If the list can be empty, call isEmpty() before
- calling this function.
-
- \sa constLast(), first(), isEmpty()
-*/
-
-/*! \fn template <class T> const T& QList<T>::last() const
-
- \overload
-*/
-
-/*! \fn template <class T> const T& QList<T>::constLast() const
- \since 5.6
-
- Returns a reference to the last item in the list. The list must
- not be empty. If the list can be empty, call isEmpty() before
- calling this function.
-
- \sa constFirst(), isEmpty(), last()
-*/
-
-/*! \fn template <class T> void QList<T>::removeFirst()
-
- Removes the first item in the list. Calling this function is
- equivalent to calling removeAt(0). The list must not be empty. If
- the list can be empty, call isEmpty() before calling this
- function.
-
- \sa removeAt(), takeFirst()
-*/
-
-/*! \fn template <class T> void QList<T>::removeLast()
-
- Removes the last item in the list. Calling this function is
- equivalent to calling removeAt(size() - 1). The list must not be
- empty. If the list can be empty, call isEmpty() before calling
- this function.
-
- \sa removeAt(), takeLast()
-*/
-
-/*! \fn template <class T> T QList<T>::value(int i) const
-
- Returns the value at index position \a i in the list.
-
- If the index \a i is out of bounds, the function returns a
- \l{default-constructed value}. If you are certain that the index
- is going to be within bounds, you can use at() instead, which is
- slightly faster.
-
- \sa at(), operator[]()
-*/
-
-/*! \fn template <class T> T QList<T>::value(int i, const T &defaultValue) const
-
- \overload
-
- If the index \a i is out of bounds, the function returns
- \a defaultValue.
-*/
-
-/*! \fn template <class T> void QList<T>::push_back(const T &value)
-
- This function is provided for STL compatibility. It is equivalent
- to \l{QList::append()}{append(\a value)}.
-*/
-
-/*! \fn template <class T> void QList<T>::push_front(const T &value)
-
- This function is provided for STL compatibility. It is equivalent
- to \l{QList::prepend()}{prepend(\a value)}.
-*/
-
-/*! \fn template <class T> T& QList<T>::front()
-
- This function is provided for STL compatibility. It is equivalent
- to first(). The list must not be empty. If the list can be empty,
- call isEmpty() before calling this function.
-*/
-
-/*! \fn template <class T> const T& QList<T>::front() const
-
- \overload
-*/
-
-/*! \fn template <class T> T& QList<T>::back()
-
- This function is provided for STL compatibility. It is equivalent
- to last(). The list must not be empty. If the list can be empty,
- call isEmpty() before calling this function.
-*/
-
-/*! \fn template <class T> const T& QList<T>::back() const
-
- \overload
-*/
-
-/*! \fn template <class T> void QList<T>::pop_front()
-
- This function is provided for STL compatibility. It is equivalent
- to removeFirst(). The list must not be empty. If the list can be
- empty, call isEmpty() before calling this function.
-*/
-
-/*! \fn template <class T> void QList<T>::pop_back()
-
- This function is provided for STL compatibility. It is equivalent
- to removeLast(). The list must not be empty. If the list can be
- empty, call isEmpty() before calling this function.
-*/
-
-/*! \fn template <class T> bool QList<T>::empty() const
-
- This function is provided for STL compatibility. It is equivalent
- to isEmpty() and returns \c true if the list is empty.
-*/
-
-/*! \fn template <class T> QList<T> &QList<T>::operator+=(const QList<T> &other)
-
- Appends the items of the \a other list to this list and returns a
- reference to this list.
-
- \sa operator+(), append()
-*/
-
-/*! \fn template <class T> void QList<T>::operator+=(const T &value)
-
- \overload
-
- Appends \a value to the list.
-
- \sa append(), operator<<()
-*/
-
-/*! \fn template <class T> QList<T> QList<T>::operator+(const QList<T> &other) const
-
- Returns a list that contains all the items in this list followed
- by all the items in the \a other list.
-
- \sa operator+=()
-*/
-
-/*! \fn template <class T> QList<T> &QList<T>::operator<<(const QList<T> &other)
-
- Appends the items of the \a other list to this list and returns a
- reference to this list.
-
- \sa operator+=(), append()
-*/
-
-/*! \fn template <class T> void QList<T>::operator<<(const T &value)
-
- \overload
-
- Appends \a value to the list.
-*/
-
-/*! \class QList::iterator
- \inmodule QtCore
- \brief The QList::iterator class provides an STL-style non-const iterator for QList and QQueue.
-
- QList features both \l{STL-style iterators} and \l{Java-style
- iterators}. The STL-style iterators are more low-level and more
- cumbersome to use; on the other hand, they are slightly faster
- and, for developers who already know STL, have the advantage of
- familiarity.
-
- QList\<T\>::iterator allows you to iterate over a QList\<T\> (or
- QQueue\<T\>) and to modify the list item associated with the
- iterator. If you want to iterate over a const QList, use
- QList::const_iterator instead. It is generally good practice to
- use QList::const_iterator on a non-const QList as well, unless
- you need to change the QList through the iterator. Const
- iterators are slightly faster, and can improve code readability.
-
- The default QList::iterator constructor creates an uninitialized
- iterator. You must initialize it using a QList function like
- QList::begin(), QList::end(), or QList::insert() before you can
- start iterating. Here's a typical loop that prints all the items
- stored in a list:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 15
-
- Let's see a few examples of things we can do with a
- QList::iterator that we cannot do with a QList::const_iterator.
- Here's an example that increments every value stored in a
- QList\<int\> by 2:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 16
-
- Most QList functions accept an integer index rather than an
- iterator. For that reason, iterators are rarely useful in
- connection with QList. One place where STL-style iterators do
- make sense is as arguments to \l{generic algorithms}.
-
- For example, here's how to delete all the widgets stored in a
- QList\<QWidget *\>:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 17
-
- Multiple iterators can be used on the same list. However, be
- aware that any non-const function call performed on the QList
- will render all existing iterators undefined. If you need to keep
- iterators over a long period of time, we recommend that you use
- QLinkedList rather than QList.
-
- \warning Iterators on implicitly shared containers do not work
- exactly like STL-iterators. You should avoid copying a container
- while iterators are active on that container. For more information,
- read \l{Implicit sharing iterator problem}.
-
- \sa QList::const_iterator, QMutableListIterator
-*/
-
-/*! \typedef QList::iterator::iterator_category
-
- A synonym for \e {std::random_access_iterator_tag} indicating
- this iterator is a random access iterator.
-*/
-
-/*! \typedef QList::iterator::difference_type
-
- \internal
-*/
-
-/*! \typedef QList::iterator::value_type
-
- \internal
-*/
-
-/*! \typedef QList::iterator::pointer
-
- \internal
-*/
-
-/*! \typedef QList::iterator::reference
-
- \internal
-*/
-
-/*! \fn template <class T> QList<T>::iterator::iterator()
-
- Constructs an uninitialized iterator.
-
- Functions like operator*() and operator++() should not be called
- on an uninitialized iterator. Use operator=() to assign a value
- to it before using it.
-
- \sa QList::begin(), QList::end()
-*/
-
-/*! \fn template <class T> QList<T>::iterator::iterator(Node *node)
-
- \internal
-*/
-
-/*! \fn template <class T> QList<T>::iterator::iterator(const iterator &other)
-
- Constructs a copy of \a other.
-*/
-
-/*! \fn template <class T> T &QList<T>::iterator::operator*() const
-
- Returns a modifiable reference to the current item.
-
- You can change the value of an item by using operator*() on the
- left side of an assignment, for example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 18
-
- \sa operator->()
-*/
-
-/*! \fn template <class T> T *QList<T>::iterator::operator->() const
-
- Returns a pointer to the current item.
-
- \sa operator*()
-*/
-
-/*! \fn template <class T> T &QList<T>::iterator::operator[](difference_type j) const
-
- Returns a modifiable reference to the item at position *this +
- \a{j}.
-
- This function is provided to make QList iterators behave like C++
- pointers.
-
- \sa operator+()
-*/
-
-/*!
- \fn template <class T> bool QList<T>::iterator::operator==(const iterator &other) const
- \fn template <class T> bool QList<T>::iterator::operator==(const const_iterator &other) const
-
- Returns \c true if \a other points to the same item as this
- iterator; otherwise returns \c false.
-
- \sa operator!=()
-*/
-
-/*!
- \fn template <class T> bool QList<T>::iterator::operator!=(const iterator &other) const
- \fn template <class T> bool QList<T>::iterator::operator!=(const const_iterator &other) const
-
- Returns \c true if \a other points to a different item than this
- iterator; otherwise returns \c false.
-
- \sa operator==()
-*/
-
-/*!
- \fn template <class T> bool QList<T>::iterator::operator<(const iterator& other) const
- \fn template <class T> bool QList<T>::iterator::operator<(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is less than
- the item pointed to by the \a other iterator.
-*/
-
-/*!
- \fn template <class T> bool QList<T>::iterator::operator<=(const iterator& other) const
- \fn template <class T> bool QList<T>::iterator::operator<=(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is less than
- or equal to the item pointed to by the \a other iterator.
-*/
-
-/*!
- \fn template <class T> bool QList<T>::iterator::operator>(const iterator& other) const
- \fn template <class T> bool QList<T>::iterator::operator>(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is greater
- than the item pointed to by the \a other iterator.
-*/
-
-/*!
- \fn template <class T> bool QList<T>::iterator::operator>=(const iterator& other) const
- \fn template <class T> bool QList<T>::iterator::operator>=(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is greater
- than or equal to the item pointed to by the \a other iterator.
-*/
-
-/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator++()
-
- The prefix ++ operator (\c{++it}) advances the iterator to the
- next item in the list and returns an iterator to the new current
- item.
-
- Calling this function on QList::end() leads to undefined results.
-
- \sa operator--()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator++(int)
-
- \overload
-
- The postfix ++ operator (\c{it++}) advances the iterator to the
- next item in the list and returns an iterator to the previously
- current item.
-*/
-
-/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator--()
-
- The prefix -- operator (\c{--it}) makes the preceding item
- current and returns an iterator to the new current item.
-
- Calling this function on QList::begin() leads to undefined results.
-
- \sa operator++()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator--(int)
-
- \overload
-
- The postfix -- operator (\c{it--}) makes the preceding item
- current and returns an iterator to the previously current item.
-*/
-
-/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator+=(difference_type j)
-
- Advances the iterator by \a j items. (If \a j is negative, the
- iterator goes backward.)
-
- \sa operator-=(), operator+()
-*/
-
-/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator-=(difference_type j)
-
- Makes the iterator go back by \a j items. (If \a j is negative,
- the iterator goes forward.)
-
- \sa operator+=(), operator-()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator+(difference_type j) const
-
- Returns an iterator to the item at \a j positions forward from
- this iterator. (If \a j is negative, the iterator goes backward.)
-
- \sa operator-(), operator+=()
-*/
-
-/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator-(difference_type j) const
-
- Returns an iterator to the item at \a j positions backward from
- this iterator. (If \a j is negative, the iterator goes forward.)
-
- \sa operator+(), operator-=()
-*/
-
-/*! \fn template <class T> int QList<T>::iterator::operator-(iterator other) const
-
- Returns the number of items between the item pointed to by \a
- other and the item pointed to by this iterator.
-*/
-
-/*! \class QList::const_iterator
- \inmodule QtCore
- \brief The QList::const_iterator class provides an STL-style const iterator for QList and QQueue.
-
- QList provides both \l{STL-style iterators} and \l{Java-style
- iterators}. The STL-style iterators are more low-level and more
- cumbersome to use; on the other hand, they are slightly faster
- and, for developers who already know STL, have the advantage of
- familiarity.
-
- QList\<T\>::const_iterator allows you to iterate over a
- QList\<T\> (or a QQueue\<T\>). If you want to modify the QList as
- you iterate over it, use QList::iterator instead. It is generally
- good practice to use QList::const_iterator on a non-const QList
- as well, unless you need to change the QList through the
- iterator. Const iterators are slightly faster, and can improve
- code readability.
-
- The default QList::const_iterator constructor creates an
- uninitialized iterator. You must initialize it using a QList
- function like QList::constBegin(), QList::constEnd(), or
- QList::insert() before you can start iterating. Here's a typical
- loop that prints all the items stored in a list:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 19
-
- Most QList functions accept an integer index rather than an
- iterator. For that reason, iterators are rarely useful in
- connection with QList. One place where STL-style iterators do
- make sense is as arguments to \l{generic algorithms}.
-
- For example, here's how to delete all the widgets stored in a
- QList\<QWidget *\>:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 20
-
- Multiple iterators can be used on the same list. However, be
- aware that any non-const function call performed on the QList
- will render all existing iterators undefined. If you need to keep
- iterators over a long period of time, we recommend that you use
- QLinkedList rather than QList.
-
- \warning Iterators on implicitly shared containers do not work
- exactly like STL-iterators. You should avoid copying a container
- while iterators are active on that container. For more information,
- read \l{Implicit sharing iterator problem}.
-
- \sa QList::iterator, QListIterator
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator::const_iterator()
-
- Constructs an uninitialized iterator.
-
- Functions like operator*() and operator++() should not be called
- on an uninitialized iterator. Use operator=() to assign a value
- to it before using it.
-
- \sa QList::constBegin(), QList::constEnd()
-*/
-
-/*! \typedef QList::const_iterator::iterator_category
-
- A synonym for \e {std::random_access_iterator_tag} indicating
- this iterator is a random access iterator.
-*/
-
-/*! \typedef QList::const_iterator::difference_type
-
- \internal
-*/
-
-/*! \typedef QList::const_iterator::value_type
-
- \internal
-*/
-
-/*! \typedef QList::const_iterator::pointer
-
- \internal
-*/
-
-/*! \typedef QList::const_iterator::reference
-
- \internal
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator::const_iterator(Node *node)
-
- \internal
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator::const_iterator(const const_iterator &other)
-
- Constructs a copy of \a other.
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator::const_iterator(const iterator &other)
-
- Constructs a copy of \a other.
-*/
-
-/*! \fn template <class T> const T &QList<T>::const_iterator::operator*() const
-
- Returns the current item.
-
- \sa operator->()
-*/
-
-/*! \fn template <class T> const T *QList<T>::const_iterator::operator->() const
-
- Returns a pointer to the current item.
-
- \sa operator*()
-*/
-
-/*! \fn template <class T> const T &QList<T>::const_iterator::operator[](difference_type j) const
-
- Returns the item at position *this + \a{j}.
-
- This function is provided to make QList iterators behave like C++
- pointers.
-
- \sa operator+()
-*/
-
-/*! \fn template <class T> bool QList<T>::const_iterator::operator==(const const_iterator &other) const
-
- Returns \c true if \a other points to the same item as this
- iterator; otherwise returns \c false.
-
- \sa operator!=()
-*/
-
-/*! \fn template <class T> bool QList<T>::const_iterator::operator!=(const const_iterator &other) const
-
- Returns \c true if \a other points to a different item than this
- iterator; otherwise returns \c false.
-
- \sa operator==()
-*/
-
-/*!
- \fn template <class T> bool QList<T>::const_iterator::operator<(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is less than
- the item pointed to by the \a other iterator.
-*/
-
-/*!
- \fn template <class T> bool QList<T>::const_iterator::operator<=(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is less than
- or equal to the item pointed to by the \a other iterator.
-*/
-
-/*!
- \fn template <class T> bool QList<T>::const_iterator::operator>(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is greater
- than the item pointed to by the \a other iterator.
-*/
-
-/*!
- \fn template <class T> bool QList<T>::const_iterator::operator>=(const const_iterator& other) const
-
- Returns \c true if the item pointed to by this iterator is greater
- than or equal to the item pointed to by the \a other iterator.
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator++()
-
- The prefix ++ operator (\c{++it}) advances the iterator to the
- next item in the list and returns an iterator to the new current
- item.
-
- Calling this function on QList::end() leads to undefined results.
-
- \sa operator--()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator++(int)
-
- \overload
-
- The postfix ++ operator (\c{it++}) advances the iterator to the
- next item in the list and returns an iterator to the previously
- current item.
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator--()
-
- The prefix -- operator (\c{--it}) makes the preceding item
- current and returns an iterator to the new current item.
-
- Calling this function on QList::begin() leads to undefined results.
-
- \sa operator++()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator--(int)
-
- \overload
-
- The postfix -- operator (\c{it--}) makes the preceding item
- current and returns an iterator to the previously current item.
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator+=(difference_type j)
-
- Advances the iterator by \a j items. (If \a j is negative, the
- iterator goes backward.)
-
- \sa operator-=(), operator+()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator-=(difference_type j)
-
- Makes the iterator go back by \a j items. (If \a j is negative,
- the iterator goes forward.)
-
- \sa operator+=(), operator-()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator+(difference_type j) const
-
- Returns an iterator to the item at \a j positions forward from
- this iterator. (If \a j is negative, the iterator goes backward.)
-
- \sa operator-(), operator+=()
-*/
-
-/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator-(difference_type j) const
-
- Returns an iterator to the item at \a j positions backward from
- this iterator. (If \a j is negative, the iterator goes forward.)
-
- \sa operator+(), operator-=()
-*/
-
-/*! \fn template <class T> int QList<T>::const_iterator::operator-(const_iterator other) const
-
- Returns the number of items between the item pointed to by \a
- other and the item pointed to by this iterator.
-*/
-
-/*! \fn template <class T> QDataStream &operator<<(QDataStream &out, const QList<T> &list)
- \relates QList
-
- Writes the list \a list to stream \a out.
-
- This function requires the value type to implement \c
- operator<<().
-
- \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
-*/
-
-/*! \fn template <class T> QDataStream &operator>>(QDataStream &in, QList<T> &list)
- \relates QList
-
- Reads a list from stream \a in into \a list.
-
- This function requires the value type to implement \c
- operator>>().
-
- \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
-*/
-
-/*! \fn template <class T> QList<T> QList<T>::fromVector(const QVector<T> &vector)
-
- Returns a QList object with the data contained in \a vector.
-
- Example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 21
-
- \include containers-range-constructor.qdocinc
-
- \sa fromSet(), toVector(), QVector::toList()
-*/
-
-/*! \fn template <class T> QVector<T> QList<T>::toVector() const
-
- Returns a QVector object with the data contained in this QList.
-
- Example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 22
-
- \include containers-range-constructor.qdocinc
-
- \sa toSet(), fromVector(), QVector::fromList()
-*/
-
-/*! \fn template <class T> QList<T> QList<T>::fromSet(const QSet<T> &set)
-
- Returns a QList object with the data contained in \a set. The
- order of the elements in the QList is undefined.
-
- Example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 23
-
- \include containers-range-constructor.qdocinc
-
- \sa fromVector(), toSet(), QSet::toList()
-*/
-
-/*! \fn template <class T> QSet<T> QList<T>::toSet() const
-
- Returns a QSet object with the data contained in this QList.
- Since QSet doesn't allow duplicates, the resulting QSet might be
- smaller than the original list was.
-
- Example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 24
-
- \include containers-range-constructor.qdocinc
-
- \sa toVector(), fromSet(), QSet::fromList()
-*/
-
-/*! \fn template <class T> QList<T> QList<T>::fromStdList(const std::list<T> &list)
-
- Returns a QList object with the data contained in \a list. The
- order of the elements in the QList is the same as in \a list.
-
- Example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 25
-
- \include containers-range-constructor.qdocinc
-
- \sa toStdList(), QVector::fromStdVector()
-*/
-
-/*! \fn template <class T> std::list<T> QList<T>::toStdList() const
-
- Returns a std::list object with the data contained in this QList.
- Example:
-
- \snippet code/src_corelib_tools_qlistdata.cpp 26
-
- \include containers-range-constructor.qdocinc
-
- \sa fromStdList(), QVector::toStdVector()
-*/
-
QT_END_NAMESPACE
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index ffd470efcd..515fba6530 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -40,1160 +40,19 @@
#ifndef QLIST_H
#define QLIST_H
-#include <QtCore/qalgorithms.h>
-#include <QtCore/qiterator.h>
-#include <QtCore/qrefcount.h>
-#include <QtCore/qarraydata.h>
-#include <QtCore/qhashfunctions.h>
#include <QtCore/qvector.h>
-#include <QtCore/qcontainertools_impl.h>
-
-#include <algorithm>
-#include <initializer_list>
-#include <iterator>
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
-#include <list>
-#endif
-
-#include <stdlib.h>
-#include <new>
-#include <limits.h>
-#include <string.h>
-
-#ifdef Q_CC_MSVC
-#pragma warning( push )
-#pragma warning( disable : 4127 ) // "conditional expression is constant"
-#endif
+#include <QtCore/qcontainerfwd.h>
+#if !defined(QT_NO_JAVA_STYLE_ITERATORS)
QT_BEGIN_NAMESPACE
-
-
-template <typename T> class QVector;
-template <typename T> class QSet;
-
-template <typename T> struct QListSpecialMethods
-{
-protected:
- ~QListSpecialMethods() = default;
-};
-template <> struct QListSpecialMethods<QByteArray>;
-template <> struct QListSpecialMethods<QString>;
-
-struct Q_CORE_EXPORT QListData {
- // tags for tag-dispatching of QList implementations,
- // based on QList's three different memory layouts:
- struct NotArrayCompatibleLayout {};
- struct NotIndirectLayout {};
- struct ArrayCompatibleLayout : NotIndirectLayout {}; // data laid out like a C array
- struct InlineWithPaddingLayout : NotArrayCompatibleLayout, NotIndirectLayout {}; // data laid out like a C array with padding
- struct IndirectLayout : NotArrayCompatibleLayout {}; // data allocated on the heap
-
- struct Data {
- QtPrivate::RefCount ref;
- int alloc, begin, end;
- void *array[1];
- };
- enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };
-
- Data *detach(int alloc);
- Data *detach_grow(int *i, int n);
- void realloc(int alloc);
- void realloc_grow(int growth);
- inline void dispose() { dispose(d); }
- static void dispose(Data *d);
- static const Data shared_null;
- Data *d;
- void **erase(void **xi);
- void **append(int n);
- void **append();
- void **append(const QListData &l);
- void **prepend();
- void **insert(int i);
- void remove(int i);
- void remove(int i, int n);
- void move(int from, int to);
- inline int size() const noexcept { return int(d->end - d->begin); } // q6sizetype
- inline bool isEmpty() const noexcept { return d->end == d->begin; }
- inline void **at(int i) const noexcept { return d->array + d->begin + i; }
- inline void **begin() const noexcept { return d->array + d->begin; }
- inline void **end() const noexcept { return d->array + d->end; }
-};
-
-namespace QtPrivate {
- template <typename V, typename U> int indexOf(const QList<V> &list, const U &u, int from);
- template <typename V, typename U> int lastIndexOf(const QList<V> &list, const U &u, int from);
-}
-
-template <typename T>
-class QList
-#ifndef Q_QDOC
- : public QListSpecialMethods<T>
-#endif
-{
-public:
- struct MemoryLayout
- : std::conditional<
- // must stay isStatic until ### Qt 6 for BC reasons (don't use !isRelocatable)!
- QTypeInfo<T>::isStatic || QTypeInfo<T>::isLarge,
- QListData::IndirectLayout,
- typename std::conditional<
- sizeof(T) == sizeof(void*),
- QListData::ArrayCompatibleLayout,
- QListData::InlineWithPaddingLayout
- >::type>::type {};
-private:
- template <typename V, typename U> friend int QtPrivate::indexOf(const QList<V> &list, const U &u, int from);
- template <typename V, typename U> friend int QtPrivate::lastIndexOf(const QList<V> &list, const U &u, int from);
- struct Node { void *v;
-#if defined(Q_CC_BOR)
- Q_INLINE_TEMPLATE T &t();
-#else
- Q_INLINE_TEMPLATE T &t()
- { return *reinterpret_cast<T*>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic
- ? v : this); }
-#endif
- };
-
- union { QListData p; QListData::Data *d; };
-
-public:
- inline QList() noexcept : d(const_cast<QListData::Data *>(&QListData::shared_null)) { }
- QList(const QList<T> &l);
- ~QList();
- QList<T> &operator=(const QList<T> &l);
- inline QList(QList<T> &&other) noexcept
- : d(other.d) { other.d = const_cast<QListData::Data *>(&QListData::shared_null); }
- inline QList &operator=(QList<T> &&other) noexcept
- { QList moved(std::move(other)); swap(moved); return *this; }
- inline void swap(QList<T> &other) noexcept { qSwap(d, other.d); }
- inline QList(std::initializer_list<T> args)
- : QList(args.begin(), args.end()) {}
- template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
- QList(InputIterator first, InputIterator last);
- bool operator==(const QList<T> &l) const;
- inline bool operator!=(const QList<T> &l) const { return !(*this == l); }
-
- inline int size() const noexcept { return p.size(); }
-
- inline void detach() { if (d->ref.isShared()) detach_helper(); }
-
- inline void detachShared()
- {
- // The "this->" qualification is needed for GCCE.
- if (d->ref.isShared() && this->d != &QListData::shared_null)
- detach_helper();
- }
-
- inline bool isDetached() const { return !d->ref.isShared(); }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable)
- {
- if (sharable == d->ref.isSharable())
- return;
- if (!sharable)
- detach();
- if (d != &QListData::shared_null)
- d->ref.setSharable(sharable);
- }
-#endif
- inline bool isSharedWith(const QList<T> &other) const noexcept { return d == other.d; }
-
- inline bool isEmpty() const noexcept { return p.isEmpty(); }
-
- void clear();
-
- const T &at(int i) const;
- const T &operator[](int i) const;
- T &operator[](int i);
-
- void reserve(int size);
- void append(const T &t);
- void append(const QList<T> &t);
- void prepend(const T &t);
- void insert(int i, const T &t);
- void replace(int i, const T &t);
- void removeAt(int i);
- int removeAll(const T &t);
- bool removeOne(const T &t);
- T takeAt(int i);
- T takeFirst();
- T takeLast();
- void move(int from, int to);
- void swapItemsAt(int i, int j);
-#if QT_DEPRECATED_SINCE(5, 13) && QT_VERSION < QT_VERSION_CHECK(6,0,0)
- QT_DEPRECATED_X("Use QList<T>::swapItemsAt()")
- void swap(int i, int j) { swapItemsAt(i, j); }
-#endif
- int indexOf(const T &t, int from = 0) const;
- int lastIndexOf(const T &t, int from = -1) const;
- bool contains(const T &t) const;
- int count(const T &t) const;
-
- class const_iterator;
-
- class iterator {
- public:
- Node *i;
- typedef std::random_access_iterator_tag iterator_category;
- // ### Qt6: use int
- typedef qptrdiff difference_type;
- typedef T value_type;
- typedef T *pointer;
- typedef T &reference;
-
- inline iterator() noexcept : i(nullptr) {}
- inline iterator(Node *n) noexcept : i(n) {}
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
- // can't remove it in Qt 5, since doing so would make the type trivial,
- // which changes the way it's passed to functions by value.
- inline iterator(const iterator &o) noexcept : i(o.i){}
- inline iterator &operator=(const iterator &o) noexcept
- { i = o.i; return *this; }
-#endif
- inline T &operator*() const { return i->t(); }
- inline T *operator->() const { return &i->t(); }
- inline T &operator[](difference_type j) const { return i[j].t(); }
- inline bool operator==(const iterator &o) const noexcept { return i == o.i; }
- inline bool operator!=(const iterator &o) const noexcept { return i != o.i; }
- inline bool operator<(const iterator& other) const noexcept { return i < other.i; }
- inline bool operator<=(const iterator& other) const noexcept { return i <= other.i; }
- inline bool operator>(const iterator& other) const noexcept { return i > other.i; }
- inline bool operator>=(const iterator& other) const noexcept { return i >= other.i; }
-#ifndef QT_STRICT_ITERATORS
- inline bool operator==(const const_iterator &o) const noexcept
- { return i == o.i; }
- inline bool operator!=(const const_iterator &o) const noexcept
- { return i != o.i; }
- inline bool operator<(const const_iterator& other) const noexcept
- { return i < other.i; }
- inline bool operator<=(const const_iterator& other) const noexcept
- { return i <= other.i; }
- inline bool operator>(const const_iterator& other) const noexcept
- { return i > other.i; }
- inline bool operator>=(const const_iterator& other) const noexcept
- { return i >= other.i; }
-#endif
- inline iterator &operator++() { ++i; return *this; }
- inline iterator operator++(int) { Node *n = i; ++i; return n; }
- inline iterator &operator--() { i--; return *this; }
- inline iterator operator--(int) { Node *n = i; i--; return n; }
- inline iterator &operator+=(difference_type j) { i+=j; return *this; }
- inline iterator &operator-=(difference_type j) { i-=j; return *this; }
- inline iterator operator+(difference_type j) const { return iterator(i+j); }
- inline iterator operator-(difference_type j) const { return iterator(i-j); }
- friend inline iterator operator+(difference_type j, iterator k) { return k + j; }
- inline int operator-(iterator j) const { return int(i - j.i); }
- };
- friend class iterator;
-
- class const_iterator {
- public:
- Node *i;
- typedef std::random_access_iterator_tag iterator_category;
- // ### Qt6: use int
- typedef qptrdiff difference_type;
- typedef T value_type;
- typedef const T *pointer;
- typedef const T &reference;
-
- inline const_iterator() noexcept : i(nullptr) {}
- inline const_iterator(Node *n) noexcept : i(n) {}
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
- // can't remove it in Qt 5, since doing so would make the type trivial,
- // which changes the way it's passed to functions by value.
- inline const_iterator(const const_iterator &o) noexcept : i(o.i) {}
- inline const_iterator &operator=(const const_iterator &o) noexcept
- { i = o.i; return *this; }
-#endif
-#ifdef QT_STRICT_ITERATORS
- inline explicit const_iterator(const iterator &o) noexcept : i(o.i) {}
-#else
- inline const_iterator(const iterator &o) noexcept : i(o.i) {}
-#endif
- inline const T &operator*() const { return i->t(); }
- inline const T *operator->() const { return &i->t(); }
- inline const T &operator[](difference_type j) const { return i[j].t(); }
- inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
- inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
- inline bool operator<(const const_iterator& other) const noexcept { return i < other.i; }
- inline bool operator<=(const const_iterator& other) const noexcept { return i <= other.i; }
- inline bool operator>(const const_iterator& other) const noexcept { return i > other.i; }
- inline bool operator>=(const const_iterator& other) const noexcept { return i >= other.i; }
- inline const_iterator &operator++() { ++i; return *this; }
- inline const_iterator operator++(int) { Node *n = i; ++i; return n; }
- inline const_iterator &operator--() { i--; return *this; }
- inline const_iterator operator--(int) { Node *n = i; i--; return n; }
- inline const_iterator &operator+=(difference_type j) { i+=j; return *this; }
- inline const_iterator &operator-=(difference_type j) { i-=j; return *this; }
- inline const_iterator operator+(difference_type j) const { return const_iterator(i+j); }
- inline const_iterator operator-(difference_type j) const { return const_iterator(i-j); }
- friend inline const_iterator operator+(difference_type j, const_iterator k) { return k + j; }
- inline int operator-(const_iterator j) const { return int(i - j.i); }
- };
- friend class const_iterator;
-
- // stl style
- typedef std::reverse_iterator<iterator> reverse_iterator;
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- inline iterator begin() { detach(); return reinterpret_cast<Node *>(p.begin()); }
- inline const_iterator begin() const noexcept { return reinterpret_cast<Node *>(p.begin()); }
- inline const_iterator cbegin() const noexcept { return reinterpret_cast<Node *>(p.begin()); }
- inline const_iterator constBegin() const noexcept { return reinterpret_cast<Node *>(p.begin()); }
- inline iterator end() { detach(); return reinterpret_cast<Node *>(p.end()); }
- inline const_iterator end() const noexcept { return reinterpret_cast<Node *>(p.end()); }
- inline const_iterator cend() const noexcept { return reinterpret_cast<Node *>(p.end()); }
- inline const_iterator constEnd() const noexcept { return reinterpret_cast<Node *>(p.end()); }
- reverse_iterator rbegin() { return reverse_iterator(end()); }
- reverse_iterator rend() { return reverse_iterator(begin()); }
- const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
- const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
- const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
- const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
- iterator insert(iterator before, const T &t);
- iterator erase(iterator pos);
- iterator erase(iterator first, iterator last);
-
- // more Qt
- typedef iterator Iterator;
- typedef const_iterator ConstIterator;
- inline int count() const { return p.size(); }
- inline int length() const { return p.size(); } // Same as count()
- inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
- inline const T& constFirst() const { return first(); }
- inline const T& first() const { Q_ASSERT(!isEmpty()); return at(0); }
- T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
- const T& last() const { Q_ASSERT(!isEmpty()); return at(count() - 1); }
- inline const T& constLast() const { return last(); }
- inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
- inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
- inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
- inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
- QList<T> mid(int pos, int length = -1) const;
-
- T value(int i) const;
- T value(int i, const T &defaultValue) const;
-
- // stl compatibility
- inline void push_back(const T &t) { append(t); }
- inline void push_front(const T &t) { prepend(t); }
- inline T& front() { return first(); }
- inline const T& front() const { return first(); }
- inline T& back() { return last(); }
- inline const T& back() const { return last(); }
- inline void pop_front() { removeFirst(); }
- inline void pop_back() { removeLast(); }
- inline bool empty() const { return isEmpty(); }
- typedef int size_type;
- typedef T value_type;
- typedef value_type *pointer;
- typedef const value_type *const_pointer;
- typedef value_type &reference;
- typedef const value_type &const_reference;
- // ### Qt6: use int
- typedef qptrdiff difference_type;
-
- // comfort
- QList<T> &operator+=(const QList<T> &l);
- inline QList<T> operator+(const QList<T> &l) const
- { QList n = *this; n += l; return n; }
- inline QList<T> &operator+=(const T &t)
- { append(t); return *this; }
- inline QList<T> &operator<< (const T &t)
- { append(t); return *this; }
- inline QList<T> &operator<<(const QList<T> &l)
- { *this += l; return *this; }
-
- static QList<T> fromVector(const QVector<T> &vector);
- QVector<T> toVector() const;
-
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
- Q_DECL_DEPRECATED_X("Use QList<T>(set.begin(), set.end()) instead.")
- static QList<T> fromSet(const QSet<T> &set);
- Q_DECL_DEPRECATED_X("Use QSet<T>(list.begin(), list.end()) instead.")
- QSet<T> toSet() const;
-
- Q_DECL_DEPRECATED_X("Use QList<T>(list.begin(), list.end()) instead.")
- static inline QList<T> fromStdList(const std::list<T> &list)
- { return QList<T>(list.begin(), list.end()); }
- Q_DECL_DEPRECATED_X("Use std::list<T>(list.begin(), list.end()) instead.")
- inline std::list<T> toStdList() const
- { return std::list<T>(begin(), end()); }
-#endif
-
-private:
- Node *detach_helper_grow(int i, int n);
- void detach_helper(int alloc);
- void detach_helper();
- void dealloc(QListData::Data *d);
-
- void node_construct(Node *n, const T &t);
- void node_destruct(Node *n);
- void node_copy(Node *from, Node *to, Node *src);
- void node_destruct(Node *from, Node *to);
-
- bool isValidIterator(const iterator &i) const noexcept
- {
- const std::less<const Node *> less = {};
- return !less(i.i, cbegin().i) && !less(cend().i, i.i);
- }
-
-private:
- inline bool op_eq_impl(const QList &other, QListData::NotArrayCompatibleLayout) const;
- inline bool op_eq_impl(const QList &other, QListData::ArrayCompatibleLayout) const;
- inline bool contains_impl(const T &, QListData::NotArrayCompatibleLayout) const;
- inline bool contains_impl(const T &, QListData::ArrayCompatibleLayout) const;
- inline int count_impl(const T &, QListData::NotArrayCompatibleLayout) const;
- inline int count_impl(const T &, QListData::ArrayCompatibleLayout) const;
-};
-
-#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
-template <typename InputIterator,
- typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
- QtPrivate::IfIsInputIterator<InputIterator> = true>
-QList(InputIterator, InputIterator) -> QList<ValueType>;
-#endif
-
-#if defined(Q_CC_BOR)
-template <typename T>
-Q_INLINE_TEMPLATE T &QList<T>::Node::t()
-{ return QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic ? *(T*)v:*(T*)this; }
-#endif
-
-template <typename T>
-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);
-#if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__)
- // This violates pointer aliasing rules, but it is known to be safe (and silent)
- // in unoptimized GCC builds (-fno-strict-aliasing). The other compilers which
- // set the same define are assumed to be safe.
- else *reinterpret_cast<T*>(n) = t;
-#else
- // This is always safe, but penaltizes unoptimized builds a lot.
- else ::memcpy(n, static_cast<const void *>(&t), sizeof(T));
-#endif
-}
-
-template <typename T>
-Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n)
-{
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v);
- else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T();
-}
-
-template <typename T>
-Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src)
-{
- Node *current = from;
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- QT_TRY {
- while(current != to) {
- current->v = new T(*reinterpret_cast<T*>(src->v));
- ++current;
- ++src;
- }
- } QT_CATCH(...) {
- while (current-- != from)
- delete reinterpret_cast<T*>(current->v);
- QT_RETHROW;
- }
-
- } else if (QTypeInfo<T>::isComplex) {
- QT_TRY {
- while(current != to) {
- new (current) T(*reinterpret_cast<T*>(src));
- ++current;
- ++src;
- }
- } QT_CATCH(...) {
- while (current-- != from)
- (reinterpret_cast<T*>(current))->~T();
- QT_RETHROW;
- }
- } else {
- if (src != from && to - from > 0)
- memcpy(from, src, (to - from) * sizeof(Node));
- }
-}
-
-template <typename T>
-Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *from, Node *to)
-{
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic)
- while(from != to) --to, delete reinterpret_cast<T*>(to->v);
- else if (QTypeInfo<T>::isComplex)
- while (from != to) --to, reinterpret_cast<T*>(to)->~T();
-}
-
-template <typename T>
-Q_INLINE_TEMPLATE QList<T> &QList<T>::operator=(const QList<T> &l)
-{
- if (d != l.d) {
- QList<T> tmp(l);
- tmp.swap(*this);
- }
- return *this;
-}
-template <typename T>
-inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t)
-{
- Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid");
-
- int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin()));
- Node *n = nullptr;
- if (d->ref.isShared())
- n = detach_helper_grow(iBefore, 1);
- else
- n = reinterpret_cast<Node *>(p.insert(iBefore));
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- p.remove(iBefore);
- QT_RETHROW;
- }
- return n;
-}
-template <typename T>
-inline typename QList<T>::iterator QList<T>::erase(iterator it)
-{
- Q_ASSERT_X(isValidIterator(it), "QList::erase", "The specified iterator argument 'it' is invalid");
- if (d->ref.isShared()) {
- int offset = int(it.i - reinterpret_cast<Node *>(p.begin()));
- it = begin(); // implies detach()
- it += offset;
- }
- node_destruct(it.i);
- return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void**>(it.i)));
-}
-template <typename T>
-inline const T &QList<T>::at(int i) const
-{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::at", "index out of range");
- return reinterpret_cast<Node *>(p.at(i))->t(); }
-template <typename T>
-inline const T &QList<T>::operator[](int i) const
-{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
- return reinterpret_cast<Node *>(p.at(i))->t(); }
-template <typename T>
-inline T &QList<T>::operator[](int i)
-{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
- detach(); return reinterpret_cast<Node *>(p.at(i))->t(); }
-template <typename T>
-inline void QList<T>::removeAt(int i)
-{
-#if !QT_DEPRECATED_SINCE(5, 15)
- Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::removeAt", "index out of range");
-#elif !defined(QT_NO_DEBUG)
- if (i < 0 || i >= p.size())
- qWarning("QList::removeAt(): Index out of range.");
-#endif
- detach();
- node_destruct(reinterpret_cast<Node *>(p.at(i))); p.remove(i);
-}
-template <typename T>
-inline T QList<T>::takeAt(int i)
-{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::take", "index out of range");
- detach(); Node *n = reinterpret_cast<Node *>(p.at(i)); T t = std::move(n->t()); node_destruct(n);
- p.remove(i); return t; }
-template <typename T>
-inline T QList<T>::takeFirst()
-{ T t = std::move(first()); removeFirst(); return t; }
-template <typename T>
-inline T QList<T>::takeLast()
-{ T t = std::move(last()); removeLast(); return t; }
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc)
-{
- if (d->alloc < alloc) {
- if (d->ref.isShared())
- detach_helper(alloc);
- else
- p.realloc(alloc);
- }
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
-{
- if (d->ref.isShared()) {
- Node *n = detach_helper_grow(INT_MAX, 1);
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- --d->end;
- QT_RETHROW;
- }
- } else {
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- Node *n = reinterpret_cast<Node *>(p.append());
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- --d->end;
- QT_RETHROW;
- }
- } else {
- Node *n, copy;
- node_construct(&copy, t); // t might be a reference to an object in the array
- QT_TRY {
- n = reinterpret_cast<Node *>(p.append());;
- } QT_CATCH(...) {
- node_destruct(&copy);
- QT_RETHROW;
- }
- *n = copy;
- }
- }
-}
-
-template <typename T>
-inline void QList<T>::prepend(const T &t)
-{
- if (d->ref.isShared()) {
- Node *n = detach_helper_grow(0, 1);
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- ++d->begin;
- QT_RETHROW;
- }
- } else {
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- Node *n = reinterpret_cast<Node *>(p.prepend());
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- ++d->begin;
- QT_RETHROW;
- }
- } else {
- Node *n, copy;
- node_construct(&copy, t); // t might be a reference to an object in the array
- QT_TRY {
- n = reinterpret_cast<Node *>(p.prepend());;
- } QT_CATCH(...) {
- node_destruct(&copy);
- QT_RETHROW;
- }
- *n = copy;
- }
- }
-}
-
-template <typename T>
-inline void QList<T>::insert(int i, const T &t)
-{
-#if !QT_DEPRECATED_SINCE(5, 15)
- Q_ASSERT_X(i >= 0 && i <= p.size(), "QList<T>::insert", "index out of range");
-#elif !defined(QT_NO_DEBUG)
- if (i < 0 || i > p.size())
- qWarning("QList::insert(): Index out of range.");
-#endif
- if (d->ref.isShared()) {
- Node *n = detach_helper_grow(i, 1);
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- p.remove(i);
- QT_RETHROW;
- }
- } else {
- if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
- Node *n = reinterpret_cast<Node *>(p.insert(i));
- QT_TRY {
- node_construct(n, t);
- } QT_CATCH(...) {
- p.remove(i);
- QT_RETHROW;
- }
- } else {
- Node *n, copy;
- node_construct(&copy, t); // t might be a reference to an object in the array
- QT_TRY {
- n = reinterpret_cast<Node *>(p.insert(i));;
- } QT_CATCH(...) {
- node_destruct(&copy);
- QT_RETHROW;
- }
- *n = copy;
- }
- }
-}
-
-template <typename T>
-inline void QList<T>::replace(int i, const T &t)
-{
- Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace", "index out of range");
- detach();
- reinterpret_cast<Node *>(p.at(i))->t() = t;
-}
-
-template <typename T>
-inline void QList<T>::swapItemsAt(int i, int j)
-{
- Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(),
- "QList<T>::swap", "index out of range");
- detach();
- qSwap(d->array[d->begin + i], d->array[d->begin + j]);
-}
-
-template <typename T>
-inline void QList<T>::move(int from, int to)
-{
- Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(),
- "QList<T>::move", "index out of range");
- detach();
- p.move(from, to);
-}
-
-template<typename T>
-Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const
-{
- using namespace QtPrivate;
- switch (QContainerImplHelper::mid(size(), &pos, &alength)) {
- case QContainerImplHelper::Null:
- case QContainerImplHelper::Empty:
- return QList<T>();
- case QContainerImplHelper::Full:
- return *this;
- case QContainerImplHelper::Subset:
- break;
- }
-
- QList<T> cpy;
- if (alength <= 0)
- return cpy;
- cpy.reserve(alength);
- cpy.d->end = alength;
- QT_TRY {
- cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()),
- reinterpret_cast<Node *>(cpy.p.end()),
- reinterpret_cast<Node *>(p.begin() + pos));
- } QT_CATCH(...) {
- // restore the old end
- cpy.d->end = 0;
- QT_RETHROW;
- }
- return cpy;
-}
-
template<typename T>
-Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i) const
-{
- if (i < 0 || i >= p.size()) {
- return T();
- }
- return reinterpret_cast<Node *>(p.at(i))->t();
-}
-
+using QMutableListIterator = QMutableVectorIterator<T>;
template<typename T>
-Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const
-{
- return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t());
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c)
-{
- Node *n = reinterpret_cast<Node *>(p.begin());
- QListData::Data *x = p.detach_grow(&i, c);
- QT_TRY {
- node_copy(reinterpret_cast<Node *>(p.begin()),
- reinterpret_cast<Node *>(p.begin() + i), n);
- } QT_CATCH(...) {
- p.dispose();
- d = x;
- QT_RETHROW;
- }
- QT_TRY {
- node_copy(reinterpret_cast<Node *>(p.begin() + i + c),
- reinterpret_cast<Node *>(p.end()), n + i);
- } QT_CATCH(...) {
- node_destruct(reinterpret_cast<Node *>(p.begin()),
- reinterpret_cast<Node *>(p.begin() + i));
- p.dispose();
- d = x;
- QT_RETHROW;
- }
-
- if (!x->ref.deref())
- dealloc(x);
-
- return reinterpret_cast<Node *>(p.begin() + i);
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc)
-{
- Node *n = reinterpret_cast<Node *>(p.begin());
- QListData::Data *x = p.detach(alloc);
- QT_TRY {
- node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
- } QT_CATCH(...) {
- p.dispose();
- d = x;
- QT_RETHROW;
- }
-
- if (!x->ref.deref())
- dealloc(x);
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper()
-{
- detach_helper(d->alloc);
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE QList<T>::QList(const QList<T> &l)
- : QListSpecialMethods<T>(l), d(l.d)
-{
- if (!d->ref.ref()) {
- p.detach(d->alloc);
-
- QT_TRY {
- node_copy(reinterpret_cast<Node *>(p.begin()),
- reinterpret_cast<Node *>(p.end()),
- reinterpret_cast<Node *>(l.p.begin()));
- } QT_CATCH(...) {
- QListData::dispose(d);
- QT_RETHROW;
- }
- }
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE QList<T>::~QList()
-{
- if (!d->ref.deref())
- dealloc(d);
-}
-
-template <typename T>
-template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>>
-QList<T>::QList(InputIterator first, InputIterator last)
- : QList()
-{
- QtPrivate::reserveIfForwardIterator(this, first, last);
- std::copy(first, last, std::back_inserter(*this));
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const
-{
- if (d == l.d)
- return true;
- if (p.size() != l.p.size())
- return false;
- return this->op_eq_impl(l, MemoryLayout());
-}
-
-template <typename T>
-inline bool QList<T>::op_eq_impl(const QList &l, QListData::NotArrayCompatibleLayout) const
-{
- Node *i = reinterpret_cast<Node *>(p.begin());
- Node *e = reinterpret_cast<Node *>(p.end());
- Node *li = reinterpret_cast<Node *>(l.p.begin());
- for (; i != e; ++i, ++li) {
- if (!(i->t() == li->t()))
- return false;
- }
- return true;
-}
-
-template <typename T>
-inline bool QList<T>::op_eq_impl(const QList &l, QListData::ArrayCompatibleLayout) const
-{
- const T *lb = reinterpret_cast<const T*>(l.p.begin());
- const T *b = reinterpret_cast<const T*>(p.begin());
- const T *e = reinterpret_cast<const T*>(p.end());
- return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(lb, l.p.size()));
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::dealloc(QListData::Data *data)
-{
- node_destruct(reinterpret_cast<Node *>(data->array + data->begin),
- reinterpret_cast<Node *>(data->array + data->end));
- QListData::dispose(data);
-}
-
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE void QList<T>::clear()
-{
- *this = QList<T>();
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t)
-{
- int index = indexOf(_t);
- if (index == -1)
- return 0;
-
- const T t = _t;
- detach();
-
- Node *i = reinterpret_cast<Node *>(p.at(index));
- Node *e = reinterpret_cast<Node *>(p.end());
- Node *n = i;
- node_destruct(i);
- while (++i != e) {
- if (i->t() == t)
- node_destruct(i);
- else
- *n++ = *i;
- }
-
- int removedCount = int(e - n);
- d->end -= removedCount;
- return removedCount;
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE bool QList<T>::removeOne(const T &_t)
-{
- int index = indexOf(_t);
- if (index != -1) {
- removeAt(index);
- return true;
- }
- return false;
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst,
- typename QList<T>::iterator alast)
-{
- Q_ASSERT_X(isValidIterator(afirst), "QList::erase", "The specified iterator argument 'afirst' is invalid");
- Q_ASSERT_X(isValidIterator(alast), "QList::erase", "The specified iterator argument 'alast' is invalid");
-
- if (d->ref.isShared()) {
- // ### A block is erased and a detach is needed. We should shrink and only copy relevant items.
- int offsetfirst = int(afirst.i - reinterpret_cast<Node *>(p.begin()));
- int offsetlast = int(alast.i - reinterpret_cast<Node *>(p.begin()));
- afirst = begin(); // implies detach()
- alast = afirst;
- afirst += offsetfirst;
- alast += offsetlast;
- }
-
- for (Node *n = afirst.i; n < alast.i; ++n)
- node_destruct(n);
- int idx = afirst - begin();
- p.remove(idx, alast - afirst);
- return begin() + idx;
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l)
-{
- if (!l.isEmpty()) {
- if (d == &QListData::shared_null) {
- *this = l;
- } else {
- Node *n = (d->ref.isShared())
- ? detach_helper_grow(INT_MAX, l.size())
- : reinterpret_cast<Node *>(p.append(l.p));
- QT_TRY {
- node_copy(n, reinterpret_cast<Node *>(p.end()),
- reinterpret_cast<Node *>(l.p.begin()));
- } QT_CATCH(...) {
- // restore the old end
- d->end -= int(reinterpret_cast<Node *>(p.end()) - n);
- QT_RETHROW;
- }
- }
- }
- return *this;
-}
-
-template <typename T>
-inline void QList<T>::append(const QList<T> &t)
-{
- *this += t;
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE int QList<T>::indexOf(const T &t, int from) const
-{
- return QtPrivate::indexOf<T, T>(*this, t, from);
-}
-
-namespace QtPrivate
-{
-template <typename T, typename U>
-int indexOf(const QList<T> &list, const U &u, int from)
-{
- typedef typename QList<T>::Node Node;
-
- if (from < 0)
- from = qMax(from + list.p.size(), 0);
- if (from < list.p.size()) {
- Node *n = reinterpret_cast<Node *>(list.p.at(from -1));
- Node *e = reinterpret_cast<Node *>(list.p.end());
- while (++n != e)
- if (n->t() == u)
- return int(n - reinterpret_cast<Node *>(list.p.begin()));
- }
- return -1;
-}
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE int QList<T>::lastIndexOf(const T &t, int from) const
-{
- return QtPrivate::lastIndexOf<T, T>(*this, t, from);
-}
-
-namespace QtPrivate
-{
-template <typename T, typename U>
-int lastIndexOf(const QList<T> &list, const U &u, int from)
-{
- typedef typename QList<T>::Node Node;
-
- if (from < 0)
- from += list.p.size();
- else if (from >= list.p.size())
- from = list.p.size()-1;
- if (from >= 0) {
- Node *b = reinterpret_cast<Node *>(list.p.begin());
- Node *n = reinterpret_cast<Node *>(list.p.at(from + 1));
- while (n-- != b) {
- if (n->t() == u)
- return int(n - b);
- }
- }
- return -1;
-}
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE bool QList<T>::contains(const T &t) const
-{
- return contains_impl(t, MemoryLayout());
-}
-
-template <typename T>
-inline bool QList<T>::contains_impl(const T &t, QListData::NotArrayCompatibleLayout) const
-{
- Node *e = reinterpret_cast<Node *>(p.end());
- Node *i = reinterpret_cast<Node *>(p.begin());
- for (; i != e; ++i)
- if (i->t() == t)
- return true;
- return false;
-}
-
-template <typename T>
-inline bool QList<T>::contains_impl(const T &t, QListData::ArrayCompatibleLayout) const
-{
- const T *b = reinterpret_cast<const T*>(p.begin());
- const T *e = reinterpret_cast<const T*>(p.end());
- return std::find(b, e, t) != e;
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const
-{
- return this->count_impl(t, MemoryLayout());
-}
-
-template <typename T>
-inline int QList<T>::count_impl(const T &t, QListData::NotArrayCompatibleLayout) const
-{
- int c = 0;
- Node *e = reinterpret_cast<Node *>(p.end());
- Node *i = reinterpret_cast<Node *>(p.begin());
- for (; i != e; ++i)
- if (i->t() == t)
- ++c;
- return c;
-}
-
-template <typename T>
-inline int QList<T>::count_impl(const T &t, QListData::ArrayCompatibleLayout) const
-{
- return int(std::count(reinterpret_cast<const T*>(p.begin()),
- reinterpret_cast<const T*>(p.end()),
- t));
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const
-{
- return QVector<T>(begin(), end());
-}
-
-template <typename T>
-QList<T> QList<T>::fromVector(const QVector<T> &vector)
-{
- return vector.toList();
-}
-
-template <typename T>
-Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const
-{
- return QList<T>(begin(), end());
-}
-
-template <typename T>
-QVector<T> QVector<T>::fromList(const QList<T> &list)
-{
- return list.toVector();
-}
-
-Q_DECLARE_SEQUENTIAL_ITERATOR(List)
-Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List)
-
-template <typename T>
-uint qHash(const QList<T> &key, uint seed = 0)
- noexcept(noexcept(qHashRange(key.cbegin(), key.cend(), seed)))
-{
- return qHashRange(key.cbegin(), key.cend(), seed);
-}
-
-template <typename T>
-bool operator<(const QList<T> &lhs, const QList<T> &rhs)
- noexcept(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(),
- rhs.begin(), rhs.end())))
-{
- return std::lexicographical_compare(lhs.begin(), lhs.end(),
- rhs.begin(), rhs.end());
-}
-
-template <typename T>
-inline bool operator>(const QList<T> &lhs, const QList<T> &rhs)
- noexcept(noexcept(lhs < rhs))
-{
- return rhs < lhs;
-}
-
-template <typename T>
-inline bool operator<=(const QList<T> &lhs, const QList<T> &rhs)
- noexcept(noexcept(lhs < rhs))
-{
- return !(lhs > rhs);
-}
-
-template <typename T>
-inline bool operator>=(const QList<T> &lhs, const QList<T> &rhs)
- noexcept(noexcept(lhs < rhs))
-{
- return !(lhs < rhs);
-}
-
+using QListIterator = QVectorIterator<T>;
QT_END_NAMESPACE
+#endif
#include <QtCore/qbytearraylist.h>
#include <QtCore/qstringlist.h>
-#ifdef Q_CC_MSVC
-#pragma warning( pop )
-#endif
-
#endif // QLIST_H
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index fa736e8413..5cc3116903 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -219,7 +219,7 @@ struct QMapData : public QMapDataBase
Node *createNode(const Key &k, const T &v, Node *parent = nullptr, bool left = false)
{
- Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node),
+ Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), alignof(Node),
parent, left));
QT_TRY {
new (&n->key) Key(k);
@@ -243,7 +243,7 @@ struct QMapData : public QMapDataBase
void destroy() {
if (root()) {
root()->destroySubTree();
- freeTree(header.left, Q_ALIGNOF(Node));
+ freeTree(header.left, alignof(Node));
}
freeData(this);
}
@@ -356,17 +356,6 @@ public:
inline void detach() { if (d->ref.isShared()) detach_helper(); }
inline bool isDetached() const { return !d->ref.isShared(); }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable)
- {
- if (sharable == d->ref.isSharable())
- return;
- if (!sharable)
- detach();
- // Don't call on shared_null
- d->ref.setSharable(sharable);
- }
-#endif
inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
void clear();
@@ -444,13 +433,8 @@ public:
inline iterator &operator-=(int j) { return *this = *this - j; }
friend inline iterator operator+(int j, iterator k) { return k + j; }
-#ifndef QT_STRICT_ITERATORS
- public:
- inline bool operator==(const const_iterator &o) const
- { return i == o.i; }
- inline bool operator!=(const const_iterator &o) const
- { return i != o.i; }
-#endif
+ inline bool operator==(const const_iterator &o) const { return i == o.i; }
+ inline bool operator!=(const const_iterator &o) const { return i != o.i; }
friend class QMap<Key, T>;
};
friend class iterator;
@@ -469,12 +453,7 @@ public:
Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
inline const_iterator(const Node *node) : i(node) { }
-#ifdef QT_STRICT_ITERATORS
- explicit inline const_iterator(const iterator &o)
-#else
- inline const_iterator(const iterator &o)
-#endif
- { i = o.i; }
+ inline const_iterator(const iterator &o) { i = o.i; }
inline const Key &key() const { return i->key; }
inline const T &value() const { return i->value; }
@@ -508,11 +487,6 @@ public:
inline const_iterator &operator-=(int j) { return *this = *this - j; }
friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
-#ifdef QT_STRICT_ITERATORS
- private:
- inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
- inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
-#endif
friend class QMap<Key, T>;
};
friend class const_iterator;
diff --git a/src/corelib/tools/qrefcount.h b/src/corelib/tools/qrefcount.h
index 2e5388ad9a..982a9c2bbf 100644
--- a/src/corelib/tools/qrefcount.h
+++ b/src/corelib/tools/qrefcount.h
@@ -53,10 +53,6 @@ class RefCount
public:
inline bool ref() noexcept {
int count = atomic.loadRelaxed();
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- if (count == 0) // !isSharable
- return false;
-#endif
if (count != -1) // !isStatic
atomic.ref();
return true;
@@ -64,32 +60,11 @@ public:
inline bool deref() noexcept {
int count = atomic.loadRelaxed();
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- if (count == 0) // !isSharable
- return false;
-#endif
if (count == -1) // isStatic
return true;
return atomic.deref();
}
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- bool setSharable(bool sharable) noexcept
- {
- Q_ASSERT(!isShared());
- if (sharable)
- return atomic.testAndSetRelaxed(0, 1);
- else
- return atomic.testAndSetRelaxed(1, 0);
- }
-
- bool isSharable() const noexcept
- {
- // Sharable === Shared ownership.
- return atomic.loadRelaxed() != 0;
- }
-#endif
-
bool isStatic() const noexcept
{
// Persistent object, never deleted
diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h
index 879e2176f2..f98bb051ec 100644
--- a/src/corelib/tools/qset.h
+++ b/src/corelib/tools/qset.h
@@ -86,9 +86,6 @@ public:
inline void detach() { q_hash.detach(); }
inline bool isDetached() const { return q_hash.isDetached(); }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable) { q_hash.setSharable(sharable); }
-#endif
inline void clear() { q_hash.clear(); }
@@ -260,12 +257,6 @@ public:
{ QSet<T> result = *this; result -= other; return result; }
QList<T> values() const;
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
- Q_DECL_DEPRECATED_X("Use values() instead.")
- QList<T> toList() const { return values(); }
- Q_DECL_DEPRECATED_X("Use QSet<T>(list.begin(), list.end()) instead.")
- static QSet<T> fromList(const QList<T> &list);
-#endif
private:
Hash q_hash;
@@ -397,30 +388,6 @@ Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::values() const
return result;
}
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
-template <typename T>
-Q_OUTOFLINE_TEMPLATE QSet<T> QList<T>::toSet() const
-{
- QSet<T> result;
- result.reserve(size());
- for (int i = 0; i < size(); ++i)
- result.insert(at(i));
- return result;
-}
-
-template <typename T>
-QSet<T> QSet<T>::fromList(const QList<T> &list)
-{
- return list.toSet();
-}
-
-template <typename T>
-QList<T> QList<T>::fromSet(const QSet<T> &set)
-{
- return set.toList();
-}
-#endif
-
Q_DECLARE_SEQUENTIAL_ITERATOR(Set)
#if !defined(QT_NO_JAVA_STYLE_ITERATORS)
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index 62fbdb4a2a..8d01b7ec12 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -1,6 +1,7 @@
/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2019 Intel Corporation
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
@@ -40,127 +41,266 @@
#ifndef QVECTOR_H
#define QVECTOR_H
-#include <QtCore/qalgorithms.h>
-#include <QtCore/qiterator.h>
-#include <QtCore/qrefcount.h>
-#include <QtCore/qarraydata.h>
+#include <QtCore/qarraydatapointer.h>
+#include <QtCore/qnamespace.h>
#include <QtCore/qhashfunctions.h>
-#include <QtCore/qcontainertools_impl.h>
+#include <QtCore/qiterator.h>
-#include <iterator>
+#include <functional>
+#include <limits>
#include <initializer_list>
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
-#include <vector>
-#endif
-#include <stdlib.h>
-#include <string.h>
-
-#include <algorithm>
+#include <type_traits>
QT_BEGIN_NAMESPACE
+namespace QtPrivate {
+ template <typename V, typename U> int indexOf(const QVector<V> &list, const U &u, int from);
+ template <typename V, typename U> int lastIndexOf(const QVector<V> &list, const U &u, int from);
+}
+
+template <typename T> struct QVectorSpecialMethods
+{
+protected:
+ ~QVectorSpecialMethods() = default;
+};
+template <> struct QVectorSpecialMethods<QByteArray>;
+template <> struct QVectorSpecialMethods<QString>;
+
template <typename T>
class QVector
+#ifndef Q_QDOC
+ : public QVectorSpecialMethods<T>
+#endif
{
typedef QTypedArrayData<T> Data;
- Data *d;
+ typedef QArrayDataOps<T> DataOps;
+ typedef QArrayDataPointer<T> DataPointer;
+ class DisableRValueRefs {};
+
+ DataPointer d;
+
+ template <typename V, typename U> friend int QtPrivate::indexOf(const QVector<V> &list, const U &u, int from);
+ template <typename V, typename U> friend int QtPrivate::lastIndexOf(const QVector<V> &list, const U &u, int from);
public:
- inline QVector() noexcept : d(Data::sharedNull()) { }
- explicit QVector(int size);
- QVector(int size, const T &t);
- inline QVector(const QVector<T> &v);
- inline ~QVector() { if (!d->ref.deref()) freeData(d); }
- QVector<T> &operator=(const QVector<T> &v);
- QVector(QVector<T> &&other) noexcept : d(other.d) { other.d = Data::sharedNull(); }
- QVector<T> &operator=(QVector<T> &&other) noexcept
- { QVector moved(std::move(other)); swap(moved); return *this; }
- void swap(QVector<T> &other) noexcept { qSwap(d, other.d); }
- inline QVector(std::initializer_list<T> args);
- QVector<T> &operator=(std::initializer_list<T> args);
- template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
- inline QVector(InputIterator first, InputIterator last);
- explicit QVector(QArrayDataPointerRef<T> ref) noexcept : d(ref.ptr) {}
+ typedef T Type;
+ typedef T value_type;
+ typedef value_type *pointer;
+ typedef const value_type *const_pointer;
+ typedef value_type &reference;
+ typedef const value_type &const_reference;
+ typedef int size_type;
+ typedef qptrdiff difference_type;
+ typedef typename Data::iterator iterator;
+ typedef typename Data::const_iterator const_iterator;
+ typedef iterator Iterator;
+ typedef const_iterator ConstIterator;
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef typename DataPointer::parameter_type parameter_type;
+ using rvalue_ref = typename std::conditional<DataPointer::pass_parameter_by_value, DisableRValueRefs, T &&>::type;
- bool operator==(const QVector<T> &v) const;
- inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
+private:
+ void resize_internal(int i, Qt::Initialization);
+ bool isValidIterator(const_iterator i) const
+ {
+ const std::less<const T*> less = {};
+ return !less(d->end(), i) && !less(i, d->begin());
+ }
+public:
+ QVector(DataPointer dd) noexcept
+ : d(dd)
+ {
+ }
- inline int size() const { return d->size; }
+public:
+ inline QVector() noexcept { }
+ explicit QVector(int size)
+ : d(Data::allocate(size))
+ {
+ if (size)
+ d->appendInitialize(size);
+ }
+ QVector(int size, const T &t)
+ : d(Data::allocate(size))
+ {
+ if (size)
+ d->copyAppend(size, t);
+ }
- inline bool isEmpty() const { return d->size == 0; }
+ inline QVector(const QVector<T> &other) noexcept : d(other.d) {}
+ QVector(QVector<T> &&other) noexcept : d(std::move(other.d)) {}
+ inline QVector(std::initializer_list<T> args)
+ : d(Data::allocate(args.size()))
+ {
+ if (args.size())
+ d->copyAppend(args.begin(), args.end());
+ }
- void resize(int size);
+ ~QVector() /*noexcept(std::is_nothrow_destructible<T>::value)*/ {}
+ QVector<T> &operator=(const QVector<T> &other) { d = other.d; return *this; }
+ QVector &operator=(QVector &&other) noexcept(std::is_nothrow_destructible<T>::value)
+ {
+ d = std::move(other.d);
+ return *this;
+ }
+ QVector<T> &operator=(std::initializer_list<T> args)
+ {
+ d = DataPointer(Data::allocate(args.size()));
+ if (args.size())
+ d->copyAppend(args.begin(), args.end());
+ return *this;
+ }
+ template <typename InputIterator, QtPrivate::IfIsForwardIterator<InputIterator> = true>
+ QVector(InputIterator i1, InputIterator i2)
+ : d(Data::allocate(std::distance(i1, i2)))
+ {
+ if (std::distance(i1, i2))
+ d->copyAppend(i1, i2);
+ }
- inline int capacity() const { return int(d->alloc); }
- void reserve(int size);
- inline void squeeze()
+ template <typename InputIterator, QtPrivate::IfIsNotForwardIterator<InputIterator> = true>
+ QVector(InputIterator i1, InputIterator i2)
+ : QVector()
{
- if (d->size < int(d->alloc)) {
- if (!d->size) {
- *this = QVector<T>();
- return;
- }
- realloc(d->size);
- }
- if (d->capacityReserved) {
- // capacity reserved in a read only memory would be useless
- // this checks avoid writing to such memory.
- d->capacityReserved = 0;
- }
+ QtPrivate::reserveIfForwardIterator(this, i1, i2);
+ std::copy(i1, i2, std::back_inserter(*this));
}
- inline void detach();
- inline bool isDetached() const { return !d->ref.isShared(); }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable)
+ void swap(QVector<T> &other) noexcept { qSwap(d, other.d); }
+
+ friend bool operator==(const QVector &l, const QVector &r)
{
- if (sharable == d->ref.isSharable())
- return;
- if (!sharable)
- detach();
+ if (l.size() != r.size())
+ return false;
+ if (l.begin() == r.begin())
+ return true;
- if (d == Data::unsharableEmpty()) {
- if (sharable)
- d = Data::sharedNull();
+ // do element-by-element comparison
+ return l.d->compare(l.begin(), r.begin(), l.size());
+ }
+ friend bool operator!=(const QVector &l, const QVector &r)
+ {
+ return !(l == r);
+ }
+
+ int size() const noexcept { return int(d->size); }
+ int count() const noexcept { return size(); }
+ int length() const noexcept { return size(); }
+
+ inline bool isEmpty() const noexcept { return d->size == 0; }
+
+ void resize(int size)
+ {
+ resize_internal(size, Qt::Uninitialized);
+ if (size > this->size())
+ d->appendInitialize(size);
+ }
+ void resize(int size, parameter_type c)
+ {
+ resize_internal(size, Qt::Uninitialized);
+ if (size > this->size())
+ d->copyAppend(size - this->size(), c);
+ }
+
+ inline int capacity() const { return int(d->constAllocatedCapacity()); }
+ void reserve(int size);
+ inline void squeeze();
+
+ void detach() { d.detach(); }
+ bool isDetached() const noexcept { return !d->isShared(); }
+
+ inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; }
+
+ pointer data() { detach(); return d->data(); }
+ const_pointer data() const noexcept { return d->data(); }
+ const_pointer constData() const noexcept { return d->data(); }
+ void clear() {
+ if (!size())
+ return;
+ if (d->needsDetach()) {
+ // must allocate memory
+ DataPointer detached(Data::allocate(d.allocatedCapacity(), d->detachFlags()));
+ d.swap(detached);
} else {
- d->ref.setSharable(sharable);
+ d->truncate(0);
}
- Q_ASSERT(d->ref.isSharable() == sharable);
}
+
+ const_reference at(int i) const noexcept
+ {
+ Q_ASSERT_X(size_t(i) < size_t(d->size), "QVector::at", "index out of range");
+ return data()[i];
+ }
+ reference operator[](int i)
+ {
+ Q_ASSERT_X(size_t(i) < size_t(d->size), "QVector::operator[]", "index out of range");
+ detach();
+ return data()[i];
+ }
+ const_reference operator[](int i) const noexcept { return at(i); }
+ void append(const_reference t)
+ { append(const_iterator(std::addressof(t)), const_iterator(std::addressof(t)) + 1); }
+ void append(const_iterator i1, const_iterator i2);
+ void append(value_type &&t);
+ void append(const QVector<T> &l) { append(l.constBegin(), l.constEnd()); }
+ void prepend(rvalue_ref t);
+ void prepend(const T &t);
+ iterator insert(int i, parameter_type t)
+ { return insert(i, 1, t); }
+ iterator insert(int i, int n, parameter_type t);
+ iterator insert(const_iterator before, parameter_type t)
+ {
+ Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid");
+ return insert(before, 1, t);
+ }
+ iterator insert(const_iterator before, int n, parameter_type t)
+ {
+ Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid");
+ return insert(std::distance(constBegin(), before), n, t);
+ }
+ iterator insert(const_iterator before, rvalue_ref t)
+ {
+ Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid");
+ return insert(std::distance(constBegin(), before), std::move(t));
+ }
+ iterator insert(int i, rvalue_ref t);
+#if 0
+ template< class InputIt >
+ iterator insert( const_iterator pos, InputIt first, InputIt last );
+ iterator insert( const_iterator pos, std::initializer_list<T> ilist );
#endif
+ void replace(int i, const T &t)
+ {
+ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");
+ const T copy(t);
+ data()[i] = copy;
+ }
+ void replace(int i, rvalue_ref t)
+ {
+ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");
+ const T copy(std::move(t));
+ data()[i] = std::move(copy);
+ }
- inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; }
+ void remove(int i, int n = 1);
+ void removeFirst() { Q_ASSERT(!isEmpty()); remove(0); }
+ void removeLast() { Q_ASSERT(!isEmpty()); remove(size() - 1); }
+ value_type takeFirst() { Q_ASSERT(!isEmpty()); value_type v = std::move(first()); remove(0); return v; }
+ value_type takeLast() { Q_ASSERT(!isEmpty()); value_type v = std::move(last()); remove(size() - 1); return v; }
- inline T *data() { detach(); return d->begin(); }
- inline const T *data() const { return d->begin(); }
- inline const T *constData() const { return d->begin(); }
- void clear();
-
- const T &at(int i) const;
- T &operator[](int i);
- const T &operator[](int i) const;
- void append(const T &t);
- void append(T &&t);
- inline void append(const QVector<T> &l) { *this += l; }
- void prepend(T &&t);
- void prepend(const T &t);
- void insert(int i, T &&t);
- void insert(int i, const T &t);
- void insert(int i, int n, const T &t);
- void replace(int i, const T &t);
- void remove(int i);
- void remove(int i, int n);
- inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(d->begin()); }
- inline void removeLast();
- T takeFirst() { Q_ASSERT(!isEmpty()); T r = std::move(first()); removeFirst(); return r; }
- T takeLast() { Q_ASSERT(!isEmpty()); T r = std::move(last()); removeLast(); return r; }
-
- QVector<T> &fill(const T &t, int size = -1);
-
- int indexOf(const T &t, int from = 0) const;
- int lastIndexOf(const T &t, int from = -1) const;
- bool contains(const T &t) const;
- int count(const T &t) const;
+ QVector<T> &fill(parameter_type t, int size = -1);
+
+ int indexOf(const T &t, int from = 0) const noexcept;
+ int lastIndexOf(const T &t, int from = -1) const noexcept;
+ bool contains(const T &t) const noexcept
+ {
+ return indexOf(t) != -1;
+ }
+ int count(const T &t) const noexcept
+ {
+ return int(std::count(&*cbegin(), &*cend(), t));
+ }
// QList compatibility
void removeAt(int i) { remove(i); }
@@ -169,10 +309,10 @@ public:
const const_iterator ce = this->cend(), cit = std::find(this->cbegin(), ce, t);
if (cit == ce)
return 0;
+ int index = cit - this->cbegin();
// next operation detaches, so ce, cit, t may become invalidated:
const T tCopy = t;
- const int firstFoundIdx = std::distance(this->cbegin(), cit);
- const iterator e = end(), it = std::remove(begin() + firstFoundIdx, e, tCopy);
+ const iterator e = end(), it = std::remove(begin() + index, e, tCopy);
const int result = std::distance(it, e);
erase(it, e);
return result;
@@ -185,7 +325,6 @@ public:
remove(i);
return true;
}
- int length() const { return size(); }
T takeAt(int i) { T t = std::move((*this)[i]); remove(i); return t; }
void move(int from, int to)
{
@@ -202,43 +341,26 @@ public:
}
// STL-style
- typedef typename Data::iterator iterator;
- typedef typename Data::const_iterator const_iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator;
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-#if !defined(QT_STRICT_ITERATORS) || defined(Q_CLANG_QDOC)
- inline iterator begin() { detach(); return d->begin(); }
- inline const_iterator begin() const noexcept { return d->constBegin(); }
- inline const_iterator cbegin() const noexcept { return d->constBegin(); }
- inline const_iterator constBegin() const noexcept { return d->constBegin(); }
- inline iterator end() { detach(); return d->end(); }
- inline const_iterator end() const noexcept { return d->constEnd(); }
- inline const_iterator cend() const noexcept { return d->constEnd(); }
- inline const_iterator constEnd() const noexcept { return d->constEnd(); }
-#else
- inline iterator begin(iterator = iterator()) { detach(); return d->begin(); }
- inline const_iterator begin(const_iterator = const_iterator()) const noexcept { return d->constBegin(); }
- inline const_iterator cbegin(const_iterator = const_iterator()) const noexcept { return d->constBegin(); }
- inline const_iterator constBegin(const_iterator = const_iterator()) const noexcept { return d->constBegin(); }
- inline iterator end(iterator = iterator()) { detach(); return d->end(); }
- inline const_iterator end(const_iterator = const_iterator()) const noexcept { return d->constEnd(); }
- inline const_iterator cend(const_iterator = const_iterator()) const noexcept { return d->constEnd(); }
- inline const_iterator constEnd(const_iterator = const_iterator()) const noexcept { return d->constEnd(); }
-#endif
+ iterator begin() { detach(); return d->begin(); }
+ iterator end() { detach(); return d->end(); }
+
+ const_iterator begin() const noexcept { return d->constBegin(); }
+ const_iterator end() const noexcept { return d->constEnd(); }
+ const_iterator cbegin() const noexcept { return d->constBegin(); }
+ const_iterator cend() const noexcept { return d->constEnd(); }
+ const_iterator constBegin() const noexcept { return d->constBegin(); }
+ const_iterator constEnd() const noexcept { return d->constEnd(); }
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
- iterator insert(iterator before, int n, const T &x);
- inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
- inline iterator insert(iterator before, T &&x);
+
iterator erase(iterator begin, iterator end);
inline iterator erase(iterator pos) { return erase(pos, pos+1); }
// more Qt
- inline int count() const { return d->size; }
inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); }
inline const T &constFirst() const { Q_ASSERT(!isEmpty()); return *begin(); }
@@ -249,7 +371,7 @@ public:
inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
QVector<T> mid(int pos, int len = -1) const;
- T value(int i) const;
+ T value(int i) const { return value(i, T()); }
T value(int i, const T &defaultValue) const;
void swapItemsAt(int i, int j) {
@@ -260,31 +382,22 @@ public:
}
// STL compatibility
- typedef T value_type;
- typedef value_type* pointer;
- typedef const value_type* const_pointer;
- typedef value_type& reference;
- typedef const value_type& const_reference;
- typedef qptrdiff difference_type;
- typedef iterator Iterator;
- typedef const_iterator ConstIterator;
- typedef int size_type;
inline void push_back(const T &t) { append(t); }
- void push_back(T &&t) { append(std::move(t)); }
- void push_front(T &&t) { prepend(std::move(t)); }
+ void push_back(rvalue_ref t) { append(std::move(t)); }
+ void push_front(rvalue_ref t) { prepend(std::move(t)); }
inline void push_front(const T &t) { prepend(t); }
void pop_back() { removeLast(); }
void pop_front() { removeFirst(); }
inline bool empty() const
{ return d->size == 0; }
- inline T& front() { return first(); }
+ inline reference front() { return first(); }
inline const_reference front() const { return first(); }
inline reference back() { return last(); }
inline const_reference back() const { return last(); }
void shrink_to_fit() { squeeze(); }
// comfort
- QVector<T> &operator+=(const QVector<T> &l);
+ QVector<T> &operator+=(const QVector<T> &l) { append(l.cbegin(), l.cend()); return *this; }
inline QVector<T> operator+(const QVector<T> &l) const
{ QVector n = *this; n += l; return n; }
inline QVector<T> &operator+=(const T &t)
@@ -293,37 +406,17 @@ public:
{ append(t); return *this; }
inline QVector<T> &operator<<(const QVector<T> &l)
{ *this += l; return *this; }
- inline QVector<T> &operator+=(T &&t)
+ inline QVector<T> &operator+=(rvalue_ref t)
{ append(std::move(t)); return *this; }
- inline QVector<T> &operator<<(T &&t)
+ inline QVector<T> &operator<<(rvalue_ref t)
{ append(std::move(t)); return *this; }
- static QVector<T> fromList(const QList<T> &list);
- QList<T> toList() const;
+ // Consider deprecating in 6.4 or later
+ static QVector<T> fromList(const QVector<T> &list) { return list; }
+ QVector<T> toList() const { return *this; }
-#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
- Q_DECL_DEPRECATED_X("Use QVector<T>(vector.begin(), vector.end()) instead.")
- static inline QVector<T> fromStdVector(const std::vector<T> &vector)
- { return QVector<T>(vector.begin(), vector.end()); }
- Q_DECL_DEPRECATED_X("Use std::vector<T>(vector.begin(), vector.end()) instead.")
- inline std::vector<T> toStdVector() const
- { return std::vector<T>(d->begin(), d->end()); }
-#endif
-private:
- // ### Qt6: remove methods, they are unused
- void reallocData(const int size, const int alloc, QArrayData::AllocationOptions options = QArrayData::Default);
- void reallocData(const int sz) { reallocData(sz, d->alloc); }
- void realloc(int alloc, QArrayData::AllocationOptions options = QArrayData::Default);
- void freeData(Data *d);
- void defaultConstruct(T *from, T *to);
- void copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom);
- void destruct(T *from, T *to);
- bool isValidIterator(const iterator &i) const
- {
- const std::less<const T*> less = {};
- return !less(d->end(), i) && !less(i, d->begin());
- }
- class AlignmentDummy { Data header; T array[1]; };
+ static inline QVector<T> fromVector(const QVector<T> &vector) { return vector; }
+ inline QVector<T> toVector() const { return *this; }
};
#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
@@ -333,570 +426,193 @@ template <typename InputIterator,
QVector(InputIterator, InputIterator) -> QVector<ValueType>;
#endif
-#ifdef Q_CC_MSVC
-// behavior change: an object of POD type constructed with an initializer of the form ()
-// will be default-initialized
-# pragma warning ( push )
-# pragma warning ( disable : 4345 )
-# pragma warning(disable : 4127) // conditional expression is constant
-#endif
-
template <typename T>
-void QVector<T>::defaultConstruct(T *from, T *to)
+inline void QVector<T>::resize_internal(int newSize, Qt::Initialization)
{
- if (QTypeInfo<T>::isComplex) {
- while (from != to) {
- new (from++) T();
+ Q_ASSERT(newSize >= 0);
+
+ if (d->needsDetach() || newSize > capacity()) {
+ // must allocate memory
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize),
+ d->detachFlags()));
+ if (size() && newSize) {
+ detached->copyAppend(constBegin(), constBegin() + qMin(newSize, size()));
}
- } else {
- ::memset(static_cast<void *>(from), 0, (to - from) * sizeof(T));
+ d.swap(detached);
}
-}
-template <typename T>
-void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom)
-{
- if (QTypeInfo<T>::isComplex) {
- while (srcFrom != srcTo)
- new (dstFrom++) T(*srcFrom++);
- } else {
- ::memcpy(static_cast<void *>(dstFrom), static_cast<const void *>(srcFrom), (srcTo - srcFrom) * sizeof(T));
- }
+ if (newSize < size())
+ d->truncate(newSize);
}
template <typename T>
-void QVector<T>::destruct(T *from, T *to)
+void QVector<T>::reserve(int asize)
{
- if (QTypeInfo<T>::isComplex) {
- while (from != to) {
- from++->~T();
+ // capacity() == 0 for immutable data, so this will force a detaching below
+ if (asize <= capacity()) {
+ if (d->flags() & Data::CapacityReserved)
+ return; // already reserved, don't shrink
+ if (!d->isShared()) {
+ // accept current allocation, don't shrink
+ d->flags() |= Data::CapacityReserved;
+ return;
}
}
+
+ DataPointer detached(Data::allocate(qMax(asize, size()),
+ d->detachFlags() | Data::CapacityReserved));
+ detached->copyAppend(constBegin(), constEnd());
+ d.swap(detached);
}
template <typename T>
-inline QVector<T>::QVector(const QVector<T> &v)
+inline void QVector<T>::squeeze()
{
- if (v.d->ref.ref()) {
- d = v.d;
- } else {
- if (v.d->capacityReserved) {
- d = Data::allocate(v.d->alloc);
- Q_CHECK_PTR(d);
- d->capacityReserved = true;
- } else {
- d = Data::allocate(v.d->size);
- Q_CHECK_PTR(d);
- }
- if (d->alloc) {
- copyConstruct(v.d->begin(), v.d->end(), d->begin());
- d->size = v.d->size;
+ if (d->needsDetach() || size() != capacity()) {
+ // must allocate memory
+ DataPointer detached(Data::allocate(size(), d->detachFlags() & ~Data::CapacityReserved));
+ if (size()) {
+ detached->copyAppend(constBegin(), constEnd());
}
+ d.swap(detached);
}
}
-#if defined(Q_CC_MSVC)
-#pragma warning( pop )
-#endif
-
template <typename T>
-void QVector<T>::detach()
+inline void QVector<T>::remove(int i, int n)
{
- if (!isDetached()) {
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- if (!d->alloc)
- d = Data::unsharableEmpty();
- else
-#endif
- realloc(int(d->alloc));
- }
- Q_ASSERT(isDetached());
-}
+ Q_ASSERT_X(size_t(i) + size_t(n) <= size_t(d->size), "QVector::remove", "index out of range");
+ Q_ASSERT_X(n >= 0, "QVector::remove", "invalid count");
-template <typename T>
-void QVector<T>::reserve(int asize)
-{
- if (asize > int(d->alloc))
- realloc(asize);
- if (isDetached()
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- && d != Data::unsharableEmpty()
-#endif
- )
- d->capacityReserved = 1;
- Q_ASSERT(capacity() >= asize);
-}
+ if (n == 0)
+ return;
-template <typename T>
-void QVector<T>::resize(int asize)
-{
- if (asize == d->size)
- return detach();
- if (asize > int(d->alloc) || !isDetached()) { // there is not enough space
- QArrayData::AllocationOptions opt = asize > int(d->alloc) ? QArrayData::Grow : QArrayData::Default;
- realloc(qMax(int(d->alloc), asize), opt);
+ const size_t newSize = size() - n;
+ if (d->needsDetach() ||
+ ((d->flags() & Data::CapacityReserved) == 0
+ && newSize < d->allocatedCapacity()/2)) {
+ // allocate memory
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize),
+ d->detachFlags() & ~(Data::GrowsBackwards | Data::GrowsForward)));
+ const_iterator where = constBegin() + i;
+ if (newSize) {
+ detached->copyAppend(constBegin(), where);
+ detached->copyAppend(where + n, constEnd());
+ }
+ d.swap(detached);
+ } else {
+ // we're detached and we can just move data around
+ d->erase(d->begin() + i, d->begin() + i + n);
}
- if (asize < d->size)
- destruct(begin() + asize, end());
- else
- defaultConstruct(end(), begin() + asize);
- d->size = asize;
-}
-template <typename T>
-inline void QVector<T>::clear()
-{
- if (!d->size)
- return;
- destruct(begin(), end());
- d->size = 0;
}
-template <typename T>
-inline const T &QVector<T>::at(int i) const
-{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
- return d->begin()[i]; }
-template <typename T>
-inline const T &QVector<T>::operator[](int i) const
-{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
- return d->begin()[i]; }
-template <typename T>
-inline T &QVector<T>::operator[](int i)
-{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
- return data()[i]; }
-template <typename T>
-inline void QVector<T>::insert(int i, const T &t)
-{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
- insert(begin() + i, 1, t); }
-template <typename T>
-inline void QVector<T>::insert(int i, int n, const T &t)
-{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
- insert(begin() + i, n, t); }
-template <typename T>
-inline void QVector<T>::insert(int i, T &&t)
-{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
- insert(begin() + i, std::move(t)); }
-template <typename T>
-inline void QVector<T>::remove(int i, int n)
-{ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range");
- erase(d->begin() + i, d->begin() + i + n); }
-template <typename T>
-inline void QVector<T>::remove(int i)
-{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove", "index out of range");
- erase(d->begin() + i, d->begin() + i + 1); }
+
template <typename T>
inline void QVector<T>::prepend(const T &t)
{ insert(begin(), 1, t); }
template <typename T>
-inline void QVector<T>::prepend(T &&t)
+void QVector<T>::prepend(rvalue_ref t)
{ insert(begin(), std::move(t)); }
-template <typename T>
-inline void QVector<T>::replace(int i, const T &t)
-{
- Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");
- const T copy(t);
- data()[i] = copy;
-}
-
-template <typename T>
-QVector<T> &QVector<T>::operator=(const QVector<T> &v)
+template<typename T>
+inline T QVector<T>::value(int i, const T &defaultValue) const
{
- if (v.d != d) {
- QVector<T> tmp(v);
- tmp.swap(*this);
- }
- return *this;
+ return size_t(i) < size_t(d->size) ? at(i) : defaultValue;
}
template <typename T>
-QVector<T>::QVector(int asize)
+inline void QVector<T>::append(const_iterator i1, const_iterator i2)
{
- Q_ASSERT_X(asize >= 0, "QVector::QVector", "Size must be greater than or equal to 0.");
- if (Q_LIKELY(asize > 0)) {
- d = Data::allocate(asize);
- Q_CHECK_PTR(d);
- d->size = asize;
- defaultConstruct(d->begin(), d->end());
+ if (i1 == i2)
+ return;
+ const size_t newSize = size() + std::distance(i1, i2);
+ if (d->needsDetach() || newSize > d->allocatedCapacity()) {
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize),
+ d->detachFlags() | Data::GrowsForward));
+ detached->copyAppend(constBegin(), constEnd());
+ detached->copyAppend(i1, i2);
+ d.swap(detached);
} else {
- d = Data::sharedNull();
+ // we're detached and we can just move data around
+ d->copyAppend(i1, i2);
}
}
template <typename T>
-QVector<T>::QVector(int asize, const T &t)
+inline void QVector<T>::append(value_type &&t)
{
- Q_ASSERT_X(asize >= 0, "QVector::QVector", "Size must be greater than or equal to 0.");
- if (asize > 0) {
- d = Data::allocate(asize);
- Q_CHECK_PTR(d);
- d->size = asize;
- T* i = d->end();
- while (i != d->begin())
- new (--i) T(t);
+ const size_t newSize = size() + 1;
+ const bool isTooSmall = newSize > d->allocatedCapacity();
+ const bool isOverlapping = std::addressof(*d->begin()) <= std::addressof(t)
+ && std::addressof(t) < std::addressof(*d->end());
+ if (isTooSmall || d->needsDetach() || Q_UNLIKELY(isOverlapping)) {
+ typename Data::ArrayOptions flags = d->detachFlags();
+ if (isTooSmall)
+ flags |= Data::GrowsForward;
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
+ detached->copyAppend(constBegin(), constEnd());
+ detached->moveAppend(std::addressof(t), std::addressof(t) + 1);
+ d.swap(detached);
} else {
- d = Data::sharedNull();
+ // we're detached and we can just move data around
+ d->moveAppend(std::addressof(t), std::addressof(t) + 1);
}
}
-#if defined(Q_CC_MSVC)
-QT_WARNING_PUSH
-QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant
-#endif // Q_CC_MSVC
-
template <typename T>
-QVector<T>::QVector(std::initializer_list<T> args)
+inline typename QVector<T>::iterator
+QVector<T>::insert(int i, int n, parameter_type t)
{
- if (args.size() > 0) {
- d = Data::allocate(args.size());
- Q_CHECK_PTR(d);
- // std::initializer_list<T>::iterator is guaranteed to be
- // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct
- copyConstruct(args.begin(), args.end(), d->begin());
- d->size = int(args.size());
- } else {
- d = Data::sharedNull();
- }
-}
+ Q_ASSERT_X(size_t(i) <= size_t(d->size), "QVector<T>::insert", "index out of range");
-template <typename T>
-QVector<T> &QVector<T>::operator=(std::initializer_list<T> args)
-{
- QVector<T> tmp(args);
- tmp.swap(*this);
- return *this;
-}
-
-#if defined(Q_CC_MSVC)
-QT_WARNING_POP
-#endif // Q_CC_MSVC
+ // we don't have a quick exit for n == 0
+ // it's not worth wasting CPU cycles for that
-template <typename T>
-template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>>
-QVector<T>::QVector(InputIterator first, InputIterator last)
- : QVector()
-{
- QtPrivate::reserveIfForwardIterator(this, first, last);
- std::copy(first, last, std::back_inserter(*this));
-}
-
-template <typename T>
-void QVector<T>::freeData(Data *x)
-{
- destruct(x->begin(), x->end());
- Data::deallocate(x);
-}
+ const size_t newSize = size() + n;
+ if (d->needsDetach() || newSize > d->allocatedCapacity()) {
+ typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward;
+ if (size_t(i) <= newSize / 4)
+ flags |= Data::GrowsBackwards;
-#if defined(Q_CC_MSVC)
-QT_WARNING_PUSH
-QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant
-#endif
-
-template <typename T>
-void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options)
-{
- Q_ASSERT(asize >= 0 && asize <= aalloc);
- Data *x = d;
-
- const bool isShared = d->ref.isShared();
-
- if (aalloc != 0) {
- if (aalloc != int(d->alloc) || isShared) {
- QT_TRY {
- // allocate memory
- x = Data::allocate(aalloc, options);
- Q_CHECK_PTR(x);
- // aalloc is bigger then 0 so it is not [un]sharedEmpty
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable));
-#endif
- Q_ASSERT(!x->ref.isStatic());
- x->size = asize;
-
- T *srcBegin = d->begin();
- T *srcEnd = asize > d->size ? d->end() : d->begin() + asize;
- T *dst = x->begin();
-
- if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) {
- QT_TRY {
- if (isShared || !std::is_nothrow_move_constructible<T>::value) {
- // we can not move the data, we need to copy construct it
- while (srcBegin != srcEnd)
- new (dst++) T(*srcBegin++);
- } else {
- while (srcBegin != srcEnd)
- new (dst++) T(std::move(*srcBegin++));
- }
- } QT_CATCH (...) {
- // destruct already copied objects
- destruct(x->begin(), dst);
- QT_RETHROW;
- }
- } else {
- ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T));
- dst += srcEnd - srcBegin;
-
- // destruct unused / not moved data
- if (asize < d->size)
- destruct(d->begin() + asize, d->end());
- }
-
- if (asize > d->size) {
- // construct all new objects when growing
- if (!QTypeInfo<T>::isComplex) {
- ::memset(static_cast<void *>(dst), 0, (static_cast<T *>(x->end()) - dst) * sizeof(T));
- } else {
- QT_TRY {
- while (dst != x->end())
- new (dst++) T();
- } QT_CATCH (...) {
- // destruct already copied objects
- destruct(x->begin(), dst);
- QT_RETHROW;
- }
- }
- }
- } QT_CATCH (...) {
- Data::deallocate(x);
- QT_RETHROW;
- }
- x->capacityReserved = d->capacityReserved;
- } else {
- Q_ASSERT(int(d->alloc) == aalloc); // resize, without changing allocation size
- Q_ASSERT(isDetached()); // can be done only on detached d
- Q_ASSERT(x == d); // in this case we do not need to allocate anything
- if (asize <= d->size) {
- destruct(x->begin() + asize, x->end()); // from future end to current end
- } else {
- defaultConstruct(x->end(), x->begin() + asize); // from current end to future end
- }
- x->size = asize;
- }
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
+ const_iterator where = constBegin() + i;
+ detached->copyAppend(constBegin(), where);
+ detached->copyAppend(n, t);
+ detached->copyAppend(where, constEnd());
+ d.swap(detached);
} else {
- x = Data::sharedNull();
- }
- if (d != x) {
- if (!d->ref.deref()) {
- if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) {
- // data was copy constructed, we need to call destructors
- // or if !alloc we did nothing to the old 'd'.
- freeData(d);
- } else {
- Data::deallocate(d);
- }
- }
- d = x;
- }
-
- Q_ASSERT(d->data());
- Q_ASSERT(uint(d->size) <= d->alloc);
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- Q_ASSERT(d != Data::unsharableEmpty());
-#endif
- Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull());
- Q_ASSERT(d->alloc >= uint(aalloc));
- Q_ASSERT(d->size == asize);
-}
-
-template<typename T>
-void QVector<T>::realloc(int aalloc, QArrayData::AllocationOptions options)
-{
- Q_ASSERT(aalloc >= d->size);
- Data *x = d;
-
- const bool isShared = d->ref.isShared();
-
- QT_TRY {
- // allocate memory
- x = Data::allocate(aalloc, options);
- Q_CHECK_PTR(x);
- // aalloc is bigger then 0 so it is not [un]sharedEmpty
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable));
-#endif
- Q_ASSERT(!x->ref.isStatic());
- x->size = d->size;
-
- T *srcBegin = d->begin();
- T *srcEnd = d->end();
- T *dst = x->begin();
-
- if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) {
- QT_TRY {
- if (isShared || !std::is_nothrow_move_constructible<T>::value) {
- // we can not move the data, we need to copy construct it
- while (srcBegin != srcEnd)
- new (dst++) T(*srcBegin++);
- } else {
- while (srcBegin != srcEnd)
- new (dst++) T(std::move(*srcBegin++));
- }
- } QT_CATCH (...) {
- // destruct already copied objects
- destruct(x->begin(), dst);
- QT_RETHROW;
- }
- } else {
- ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T));
- dst += srcEnd - srcBegin;
- }
-
- } QT_CATCH (...) {
- Data::deallocate(x);
- QT_RETHROW;
- }
- x->capacityReserved = d->capacityReserved;
-
- Q_ASSERT(d != x);
- if (!d->ref.deref()) {
- if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) {
- // data was copy constructed, we need to call destructors
- // or if !alloc we did nothing to the old 'd'.
- freeData(d);
+ // we're detached and we can just move data around
+ if (i == size()) {
+ d->copyAppend(n, t);
} else {
- Data::deallocate(d);
+ T copy(t);
+ d->insert(d.begin() + i, n, copy);
}
}
- d = x;
-
- Q_ASSERT(d->data());
- Q_ASSERT(uint(d->size) <= d->alloc);
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- Q_ASSERT(d != Data::unsharableEmpty());
-#endif
- Q_ASSERT(d != Data::sharedNull());
- Q_ASSERT(d->alloc >= uint(aalloc));
-}
-
-#if defined(Q_CC_MSVC)
-QT_WARNING_POP
-#endif
-
-template<typename T>
-Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const
-{
- if (uint(i) >= uint(d->size)) {
- return T();
- }
- return d->begin()[i];
-}
-template<typename T>
-Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const
-{
- return uint(i) >= uint(d->size) ? defaultValue : d->begin()[i];
-}
-
-template <typename T>
-void QVector<T>::append(const T &t)
-{
- const bool isTooSmall = uint(d->size + 1) > d->alloc;
- if (!isDetached() || isTooSmall) {
- T copy(t);
- QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
- realloc(isTooSmall ? d->size + 1 : d->alloc, opt);
-
- if (QTypeInfo<T>::isComplex)
- new (d->end()) T(std::move(copy));
- else
- *d->end() = std::move(copy);
-
- } else {
- if (QTypeInfo<T>::isComplex)
- new (d->end()) T(t);
- else
- *d->end() = t;
- }
- ++d->size;
+ return d.begin() + i;
}
template <typename T>
-void QVector<T>::append(T &&t)
+typename QVector<T>::iterator
+QVector<T>::insert(int i, rvalue_ref t)
{
- const bool isTooSmall = uint(d->size + 1) > d->alloc;
- if (!isDetached() || isTooSmall) {
- QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
- realloc(isTooSmall ? d->size + 1 : d->alloc, opt);
- }
-
- new (d->end()) T(std::move(t));
+ Q_ASSERT_X(size_t(i) <= size_t(d->size), "QVector<T>::insert", "index out of range");
- ++d->size;
-}
-
-template <typename T>
-void QVector<T>::removeLast()
-{
- Q_ASSERT(!isEmpty());
- Q_ASSERT(d->alloc);
-
- if (d->ref.isShared())
- detach();
- --d->size;
- if (QTypeInfo<T>::isComplex)
- (d->data() + d->size)->~T();
-}
-
-template <typename T>
-typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
-{
- Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid");
-
- const auto offset = std::distance(d->begin(), before);
- if (n != 0) {
- const T copy(t);
- if (!isDetached() || d->size + n > int(d->alloc))
- realloc(d->size + n, QArrayData::Grow);
- if (!QTypeInfoQuery<T>::isRelocatable) {
- T *b = d->end();
- T *i = d->end() + n;
- while (i != b)
- new (--i) T;
- i = d->end();
- T *j = i + n;
- b = d->begin() + offset;
- while (i != b)
- *--j = *--i;
- i = b+n;
- while (i != b)
- *--i = copy;
- } else {
- T *b = d->begin() + offset;
- T *i = b + n;
- memmove(static_cast<void *>(i), static_cast<const void *>(b), (d->size - offset) * sizeof(T));
- while (i != b)
- new (--i) T(copy);
- }
- d->size += n;
- }
- return d->begin() + offset;
-}
+ const size_t newSize = size() + 1;
+ if (d->needsDetach() || newSize > d->allocatedCapacity()) {
+ typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward;
+ if (size_t(i) <= newSize / 4)
+ flags |= Data::GrowsBackwards;
-template <typename T>
-typename QVector<T>::iterator QVector<T>::insert(iterator before, T &&t)
-{
- Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid");
-
- const auto offset = std::distance(d->begin(), before);
- if (!isDetached() || d->size + 1 > int(d->alloc))
- realloc(d->size + 1, QArrayData::Grow);
- if (!QTypeInfoQuery<T>::isRelocatable) {
- T *i = d->end();
- T *j = i + 1;
- T *b = d->begin() + offset;
- // The new end-element needs to be constructed, the rest must be move assigned
- if (i != b) {
- new (--j) T(std::move(*--i));
- while (i != b)
- *--j = std::move(*--i);
- *b = std::move(t);
- } else {
- new (b) T(std::move(t));
- }
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
+ const_iterator where = constBegin() + i;
+ detached->copyAppend(constBegin(), where);
+ detached->moveAppend(std::addressof(t), std::addressof(t) + 1);
+ detached->copyAppend(where, constEnd());
+ d.swap(detached);
} else {
- T *b = d->begin() + offset;
- memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (d->size - offset) * sizeof(T));
- new (b) T(std::move(t));
+ d->insert(d.begin() + i, std::move(t));
}
- d->size += 1;
- return d->begin() + offset;
+ return d.begin() + i;
}
template <typename T>
@@ -904,176 +620,102 @@ typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
{
Q_ASSERT_X(isValidIterator(abegin), "QVector::erase", "The specified iterator argument 'abegin' is invalid");
Q_ASSERT_X(isValidIterator(aend), "QVector::erase", "The specified iterator argument 'aend' is invalid");
+ Q_ASSERT(aend >= abegin);
- const auto itemsToErase = aend - abegin;
-
- if (!itemsToErase)
- return abegin;
-
- Q_ASSERT(abegin >= d->begin());
- Q_ASSERT(aend <= d->end());
- Q_ASSERT(abegin <= aend);
-
- const auto itemsUntouched = abegin - d->begin();
-
- // FIXME we could do a proper realloc, which copy constructs only needed data.
- // FIXME we are about to delete data - maybe it is good time to shrink?
- // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this.
- if (d->alloc) {
- detach();
- abegin = d->begin() + itemsUntouched;
- aend = abegin + itemsToErase;
- if (!QTypeInfoQuery<T>::isRelocatable) {
- iterator moveBegin = abegin + itemsToErase;
- iterator moveEnd = d->end();
- while (moveBegin != moveEnd) {
- if (QTypeInfo<T>::isComplex)
- static_cast<T *>(abegin)->~T();
- new (abegin++) T(*moveBegin++);
- }
- if (abegin < d->end()) {
- // destroy rest of instances
- destruct(abegin, d->end());
- }
- } else {
- destruct(abegin, aend);
- // QTBUG-53605: static_cast<void *> masks clang errors of the form
- // error: destination for this 'memmove' call is a pointer to class containing a dynamic class
- // FIXME maybe use std::is_polymorphic (as soon as allowed) to avoid the memmove
- memmove(static_cast<void *>(abegin), static_cast<void *>(aend),
- (d->size - itemsToErase - itemsUntouched) * sizeof(T));
- }
- d->size -= int(itemsToErase);
- }
- return d->begin() + itemsUntouched;
-}
-
-template <typename T>
-bool QVector<T>::operator==(const QVector<T> &v) const
-{
- if (d == v.d)
- return true;
- if (d->size != v.d->size)
- return false;
- const T *vb = v.d->begin();
- const T *b = d->begin();
- const T *e = d->end();
- return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(vb, v.d->size));
-}
+ // d.begin() so we don't detach just yet
+ int i = std::distance(d.begin(), abegin);
+ int n = std::distance(abegin, aend);
+ remove(i, n);
-template <typename T>
-QVector<T> &QVector<T>::fill(const T &from, int asize)
-{
- const T copy(from);
- resize(asize < 0 ? d->size : asize);
- if (d->size) {
- T *i = d->end();
- T *b = d->begin();
- while (i != b)
- *--i = copy;
- }
- return *this;
+ return d.begin() + i;
}
template <typename T>
-QVector<T> &QVector<T>::operator+=(const QVector &l)
+inline QVector<T> &QVector<T>::fill(parameter_type t, int newSize)
{
- if (d->size == 0) {
- *this = l;
+ if (newSize == -1)
+ newSize = size();
+ if (d->needsDetach() || newSize > capacity()) {
+ // must allocate memory
+ DataPointer detached(Data::allocate(d->detachCapacity(newSize),
+ d->detachFlags()));
+ detached->copyAppend(newSize, t);
+ d.swap(detached);
} else {
- uint newSize = d->size + l.d->size;
- const bool isTooSmall = newSize > d->alloc;
- if (!isDetached() || isTooSmall) {
- QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
- realloc(isTooSmall ? newSize : d->alloc, opt);
- }
-
- if (d->alloc) {
- T *w = d->begin() + newSize;
- T *i = l.d->end();
- T *b = l.d->begin();
- while (i != b) {
- if (QTypeInfo<T>::isComplex)
- new (--w) T(*--i);
- else
- *--w = *--i;
- }
- d->size = newSize;
- }
+ // we're detached
+ const T copy(t);
+ d->assign(d.begin(), d.begin() + qMin(size(), newSize), t);
+ if (newSize > size())
+ d->copyAppend(newSize - size(), copy);
}
return *this;
}
-template <typename T>
-int QVector<T>::indexOf(const T &t, int from) const
+namespace QtPrivate {
+template <typename T, typename U>
+int indexOf(const QVector<T> &vector, const U &u, int from)
{
if (from < 0)
- from = qMax(from + d->size, 0);
- if (from < d->size) {
- T* n = d->begin() + from - 1;
- T* e = d->end();
+ from = qMax(from + vector.size(), 0);
+ if (from < vector.size()) {
+ auto n = vector.begin() + from - 1;
+ auto e = vector.end();
while (++n != e)
- if (*n == t)
- return n - d->begin();
+ if (*n == u)
+ return n - vector.begin();
}
return -1;
}
-template <typename T>
-int QVector<T>::lastIndexOf(const T &t, int from) const
+template <typename T, typename U>
+int lastIndexOf(const QVector<T> &vector, const U &u, int from)
{
if (from < 0)
- from += d->size;
- else if (from >= d->size)
- from = d->size-1;
+ from += vector.d->size;
+ else if (from >= vector.size())
+ from = vector.size() - 1;
if (from >= 0) {
- T* b = d->begin();
- T* n = d->begin() + from + 1;
+ auto b = vector.begin();
+ auto n = vector.begin() + from + 1;
while (n != b) {
- if (*--n == t)
+ if (*--n == u)
return n - b;
}
}
return -1;
}
+}
template <typename T>
-bool QVector<T>::contains(const T &t) const
+int QVector<T>::indexOf(const T &t, int from) const noexcept
{
- const T *b = d->begin();
- const T *e = d->end();
- return std::find(b, e, t) != e;
+ return QtPrivate::indexOf<T, T>(*this, t, from);
}
template <typename T>
-int QVector<T>::count(const T &t) const
+int QVector<T>::lastIndexOf(const T &t, int from) const noexcept
{
- const T *b = d->begin();
- const T *e = d->end();
- return int(std::count(b, e, t));
+ return QtPrivate::lastIndexOf(*this, t, from);
}
template <typename T>
-Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int len) const
+inline QVector<T> QVector<T>::mid(int pos, int len) const
{
using namespace QtPrivate;
- switch (QContainerImplHelper::mid(d->size, &pos, &len)) {
+ switch (QContainerImplHelper::mid(d.size, &pos, &len)) {
case QContainerImplHelper::Null:
case QContainerImplHelper::Empty:
- return QVector<T>();
+ return QVector();
case QContainerImplHelper::Full:
return *this;
case QContainerImplHelper::Subset:
break;
}
- QVector<T> midResult;
- midResult.realloc(len);
- T *srcFrom = d->begin() + pos;
- T *srcTo = d->begin() + pos + len;
- midResult.copyConstruct(srcFrom, srcTo, midResult.data());
- midResult.d->size = len;
- return midResult;
+ // Allocate memory
+ DataPointer copied(Data::allocate(len));
+ copied->copyAppend(constBegin() + pos, constBegin() + pos + len);
+ return copied;
}
Q_DECLARE_SEQUENTIAL_ITERATOR(Vector)
@@ -1153,4 +795,7 @@ QVector<QStringRef> QStringRef::split(QChar sep, Qt::SplitBehavior behavior, Qt:
QT_END_NAMESPACE
+#include <QtCore/qbytearraylist.h>
+#include <QtCore/qstringlist.h>
+
#endif // QVECTOR_H
diff --git a/src/corelib/tools/qvector_msvc.cpp b/src/corelib/tools/qvector_msvc.cpp
index cee343e72b..7e87467d42 100644
--- a/src/corelib/tools/qvector_msvc.cpp
+++ b/src/corelib/tools/qvector_msvc.cpp
@@ -47,12 +47,5 @@
# error "This file must be compiled with no precompiled headers"
#endif
-// invert the setting of QT_STRICT_ITERATORS, whichever it was
-#ifdef QT_STRICT_ITERATORS
-# undef QT_STRICT_ITERATORS
-#else
-# define QT_STRICT_ITERATORS
-#endif
-
// the Q_TEMPLATE_EXTERN at the bottom of qvector.h will do the trick
#include <QtCore/qvector.h>
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index 40c84157cd..230456bef9 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -12,6 +12,7 @@ HEADERS += \
tools/qcontainerfwd.h \
tools/qcontainertools_impl.h \
tools/qcryptographichash.h \
+ tools/qflatmap_p.h \
tools/qfreelist_p.h \
tools/qhash.h \
tools/qhashfunctions.h \
@@ -47,7 +48,6 @@ HEADERS += \
tools/qvector.h \
tools/qversionnumber.h
-
SOURCES += \
tools/qarraydata.cpp \
tools/qbitarray.cpp \
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-01 04:46:36 +0000