Iterator as a member: Tree/Graph-like structure

[Pl45m4]

Hi guys,

I'm wondering if it is a good pratice to have a "global" (actually not global but member) iterator in some class?

Context (also related to my topic here):
My project uses some graph-like data structure / logic, similar to PowerPoints slide animations. You can schedule tasks, order them in parallel or sequencially and therefore build the "model".
Instead of exposing the (current) item like

private:
     MyTask *current;
     QList<MyTask*> m_taskList;

the class in my current approach holds a QList<MyTask *> and a matching QList<MyTask*>::iterator, which points to the active task at all time.

private:
    QList<MyTask*>::iterator m_it; // makes sense?!
    QList<MyTask*> m_taskList;

When running the program I simply iterate through the list and start the next task with m_it++ once the previous has finished. When reaching the end, I set the iterator back to m_taskList.begin() and start all over.

Is there a more elegant, efficient way of doing this?
(C-Std doesn't matter, so up to C++24 is possible)

Keeping the list index of the active item does not work since the list can change during runtime and from the item itself or some index you wouldn't know the next item.

Open for any suggstions :)

TIA

[Christian Ehrlicher]

@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:

QList<MyTask*>::iterator m_it; // makes sense?!

Keeping the list index of the active item does not work since the list can change during runtime and from the item itself or some index you wouldn't know the next item.

An iterator is nothing more than a pointer to a memory location. So it's even more unstable than your index because when you add (or remove) items it will become invalid.
I would store the index and update it when adding/removing something from the container.

[Pl45m4]

@Christian-Ehrlicher said in Iterator as a member: Tree/Graph-like structure:

I would store the index and update it when adding/removing something from the container.

But then I need to iterate from the start, find my current element in the list and then the next one, every time I want to access the following element. So no simple it++ possible.

For this I'm also experimenting with various Qt container classes... I tried QList, QHash and QMap and I'm aware of the major differences. QHash provides faster lookup, QMap for example is sorted, as stated here

When iterating over a QHash, the items are arbitrarily ordered. With QMap, the items are always sorted by key.
( https://doc.qt.io/qt-6/qmap.html#details )

Based on this information I expect QObject-type keys in a QMap to be ordered by their pointers and not by any useful data members from that QObject-type class... So no "real" ordering by e.g. MyTask::m_id...

Similar to @VRonin 's good suggestion for another topic of mine...
Is there a way to influence the way QMap sorts its elements while iterating?!
Like telling a QMap<MyTask*, something> that elements should be iterated/sorted from lowest MyTask::m_id to highest.
This would solve the problem of keeping track of the index after each change to the container.

[Christian Ehrlicher]

You can create an own key struct:

struct Key {
  MyTask *task;
}
uint qHash(const key &k)
{
  return k.task->id;
}

 QMap<Key, something>

[JonB]

@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:

Keeping the list index of the active item does not work since the list can change during runtime and from the item itself or some index you wouldn't know the next item.

So what is your active item then? There must be something which makes it the current one, either by its position in the list or by its content....

If it's by position then maintaining that as a number and altering on insertions/deletions like @Christian-Ehrlicher said seems good.

If it's by content --- you say there is an id in each item, they are unique possibly with gaps and you are happy to keep those ordered --- then @Christian-Ehrlicher's hash with look up by that. Or don't forget you can always do a binary search to find a sorted value, it's amazing how much log(n) helps :)

In both cases, especially the second, you have to decide what you want to do about restarting if you allow the current/active item itself to be deleted.

[Pl45m4]

@JonB said in Iterator as a member: Tree/Graph-like structure:

So what is your active item then?

Currently my active item is the one where my iterator member points to. And because it's a member of my class I can do it++ anywhere to move to the next item in my container.
The main purpose is to iterate the container repeatedly and execute all tasks in order (depending on config, move to the next "current" when all tasks related to the previous item have finished).

Having the items (in my example of class MyTask) ordered by their id helps a lot since the loop should run from lowest ID to highest.
So either I use a container where my items are already ordered by MyTask::id (looking at @Christian-Ehrlicher answer to modify the key in a way to use the id member) or I keep the container (QList<MyTask*>) unordered and have to find the position of next valid task(s) myself (using a linked list, for example).

-- MyTask::ID:01
---- foo()
---- bar()
---- mooh()

-- MyTask::ID:02       <--- m_it
---- fooBar()
---- something()

-- MyTask::ID:03       <--- m_it++
---- blub()

-- MyTask::ID:04
---- randomFnct()

-- MyTask::ID:05
---- anotherOne()
---- andAnotherOne()
---- moreFncts()

[SimonSchroeder]

@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:

But then I need to iterate from the start, find my current element in the list and then the next one, every time I want to access the following element. So no simple it++ possible.

Nope. You can easily use an index instead of an iterator with QList. Contrary to what the name suggests it is not a singly (or doubly) linked list. Instead it is a lot more like a vector. You can immediately use the index to access the appropriate element in the list. There is not need to 'find' the element at that position.

[JonB]

@SimonSchroeder said in Iterator as a member: Tree/Graph-like structure:

There is not need to 'find' the element at that position.

This is, of course, true in itself. However if I understand the OP correctly, per my earlier comment he is saying his "last index executed" or "next index to be executed" is liable to change because he can have inserted or deleted elements since last used. That is why I was trying to discover how exactly he knows where he wants to continue from, e.g. is it really by index number or is it something about the content, such as an id field.

[Pl45m4]

@SimonSchroeder said in Iterator as a member: Tree/Graph-like structure:

Contrary to what the name suggests it is not a singly (or doubly) linked list. Instead it is a lot more like a vector.

Yes, I know and there used to be a QLinkedList which is deprecated as of Qt6+...

Anyway, like @JonB said correctly I have a class, let's call it MyTask which has an int id class member.
The IDs of MyTask objects are mapped to a custom widget class using a QHash<MyWidget*, int>

The container (currently I'm still not sure what structure or container will be the best fitting solution) which holds the MyTask items is planned to be iterated when running the program to simulate a Graph/Sequence/Tree-like behavior... similar to PowerPoints "Advanced Animation" / "Animation Trigger" function where one can manage various actions and effects. For example "start with previous", "start after", "begin with..." etc etc...

In another topic @Christian-Ehrlicher refered to TaskTree, which is kinda what I'm looking for, but instead of some complicated threaded call stack (no need for QFuture, promises, threads, mutex locks etc etc), I thought of some data structure only. I also don't need any threading as my "task" and actions are GUI related so I can't call them from separate threads anyway :)
I tried many things and looked into some existing "graph" implementations but none of them seem to be suited for my use case unfortunately.
As you (@SimonSchroeder ) mentioned linked lists, I also tried replacing my MyTask-QObject with a plain C-style linked list (chaining the MyTask struct nodes together using a next pointer)... but this made the process of managing the structure even more complicated.

The handling when move the active "task" to the next "group" (e.g. everything associated with MyTask::id = 42) is done by me in a top-level "Task Manager" class which is also responsible for managing the list/hashmap/container of MyTask objects and its insertation+deletion...

Long story short, @SimonSchroeder your idea would work if I had just an integer in my list, but instead I have MyTask * objects, which have an ID beside other things I need... (casual QObject derived class with ID and logic stuff)... so I have to do some look-up or search, assuming that the objects are not sorted by their ID, to find the "next" one, i.e. MyTask obj with next higher ID.
Gaps should be allowed, so after every action of MyTask::id = 0 is done MyTask::id = 42 should start its work when there is no MyTask::id (1, 2, .... 41)... but this is taken care of by the manager class to find the next valid MyTask obj.

I'm currently pulling the part out of my main program creating a test case, if anybody is interested :)

[Christian Ehrlicher]

@Pl45m4 said in Iterator as a member: Tree/Graph-like structure:

ong story short, @SimonSchroeder your idea would work if I had just an integer in my list, but instead I have MyTask * objects, which have an ID beside other things I need... (casual QObject derived class with ID and logic stuff)... so I have to do some look-up or search, assuming that the objects are not sorted by their ID, to find the "next" one, i.e. MyTask obj with next higher ID.

I already wrote how to sort a QMap by a custom key

[Pl45m4]

@Christian-Ehrlicher said in Iterator as a member: Tree/Graph-like structure:

I already wrote how to sort a QMap by a custom key

But what would be the key or value? Then I would make things even more complicated, wouldn't I?! Because I'm adding another level to it?!
Or what should be the key-value pair in my case then?

[Christian Ehrlicher]

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;

[JonB]

@Pl45m4
The key would be the id number. You would then have to look through the QMap/QHash in indexed order to find the next element. If you're clever you could do that via binary search, else sequential.

Honestly, if your problem is that you know the last id used or the next one to be used, want to find it, but cannot rely on where you got to previously (e.g. because of insertions/deletions you don't track), and place in a list cannot be re-used because it might have been deleted, then it seems to me the easiest way is a sorted vector which you can binary search. The advantage over QMap/QHash here is that it is easy to make your binary search return the next lower or higher element than the previously-saved value for which you want to find the successor, because that is what the algorithm can naturally return when it does not find the exact element. As I said, if you do wish to use QMap/QHash then if they are sorted by id key value you can binary search them too as well as any old vector you might use instead. (Looking now, QMap<Key, T>::iterator QMap::lowerBound(const Key &key) may do this for you on a QMap, internally (hopefully) it will use a binary search or some kind of red-black-type tree doubtless.)

[Christian Ehrlicher]

@JonB said in Iterator as a member: Tree/Graph-like structure:

The key would be the id number.

Not in my approach

[JonB]

@Christian-Ehrlicher
Isn't that what your earlier

uint qHash(const key &k)
{
  return k.task->id;
}

produces?

We have a lot of text in this thread. I'm still not sure what OP wants. My current understanding is
(a) He has a bunch of elements with unique, incrementing ids, but may contain gaps, get deleted etc.
(b) He just did task with id == 10. He saves 10 or 11 as where he got to. He wants to find task with id > 10 or id >= 11 as efficiently as possible.
(c) The old elements with id == 10 or id == 11 cannot have their pointer or iterator saved as they may have been deleted. And OP does want to adjust stuff as insertions/deletions happen to maintain next place to start from.

I'm happy to binary search a vector sorted by id, or a QMap sorted by id and maybe with QMap::lowerBound() to do the search, to find the next item with id > last time. No?

[Christian Ehrlicher]

@JonB said in Iterator as a member: Tree/Graph-like structure:

Isn't that what your earlier

uint qHash(const key &k)
{
return k.task->id;
}

produces?

Ignore this - we don't use QHash here so we don't need a hash function. We need a operator<() for properly sorting as I wrote in my last post.

[JonB]

@Christian-Ehrlicher
Yeah, but the same principle could have been used if OP went for QHash instead of QMap.

In any case. You wrote above to me

Not in my approach

I don't see where we (you and I) are disagreeing. OP needs a container, of whatever color, sorted by the id stored in his MyTask structure, in order to easily move between ids. Do we not agree on that? So I don't understand what you are saying that I am saying that is any different from what you are saying...? ;-)

[Christian Ehrlicher]

@JonB said in Iterator as a member: Tree/Graph-like structure:

but the same principle could have been used if OP went for QHash instead of QMap.

No, a QHash is not ordered.
The OP wants an ordered container.

don't see where we (you and I) are disagreeing. OP needs a container, of whatever color, sorted by the id stored in his MyTask structure, in order to easily move between ids. Do we not agree on that?

I only need one container, no (external) lookup needed with a second container id -> MyTask pointer.

[JonB]

@Christian-Ehrlicher said in Iterator as a member: Tree/Graph-like structure:

No, a QHash is not ordered.

Yeah I forgot to check. That's why QMap does have lower/upperBound() while QHash does not :)

I only need one container, no (external) lookup needed with a second container id -> MyTask pointer.

I never said or meant to imply I would have two containers? My elements would always be MyTasks (or pointers to them) and they would be sorted by/use key as MyTask::id. So I don't know where we differ, if anywhere, or whether it's all a question of words/explanations.

[Pl45m4]

@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, including QMap, QHash, QList and plain C-style linked list of nodes...
When using QHash and I want to iterate straight through, I have to search for "next" ID manually... 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 :)

QMake project:

taskSimulation.pro

QT       += 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 += target

mainwindow.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_H

mainwindow.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_H

mytask.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_H

taskmanager.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 maps QWidgets to 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 :)