Удалить дубликат объекта из QList

Question

Удалить дубликат объекта из QList

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

Некоторые из моих идей после Google-ed на весь день:

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

3

c++list qlist qt

Решение

Другие решения

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

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,

2

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

0

Источник

Accepted Answer

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

5