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