Что такое QT или шаблон с открытым исходным кодом C ++ для обычной сортировки - PullRequest
Новая
       11

Что такое QT или шаблон с открытым исходным кодом C ++ для обычной сортировки

0 голосов
/ 17 ноября 2009

Я ищу специальный шаблонный класс, надеюсь, либо шаблон QT, либо автономную библиотеку с открытым исходным кодом. Этот шаблонный класс предназначен для использования в качестве контейнера для набора объектов. Каждый объект в наборе имеет целочисленную весовую функцию, но сама весовая функция является произвольной. Оно может варьироваться от 10 до 100 или неравномерно от 1000 до 10000 или быть постоянным значением.

Шаблон будет хранить список объектов, отсортированных по этому весу (разрешая связи произвольно). Это позволило бы мне быстро получить из списка объект, имеющий n-й максимальный вес , по порядку, а не по значению (произвольный доступ с использованием целого числа, такого как QList). Шаблон также позволяет мне быстро добавлять и удалять произвольные элементы, сохраняя упорядоченный список по весу (например, QMap).

Для моих целей достаточно было бы просто найти объекты в пределах порядка - IE, найти 1-й, 10-й, 100-й, 1000-й и т. Д. Элементы в моем упорядоченном списке.

Я мог бы сам реализовать такую ​​структуру данных (как массив списков с увеличивающимся размером или как модифицированное двоичное дерево, имеющее количество n элементов ниже каждого узла). Но для решения проблемы лучше использовать стандартный общедоступный шаблон , хорошо документированный . Я бы предпочел избегать STL, но если есть решение STL, мне было бы интересно.

Редактировать : Я ищу, по крайней мере, порядков - не только первый , но 1-й , 10-е, 100-е , упорядоченные по весу до конца (внутреннее упорядочение структуры данных кучи было бы здорово, но я не вижу функций, которые напрямую обращаются к этому). Я вижу, что STL предоставляет «итератор произвольного доступа», но после просмотра большого количества документации я все еще не могу найти, будет ли этот итератор давать n-е значение без необходимости сортировки списка для каждого вызова - действительно, мой расплывчатый Такое впечатление, что так и будет. STL также предоставляет функцию «nth element», но, похоже, это относительно дорого, если вы вызываете ее для каждого доступа к списку.

Edit2: По этой причине нельзя просто использовать итератор QMap и сделать это2 = it.begin () + 1000; ( из документации QT ):

итератор итератор :: оператор + (int j) сопз

Возвращает итератор для элемента в j позиции вперед от этого итератора. (Если j отрицательно, итератор назад.)

Эта операция может быть медленной для больших j значения.

См. Также оператор - ().

Ответы [ 2 ]

1 голос
/ 17 ноября 2009

Структура данных, которую вы ищете, - это куча. В stdlib есть std :: make_help, push_heap и pop_heap. Также есть std :: priority_queue. (Я не уверен, почему вы должны избегать этого, если нет каких-то других требований, о которых вы нам не сказали.)

Дерево, такое как карта, также будет работать, но оно будет сортировать каждый элемент. Например, если вам нужны только «лучшие» три из 1 000 000, сортировка их всех будет бесполезной.

0 голосов
/ 17 ноября 2009

QMap сортирует по ключу, так что вы можете просто использовать это. например, 

QMap<int, YourValueType>

Затем вы можете использовать итераторы для получения n-го последнего элемента, например, последний: map.end() - 1, рядом с последним, map.end() - 2, ...

Полный пример: 

#include <QMap>
#include <QString>
#include <QDebug>

int main()
{
    QMap<int, QString> foo;

    foo.insert(2, "foo");
    foo.insert(1, "bar");
    foo.insert(5, "baz");

    qDebug() << (foo.end() - 1).value();
    qDebug() << (foo.end() - 2).value();

    return 0;
}

Производит: 

"baz" 
"foo"
...