Question about iterator's choice

[Dark_Tower]

Hi all, I have the following method where I manage various lists: "llistaAccions" is a list containing identificators to the actions that I need to execute sequentally until the previous to the last one. "llistaParamsColors", "llistaParamsRects", "llistaParamsDoubles" and "llistaParamsInts" contain the parameters of each action. Now, I use QMutableListIterators to iterate through the lists but I think that the code can be slighty more efficient because I go through the list sequentally and, also, I need to delete only the last items on each list and not the items in the middle. Here's the code:


void MyApp::executeAllUntilPrevious()
{
int aux1, aux2, aux3, aux4;
double auxd1, auxd2, auxd3, auxd4;
QImage imatgeEnganxar;

llistaAccions.removeLast();

QMutableListIterator<IdentificadorAccions> itAccions(llistaAccions);
QMutableListIterator<QColor> itColors(llistaParamsColors);
QMutableListIterator<QRect> itRects(llistaParamsRects);
QMutableListIterator<double> itDoubles(llistaParamsDoubles);
QMutableListIterator<int> itInts(llistaParamsInts);

while(itAccions.hasNext())
{
switch(itAccions.next())
{
case Rotat:
rotat(itColors.next(), itDoubles.next());
break;

case Retallat:
retallat(itRects.next());
break;

case Pintat:
pintat(itColors.next(), itRects.next());
break;

case Copiat:
if (itAccions.hasNext())
imatgeEnganxar = foto -> copiarImatge(itRects.next());
else
itAccions.remove();
break;

case Enganxat:
enganxat(itRects.next(), imatgeEnganxar);
break;

case Restaurat:
restaurat();
break;

case EscalatCm:
auxd1 = itDoubles.next();
auxd2 = itDoubles.next();
canviTamanyCm(auxd1, auxd2);
break;

case EscalatPixels:
aux1 = itInts.next();
aux2 = itInts.next();
canviTamanyPixels(aux1, aux2);
break;

case CanviatResolucioPixelsCm:
aux1 = itInts.next();
aux2 = itInts.next();
canviResolucioPixelsCm(aux1, aux2);
break;

case CanviatResolucioPixelsPolzada:
aux1 = itInts.next();
aux2 = itInts.next();
canviResolucioPixelsPolzada(aux1, aux2);
break;

case CanviatMargesCm:
auxd1 = itDoubles.next();
auxd2 = itDoubles.next();
auxd3 = itDoubles.next();
auxd4 = itDoubles.next();
canviTamanyMargesCm(itColors.next(), auxd1, auxd2, auxd3, auxd4);
break;

case CanviatMargesPixels:
aux1 = itInts.next();
aux2 = itInts.next();
aux3 = itInts.next();
aux4 = itInts.next();
canviTamanyMargesPixels(itColors.next(), aux1, aux2, aux3, aux4);
}
}

//This part is a bit "dirty" and I think that could be achieved with just one sentence...
while(itColors.hasNext())
{
itColors.next();
itColors.remove();
}

while(itRects.hasNext())
{
itRects.next();
itRects.remove();
}

while(itDoubles.hasNext())
{
itDoubles.next();
itDoubles.remove();
}

while(itInts.hasNext())
{
itInts.next();
itInts.remove();
}
}

Well, I've readed that STL style iterators can be slightly faster than the Java-style iterators (QMutableListIterator). And, inside the STL style iterators, QList::const_iterator is slightly faster than QList::iterator. First of all, do you think that I really need iterators with the code above to obtain a better performance and/or readability? And, in that case, what kind of iterator you think that could fit better in what I need to do: iterate sequentially through the lists and, at the end, delete all the items from the current position until the end. Thanks.

[hickscorp]

I'm not sure if i understand your question, but i would rather use this kind of code:

- Create a class for instance IAction, which would be abstract (I think people who went to computer school call this an interface, i'm not sure). In this abstract class i would create a virtual protected method like "virtual int GetType() = 0", to force inheriting classes to implement it. I would then create a public method in it named "int Type() { return GetType(); };".
- Then, create as many derived classes as you need of action types. For instance, i woud create CAction_Rotate (Implementing IAction), CAction_Restaure (Implementing IAction too) etc... So each derived class implements GetType(), with an unique return value, like an identification of your action. For instance, CAction_Rotate would return 0, defined as a const to "ROTATE".
- Then in each of your specific action classes you can put parametters (For instance, in CAction_Rotate there would be a public member like "iRotationAngle".
- Then in your main application, you would just have to maintain a std::stack containing only IAction* pointers.
- In your loop, you would then be able to get one by one a pointer on the current IAction stack, for instance poping the next action into "pCurrentAction".
- Then your switch would become "switch (pCurrentAction->Type())".
- Then on each case, you could change the cast of the pCurrentAction pointer to the required class type, and get parametters for the action. For instance you would have a "case ROTATE : (or case 0 :) CAction_Rotate* pRotation = (CAction_Rotate*)pCurrentAction; MyRotationFunction(pRotation->iRotationAngle); break;"

The benefits would be (I guess) that a stack is way faster, you would have only one "stack" for any action type, each one holding it's own parametters.

But, that's maybe too much complicated for what you're trying to achieve.

Hope this helps, Good luck and have a nice day!
Pierre.

[EDIT:] Just one additionnal stuff, an interesting feature you can add with the way i suggested you, is a Description() method in IAction which returns GetDescription() of course virtual (Based on the same schemas as explained for Type()). It would allow each action to carry a descriptive, translatable information to be displayed for instance in the status bar of your application ;)

[Dark_Tower]

Thanks hickscorp, the way you have descripted is better, as you say it only has to manage one queue, although it requieres a little more code. Tomorrow I will program it. Have a nice day you too.

[Dark_Tower]

Hi again, I have now programmed it as hickscorp descripted. Now I've got a simple question: what kind of list do you think that would be more efficient for the action's list:
- QList has appending Ammort O(1) because it preallocates extra space on both sides of its internal buffer to allow for fast growth at both ends of the list and index lookup O(1)
- QLinkedList has appending O(1) and index lookup O(n) but, as I believe, if you access it with an iterator sequentially it's O(1) to acess to the next/previous position.
I would choose the linked list because I only need to append actions in the list and iterate it sequentially. But the docs says that "For most purposes, QList is the right class to use. Its index-based API is more convenient than QLinkedList's iterator-based API, and it is usually faster than QVector because of the way it stores its items in memory. It also expands to less code in your executable". What do you think?

[hickscorp]

You're welcome,

About the QT specific list question, i'm not sure since i'm such a beginner with QT, my skills stops after C++ for now ;)

But, knowing linked lists basic functionnality, i would choose a simple linked list on pointers (Not much memory allocated for each container since it points to the original object you've created, and since you can get a template one it would compile perfectly to suit your code needs). And, a linked list would be very fast since the current index container holds a pointer on the next one (But again, i don't know how Q* objects work internaly). Be carefull to not use a circular linked list, since if you don't "pop" your actions from it you can end in an infinite loop...

Bye!

[wysota]

If you only iterate sequencially, you can go for the linked list, but you won't have any benefits from using it, the regular list will be just as good and is more convenient than using the linked list. Using linked lists practically only makes sense if you intend to insert items in the middle of the list and not at either end.

[Dark_Tower]

Thanks for the suggestion hirckscorp and wysota. Maybe the QList would be less efficent than the QLinkedList in some appends when it has to reallocate more memory (i doubt if it has to copy all the list items again in the new space)

[wysota]

(i doubt if it has to copy all the list items again in the new space)

It moves pointers to the contents, items themselves are not copied.

[Dark_Tower]

Thanks wysota is good to know it