4

私には がありQList<MyData>、MyData2 つのメンバーint id(一意) とがありQString nameます。に基づいてすべての重複エントリを削除したいのですが、そのエントリは、同じ を持つ他のオブジェクト間nameで最も高くなければなりません。最速の方法でそれを行う方法の提案はありますか? ここでは、パフォーマンスが非常に重要な要素です。idname

一日中 Google で編集した後の私のアイデアの一部:

  • qStableSort()ID に基づいて (降順)、 をループし、エントリごとに、エントリが新しいエントリに存在しない場合はQList別の新しいエントリにコピーします。QListnameQList
  • を使用QList::toSet(すべての重複エントリを削除) し、operator==() と qHash() に基づく実装を提供しますnameが、一意のエントリは最高の ID を持っていない可能性があります
  • を使用しますstd::list::uniqueが、どのように機能するかわかりません。
4

3 に答える 3

5

std::list::unique次のプロパティを持つ関数を引数として取ることができます。

リストに含まれる値と同じ型の 2 つの値を取り、最初の引数として渡された要素をコンテナーから削除する場合は 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

編集

（STLサポートでビルドされている場合）std::uniqueで使用できるようです。したがって、この場合、次のことができます。Qt containersQt

// 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ん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 に答える