Qt 6: Move QList contents without copying?

Axel Spoerl

@CJha
There is no general answer to this question, because the exact behavior of std::move()depends on the compiler. In general terms it just tells the compiler, that the buffer originally used by the moved object (the list) is no longer reserved. Allowing others to play in that garden, doesn't mean that anybody is actually interested or has the need to play there.
The behavior of QListis documented here. In a nut shell: It works with shallow copies to the extent possible and sensible. No deep copies are created as long as elements are accessed read-only.

Having said that, the probable answer is: What is still shown as an object, is ready to be re-used and plundered.

If it's necessary to be completely sure that nothing's copied, a QList of pointers to heap-allocated objects is maybe an alternative. A qDeleteAll(myList) in a class destructor is a handy tool in that case.

JonB

@Axel-Spoerl
Hi Axel :) An observation from me. Since Qt6 decided in its wisdom to make QLists "QList stores its items in an array of continuous memory." so that they are arrays/vectors, by definition one cannot avoid copying when appending one list to another, unlike with a traditional or linked list. (I don't think Qt's implicit sharing helps here, even if the new list is not written to?)

I am talking about copying for the QList elements themselves. This may indeed be a shallow copy if for example the elements are pointers to objects.

Although you say

If it's necessary to be completely sure that nothing's copied, a QList of pointers to heap-allocated objects is maybe an alternative.

the OP should be aware that this does not "copy *nothing"". So for example if you want to append a QList with a million items to one with a single item the million items are going to have to be copied, even if that's just a million pointers to copy.... So QList might not be the best choice for such a requirement. Am I right?

Axel Spoerl

@JonB Hi Jon :-) You are (as always) right! It really depends on the use case, but the one you described is certainly not, what the inventors of QList had in mind.

JonB

@Axel-Spoerl
I know, I just wish they left vectors as vectors and lists as lists! Doubtless they gain efficiency/space in many/most cases,. But they even removed QLinkedList and say go use std::list() for that instead!

Axel Spoerl

@JonB
I hear you! It wasn't me, but I know who it was and who approved it!

CJha

@JonB QList does have an append overload for moving:

void QList::append(QList<T> &&value)
This is an overloaded function.
Moves the items of the value list to the end of this list.
This function was introduced in Qt 6.0.

Technically, it should not copy but rather move and append the value from the passed list to fullList. Why is this not doing that?

JonB

@CJha
I don't know since I have never used Qt 6.

Depends what you/they mean by "move" versus "copy". I stick by my claim/understanding that since QList elements are now contiguous like an array/vector it must "copy" the elements to the destination list to make it so. The only difference is that it could invalidate the passed-in source list.

I do not know how QList<T> might work with std::move(). I do not know whether it might leave list in an "unspecified state". Did you try, say, fullList.append(list); just to seen what happens to list after this case?

This is the limit of my knowledge/guesswork! You probably need a QT + std expert to help you further :)

jsulm

@JonB No it does not have to copy if using std::move. As far as I know Qt container use heap allocated memory with a pointer for the actual data. Then using std::move it is enough to assign the pointer to the data in the destination container and set it to nullptr in the source container.

CJha

@JonB Thanks. Yes, I did try multiple cases, here are few important ones

fullList.append(list); // copies and appends the data from list to fullList but list itself is not changed

fullList.append(std::move(list)); // same as above

fullList = std::move(list); // moves the data from list to fullList, the list is empty but in defined state after this move

It seems that it is only moving the data from list to fullList when the data is being assigned using = std::move() in all other cases it leaves the data in list as it was.

JonB

@jsulm said in Qt 6: Move QList contents without copying?:

@JonB No it does not have to copy if using std::move. As far as I know Qt container use heap allocated memory with a pointer for the actual data. Then using std::move it is enough to assign the pointer to the data in the destination container and set it to nullptr in the source container.

Have you read what I wrote above about Qt6 and contiguous element allocation? What you write would indeed be the case for QList::QList(const QList<T> &other) constructor. However the user is asking about QList::append(QList<T> &&value) method introduced at Qt 6.0, that's the whole point. Could you explain how it could append a list to an existing list without having to copy the elements onto the existing list while still maintaining contiguous memory like an array/vector? I welcome your input :)

jsulm

@JonB Sorry, you're of course right about append!

Christian Ehrlicher

@JonB said in Qt 6: Move QList contents without copying?:

Could you explain how it could append a list to an existing list without having to copy the elements onto the existing list while still maintaining contiguous memory like an array/vector? I welcome your input :)

It moves the data from memory a to memory b. It's just not a copy but a move operation. Nothing more.

void addList(QList<T>& list) { fullList.append(std::move(list)); }

How should this be moved at all when list is a const ref? You can move a const object...

JonB

@Christian-Ehrlicher said in Qt 6: Move QList contents without copying?:

It moves the data from memory a to memory b. It's just not a copy but a move operation. Nothing more.

For this purpose I am calling that "copy" because (does it not?) have to copy the elements (in the QList, not what they might point to) from memory area a to area b? Certainly if iterates that is O(n), I don't know whether you mean CPUs have an instruction to do that fast instead? Think about if it appends a list of 1,000,000 items to an existing list of one item. Moving and appending a list (like a linked list) could be made an O(1) operation, but not with the vector implementation of Qt6 QList, that is my point. I think of "copy" for O(n), "move" to me implies O(1) (hopefully). Is this not correct?

Christian Ehrlicher

@JonB Don't look on the QList but it's contents. The content is moved but not copied - so the move ctor is called and not the copy ctor.

JonB

@Christian-Ehrlicher said in Qt 6: Move QList contents without copying?:

so the move ctor is called and not the copy ctor.

I never suggested otherwise. My question/answer at least is based on my assumption that the implementation in move constructor will be O(n) and not O(1) at Qt6 QList which requires contiguous memory. Which is what I would care about (at least as part of the whole) if I were asking the OP's question.

Christian Ehrlicher

@JonB said in Qt 6: Move QList contents without copying?:

Which is what I would care about (at least as part of the whole) if I were asking the OP's question.

~~But even then a move would be faster than (or equal if QList contains a pod) a copy. But the complexity stays, yes. But as I said - it can't work the way it is written.~~

JonB

@Christian-Ehrlicher said in Qt 6: Move QList contents without copying?:

But the complexity stays, yes.

OK.

@Christian-Ehrlicher said in Qt 6: Move QList contents without copying?:

How should this be moved at all when list is a const ref? You can move a const object...

@Christian-Ehrlicher said in Qt 6: Move QList contents without copying?:

But as I said - it can't work the way it is written.

Sorry, don't know about others but I'm not understanding where " list is a const ref" here, where is the const? Please be gentle in your answer ;-)
[Also, did you mean "You can move a const object..." or did you mean "can't"?]

Christian Ehrlicher

@JonB said in Qt 6: Move QList contents without copying?:

list is a const ref" here, where is the const? Please be gentle in your answer ;-)

void addList(QList<T>& list) { fullList.append(std::move(list)); }

~~list is const - so nothing to move here.~~

Christian Ehrlicher

Here I somehow was in the wrong path... sorry for the noise:

class CopyMoveTest
{
public:
  CopyMoveTest() { std::cout << "CopyMoveTest: plain ctor\n"; }
  CopyMoveTest(const CopyMoveTest &) { std::cout << "CopyMoveTest: copy ctor\n"; }
  CopyMoveTest(CopyMoveTest &&) { std::cout << "CopyMoveTest: move ctor\n"; }

  CopyMoveTest operator=(const CopyMoveTest &) { std::cout << "CopyMoveTest: copy operator\n"; return *this; }
  CopyMoveTest operator=(const CopyMoveTest &&) { std::cout << "CopyMoveTest: move operator\n"; return *this; }
};

void refCopy(CopyMoveTest &in)
{
  CopyMoveTest c(in);
}

void rValueRefCopy(CopyMoveTest &&in)
{
  CopyMoveTest c(in);
}

void refMove(CopyMoveTest &in)
{
  CopyMoveTest c(std::move(in));
}

void rValueRefMove(CopyMoveTest &&in)
{
  CopyMoveTest c(std::move(in));
}

int main(int , char **)
{
  CopyMoveTest a;
  std::cout << "\nref source copy\n";
  refCopy(a);
  std::cout << "\nref source move\n";
  refMove(a);
  std::cout << "\nrvalue ref source copy\n";
  rValueRefCopy(std::move(a));
  std::cout << "\nrvalue ref source move\n";
  rValueRefMove(std::move(a));
}

-->
CopyMoveTest: plain ctor

ref source copy
CopyMoveTest: copy ctor

ref source move
CopyMoveTest: move ctor

rvalue ref source copy
CopyMoveTest: copy ctor

rvalue ref source move
CopyMoveTest: move ctor

SimonSchroeder

@JonB said in Qt 6: Move QList contents without copying?:

Think about if it appends a list of 1,000,000 items to an existing list of one item. Moving and appending a list (like a linked list) could be made an O(1) operation

Well, you are right about that. However, I would expect that something would be done with the data afterwards. Iterating over the elements of a linked list and the elements of a vector is both O(n). Still, in the general case a vector will be faster because of consecutive memory whereas a list might have many cache misses. If iteration is done more than once the vector might be faster (after copying 1,000,000 items). It is a very tricky problem.