刪除QList中的重複對象

Question

我有QList<MyData>，其中MyData有2個成員，int id（唯一）和QString name。我想刪除基於name的所有重複條目，並且該條目必須在具有相同name的其他對象之間最高的id。任何建議如何以最快的方式做到這一點？性能是一個非常重要的因素。

我的一些想法的谷歌，編了一整天后：

• qStableSort()它基於ID（降序），然後依次通過QList，然後爲每個條目，該條目複製到另一個新QList當name沒有對新QList
• 使用QList::toSet存在（其刪除所有重複的條目），並提供運營商==（）和基於name一個qHash（）實現，但獨特的條目可能不具有最高的ID
• 使用std::list::unique，但我不確定它是如何工作的。

Answer 1

std::list::unique可以作爲自變量的函數具有以下屬性：

二進制謂詞，以相同類型的比包含在列表中的那些 的兩個值，返回true，以除去通過的元件如容器的第一個參數爲 ，否則爲false。 這應該是一個函數指針或函數對象。

所以你的情況，你可以使用folllowing功能：

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

要調用它簡單地做，

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

請注意，您必須先解決的std::list

編輯

看起來您可以使用std::unique和Qt containers（如果Qt使用STL支持構建）。因此，在這種情況下，你可以做到以下幾點：

// 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

如何：

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. 

這樣做的好處，在我的眼前：您不必到列表轉換爲std - 容器和後面，如果你找到一種方法繼續使用QMap而不是QList，你只需要在初始列表上迭代一次。而QHash會給你分期付款O(1)查找複雜度。

編輯：更改爲QHash。

Answer 3

我不希望這STL的容器，但我認爲這不是很難將其轉換爲Qt的容器

包括

#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