What is the most efficient way to compare two QStringList in QT?

Question

I have two String Lists and I already have a function that compares two lists to find out which elements of list 2 do not exist in list 1. This block of code works, but maybe it is not the best way to achieve it, there are any other way to get the same result without performing so many iterations with nested loops?

QStringList list1 = {"12420", "23445", "8990", "09890", "32184", "31111"}; QStringList list2 = {"8991", "09890", "32184", "34213"}; QStringList list3; for (int i = 0; i < list2.size(); ++i) { bool exists = false; for (int j = 0; j < list1.size(); ++j) { if(list2[i] == list1[j]){ exists = true; break; } } if(!exists) list3.append(list2[i]); } qDebug() << list3;

output: ("8991", "34213")

Perhaps this small example does not seem like a problem since the lists are very small. But there might be a case where both lists contain a lot of data.

I need to compare these two lists because within my app, every time a button is clicked, it fetches an existing dataset, then runs a function that generates a new data (including existing ones, such as a data refresh), so I need to get only those that are new and didn't exist before. It might sound like strange behavior, but this is how the app works and I'm just trying to implement a new feature, so I can't change this behavior.

First, I would add a break statement when you find a match. No reason to continue after that point. Other than that, unless the lists are sorted, you still need to iterate over every item in both lists. — JarMan
– JarMan, Commented Sep 6, 2022 at 16:41
Yes, you're right I forgot to include the break statement while editing the code, thanks. I ask this question because in Python, for example, we can create data frames with pandas to simulate an inner, left or right joins to get this kind of results without using nested loops. — BadRobot
– BadRobot, Commented Sep 6, 2022 at 16:49

Botje · Accepted Answer · 2022-09-06 18:50:09Z

4

If you switch to QSet<QString>, your code snippet boils down to:

auto diff = set2 - set1;

If the input and output data structures must be QStringLists, you can still do the intermediate computation with QSets and still come out ahead:

auto diff = (QSet::fromList(list2) - QSet::fromList(list1)).toList();

answered Sep 6, 2022 at 18:50

Botje

32.1k4 gold badges36 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

JarMan Over a year ago

This is a good answer as far as how simple the code becomes. I'm curious how the performance compares to the simple for-loop approach. But that's an exercise for the OP to figure out.

Botje Over a year ago

QSet is based on hashtables, so QSet::fromList is O(n). Set subtraction is again O(n), and toList is also O(n). Total picture is then something like O(n + m + n +n) = O(n) The nested for loops in the question are O(n*m). Of course big-Oh notation only applies once inputs start becoming large, so a 4-element list is not representative.

Collectives™ on Stack Overflow

What is the most efficient way to compare two QStringList in QT?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related