0xd34df00d
29.09.2012 16:15 Azoth_primary
Почему кути такое дельфятное? Почему они не пишут оценку сложности для QList::removeDuplicates()? Хотя, слова «The entries do not have to be sorted. They will retain their original order.» навевают мысли о худшем^W квадратичной сложности.
Днища.
Recommended by:
@pooq: моча съела говно
11 comments
recommend
bookmark
subscribe
ОШИБКА SIGSEGV ЭТО ЖЕ ОЧЕВИДНО КАК ЕЕ РЕШИТЬ
Да ты поехавший какой-то.
как будто что-то плохое
Да не, каждый из нас немного поехал в душе.
int QtPrivate::QStringList_removeDuplicates(QStringList *that)
{
int n = that→size();
int j = 0;
QSet<QString> seen;
seen.reserve(n);
for (int i = 0; i < n; ++i) {
const QString &s = that→at(i);
if (seen.contains(s))
continue;
seen.insert(s);
if (j != i)
(*that)[j] = s;
++j;
}
if (n != j)
that→erase(that→begin() + j, that→end());
return n — j;
}
З.Ы. Это не QList, а QStringList.
А, ну смысл тот же.
Что-то в райне O(n²) в худшем случае, O(n) амортизированно. Это ок.
Угу, и O(n) памяти.
Да, что тоже несколько удручает. Тот же std::unique вообще инплейс.
Ну так и вызови его, зачем тебе этот Qt ?
Потому что strings.removeDuplicates() писать быстрее, чем strings.erase (std::unique (strings.begin (), strings.end ()), strings.end ());
Зато детерминированность
!
Кстати, Qt-шные контейнеры не умеют в erase по рейнджу. Ну и создаваться из рейнджа не умеют. Нахуй их.