PDA

View Full Version : Alternative iteration over a QList<QTreeWidgetItem*>



Axtroz
23rd June 2012, 22:54
Greetings.
I have a MySQL table with the following structure:


id | name | parent_node

`id` is int primary key, auto increment enabled.
`name` is a text string
`parent_node` is an int and holds the id of the previous node.

I query the database and populate a QList<QTreeWidgetItem*> item_list;


while (query->next())
{
QTreeWidgetItem* tree = new QTreeWidgetItem;
tree->setText(0, query->value(1).toString());
tree->setText(1, query->value(0).toString());
tree->setText(2, query->value(2).toString());
item_list.append(tree);
}


All is well, but I wonder if my iteration over the list and constructing the tree is optimal. The table contains 10 rows, but in the future it's gonna hold at least 1000 rows and I wonder if the program is going to behave nice, since the tree is constructed on startup (in the main class' constructor).

Here's my iterations:


for (int j=0;j<item_list.count();j++)
{
QTreeWidgetItem* current = item_list[j];
for (int i=0; i<item_list.count();i++)
{
qDebug() << "Current item: " << current->text(0);
if (current->text(2).toInt() == item_list.at(i)->text(1).toInt())
{
item_list.at(i)->addChild(current);
}
else if (current->text(2).toInt()==0)
{
ui->treeWidget->addTopLevelItem(item_list.first());
}
}
}
}

Thanks for your help!

wysota
23rd June 2012, 23:21
It's definitely not optimal. Put all your items that are going to be child items into a hash keyed by the number you are using for comparison (text(1).toInt()), put the top-level items immediately into the tree and then iterate over all the items once, attaching them to their proper parent extracted from the hash. It will make your algorithm O(n*lgn) instead of O(n*n).

Axtroz
23rd June 2012, 23:34
Wow, fast and accurate! Thank you very, very much for the quick response!

wysota
24th June 2012, 00:00
You can make it even faster (O(n)) if you change your original query to return rows in proper order (item, then all its children (with their children), then next top item, all its children, etc.).