Iterator as a member: Tree/Graph-like structure
-
@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
I'm currently pulling the part out of my main program creating a test case, if anybody is interested :)
So here is small program that shows what I'm trying to do. I hope things become clear
@JonB @Christian-Ehrlicher Thank you guys for your interest :)
Actually I don't know (I'm not sure) what's the best stucture for this... therefore I tried couple things, includingQMap,QHash,QListand plain C-style linked list of nodes...
When usingQHashand I want to iterate straight through, I have to search for "next" ID manually... on the other hand, when using aQMap, first I need to order them byMyTask::id(thanks @Christian-Ehrlicher ) but then the insertations/deletions are quite messy and complicated :)QMake project:
taskSimulation.proQT += core gui greaterThan(QT_MAJOR_VERSION, 4): QT += widgets CONFIG += c++17 # You can make your code fail to compile if it uses deprecated APIs. # In order to do so, uncomment the following line. #DEFINES += QT_DISABLE_DEPRECATED_BEFORE=0x060000 # disables all the APIs deprecated before Qt 6.0.0 SOURCES += \ main.cpp \ mainwindow.cpp \ mytask.cpp \ taskmanager.cpp HEADERS += \ mainwindow.h \ mytask.h \ taskmanager.h # Default rules for deployment. qnx: target.path = /tmp/$${TARGET}/bin else: unix:!android: target.path = /opt/$${TARGET}/bin !isEmpty(target.path): INSTALLS += targetmainwindow.h#ifndef MAINWINDOW_H #define MAINWINDOW_H #include <QMainWindow> class TaskManager; class MainWindow : public QMainWindow { Q_OBJECT public: MainWindow(QWidget *parent = nullptr); ~MainWindow(); private: TaskManager *m_taskMan; }; #endif // MAINWINDOW_Hmainwindow.cpp#include "mainwindow.h" #include "taskmanager.h" #include <QPushButton> #include <QSpinBox> #include <QVBoxLayout> #include <QFormLayout> #include <QScrollArea> #include <QHBoxLayout> #include <QTextEdit> MainWindow::MainWindow(QWidget *parent) : QMainWindow(parent) , m_taskMan(new TaskManager(this)) { QWidget *cntrwdg = new QWidget; QVBoxLayout *vbox = new QVBoxLayout; QPushButton *btn_add = new QPushButton("Add / Update", this); QPushButton *btn_rem = new QPushButton("Delete", this); QPushButton *btn_print = new QPushButton("Print", this); QHBoxLayout *hbox = new QHBoxLayout; QPushButton *btn_start = new QPushButton("Start", this); QPushButton *btn_stop = new QPushButton("Stop", this); hbox->addWidget(btn_start); hbox->addWidget(btn_stop); QSpinBox *spin_seq = new QSpinBox(this); spin_seq->setRange(0, 999); QSpinBox *spin_seqLen = new QSpinBox(this); spin_seqLen->setRange(1, 999); QTextEdit *textEdit = new QTextEdit(this); QFormLayout *laySeq = new QFormLayout; QFormLayout *layseqLen = new QFormLayout; laySeq->addRow("Task ID\t\t", spin_seq); layseqLen->addRow("Sub-Task Length\t", spin_seqLen); vbox->addLayout(laySeq); vbox->addLayout(layseqLen); vbox->addWidget(btn_add); vbox->addWidget(btn_rem); vbox->addWidget(btn_print); vbox->addWidget(textEdit); vbox->addLayout(hbox); cntrwdg->setLayout(vbox); connect(btn_add, &QPushButton::clicked, this, [=](){ m_taskMan->addTask(spin_seq->value(), spin_seqLen->value()); }); connect(btn_rem, &QPushButton::clicked, this, [=](){ m_taskMan->removeTask(spin_seq->value()); }); connect(btn_print, &QPushButton::clicked, m_taskMan, &TaskManager::print); connect(m_taskMan, &TaskManager::sendToLog, textEdit, &QTextEdit::append); connect(btn_start, &QPushButton::clicked, this, [=](){ // Assume each sub-task takes 1s to finish // just for simulation purpose m_taskMan->startSimulation(1000); }); connect(btn_stop, &QPushButton::clicked, m_taskMan, &TaskManager::stopSimulation); connect(m_taskMan, &TaskManager::taskFinished, this, [=](int id){ qDebug() << "Task" << id << "done."; }); setCentralWidget(cntrwdg); setGeometry(800, 400, 600, 300); } MainWindow::~MainWindow() {}mytask.h#ifndef MYTASK_H #define MYTASK_H #include <QObject> class MyTask : public QObject { Q_OBJECT public: explicit MyTask(int id, int len, QObject *parent = nullptr); int id() const; void setLength(int newLength); int length() const; // enqueue after seq done (or in between if needed) // "resets" counter to "max tasks" = length void enqueue(); // task counter -- // returns new cnt value int cycle(); private: int m_id; int m_length; int m_counter; }; #endif // MYTASK_Hmytask.cpp#include "mytask.h" #include <QDebug> MyTask::MyTask(int id, int len, QObject *parent) : QObject{parent} , m_id{id} , m_length{len} , m_counter{m_length} { } void MyTask::setLength(int newLength) { m_length = newLength; } int MyTask::length() const { return m_length; } void MyTask::enqueue() { m_counter = m_length; } int MyTask::cycle() { // do some tasks in a queue // ... // when all done qDebug() << "Tick (Task" << m_id << "SubTasks remaining" << m_counter << ")"; m_counter--; if (m_counter == 0) { enqueue(); return 0; } else { return m_counter; } } int MyTask::id() const { return m_id; }taskmanager.h#ifndef TASKMANAGER_H #define TASKMANAGER_H #include <QObject> #include <QList> #include <QTimer> class MyTask; class TaskManager : public QObject { Q_OBJECT public: explicit TaskManager(QObject *parent = nullptr); // id: to determine order and associate with buttons // len: important for counting down (knowing when task has finished) void addTask(int id, int length); // remove task with id void removeTask(int id); void nextTask(); void startSimulation(int tick = 1000); void stopSimulation(); void print(); signals: void sendToLog(QString); void taskFinished(int id); private: QList<MyTask*>::iterator m_it; QList<MyTask *> m_taskList; QTimer m_timer; }; #endif // TASKMANAGER_Htaskmanager.cpp#include "taskmanager.h" #include "mytask.h" #include <QDebug> TaskManager::TaskManager(QObject *parent) : QObject{parent} { m_it = m_taskList.begin(); connect(&m_timer, &QTimer::timeout, this, [=](){ // "start" all tasks // -> either at the same time // -> or (in simulation) one after another MyTask &t = *(*m_it); if (t.cycle() == 0) { emit taskFinished(t.id()); nextTask(); } }); } void TaskManager::addTask(int id, int length) { bool found = false; QListIterator<MyTask*> i(m_taskList); while (i.hasNext()) { MyTask *curr = i.next(); if (curr->id() == id) { emit sendToLog("Task exists."); found = true; if (curr->length() != length) { curr->setLength(length); emit sendToLog(QString("Task %1 updated").arg(id)); } else emit sendToLog("Nothing to do"); } } if (!found) { MyTask *t = new MyTask(id, length, this); m_taskList.append(t); m_it = m_taskList.begin(); emit sendToLog(QString("Task created: %1 / %2").arg(id).arg(length)); } } void TaskManager::removeTask(int id) { QMutableListIterator<MyTask*> i(m_taskList); while (i.hasNext()) { if (i.next()->id() == id) { i.remove(); emit sendToLog(QString("Task %1 removed").arg(id)); } } } void TaskManager::nextTask() { qDebug() << "Task" << "has finished. Starting next..."; if (++m_it == m_taskList.end()) { qDebug() << "Reaching end. Restarting..."; m_it = m_taskList.begin(); } } void TaskManager::startSimulation(int tick) { m_timer.start(tick); } void TaskManager::stopSimulation() { m_timer.stop(); } void TaskManager::print() { QString msg = "\n#####\tID ####\tLEN ###############\n"; QListIterator<MyTask*> i(m_taskList); while (i.hasNext()) { const MyTask *curr = i.next(); msg += "Task:\t" + QString::number(curr->id()) + "\t" + QString::number(curr->length()) + "\n"; } msg += "#########################################\n"; emit sendToLog(msg); }main.cpp#include "mainwindow.h" #include <QApplication> int main(int argc, char *argv[]) { QApplication a(argc, argv); MainWindow w; w.show(); return a.exec(); }Sorry if I caused any confusion :D
I not sure how to pull this off properly and in a more efficient way :)
Thanks again :)PS:This is just the "run-through" process... in my main program I also have a
QHash<MyWidget *, int>which mapsQWidgetsto the Task ID... but AFAICS this container/structure is not suited to "run" the loop and start tasks accordingly. It only manages the Widget-TaskID connection.PPS:
How this simulation works:
Create a couple "Task" with different IDs and lengths (sub-tasks to finish before allowed to move to next task) and press "Start"...
What I thought of is printed to console :)wrote on 10 Jan 2025, 14:56 last edited by@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
When using QHash and I want to iterate straight through, I have to search for "next" ID manually...
Yes that's exactly as @Christian-Ehrlicher said, because
QHashis not ordered. Forget about it!on the other hand, when using a QMap, first I need to order them by MyTask::id (thanks @Christian-Ehrlicher ) but then the insertations/deletions are quite messy and complicated :)
Why are insertions/deletions a problem?? (I haven't looked at your code!.)
-
@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
When using QHash and I want to iterate straight through, I have to search for "next" ID manually...
Yes that's exactly as @Christian-Ehrlicher said, because
QHashis not ordered. Forget about it!on the other hand, when using a QMap, first I need to order them by MyTask::id (thanks @Christian-Ehrlicher ) but then the insertations/deletions are quite messy and complicated :)
Why are insertions/deletions a problem?? (I haven't looked at your code!.)
wrote on 10 Jan 2025, 15:19 last edited by@JonB said in Iterator as a member: Tree/Graph-like structure:
Why are insertions/deletions a problem?? (I haven't looked at your code!.)
Because I still have to "search" for the next ID in order (as it's not always
lastID + 1) that would make this more like being close to O(n^2) than O(n) or even O(1), right? Or am I missing something?!Also I asked initially if it's "ok" to have a global (member) iterator around instead of keeping some index (which might change) or a direct pointer to the item itself (= what also is stored in the container).
-
@JonB said in Iterator as a member: Tree/Graph-like structure:
Why are insertions/deletions a problem?? (I haven't looked at your code!.)
Because I still have to "search" for the next ID in order (as it's not always
lastID + 1) that would make this more like being close to O(n^2) than O(n) or even O(1), right? Or am I missing something?!Also I asked initially if it's "ok" to have a global (member) iterator around instead of keeping some index (which might change) or a direct pointer to the item itself (= what also is stored in the container).
wrote on 10 Jan 2025, 15:46 last edited by JonB 1 Oct 2025, 15:52@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
Because I still have to "search" for the next ID in order (as it's not always lastID + 1) that would make this more like being close to O(n^2) than O(n) or even O(1), right? Or am I missing something?!
I don't understand this at all. I don't even know whether you mean doing this at insertion, deletion or search-for-next time, but in all cases my searches will be O(log(n)). And that applies when looking for key
10whether it finds it or returns where it ought to be if it does not exist.Since @Christian-Ehrlicher said I may not have made it 100% clear. All in all I would probably use
QMap<int, Task *> map; map.insert(task->id, task);You can use
QMap'slower/upperBound()to find where you got to/where to start from next, and this will work even if the previously noted id number no longer exists (e.g. it has been deleted). [Go read docs about what these return if the key you ask for does not exist, you do not have to explicitly findlast + 1in existence, this is the bit you are not understanding.] And you can assume that will be O(log(n)) because it knows the key search is ordered, unless it is brain-damaged, which I imagine it is not :) Which is all similar forQMapas it would be if you wrote your own ordered vector for binary search or red-black tree. (I am guessingQMapis some kind of red-black tree?)Also I asked initially if it's "ok" to have a global (member) iterator around instead of keeping some index (which might change) or a direct pointer to the item itself (= what also is stored in the container).
I think this was covered in @Christian-Ehrlicher's initial answer, where an iterator is no better than a pointer to keep around in the case where that item may have been deleted.
-
@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
Because I still have to "search" for the next ID in order (as it's not always lastID + 1) that would make this more like being close to O(n^2) than O(n) or even O(1), right? Or am I missing something?!
I don't understand this at all. I don't even know whether you mean doing this at insertion, deletion or search-for-next time, but in all cases my searches will be O(log(n)). And that applies when looking for key
10whether it finds it or returns where it ought to be if it does not exist.Since @Christian-Ehrlicher said I may not have made it 100% clear. All in all I would probably use
QMap<int, Task *> map; map.insert(task->id, task);You can use
QMap'slower/upperBound()to find where you got to/where to start from next, and this will work even if the previously noted id number no longer exists (e.g. it has been deleted). [Go read docs about what these return if the key you ask for does not exist, you do not have to explicitly findlast + 1in existence, this is the bit you are not understanding.] And you can assume that will be O(log(n)) because it knows the key search is ordered, unless it is brain-damaged, which I imagine it is not :) Which is all similar forQMapas it would be if you wrote your own ordered vector for binary search or red-black tree. (I am guessingQMapis some kind of red-black tree?)Also I asked initially if it's "ok" to have a global (member) iterator around instead of keeping some index (which might change) or a direct pointer to the item itself (= what also is stored in the container).
I think this was covered in @Christian-Ehrlicher's initial answer, where an iterator is no better than a pointer to keep around in the case where that item may have been deleted.
wrote on 10 Jan 2025, 16:13 last edited by Pl45m4 1 Oct 2025, 16:16@JonB said in Iterator as a member: Tree/Graph-like structure:
Since @Christian-Ehrlicher said I may not have made it 100% clear. All in all I would probably use
QMap<int, Task *> map; map.insert(task->id, task);This makes totally sense and I also got what @Christian-Ehrlicher wrote above about a custom "key", but is it really a good idea to map
MyTaskto members of itself?!
Is there no other magical way to do it?
That stopped me from going over this approach in my head any further.
Because the "fun" thing is that (with aQMap) I currently wouldn't know what to put as value otherwise, when using a key like @Christian-Ehrlicher described before and correctly :))I have
// my current approach task container QList<MyTask*> taskList; // (not included in my example and not relevant for looping the tasks) // where "int" equals a valid MyTask::id QHash<MyWidget *, int> taskWidgetMap;so the information what Task has which ID is already stored in
MyTaskclassTo get somewhere with this, I will try @Christian-Ehrlicher 's approach and your MyTask <--> MyTask::id mapping now and see how it integrates into the rest. ;-)
Btw: Now I've read through
QSet<T>more carefully and figured out that my initial thought (in my head without specifying any data structure) was about something like an ordered (ideally hash-based) one-dimensional structure (= "list", no key-value dict).... which does not existing in this form :)So yeah, I will report back later ;-)
Besides the data struture mess, have you tried my example @JonB @Christian-Ehrlicher ? What do you think? :)
Highly appreciate all your input and the discussion here :)
-
@JonB said in Iterator as a member: Tree/Graph-like structure:
Since @Christian-Ehrlicher said I may not have made it 100% clear. All in all I would probably use
QMap<int, Task *> map; map.insert(task->id, task);This makes totally sense and I also got what @Christian-Ehrlicher wrote above about a custom "key", but is it really a good idea to map
MyTaskto members of itself?!
Is there no other magical way to do it?
That stopped me from going over this approach in my head any further.
Because the "fun" thing is that (with aQMap) I currently wouldn't know what to put as value otherwise, when using a key like @Christian-Ehrlicher described before and correctly :))I have
// my current approach task container QList<MyTask*> taskList; // (not included in my example and not relevant for looping the tasks) // where "int" equals a valid MyTask::id QHash<MyWidget *, int> taskWidgetMap;so the information what Task has which ID is already stored in
MyTaskclassTo get somewhere with this, I will try @Christian-Ehrlicher 's approach and your MyTask <--> MyTask::id mapping now and see how it integrates into the rest. ;-)
Btw: Now I've read through
QSet<T>more carefully and figured out that my initial thought (in my head without specifying any data structure) was about something like an ordered (ideally hash-based) one-dimensional structure (= "list", no key-value dict).... which does not existing in this form :)So yeah, I will report back later ;-)
Besides the data struture mess, have you tried my example @JonB @Christian-Ehrlicher ? What do you think? :)
Highly appreciate all your input and the discussion here :)
wrote on 10 Jan 2025, 16:32 last edited by- Christian's approach of defining a
<operator for theTaskstruct itself is required if and only if you wish to have aTask *as the key for theQMap. Which is what he says you had stated initially. - But I don't see why you would want or need that (my
Task *is the value, not the key). I just use anintas the key and passtask->idfor that at map insert time.
Up to you.
- Christian's approach of defining a
-
- Christian's approach of defining a
<operator for theTaskstruct itself is required if and only if you wish to have aTask *as the key for theQMap. Which is what he says you had stated initially. - But I don't see why you would want or need that (my
Task *is the value, not the key). I just use anintas the key and passtask->idfor that at map insert time.
Up to you.
wrote on 10 Jan 2025, 16:39 last edited by@JonB said in Iterator as a member: Tree/Graph-like structure:
I just use an int as the key and pass task->id for that at map insert time
Yeah that makes sense... but my concern is/was that I have some redundancy. MyTask::id = key AND also already stored in
MyTask(and accessible via something likevalue().id)...Will try it out.
- Christian's approach of defining a
-
@JonB said in Iterator as a member: Tree/Graph-like structure:
I just use an int as the key and pass task->id for that at map insert time
Yeah that makes sense... but my concern is/was that I have some redundancy. MyTask::id = key AND also already stored in
MyTask(and accessible via something likevalue().id)...Will try it out.
wrote on 10 Jan 2025, 16:52 last edited by JonB 1 Oct 2025, 16:52@Pl45m4
You are saving/losing anintfor the key. But even another way to use aQMapyou have to provide some key to go with a value. If you useTask *as the key that costs a pointer (even if you also storeTask *as the value too) which is actually bigger than anint. Plus yourQMapactually goes wrong if you go change what the key pointer points to, or theidinside that, if you change the id in the Task yourQMapwon't rearrange itself!Many times we do key-value pairs like this. I could be wrong, but when, say, you have a database table with a primary (or unique) key/index I don't think that stores a "pointer to" its value somewhere in the row for its data, I think it copies the value to the index and then keeps that in sync if the row changes.
But if you are happier with the key as a
Task *and override the<operator that is fine too. -
Sorry but I don't understand what you mean - simply replace QMap<MyTask *, whatever> with QMap<Key, whatever> and provide a operator<() for the key (I was wrong above - you don't have to provide a qHash() but a operator <() for a QMap)
struct Key { MyTask *task; bool operator <(const Key &o) const { return task->id < o.task->id; } }; QMap<Key, something> myMap;wrote on 10 Jan 2025, 17:50 last edited by@Christian-Ehrlicher said in Iterator as a member: Tree/Graph-like structure:
simply replace QMap<MyTask *, whatever> with QMap<Key, whatever> and provide a operator<() for the key (I was wrong above - you don't have to provide a qHash() but a operator <() for a QMap)
struct Key { MyTask *task; bool operator <(const Key &o) const { return task->id < o.task->id; } }; QMap<Key, something> myMap;One more thing @Christian-Ehrlicher :
Is there a reason why you picked an extra struct for theKeyinstead of using theMyTask::operator <directly? -
@Christian-Ehrlicher said in Iterator as a member: Tree/Graph-like structure:
simply replace QMap<MyTask *, whatever> with QMap<Key, whatever> and provide a operator<() for the key (I was wrong above - you don't have to provide a qHash() but a operator <() for a QMap)
struct Key { MyTask *task; bool operator <(const Key &o) const { return task->id < o.task->id; } }; QMap<Key, something> myMap;One more thing @Christian-Ehrlicher :
Is there a reason why you picked an extra struct for theKeyinstead of using theMyTask::operator <directly?@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
instead of using the MyTask::operator < directly?
Because this operator would not be used by a QMap<MyTask*, ...> as you store a pointer, not a value.
-
@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:
instead of using the MyTask::operator < directly?
Because this operator would not be used by a QMap<MyTask*, ...> as you store a pointer, not a value.
wrote on 10 Jan 2025, 17:55 last edited byAh I see, thanks.
-
How many elements would there be in this container?
-
wrote on 10 Jan 2025, 22:25 last edited by
@GrecKo
:) Unless it's like more than 100, and this is called many times, and the tasks don't take long to run comparatively, I suspect the whole "fast lookup" won't matter much! But maybe still the principle of how you pick up where you left off from. -
An "inefficient" simple for loop may very well be the most efficient after all. When you have 50 elements it won't matter much anyway, pick the container with the friendliest API depending on how you plan to access it.
-
An "inefficient" simple for loop may very well be the most efficient after all. When you have 50 elements it won't matter much anyway, pick the container with the friendliest API depending on how you plan to access it.
wrote on 11 Jan 2025, 00:40 last edited by@GrecKo said in Iterator as a member: Tree/Graph-like structure:
pick the container with the friendliest API depending on how you plan to access it.
Still what @Christian-Ehrlicher and @JonB suggested doesn't sound too bad :)
Will definitely try it.Similar question: Why is
QButtonGroupusing aQHash-map for its member buttons? :))
I doubt that there ever will be thousands of button widgets in one group :)
30/35