Удалить повторяющийся объект из QList

У меня есть QList<MyData>, где MyData есть 2 члена, int id (уникальный) и QString name. Я хочу удалить все повторяющиеся записи на основе name, и эта запись должна иметь наивысшее значение id между другими объектами, имеющими такое же name. Любое предложение о том, как сделать это самым быстрым способом? Производительность здесь очень важный фактор.

Некоторые из моих идей после гугления в течение всего дня:

  • qStableSort() он основан на идентификаторе (по убыванию), затем перебирает QList, затем для каждой записи копирует запись в другой новый QList, когда name не существует в новом QList
  • используйте QList::toSet (который удаляет все повторяющиеся записи) и предоставьте оператор ==() и реализацию qHash() на основе name, но уникальная запись может не иметь самый высокий идентификатор
  • используйте std::list::unique, но я не уверен, как это работает.

person Dickson    schedule 14.01.2013    source источник
comment
Использование стандартных функций библиотек C++ (либо std::list::unique, либо общей функции std::unique) означает, что вам необходимо скопировать данные в стандартный контейнер, а затем скопировать их обратно в файл QList.   -  person Some programmer dude    schedule 14.01.2013


Ответы (3)


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::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());
person pnezis    schedule 14.01.2013

Как насчет этого:

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.

person lethal-guitar    schedule 14.01.2013
comment
Это тоже хорошая идея, но я упустил 1 важный момент в своем вопросе: на самом деле у меня более 2 участников в MyData. Виноват :( - person Dickson; 14.01.2013
comment
Это не большая проблема: просто используйте QHash<QString, MyData>, а затем измените второе условие оператора if на: iter.second.id > element.id. Или, может быть, поместите MyData* в QHash, чтобы избежать копирования всех MyData. - person lethal-guitar; 14.01.2013
comment
+1: круто для синтаксиса! Я должен перейти на новый стандарт как можно скорее :-) - person Valentin Heinitz; 13.08.2013

Я сделал это с помощью 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

person borisbn    schedule 14.01.2013
comment
Вы уже используете лямбда-выражения — почему бы не для сортировки и сравнения наборов? - person lethal-guitar; 14.01.2013
comment
@lethal-guitar, я не люблю длинные лямбды, поэтому не использовал их в сортировке. С другой стороны, я не знаю, как использовать лямбда в определении множества. Не могли бы вы рассказать мне, как объявить theSet в моем примере с помощью лямбда? Спасибо - person borisbn; 14.01.2013
comment
Хорошо, по-видимому, это невозможно в определении набора.. очень плохо, мне нравится использовать лямбда-выражения для всего.. - person lethal-guitar; 14.01.2013