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

Answer 2

How about this:

QList<MyData> theList = ...;

QHash<QString, int> nameToIdMap;

for (const MyData& element : theList) {

    auto iter = nameToIdMap.find(element.name);
    if (iter != nameToIdMap.end() && iter.second > element.id) {
        // If item exists in map (name already occured) and the ID is 
        // bigger than in the current element, just skip the current element.
        continue;
    }

    // Otherwise, insert/overwrite it in the map.
    nameToIdMap[element.name] = element.id;
});

// nameToIdMap should now map unique names to highest IDs. If desired,
// you could copy it back into a new list by iterating over the map's entries
// and creating new MyData elements accordingly.

The advantage of this, in my eyes: You don't have to convert the list to a std-container and back, and if you find a way to continue working with the QMap instead of a QList, you will only have to iterate once over the initial list. And QHash will give you amortized O(1) lookup complexity.

Edit: Changed to QHash.

Answer 3

I did this by STL-containers, but I think it's not very hard to convert it to Qt-containers

include

#include <list>
#include <set>
#include <iostream>
#include <algorithm>

struct MyData {
    int id;
    std::string name;
};

struct MyDataSortComparator {
    bool operator()( const MyData & left, const MyData & right ) {
        if ( left.name < right.name ) {
            return true;
        }
        else if ( left.name > right.name ) {
            return false;
        }
        return left.id > right.id;
    }
};

struct MyDataSetComparator {
    bool operator()( const MyData & left, const MyData & right ) {
        return left.name < right.name;
    }
};


int main() {
    std::list< MyData > theList = {
        { 1, "Dickson" },
        { 2, "Dickson" },
        { 3, "Dickson" },
        { 2, "borisbn" },
        { 1, "borisbn" }
    };
    std::set< MyData, MyDataSetComparator > theSet;
    theList.sort( MyDataSortComparator() );
    std::for_each( theList.begin(), theList.end(), []( const MyData & data ) {
        std::cout << data.id << ", " << data.name << std::endl;
    } );
    std::for_each( theList.begin(), theList.end(), [&theSet]( const MyData & data ) {
        theSet.insert( data );
    } );
    std::cout << "-------------------" << std::endl;
    std::for_each( theSet.begin(), theSet.end(), []( const MyData & data ) {
        std::cout << data.id << ", " << data.name << std::endl;
    } );
}

http://liveworkspace.org/code/wOFnM$5