# indexes of different items in two QStringLists

• i have two `QStringList`s:

``````QStringList l1 = {a1, a2, a3, a4, a5};
QStringList l2 = {a3, a5};
``````

assume first list is always longer.
i need the indexes of "extra" items from first list, that aren't in second list.
in this example i need result to be `{0, 1, 3}` because items at those indexes in first list, i.e. `a1, a2, a4` aren't in second list.

how can i get those indexes effieciently?

• @user4592357 hi
you can iterate over the first QStringList and check if each value is present in de 2nd QStringList with QStringList::contains, if it returns false then you need the index

• @LeLev
yeah i know, but that's almost quadratic time, right?

• @user4592357
You can do it yourself like @LeLev says :)

I don't think Qt has available methods, but I assume you could convert to `std::vector<std::string>` and doubtless there are `std::` functions for returning the items in one list but not in the other. Whether that's worth it I don't know, do your lists contain 5 or 5,000 items? :) [BTW are the lists sorted?] A C++ `std::` algorithms persons here should be able to answer that...? :)

• yeah i know, but that's almost quadratic time, right?

So you do care about the algorithm! Read my post which has crossed with yours. Are the items sorted?

• @JonB
lists aren't sorted, i was thinking of converting them both to sets and subtract and get the items.
but that's it, it just returns the items, but i need the indexes.

• I started Googling for `c++ vector difference`, I think those are reasonable key words.

`std::set_difference`

Also, is it important you get the indexes into `l1`? I suspect stuff out there will return some kind of collection of the different items.

• @JonB
yes i need the indexes

• @user4592357
Brainstorm suggestion:

1. Put `l2` into a hash/map table, for quick lookup.
2. Leave `l1` unsorted as it is, so you keep indexes.
3. Iterate through `l1`, doing hash lookup in `l2`-hash.

That's much better than quadratic behaviour? That's O(n), plus whatever it takes to create the hash table and do its lookups.

• Whatever you do: benchmark and compare methods.