CODEWITHSUNDEEP
c++
user2381422
user2381422

Reputation: 5805

How to efficiently compare two vectors in C++, whose content can't be meaningfully sorted?

How to efficiently compare two vectors in C++, whose content can't be meaningfully sorted?

I read many posts but most talk about first sorting the two vectors and then comparing the elements. But in my case I can't sort the vectors in a meaningful way that can help the comparison. That means I will have to do an O(N^2) operation rather than O(N), I will have to compare each element from the first vector and try to find a unique match for it in the second vector. So I will have to match up all the elements and if I can find a unique match for each then the vectors are equal.

Is there an efficient and simple way to do this? Will I have to code it myself?

Edit: by meaningful sorting I mean a way to sort them so that later you can compare them in linear fashion.

Thank you

Upvotes: 0

Views: 588

Answers (4)

bazza
bazza

Reputation: 8414

If you really can't sort the vectors you could try this. C++ gurus please free to point out flaws, obvious failures to exploit STL and other libraries, failures to comprehend previous answers, etc, etc :) Apologies in advance as necessary.

Have a vector of ints, 0..n, called C. These ints are the indices of each element in vector B. For each element in vector A compare it against elements in B according to the B indices that are in C. If you find a match remove that index from C. C is now one shorter. For the next A you're again searching B according to indices in C, which being one shorter, takes less time. And if you get lucky it will be quite quick.

Or you could build up a vector of B indices that you have already checked so that you ignore those B's next time round the loop. Saves building a complete C first.

Upvotes: 0

bbm
bbm

Reputation: 140

No reason to use a map, since there's no values to associate with, just keys (the elements themselves). In this case you should look at using a set or an unordered_set. Put all elements from A into a new set, and then loop through B. For each element, if( set.find(element) == set.end() ) return false;

If you're set on sorting the array against some arbitrary value, you might want to look at C++11's hash, which returns a size_t. Using this you can write a comparator which hashes the two objects and compares them, which you can use with std::sort to perform a O(n log n) sort on it.

Upvotes: 1

Konrad Rudolph
Konrad Rudolph

Reputation: 545953

  1. Put all elements of vector A into a hash table, where the element is the key, and the value is a counter of how many times you’ve added the element. [O(n) expected]
  2. Iterate over vector B and decrease the counters in the hash table for each element. [O(n) expected]
  3. Iterate over the hash table and check that each counter is 0. [O(n) expected]

= O(n) expected runtime.

Upvotes: 5

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37980

If the elements can be hashed in some meaningful way, you can get expected O(n) performance by using a hashmap: Insert all elements from list A into the hashmap, and for each element in list B, check if it exists in the hashmap.

In C++, I believe that unordered_map is the standard hashmap implementation (though I haven't used it myself).

Upvotes: 9

Related Questions