PDA

View Full Version : Sorting a QVector



jiveaxe
9th August 2007, 15:41
Hi,
I have created a vector of structs like this:


struct Review {
QString title;
QString page;
};

I filled it with data from a database; now I need to sort alphabetically by title this vector; I made a bubbleSort function:


void MagazineWidget::bubbleSort(QVector<Review> vector)
{
bool swap = true;

for(int j = 0; swap; j++)
{
swap = false;
for(int k = vector.size()-1; k > j; k--)
{
if(vector.at(k).title < vector.at(k-1).title)
{
Review temp;
temp.title = vector.at(k).title;
temp.page = vector.at(k).page;
vector.at(k).title = vector.at(k-1).title;
vector.at(k).page = vector.at(k-1).page;
vector.at(k-1).title = temp.title;
vector.at(k-1).page = temp.page;
swap = true;
}
}
}
}

and call it with this statement:


QVector<Review> reviews;
// ...
// Filling the vector
// ...
bubbleSort(reviews);

During compilation I got the following error on lines 15-18:


error: passing ‘const QString’ as ‘this’ argument of ‘QString& QString::operator=(const QString&)’ discards qualifiers

Thanks

Michiel
9th August 2007, 16:10
QVector only has a const version of at(). In other words, you can't use QVector::at() as a left-hand value. Use the subscript operator:


vector[k].title = vector.at(k-1).title;
vector[k].page = vector.at(k-1).page;
vector[k-1].title = temp.title;
vector[k-1].page = temp.page;

Also, as it is now, your function only sorts a local copy. You have to pass the parameter by reference.

Also, Qt already has some sorting algorithms for you. Look at this one (http://doc.trolltech.com/qtopia4.2/qtalgorithms.html#qSort-2).

jiveaxe
9th August 2007, 16:22
Hi Michiel,
thank you for your post; i have corrected the function with your code and now works great; thanks also for mentioning qSort: now read the manual and give it a try.

Regards

pdima
10th August 2007, 20:45
Hi Michiel,
thank you for your post; i have corrected the function with your code and now works great; thanks also for mentioning qSort: now read the manual and give it a try.

Regards

Except of already implemented and tested sort implementation, qSort also gives you faster solution with O(n*log(n)) complexity instead of O(n*n) in your case.

Michiel
10th August 2007, 21:10
Yes, bubblesort is never used in serious applications. It is now mainly used for educational purposes.

Edit:

Another thing about your code (if you choose to keep it). You can shave off some lines of code by using struct assignment.


Review temp;
temp = vector.at(k);
vector[k] = vector.at(k-1);
vector[k-1] = temp;

And, well, you can also just use the standard C++ swap() or the Qt qSwap() (http://doc.trolltech.com/qtopia4.2/qtalgorithms.html#qSwap) function. (They're identical. One wonders why Qt has its own version.)


qSwap(vector[k], vector[k-1]);

wysota
10th August 2007, 22:59
Hi,
I have created a vector of structs like this:


struct Review {
QString title;
QString page;
};

I filled it with data from a database; now I need to sort alphabetically by title this vector; I made a bubbleSort function

How about:


struct Review {
QString title;
QString page;
bool operator<(const Review &other) const {
return (title < other.title);
}
};

and then:


QVector<Review> reviews;
//...
qSort(reviews);
// or std::sort(reviews.begin(), reviews.end());

wysota
10th August 2007, 23:01
And, well, you can also just use the standard C++ swap() or the Qt qSwap() (http://doc.trolltech.com/qtopia4.2/qtalgorithms.html#qSwap) function. (They're identical. One wonders why Qt has its own version.)

They are not identical. qSwap() is better than most swap() implementations.

Michiel
10th August 2007, 23:18
They are not identical. qSwap() is better than most swap() implementations.

Interesting. How (in)efficient can a swap function be? Does it swap at bit-level using xor or something?

marcel
10th August 2007, 23:40
Well, I don't know about its performance:


template <typename T>
inline void qSwap(T &value1, T &value2)
{
T t = value1;
value1 = value2;
value2 = t;
}
I think it is compiler dependent. It is up to the compiler to optimize this code.
Basically, there are 3 memcpy's, since that is what is going on.

Maybe a good compiler will optimize that using mmx, sse or whatever instruction sets are available.

Regards

wysota
10th August 2007, 23:47
Interesting. How (in)efficient can a swap function be? Does it swap at bit-level using xor or something?

The trivial implementation of swap is something like:


template< typename T> void swap(T& x, T& y){
T tmp = x;
x = y;
y = tmp;
}

Drawbacks:
- three operations
- uses assignment operator that can be quite complex (for example for trivial vector implementation)

qSwap() tries to be smarter, for instance it can detect if operator=() needs to be used or if it can use memcpy() or similar, thus it is faster for movable types.

Michiel
11th August 2007, 00:23
The trivial implementation of swap is something like:

I wasn't thinking of the trivial implementation. Because of exactly the drawbacks you describe.


qSwap() tries to be smarter, for instance it can detect if operator=() needs to be used or if it can use memcpy() or similar, thus it is faster for movable types.

operator=() should never be used for a swap operation. Why use deep copies if, after the function call, you still end up with exactly the same dynamic data? A shallow copy only moves the pointers around (and the primitive types). For the swap function this should be enough. And I'd be surprised if the standard C++ implementation did it differently.

Of course, this is only true for reasonable implementations of operator=(). But one can't assume that operator=() is going to be used in swap(). All that is required after the swap is that X behaves as Y did and Y behaves as X did.

marcel
11th August 2007, 00:38
operator=() should never be used for a swap operation. Why use deep copies if, after the function call, you still end up with exactly the same dynamic data? A shallow copy only moves the pointers around (and the primitive types). For the swap function this should be enough. And I'd be surprised if the standard C++ implementation did it differently.

But it will use the =() operator if the type T provides it(qSwap is a template function).
Otherwise it is just a memcpy over the destination.

Michiel
11th August 2007, 00:42
But it will use the =() operator if the type T provides it(qSwap is a template function).
Otherwise it is just a memcpy over the destination.

Exactly. And it should just be a memcpy. When would you want a swap function to use operator=()?

wysota
11th August 2007, 01:01
When you can't memcpy objects. And you can't memcpy most complex objects... As far as I understand the compiler will only "memcpy" PODs.

http://doc.trolltech.com/latest/qtglobal.html#Q_DECLARE_TYPEINFO
http://doc.trolltech.com/qq/qq19-containers.html (take a look at the paragraph mentioning Q_DECLARE_TYPEINFO)

And answering your question about wanting to use an assignment operator for swapping - for instance when you have a class that is to be used in multithreaded environment. Swaping using memcpy() and modifying the object from within another thread at the same time will break it completely. You have to use operator=() there to be certain you're blocking access with mutexes.

marcel
11th August 2007, 01:04
I can't imagine a reason right now.
However, even structure assignment is implemented in the language as member by member assignment.

So, in wysota's example above, no memcpy will occur(although it would work), but the two QString members will be assigned one by one, causing QString::operator=() to intervene.

Regards

Michiel
11th August 2007, 01:19
And answering your question about wanting to use an assignment operator for swapping - for instance when you have a class that is to be used in multithreaded environment. Swaping using memcpy() and modifying the object from within another thread at the same time will break it completely. You have to use operator=() there to be certain you're blocking access with mutexes.

Hm. Yes, I suppose that's true. However, if that is the only reason, deep copies are still being made when they don't have to. You could have a list with 100.000 values that must be copied twice in the name of thread safety.

If there is another way to isolate the swap operation, things could be much more efficient.

marcel
11th August 2007, 01:26
If there is another way to isolate the swap operation, things could be much more efficient.
If you are sure it is doable you can always implement your own using memcpy.



And answering your question about wanting to use an assignment operator for swapping - for instance when you have a class that is to be used in multithreaded environment. Swaping using memcpy() and modifying the object from within another thread at the same time will break it completely. You have to use operator=() there to be certain you're blocking access with mutexes.
How is qSwap thread safe?
You still have to put a lock on the mem locations you want to swap even with qSwap.
I don't mean about Qt classes that are already thread-safe, but a user class.
Would one trade performance over implementing locking in the operator=() and not in some other place?

wysota
11th August 2007, 09:13
Actually qSwap doesn't use memcpy directly (4.3 beta):

template <typename T>
inline void qSwap(T &value1, T &value2)
{
if (!QTypeInfo<T>::isComplex || QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
T t = value1;
value1 = value2;
value2 = t;
} else {
const void * const t = reinterpret_cast<const void * const &>(value1);
const_cast<const void *&>(reinterpret_cast<const void * const &>(value1)) =
reinterpret_cast<const void * const &>(value2);
const_cast<const void *&>(reinterpret_cast<const void * const &>(value2)) = t;
}
}

I admit I don't understand those spells with casting, but they look smart ;)

It's not that qSwap is thread safe, it's that you can use such classes with it. You have to care about locking your class on your own. It's a general assumption about using operator=(), not about swapping items.

Anyway we're highly offtopic here :) It doesn't really matter if you use qSwap or swap for sorting QVector.

marcel
11th August 2007, 11:39
Actually qSwap doesn't use memcpy directly (4.3 beta):

Weird enough. It must have remained a beta :).
I can't really find this implementation anywhere in 4.3.0 ( not beta ).

I even made small test and stepped in qSwap. The one I posted above is used for all types.

EDIT:
I think those casts only switch the base addresses of the variables without actually swapping any memory or calling =() operators.

Regards

arjunasd
11th August 2007, 18:25
Hi all

I am trying to sort a QList. I am using a custom type with overloaded < operator but then to check out the source of error, I changed the list to a interger one.

My code now is just this:

QList<int> list;
list << 10 << 5 << 4;
qsort(list.begin(), list.end());


I am getting the following error.

Cannot convert QList<int>::iterator to void* argument for '1' to 'void qsort(void* ,size_t, size_t, int (*) (const void*, const void*))'

Can anyone suggest what would be the possible error?

marcel
11th August 2007, 18:47
It is qSort, with capital "S".

Or, if not, try:


qSort(list.begin(), list.end(), qLess<int>());


Regards

wysota
11th August 2007, 20:24
You can also simply call "qSort(list)" if you want to sort the whole list.