Alternative iteration over a QList<QTreeWidgetItem*>

[Axtroz]

Greetings.
I have a MySQL table with the following structure:

id | name | parent_node

id | name | parent_node

To copy to clipboard, switch view to plain text mode 

`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);
}

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);
}

To copy to clipboard, switch view to plain text mode 

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

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

To copy to clipboard, switch view to plain text mode 

Thanks for your help!

[wysota]

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]

Wow, fast and accurate! Thank you very, very much for the quick response!

[wysota]

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