4

我有一个QList<MyData>，其中MyData有 2 个成员，int id（唯一）和QString name. 我想删除所有基于的重复条目name，并且该条目必须在id具有相同的其他对象之间最高name。关于如何以最快的方式做到这一点的任何建议？性能在这里是一个非常重要的因素。

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

  • qStableSort()它基于 id （降序），然后遍历，然后对于每个条目，当新条目上不存在时QList，将条目复制到另一个新条目QListnameQList
  • 使用QList::toSet（删除所有重复条目），并提供 operator==() 和基于 的 qHash() 实现name，但唯一条目可能没有最高 id
  • 使用std::list::unique，但我不确定它是如何工作的。
4

3 回答 3

5

std::list::unique可以将具有以下属性的函数作为参数：

二进制谓词，采用与列表中包含的相同类型的两个值，返回 true 以从容器中删除作为第一个参数传递的元素，否则返回 false。这应该是一个函数指针或一个函数对象。

因此，在您的情况下，您可以使用以下功能：

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::uniquewith 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());
于 2013-01-14T13:56:48.140 回答
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-container 并返回，如果您找到一种方法来继续使用QMap而不是 a QList，您只需在初始时迭代一次列表。并且QHash会给你摊销O(1)的查找复杂性。

编辑：更改为QHash.

于 2013-01-14T14:29:16.570 回答
0

我通过 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

于 2013-01-14T14:33:16.913 回答