Sorting a QVector

[jiveaxe]

Hi,
I have created a vector of structs like this:

struct Review {
	QString title;
	QString page;
};

struct Review {
	QString title;
	QString page;
};

To copy to clipboard, switch view to plain text mode 

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;
			}
		}
	}
}

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;
			}
		}
	}
}

To copy to clipboard, switch view to plain text mode 

and call it with this statement:

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

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

To copy to clipboard, switch view to plain text mode 

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

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

To copy to clipboard, switch view to plain text mode 

Thanks

[Michiel]

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;

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;

To copy to clipboard, switch view to plain text mode 

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.

[jiveaxe]

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]

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]

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;

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

To copy to clipboard, switch view to plain text mode 

And, well, you can also just use the standard C++ swap() or the Qt qSwap() function. (They're identical. One wonders why Qt has its own version.)

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

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

To copy to clipboard, switch view to plain text mode 

[wysota]

Hi,
I have created a vector of structs like this:

struct Review {
	QString title;
	QString page;
};

struct Review {
	QString title;
	QString page;
};

To copy to clipboard, switch view to plain text mode 

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);
  }
};

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

To copy to clipboard, switch view to plain text mode 

and then:

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

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

To copy to clipboard, switch view to plain text mode 

[wysota]

And, well, you can also just use the standard C++ swap() or the Qt 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]

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]

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;
}

template <typename T>
inline void qSwap(T &value1, T &value2)
{
    T t = value1;
    value1 = value2;
    value2 = t;
}

To copy to clipboard, switch view to plain text mode 

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]

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;
}

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

To copy to clipboard, switch view to plain text mode 

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]

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]

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]

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]

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/qtgl...CLARE_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]

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:perator=() to intervene.

Regards

[Michiel]

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]

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]

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;
    }
}

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;
    }
}

To copy to clipboard, switch view to plain text mode 

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]

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]

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?