Solved 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 arestd::
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...? :) -
@user4592357 said in indexes of different items in two QStringLists:
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. -
@user4592357
Start here: https://stackoverflow.com/questions/27192967/c-get-the-difference-between-two-vectorsI 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:- Put
l2
into a hash/map table, for quick lookup. - Leave
l1
unsorted as it is, so you keep indexes. - Iterate through
l1
, doing hash lookup inl2
-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.
- Put
-
Whatever you do: benchmark and compare methods.