CODEWITHSUNDEEP
c++algorithmsearch
CJAN.LEE
CJAN.LEE

Reputation: 1118

match elements algorithm in two lists C++

I am thinking a method to change the order of two loops Here are two lists:

list<element> aList1;
list<element> aList2;

I want to check each element in both lists, to make sure that element in aList1 is equal to element in aList2 or not.

the content in list can be:

<a,b,c,d> aList1
<k,a,b,z> aList2

so, the result should record not matched position 3-4 in aList1.

but the content can also be:

<a,b,c>
<d,d,b,d>

so, the result should record not matched position 1-2 and 4 in aList1. I only focus on position of aList1.

anther one:

<a,b,c,d,e,f>
<z,e,f,g>

the lists length can be different, and the matched element will be consistent for position 5-6.

I used for(aList1){for(aList2){}} to do this, but it wasted a lot, and could you give me some good method to do it? Thanks a lot!

not only for lists, the container can be vector, map also.

PS: The element is quite complicated, not 0 or 1, actually they are pointers (each element contains several factors, I need to compare one by one, so that's why I want to compare less elements than loop for all).

Upvotes: 0

Views: 1885

Answers (3)

Boris
Boris

Reputation: 622

If you can sort list then sort both and compare by two pointers in the one loop ( O(N log N) ).

If there are small number of different values (for instance, if only 0 and 1 - it's just 2 different numbers), you can calc count of each number (number of 0 and 1 in example) and check result. ( O(N) )

If you can associate numbers (like index) with elements of list, you can effectively use std::bitset. It's more complicated, but has high performance. Look at this, operation AND.

Still, look at the std::set_intersection. It's very clear and simple, and in fact works with pointers too.

Upvotes: 0

didierc
didierc

Reputation: 14730

The pattern you probably want to implement is the following:

auto it1, it2;
for  (it1 = aList1.begin(), it2 = aList2.begin(); 
     it1 != aList1.end() && it2 != aList2.end();  ++it1, ++it2) {
     // code to check elements equality here
}

which let you verify some property on elements having the same rank in both lists, or containers supporting the standard library "iterable" interface (so to speak). Note that you need your containers to return the elements always in a consistent order for the comparison to make sense.

Upvotes: 1

catscradle
catscradle

Reputation: 1719

If you want to avoid nested loops try something like this:

for (auto aIt = a.begin(), bIt = b.begin(); aIt != a.end() && bIt != b.end(); ++aIt, ++bIt)

Upvotes: 1

Related Questions