45 #include <QtCore/qiterator.h> 46 #include <QtCore/qatomic.h> 47 #include <QtCore/qalgorithms.h> 53 #ifdef Q_COMPILER_INITIALIZER_LISTS 55 #include <initializer_list> 68 template <
typename T>
class QVector;
69 template <
typename T>
class QSet;
74 int alloc, begin,
end;
78 enum { DataHeaderSize =
sizeof(
Data) -
sizeof(
void *) };
80 Data *detach(
int alloc);
81 Data *detach_grow(
int *i,
int n);
85 void realloc(
int alloc);
88 void **erase(
void **xi);
96 void remove(
int i,
int n);
97 void move(
int from,
int to);
105 template <
typename T>
109 #if defined(Q_CC_BOR) 125 #ifdef Q_COMPILER_RVALUE_REFS 127 {
qSwap(
d, other.d);
return *
this; }
130 #ifdef Q_COMPILER_INITIALIZER_LISTS 132 {
d->ref.ref();
qCopy(args.begin(), args.end(), std::back_inserter(*
this)); }
137 inline int size()
const {
return p.size(); }
139 inline void detach() {
if (
d->ref != 1) detach_helper(); }
149 inline void setSharable(
bool sharable) {
if (!sharable) detach();
d->sharable = sharable; }
152 inline bool isEmpty()
const {
return p.isEmpty(); }
156 const T &
at(
int i)
const;
157 const T &operator[](
int i)
const;
158 T &operator[](
int i);
160 void reserve(
int size);
161 void append(
const T &t);
163 void prepend(
const T &t);
164 void insert(
int i,
const T &t);
165 void replace(
int i,
const T &t);
166 void removeAt(
int i);
167 int removeAll(
const T &t);
168 bool removeOne(
const T &t);
172 void move(
int from,
int to);
173 void swap(
int i,
int j);
174 int indexOf(
const T &t,
int from = 0)
const;
175 int lastIndexOf(
const T &t,
int from = -1)
const;
176 QBool contains(
const T &t)
const;
177 int count(
const T &t)
const;
179 class const_iterator;
202 #ifndef QT_STRICT_ITERATORS 208 {
return i < other.
i; }
210 {
return i <= other.
i; }
212 {
return i > other.
i; }
214 {
return i >= other.
i; }
226 friend class iterator;
240 #ifdef QT_STRICT_ITERATORS 264 friend class const_iterator;
267 inline iterator
begin() { detach();
return reinterpret_cast<Node *
>(p.begin()); }
268 inline const_iterator
begin()
const {
return reinterpret_cast<Node *
>(p.begin()); }
269 inline const_iterator
constBegin()
const {
return reinterpret_cast<Node *
>(p.begin()); }
270 inline iterator
end() { detach();
return reinterpret_cast<Node *
>(p.end()); }
271 inline const_iterator
end()
const {
return reinterpret_cast<Node *
>(p.end()); }
272 inline const_iterator
constEnd()
const {
return reinterpret_cast<Node *
>(p.end()); }
273 iterator insert(iterator before,
const T &t);
274 iterator erase(iterator pos);
275 iterator erase(iterator first, iterator last);
280 inline int count()
const {
return p.size(); }
281 inline int length()
const {
return p.size(); }
290 QList<T> mid(
int pos,
int length = -1)
const;
292 T value(
int i)
const;
293 T value(
int i,
const T &defaultValue)
const;
298 inline T&
front() {
return first(); }
299 inline const T&
front()
const {
return first(); }
300 inline T&
back() {
return last(); }
301 inline const T&
back()
const {
return last(); }
314 inline QT3_SUPPORT iterator
remove(iterator pos) {
return erase(pos); }
315 inline QT3_SUPPORT
int remove(
const T &t) {
return removeAll(t); }
316 inline QT3_SUPPORT
int findIndex(
const T& t)
const {
return indexOf(t); }
317 inline QT3_SUPPORT iterator find(
const T& t)
318 {
int i = indexOf(t);
return (i == -1 ?
end() : (begin()+i)); }
319 inline QT3_SUPPORT const_iterator find (
const T& t)
const 320 {
int i = indexOf(t);
return (i == -1 ?
end() : (begin()+i)); }
321 inline QT3_SUPPORT iterator find(iterator from,
const T& t)
322 {
int i = indexOf(t, from - begin());
return i == -1 ?
end() : begin()+i; }
323 inline QT3_SUPPORT const_iterator find(const_iterator from,
const T& t)
const 324 {
int i = indexOf(t, from - begin());
return i == -1 ?
end() : begin()+i; }
330 {
QList n = *
this; n +=
l;
return n; }
332 { append(t);
return *
this; }
334 { append(t);
return *
this; }
336 { *
this +=
l;
return *
this; }
346 {
QList<T> tmp;
qCopy(list.begin(), list.end(), std::back_inserter(tmp));
return tmp; }
348 { std::list<T> tmp;
qCopy(constBegin(), constEnd(), std::back_inserter(tmp));
return tmp; }
352 Node *detach_helper_grow(
int i,
int n);
353 void detach_helper(
int alloc);
354 void detach_helper();
357 void node_construct(
Node *n,
const T &t);
358 void node_destruct(
Node *n);
360 void node_destruct(
Node *from,
Node *to);
363 #if defined(Q_CC_BOR) 364 template <
typename T>
369 template <
typename T>
374 #if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__) 378 else *
reinterpret_cast<T*
>(n) = t;
381 else ::memcpy(n, &t,
sizeof(T));
385 template <
typename T>
392 template <
typename T>
395 Node *current = from;
398 while(current != to) {
399 current->v =
new T(*reinterpret_cast<T*>(src->v));
404 while (current-- != from)
405 delete reinterpret_cast<T*
>(current->v);
411 while(current != to) {
412 new (current) T(*reinterpret_cast<T*>(src));
417 while (current-- != from)
418 (
reinterpret_cast<T*
>(current))->~T();
422 if (src != from && to - from > 0)
423 memcpy(from, src, (to - from) *
sizeof(
Node *));
427 template <
typename T>
431 while(from != to) --to,
delete reinterpret_cast<T*
>(to->v);
433 while (from != to) --to,
reinterpret_cast<T*
>(to)->~T();
436 template <
typename T>
450 template <
typename T>
453 int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin()));
454 Node *n =
reinterpret_cast<Node *
>(p.insert(iBefore));
456 node_construct(n, t);
463 template <
typename T>
465 { node_destruct(it.i);
466 return reinterpret_cast<Node *
>(p.erase(reinterpret_cast<void**>(it.i))); }
467 template <
typename T>
469 {
Q_ASSERT_X(i >= 0 && i < p.size(),
"QList<T>::at",
"index out of range");
470 return reinterpret_cast<Node *
>(p.at(i))->t(); }
471 template <
typename T>
473 {
Q_ASSERT_X(i >= 0 && i < p.size(),
"QList<T>::operator[]",
"index out of range");
474 return reinterpret_cast<Node *
>(p.at(i))->t(); }
475 template <
typename T>
477 {
Q_ASSERT_X(i >= 0 && i < p.size(),
"QList<T>::operator[]",
"index out of range");
478 detach();
return reinterpret_cast<Node *
>(p.at(i))->t(); }
479 template <
typename T>
481 {
if(i >= 0 && i < p.size()) { detach();
482 node_destruct(reinterpret_cast<Node *>(p.at(i))); p.remove(i); } }
483 template <
typename T>
485 {
Q_ASSERT_X(i >= 0 && i < p.size(),
"QList<T>::take",
"index out of range");
486 detach();
Node *n =
reinterpret_cast<Node *
>(p.at(i)); T t = n->t(); node_destruct(n);
487 p.remove(i);
return t; }
488 template <
typename T>
490 { T t = first(); removeFirst();
return t; }
491 template <
typename T>
493 { T t = last(); removeLast();
return t; }
495 template <
typename T>
498 if (
d->alloc < alloc) {
500 detach_helper(alloc);
506 template <
typename T>
512 node_construct(n, t);
519 Node *n =
reinterpret_cast<Node *
>(p.append());
521 node_construct(n, t);
528 node_construct(©, t);
530 n =
reinterpret_cast<Node *
>(p.append());;
532 node_destruct(©);
540 template <
typename T>
544 Node *n = detach_helper_grow(0, 1);
546 node_construct(n, t);
553 Node *n =
reinterpret_cast<Node *
>(p.prepend());
555 node_construct(n, t);
562 node_construct(©, t);
564 n =
reinterpret_cast<Node *
>(p.prepend());;
566 node_destruct(©);
574 template <
typename T>
578 Node *n = detach_helper_grow(i, 1);
580 node_construct(n, t);
587 Node *n =
reinterpret_cast<Node *
>(p.insert(i));
589 node_construct(n, t);
596 node_construct(©, t);
598 n =
reinterpret_cast<Node *
>(p.insert(i));;
600 node_destruct(©);
608 template <
typename T>
611 Q_ASSERT_X(i >= 0 && i < p.size(),
"QList<T>::replace",
"index out of range");
613 reinterpret_cast<Node *
>(p.at(i))->t() = t;
616 template <
typename T>
619 Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(),
620 "QList<T>::swap",
"index out of range");
622 void *t =
d->array[
d->begin + i];
623 d->array[
d->begin + i] =
d->array[
d->begin + j];
624 d->array[
d->begin + j] = t;
627 template <
typename T>
630 Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(),
631 "QList<T>::move",
"index out of range");
639 if (alength < 0 || pos + alength > size())
640 alength = size() - pos;
641 if (pos == 0 && alength == size())
647 cpy.
d->
end = alength;
650 reinterpret_cast<Node *>(cpy.
p.
end()),
651 reinterpret_cast<Node *>(p.begin() + pos));
663 if (i < 0 || i >= p.size()) {
666 return reinterpret_cast<Node *
>(p.at(i))->t();
672 return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t());
675 template <
typename T>
678 Node *n =
reinterpret_cast<Node *
>(p.begin());
681 node_copy(reinterpret_cast<Node *>(p.begin()),
682 reinterpret_cast<Node *>(p.begin() + i), n);
689 node_copy(reinterpret_cast<Node *>(p.begin() + i +
c),
690 reinterpret_cast<Node *>(p.end()), n + i);
692 node_destruct(reinterpret_cast<Node *>(p.begin()),
693 reinterpret_cast<Node *>(p.begin() + i));
702 return reinterpret_cast<Node *
>(p.begin() + i);
705 template <
typename T>
708 Node *n =
reinterpret_cast<Node *
>(p.begin());
711 node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
722 template <
typename T>
725 detach_helper(
d->alloc);
728 template <
typename T>
735 template <
typename T>
738 if (p.size() != l.
p.
size())
742 Node *i =
reinterpret_cast<Node *
>(p.end());
743 Node *b =
reinterpret_cast<Node *
>(p.begin());
747 if (!(i->t() == li->t()))
754 template <
typename T>
757 node_destruct(reinterpret_cast<Node *>(data->
array + data->
begin),
758 reinterpret_cast<Node *>(data->
array + data->
end));
763 template <
typename T>
769 template <
typename T>
772 int index = indexOf(_t);
779 Node *i =
reinterpret_cast<Node *
>(p.at(index));
780 Node *e =
reinterpret_cast<Node *
>(p.end());
790 int removedCount = e - n;
791 d->end -= removedCount;
795 template <
typename T>
798 int index = indexOf(_t);
806 template <
typename T>
810 for (
Node *n = afirst.
i; n < alast.
i; ++n)
812 int idx = afirst - begin();
813 p.remove(idx, alast - afirst);
814 return begin() + idx;
817 template <
typename T>
824 Node *n = (
d->ref != 1)
826 : reinterpret_cast<Node *>(p.append2(l.
p));
828 node_copy(n, reinterpret_cast<Node *>(p.end()),
829 reinterpret_cast<Node *>(l.
p.
begin()));
832 d->end -= int(reinterpret_cast<Node *>(p.end()) - n);
840 template <
typename T>
846 template <
typename T>
850 from =
qMax(from + p.size(), 0);
851 if (from < p.size()) {
852 Node *n =
reinterpret_cast<Node *
>(p.at(from -1));
853 Node *e =
reinterpret_cast<Node *
>(p.end());
856 return int(n - reinterpret_cast<Node *>(p.begin()));
861 template <
typename T>
866 else if (from >= p.size())
869 Node *b =
reinterpret_cast<Node *
>(p.begin());
870 Node *n =
reinterpret_cast<Node *
>(p.at(from + 1));
879 template <
typename T>
882 Node *b =
reinterpret_cast<Node *
>(p.begin());
883 Node *i =
reinterpret_cast<Node *
>(p.end());
890 template <
typename T>
894 Node *b =
reinterpret_cast<Node *
>(p.begin());
895 Node *i =
reinterpret_cast<Node *
>(p.end());
const T & back() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool operator<(const const_iterator &other) const
void push_front(const T &t)
This function is provided for STL compatibility.
iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
const T & operator[](int i) const
Same as at().
void push_back(const T &t)
This function is provided for STL compatibility.
QList< T > & operator+=(const T &t)
Appends value to the list.
T & operator[](int j) const
Returns a modifiable reference to the item at position *this + {j}.
bool operator<=(const const_iterator &other) const
Returns true if the item pointed to by this iterator is less than or equal to the item pointed to by ...
#define QT_END_NAMESPACE
This macro expands to.
QList(const QList< T > &l)
Constructs a copy of other.
#define it(className, varName)
void free(QListData::Data *d)
Q_INLINE_TEMPLATE T & t()
Q_CORE_EXPORT void qFree(void *ptr)
#define at(className, varName)
bool operator<(const const_iterator &other) const
Returns true if the item pointed to by this iterator is less than the item pointed to by the other it...
bool empty() const
This function is provided for STL compatibility.
const_iterator & operator-=(int j)
Makes the iterator go back by j items.
bool operator<(const iterator &other) const
Returns true if the item pointed to by this iterator is less than the item pointed to by the other it...
static void clear(QVariant::Private *d)
iterator begin()
Returns an STL-style iterator pointing to the first item in the list.
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the list.
const T & front() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
The QList::const_iterator class provides an STL-style const iterator for QList and QQueue...
void insert(int i, const T &t)
Inserts value at index position i in the list.
void removeLast()
Removes the last item in the list.
QList< T > operator+(const QList< T > &l) const
Returns a list that contains all the items in this list followed by all the items in the other list...
void pop_front()
This function is provided for STL compatibility.
bool operator!=(const QList< T > &l) const
Returns true if other is not equal to this list; otherwise returns false.
#define Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(C)
~QList()
Destroys the list.
bool operator>(const const_iterator &other) const
Returns true if the item pointed to by this iterator is greater than the item pointed to by the other...
const_iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
std::list< T > toStdList() const
Returns a std::list object with the data contained in this QList.
void node_destruct(Node *n)
iterator & operator++()
The prefix ++ operator (++it) advances the iterator to the next item in the list and returns an itera...
The QVector class is a template class that provides a dynamic array.
const_iterator(const const_iterator &o)
Constructs a copy of other.
T & operator*() const
Returns a modifiable reference to the current item.
const T & operator[](int j) const
Returns the item at position *this + {j}.
int operator-(iterator j) const
Returns the number of items between the item pointed to by other and the item pointed to by this iter...
T * operator->() const
Returns a pointer to the current item.
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
std::random_access_iterator_tag iterator_category
A synonym for {std::random_access_iterator_tag} indicating this iterator is a random access iterator...
iterator Iterator
Qt-style synonym for QList::iterator.
bool isEmpty() const
Returns true if the list contains no items; otherwise returns false.
QList< T > mid(int pos, int length=-1) const
Returns a list whose elements are copied from this list, starting at position pos.
bool operator!=(const const_iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
int size_type
Typedef for int.
bool operator>(const const_iterator &other) const
const_iterator end() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
iterator & operator+=(int j)
Advances the iterator by j items.
void move(int from, int to)
Moves the item at index position from to index position to.
bool removeOne(const T &t)
Removes the first occurrence of value in the list and returns true on success; otherwise returns fals...
const_iterator & operator--()
The prefix – operator (–it) makes the preceding item current and returns an iterator to the new cur...
void append(const T &t)
Inserts value at the end of the list.
bool operator<=(const const_iterator &other) const
#define QT_BEGIN_NAMESPACE
This macro expands to.
#define Q_DECLARE_SEQUENTIAL_ITERATOR(C)
T & front()
This function is provided for STL compatibility.
QBool contains(const T &t) const
Returns true if the list contains an occurrence of value; otherwise returns false.
static bool isEmpty(const char *str)
void pop_back()
This function is provided for STL compatibility.
const_iterator(const iterator &o)
Constructs a copy of other.
void detachShared()
This prevents needless mallocs, and makes QList more exception safe in case of cleanup work done in d...
int lastIndexOf(const T &t, int from=-1) const
Returns the index position of the last occurrence of value in the list, searching backward from index...
QIntegerForSizeof< void * >::Signed qptrdiff
T takeFirst()
Removes the first item in the list and returns it.
iterator(const iterator &o)
Constructs a copy of other.
T & back()
This function is provided for STL compatibility.
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the list...
void prepend(const T &t)
Inserts value at the beginning of the list.
const T & at(int i) const
Returns the item at index position i in the list.
bool endsWith(const T &t) const
Returns true if this list is not empty and its last item is equal to value; otherwise returns false...
const_iterator()
Constructs an uninitialized iterator.
#define Q_INLINE_TEMPLATE
static const char * data(const QByteArray &arr)
void removeFirst()
Removes the first item in the list.
bool operator>(const iterator &other) const
Returns true if the item pointed to by this iterator is greater than the item pointed to by the other...
static QList< T > fromStdList(const std::list< T > &list)
Returns a QList object with the data contained in list.
T value(int i) const
Returns the value at index position i in the list.
iterator operator++(int)
The postfix ++ operator (it++) advances the iterator to the next item in the list and returns an iter...
std::random_access_iterator_tag iterator_category
A synonym for {std::random_access_iterator_tag} indicating this iterator is a random access iterator...
bool operator==(const const_iterator &o) const
bool operator>=(const iterator &other) const
Returns true if the item pointed to by this iterator is greater than or equal to the item pointed to ...
void clear()
Removes all items from the list.
void replace(int i, const T &t)
Replaces the item at index position i with value.
iterator operator--(int)
The postfix – operator (it–) makes the preceding item current and returns an iterator to the previo...
QList< T > & operator+=(const QList< T > &l)
Appends the items of the other list to this list and returns a reference to this list.
QList< T > & operator=(const QList< T > &l)
Assigns other to this list and returns a reference to this list.
bool operator!=(const const_iterator &o) const
void qSwap(T &value1, T &value2)
iterator()
Constructs an uninitialized iterator.
The QList::iterator class provides an STL-style non-const iterator for QList and QQueue.
bool startsWith(const T &t) const
Returns true if this list is not empty and its first item is equal to value; otherwise returns false...
int operator-(const_iterator j) const
Returns the number of items between the item pointed to by other and the item pointed to by this iter...
const value_type & const_reference
Typedef for const T &.
T & first()
Returns a reference to the first item in the list.
qptrdiff difference_type
Typedef for ptrdiff_t.
const T & last() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
int count() const
Returns the number of items in the list.
iterator & operator--()
The prefix – operator (–it) makes the preceding item current and returns an iterator to the new cur...
bool operator>=(const const_iterator &other) const
#define Q_ASSERT_X(cond, where, what)
iterator erase(iterator pos)
Removes the item associated with the iterator pos from the list, and returns an iterator to the next ...
int indexOf(const T &t, int from=0) const
Returns the index position of the first occurrence of value in the list, searching forward from index...
void setSharable(bool sharable)
void node_copy(Node *from, Node *to, Node *src)
bool operator==(const QList< T > &l) const
Returns true if other is equal to this list; otherwise returns false.
const T & operator*() const
Returns the current item.
int length() const
This function is identical to count().
bool operator!=(const iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
const_iterator ConstIterator
Qt-style synonym for QList::const_iterator.
void node_construct(Node *n, const T &t)
T & last()
Returns a reference to the last item in the list.
int size() const
Returns the number of items in the list.
iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
bool operator<=(const iterator &other) const
Returns true if the item pointed to by this iterator is less than or equal to the item pointed to by ...
const value_type * const_pointer
Typedef for const T *.
T takeAt(int i)
Removes the item at index position i and returns it.
const_iterator operator++(int)
The postfix ++ operator (it++) advances the iterator to the next item in the list and returns an iter...
const T & first() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
QDataStream & operator<<(QDataStream &s, const QAxBase &c)
T takeLast()
Removes the last item in the list and returns it.
Node * detach_helper_grow(int i, int n)
OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
bool operator>=(const const_iterator &other) const
Returns true if the item pointed to by this iterator is greater than or equal to the item pointed to ...
const_iterator & operator++()
The prefix ++ operator (++it) advances the iterator to the next item in the list and returns an itera...
timeval & operator+=(timeval &t1, const timeval &t2)
iterator & operator-=(int j)
Makes the iterator go back by j items.
#define Q_OUTOFLINE_TEMPLATE
static const KeyPair *const end
const_iterator operator--(int)
The postfix – operator (it–) makes the preceding item current and returns an iterator to the previo...
bool operator==(QBool b1, bool b2)
const_iterator begin() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
void swap(QList< T > &other)
Swaps list other with this list.
T value_type
Typedef for T.
value_type & reference
Typedef for T &.
const T * operator->() const
Returns a pointer to the current item.
const_iterator & operator+=(int j)
Advances the iterator by j items.
void reserve(int size)
Reserve space for alloc elements.
bool isSharedWith(const QList< T > &other) const
QList()
Constructs an empty list.
bool operator==(const const_iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
bool operator==(const iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
The QList class is a template class that provides lists.
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the list...
const_iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
int removeAll(const T &t)
Removes all occurrences of value in the list and returns the number of entries removed.
value_type * pointer
Typedef for T *.
void removeAt(int i)
Removes the item at index position i.