CODEWITHSUNDEEP
c++
G0T0
G0T0

Reputation: 13

Fastest way to compare 2 c++ std::lists, changing in each iteration

Let's say i have 2 std::lists, each contains various numbers of elements. Every element (on each list) has UNIQUE int id value. On every iteration i need to remove elements from first list that don't appear on the second one and add elements from the second list that don't belong to the first one. E.g (numbers=unique ids):

  1. iteration: first[3,2,1], second[4,3,5,7,6], result: [3,4,5,6,7]
  2. iteration: first[3,4,5,6,7], second[4,10,9], result: [4,10,9]

etc... I cannot simply swap second one to first one (let us recognise it's impossible, too long to read). My question is: What is the best search algorithm I can perform to update first list? I mean, should i use nested loops on both sorted lists and compare ids? Remove continuously elements from first lacking in the second but also delete repeating ones in first. Then merge it? Or maybe make one of them unordered_map(hash table)?

Edited:

I wanted to simplify problem but in fact, it's unclear now. I cannot change containers, there are 2 unsorted lists contain 2 different structures each. The only link between 2 types of structures is an id parameter. In every iteration i have to check if first list looks just like the second one. Ids are unique, no repeats allowed. So if ids match lists will be identical. I can't swap them because first list has e.g 30 values and the second one 10 (it's incompleted). There are another special functions to prepare structure for first list that consist of many different structures (including structure from list 2). These functions are launched only if there are ids from the second list that don't appear in the first list. I mustn't manipulate first list but i'm able to modify the second one.

I tried in this ways. In every iteration:

1. Create a std::unordered_set with hashed ids from second list. Then compare it to first list and remove outdated ids from first list. Remove also repeating ids from unordered_set. We'll end up with the set of new structures from list 2. We can run another functions and then add suitable ones to first list.

2. Sort list2 by ids. Then do binary search.

3. Linear search. 2 loops. Id that appears in first list and doesn't in the second one is removed from first list. Id that appears in both lists is removed from the second list. And finally we got ids that appear in second list and don't in the second one. We can process them and merge with list 1.

The most important thing: There will be a lot of comparisons but lists are the same most of the time!

Upvotes: 0

Views: 710

Answers (1)

Billy ONeal
Billy ONeal

Reputation: 106530

The most efficient way to do this is probably going to be to simply assign the second list to the first:

first = second;

which will copy all the elements in second and put them in first.

If for some reason you need to keep the elements in place, you can sort each list and use the set_difference algorithm to find all the elements in one list that are not in the other list.

Upvotes: 1

Related Questions