Remove duplicate object from QList

Question

I have a QList<MyData>, where MyData have 2 member, int id (unique) and QString name. I want to remove all duplicate entries based on name, and that entry must the highest id between other object that having the same name. Any suggestion of how to doing it in the fastest way? Performance is a very important factor here.

Some of my idea after Google-ed for the whole day:

• qStableSort() it based on id (descending), then loop through the QList, then for each entry, copy the entry to another new QList when the name is not exist on the new QList
• use QList::toSet (which remove all duplicate entry), and provide operator==() and a qHash() implementation based on name, but the unique entry may not have the highest id
• use std::list::unique, but I'm not sure how it works.

Answer 1

std::list::unique can take as argument a function with the following properties:

Binary predicate that, taking two values of the same type than those contained in the list, returns true to remove the element passed as first argument from the container, and false otherwise. This shall be a function pointer or a function object.

So in your case you could use the folllowing function:

bool shouldRemove(MyData first, MyData second)
{
    // remove only if they have the same name and the first id
    // is smaller than the second one 
    return ( first.name == second.name && 
             first.id <= second.id ); 
}

To call it simply do,

std::list<MyData> myList = qlist.toStdList();
myList.unique(shouldRemove)

Notice that you need to sort first the std::list

Edit

It seems that you can use std::unique with Qt containers (if Qt is built with STL support). So in this case you could do the following:

// lessThan is a function that sorts first by name and then by id
qSort(qList.begin(), qList.end(), lessThan );
QList<MyData>::iterator it = std::unique (qList.begin(), qList.end(), shouldRemove);
qList.erase(it, qList.end());