CODEWITHSUNDEEP
c++sortingc++11vector
bartonm
bartonm

Reputation: 1650

checking for difference between two vector<T>

Suppose you have 2 vectors say v1 and v2 with the following values:

v1 = {8,4,9,9,1,3};
v2 = {9,4,3,8,1,9};

What is the most STL approach to check if they are "equal"? I am defining "equal" to mean the contents are the same regardless of the order. I would prefer to do this without sorting.

I was leaning towards building two std::map<double, int> to count up each of the vector's elements.

All, I need is a boolean Yes/No from the algorithm.

What say you?

Other conversations on Stack Overflow resort to sorting the vectors, I'd prefer to avoid that. Hence this new thread.

Upvotes: 0

Views: 238

Answers (6)

Ramesh Sugunan
Ramesh Sugunan

Reputation: 5

This util method will help you to compare 2 int[], let me know in case of any issues

public static boolean compareArray(int[] v1, int[] v2){

    boolean returnValue = false;

    if(v1.length != v2.length)
        returnValue = false;

    if(v1.length == 0 || v2.length == 0)
        returnValue = false;

    List<Integer> intList =  Ints.asList(v2);

    for(int element : v1){
        if(!intList.contains(element)){
            returnValue = false;
            break;
        }else{
            returnValue = true;
        }
    }

Upvotes: -1

billz
billz

Reputation: 45450

Sorting the vectors and call set_difference is still the best way. If the copy is heavy for you, the comparison between two unsorted arrays is even worse?

If you want current array untouched, you can make a copy of current arrays?

v1 = {8,4,9,9,1,3};
v2 = {9,4,3,8,1,9};

// can trade before copy/sort heavy work
if (v1.size() != v2.size()){
}     
std::vector<int> v3(v1);
std::vector<int> v4(v2);

sort(v3.begin(), v3.end());
sort(v4.begin(), v4.end());

return v3 == v4;

Upvotes: 4

Billy ONeal
Billy ONeal

Reputation: 106609

I was leaning towards building two std::map to count up each of the vector's elements.

This will be far slower than just creating sorted vectors. (Note also that std::map is powered by sorting; it just does so using red-black trees or AVL trees) Maps are data structures optimized for an even mix of inserts and lookups; but your use case is a whole bunch of inserts followed by a whole bunch of lookups with no overlap.

I would just sort the vectors (or make copies and sort those, if you are not allowed to destroy the source copies) and then use vector's built in operator ==.

Upvotes: 4

David Schwartz
David Schwartz

Reputation: 182827

I assume for some reason you can't sort the vectors, most likely because you still need them in their original order or they're expensive to copy. Otherwise, just sort them.

Create a "view" into each vector that allows you to see the vector in any order. You can do this with a vector of pointers that starts out pointing to the elements in order. Then sort the two views, producing a sorted view into each vector. Then compare the two views, comparing the two vectors in their view order. This avoids sorting the vectors themselves.

Upvotes: 3

Lukas
Lukas

Reputation: 52

just take the first vector and compare it with each element in the second vector.

If one value from the first one couldnt be find in the second the vectors are different. In the worst case it takes O(n*m) time which n = size of first vector and m = size second vector.

Upvotes: -1

djechlin
djechlin

Reputation: 60808

Was originally thinking of working in terms of sets since that's what you're actually thinking in terms of but that does necessitate sorting. This can be done in O(n) by converting both to hashmaps and checking for equality there.

Upvotes: 1

Related Questions