Sorting a series of QLists into the same order

[mobucl]

Hi, i have a series of QLists (1,2,3,4 etc) with float values all in a random order. They are all of the same length. Now i then use:


qSort(list1.begin(), list1.end());

to sort list1 into ascending order. OK but how can i sort all the other lists based on the order of this list? E.g. if list1[0] is moved to list1[10] during sorting i want the same thing to occur with all other lists no matter what their values.

Thanks for your help

Matt

[Zlatomir]

The simplest solution is to create a struct (class) with 4 float members, create the QList<Your_Class> and sort it depending on what member you need.
But off course this might not "fit" your problem well, so provide more information on what you are trying to achieve.

[wysota]

Create another list that will represent your items order (let's call it "order"). Have it contain elements from 0 to n-1 in sequence (where n is the size of your list1). Then sort that list according to the desired order of items in "list1" (you'll probably need to implement your own lessThan functor for this). You'll receive a list where order[i] represents an index of an element that should occupy position "i". Then loop through all your lists and rearrange their items according to the order of items from "order".

Added after 22 minutes:

Here is a sample implementation:

#include <QtCore>

struct Elem {
Elem(int p, int v) { pos = p; val = v; }
int pos;
int val;
};

bool myLessThan(const Elem& e1, const Elem &e2){
return (e1.val < e2.val);
}

int main(int argc, char **argv) {
QList<int> random;
QList<Elem> order;
QList<int> other;
for(int i=0;i<10;++i){
random.push_back(qrand()%100);
order.push_back(Elem(i,random.at(i)));
other.push_back(qrand()%100);
}
qStableSort(order.begin(), order.end(), myLessThan);
QList<int> sorted;
for(int i=0;i<other.size();++i){
sorted.push_back(other.at(order.at(i).pos));
}
qDebug() << "R:" << random;
qDebug() << "O:" << other;
qDebug() << "S:" << sorted;
}

Result:
R: (13, 8, 77, 38, 91, 66, 69, 91, 61, 30)
O: (7, 91, 99, 63, 92, 7, 8, 39, 43, 61)
S: (91, 7, 61, 63, 43, 7, 8, 99, 92, 39)

[mobucl]

hi Zlatomir and wysota,

Thanks for your input - i will take a look at this and get back to you if i need any more information!

Many thanks

Matt

[mobucl]

Hi wysota,

Ok so i can get your example to work fine so i now want to create a class based around this (please bear in mind im quite new to c++ and learning as i go so sorry if this is a simple thing i should know the answer too!) SO here is my order.h file:


#ifndef ORDER_H
#define ORDER_H
#include<QList>

class Order
{
struct Elem {
Elem(int p, float v) { pos = p; val = v; }
int pos;
float val;
};
public:
QList<Elem> MainOrder;
Order(QList<float>);
QList<float> Sort(QList<float> ToSort);
};

#endif // ORDER_H

and here is my order.cpp file:


#include "order.h"
#include <QtCore/QCoreApplication>

// initialise the class by providing a list which is then sorted
Order::Order(QList<float> in)
{
for(int i=0;i<in.length();++i)
{
MainOrder.push_back(Elem(i,in.at(i)));
}
// qStableSort(MainOrder.begin(), MainOrder.end(), myLessThan);
}


//supply another list to the class which is to be sorted based on MainOrder
QList<float> Order::Sort(QList<float> ToSort)
{
QList<float> SortedData;
for(int i=0;i<MainOrder.size();++i)
{
SortedData.push_back(ToSort.at(MainOrder.at(i).pos ));
}
return (SortedData);
}

So the problem is that the code seems to work correctly when a new instance of the class is created and it appears that MainOrder fills with the desired data, however i cannot use the line


qStableSort(MainOrder.begin(), MainOrder.end(), myLessThan);

as no matter where i put the bool myLessThan function you described below i get (various depending on location) errors.....so can you please explain where im supposed to put this function to get that line to work!!!!! Ive tried everyting i can think of!

Thanks for your time,

Matt

[wysota]

Put it in order.cpp somewhere before the first method that calls this function.

[mobucl]

Hi wysota, if i added the bool function after the includes in the cpp file i get:

error: ISO C++ forbids declaration of 'Elem' with no type

so even though i have the structure Elem defined in the order.h file i guessed i needed it here also. So i then added this above the bool function. now when i compile i dont get an error which is great BUT as soon as i add the:


qStableSort(MainOrder.begin(), MainOrder.end(), myLessThan);

Line get loads of problems:

In file included from ..\..\..\qt\include/QtCore/qalgorithms.h:1,
from ..\..\..\qt\include\QtCore/../../src/corelib/tools/qlist.h:47,
from ..\..\..\qt\include\QtCore/qlist.h:1,
from ..\..\..\qt\include\QtCore/QList:1,
from ..\attempt1\/order.h:3,
from ..\attempt1\order.cpp:1:

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h: In function 'void QAlgorithmsPrivate::qMerge(RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = const Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]':

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:459: instantiated from 'void QAlgorithmsPrivate::qStableSortHelper(RandomAccess Iterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:212: instantiated from 'void qStableSort(RandomAccessIterator, RandomAccessIterator, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, LessThan = bool (*)(const Elem&, const Elem&)]'

..\attempt1\order.cpp:21: instantiated from here

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:424: error: invalid initialization of reference of type 'const Elem&' from expression of type 'Order::Elem'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h: In function 'RandomAccessIterator QAlgorithmsPrivate::qLowerBoundHelper(RandomAccess Iterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]':

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:252: instantiated from 'RandomAccessIterator qLowerBound(RandomAccessIterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:435: instantiated from 'void QAlgorithmsPrivate::qMerge(RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = const Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:459: instantiated from 'void QAlgorithmsPrivate::qStableSortHelper(RandomAccess Iterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:212: instantiated from 'void qStableSort(RandomAccessIterator, RandomAccessIterator, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, LessThan = bool (*)(const Elem&, const Elem&)]'

..\attempt1\order.cpp:21: instantiated from here

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:478: error: invalid initialization of reference of type 'const Elem&' from expression of type 'Order::Elem'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h: In function 'RandomAccessIterator QAlgorithmsPrivate::qUpperBoundHelper(RandomAccess Iterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]':

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:285: instantiated from 'RandomAccessIterator qUpperBound(RandomAccessIterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:440: instantiated from 'void QAlgorithmsPrivate::qMerge(RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = const Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:459: instantiated from 'void QAlgorithmsPrivate::qStableSortHelper(RandomAccess Iterator, RandomAccessIterator, const T&, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, T = Order::Elem, LessThan = bool (*)(const Elem&, const Elem&)]'

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:212: instantiated from 'void qStableSort(RandomAccessIterator, RandomAccessIterator, LessThan) [with RandomAccessIterator = QList<Order::Elem>::iterator, LessThan = bool (*)(const Elem&, const Elem&)]'

..\attempt1\order.cpp:21: instantiated from here

..\..\..\qt\include/QtCore/../../src/corelib/tools/qalgorithms.h:499: error: invalid initialization of reference of type 'const Elem&' from expression of type 'const Order::Elem'

mingw32-make[1]: *** [debug/order.o] Error 1
mingw32-make: *** [debug] Error 2

The .h file is the same as described previously and the new cpp file looks like this now:


#include "order.h"
#include <QtCore/QCoreApplication>

struct Elem {
Elem(int p, float v) { pos = p; val = v; }
int pos;
float val;
};

bool myLessThan(const Elem& e1, const Elem &e2){
return (e1.val < e2.val);
}

// initialise the class by providing a list which is then sorted
Order::Order(QList<float> in)
{
for(int i=0;i<in.length();++i)
{
MainOrder.push_back(Elem(i,in.at(i)));
}
qStableSort(MainOrder.begin(), MainOrder.end(), myLessThan);
}


//supply another list to the class which is to be sorted based on MainOrder
QList<float> Order::Sort(QList<float> ToSort)
{
QList<float> SortedData;
for(int i=0;i<MainOrder.size();++i)
{
SortedData.push_back(ToSort.at(MainOrder.at(i).pos ));
}
return (SortedData);
}

Is there anything else you can suggest. Thanks alot for your continued help!

[wysota]

You don't have a struct Elem. You have a struct Order::Elem, that's two completely different things.

[mobucl]

Ok now i see the problem! Thanks for all your help, the code is working as expected now!