Сортировка связанного списка с сохранением некоторых элементов вместе
У меня есть связанный список:
MyLinkedList::LinkedList<Event *> list;
откуда LinkedList берется эта библиотека, и Event это структура:
typedef struct
{
TimeSpan time;
int value;
bool queued;
} Event;
откуда TimeSpanэта библиотека.
После заполнения списка некоторыми элементами я запускаю следующую функцию:
bool Events::Save()
{
// order the elements by the time
_listEvents.sort(compare);
// open a file for writing
for (int i = 0; i < _listEvents.size(); i++)
{
Event *event = _listEvents.get(i);
// write the item to the file
writeEvent(file, *event);
}
file.close();
return true;
}
функция compare определяется следующим образом:
int compare(Event *&ev1, Event *&ev2)
{
if (ev1->time.hours() > ev2->time.hours()) return true;
if (ev1->time.hours() < ev2->time.hours()) return false;
return (ev1->time.minutes() > ev2->time.minutes());
}
Он просто упорядочивает элементы по времени. Этот код работает нормально.
Теперь мне нужно обработать флаг queued в структуре.
Вот пример входных данных:
При сортировке элементы с установленным флагом queued должны следовать за предыдущим элементом (с не установленным queued) независимо от их временного значения (отсюда и xx:xx в таблице).
Ожидаемый результат:
Другими словами: если queued равно false, элементы будут упорядочены как обычно (по времени), если равно true, они должны следовать за предыдущим элементом (как будто они «сгруппированы» вместе).
Поскольку функция compare может обрабатывать только два элемента, и у меня нет другой информации, кроме исходного порядка, как я могу сохранить элементы queued вместе с их «родительским» элементом?
Скопируйте временную метку события, поставленного в очередь, из его родителя и добавьте queued в функцию compare.
элементы с queued == false уже расположены в нужном порядке в неотсортированном списке?
@463035818_is_not_an_ai нет, они могут быть в произвольном порядке
@n.m.couldbeanAI, это возможно, но гарантирован ли тогда первоначальный порядок элементов в очереди?
Да, std::list::sort стабилен.
Это не ответ на ваш вопрос, но ваша for-петля вызывает подозрения. Конечно, LinkedList предоставляет идиоматический способ перебора своих элементов? Итерация for (int i = 0; i < _listEvents.size(); i++) и последующее повторное использование _listEvents.get(i) внутри цикла, вероятно, имеет квадратичную сложность, если предположить, что get(i) приходится перебирать связанный список, чтобы найти элемент i.
Остерегайтесь использования класса связанного списка, на который вы ссылаетесь. Он не соблюдает правило 3/5/0.
Кроме того, библиотека, из которой вы получаете TimeSpan, написана на C++, но имеет структуры typedefs, что явно не нужно в C++.
@Stef, связанный с классом LinkedList, не предоставляет никакой формы итератора.
@Chris Да, я посмотрел исходный код, и похоже, что единственный способ зациклиться на нем — это сохранить указатель на ListNode, что неудобно, потому что структура ListNode выглядит так, будто она не предназначена для использования в качестве части общедоступного интерфейса.
Ответы 1
Сначала сгруппируйте свой список. В вашем примере [1, 2, 3, 4, 5, 6, 7] становится [[1, 2, 3], [4, 5], [6], [7]].
Затем отсортируйте их по временной метке первого элемента в каждой группе. [[1, 2, 3], [4, 5], [6], [7]] становится [[7], [6], [4, 5], [1, 2, 3]].
Затем сгладьте этот список, чтобы получить [7, 6, 4, 5, 1, 2, 3].
Используя std::vector, это может выглядеть примерно так (без этапа сглаживания).
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
struct Event {
std::string time;
int value;
bool queued;
};
int main() {
std::vector<Event> events {
{"18:00", 1, false},
{"xx:xx", 2, true},
{"xx:xx", 3, true},
{"10:30", 4, false},
{"xx:xx", 5, true},
{"08:15", 6, false},
{"06:45", 7, false}
};
std::vector<std::vector<Event>> grouped;
for (auto &e : events) {
if (!e.queued) grouped.emplace_back();
grouped.back().push_back(e);
}
for (auto &g : grouped) {
std::cout << "Group:\n";
for (auto &e : g) {
std::cout << e.value << "\n";
}
}
std::sort(
grouped.begin(), grouped.end(),
[](auto &g1, auto &g2) {
return g1[0].time < g2[0].time;
}
);
std::cout << "\nAfter sorting\n\n";
for (auto &g : grouped) {
std::cout << "Group:\n";
for (auto &e : g) {
std::cout << e.value << "\n";
}
}
}
С выводом:
Group:
1
2
3
Group:
4
5
Group:
6
Group:
7
After sorting
Group:
7
Group:
6
Group:
4
5
Group:
1
2
3
Как сгруппировать список? Должен ли я использовать вложенные связанные списки?
Используйте любую структуру данных коллекции, которая вам нравится. В C++ о связанных списках часто не думают слишком высоко, предпочтение отдается таким вещам, как std::vector.
Вам придется изменить свое определение того, что такое предмет. В этом случае элементом является событие, не поставленное в очередь, а также все последующие события, помещенные в очередь. Таким образом, структура данных, которую вы сортируете, должна состоять из этих элементов, а не из событий, которые вы сейчас сортируете.