Sorting a linked list keeping some elements packed together

I have a linked list:

MyLinkedList::LinkedList<Event *> list;

where LinkedList comes from this library, and Event is this struct:

typedef struct 
{
    TimeSpan time;
    int value;

    bool queued;
} Event;

where TimeSpan comes from this library. After filling the list with some items I run the following function:

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;
}

the compare function is defined as follow:

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

It just orders the elements by their time. This code works fine.

Now I need to handle the queued flag in the struct. Here a sample input data:

When sorting, the items with the queued flag set must follow the previous item (with queued not set) regardless their time value (hence the xx:xx in the table).

The expected output is:

In other words: if queued is false the elements will be ordered as usual (by their time), if is true they must follow the previous element (like they are "grouped" together).

Since the compare function can just handle two items and I have no other information beyond the initial order, how can I keep the queued items with their "parent" item?

First group your list. In your example, [1, 2, 3, 4, 5, 6, 7] becomes [[1, 2, 3], [4, 5], [6], [7]].

Then sort those by the timestamp of the first element in each group. [[1, 2, 3], [4, 5], [6], [7]] becomes [[7], [6], [4, 5], [1, 2, 3]].

Then flatten that list to get [7, 6, 4, 5, 1, 2, 3].

Using std::vector, this might look something like the following (minus the flattening step).

#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";
        }
    }
}

With output:

Group:
1
2
3
Group:
4
5
Group:
6
Group:
7

After sorting

Group:
7
Group:
6
Group:
4
5
Group:
1
2
3