How do I check if two std::vector's contain only the same elements?

Question

I need an algorithm or a standard library function for comparing two vector elements, like below:

class Utility
{
    template <class T>
    static bool CheckIfVectorsEquivalent(   const std::vector<T> & Vec1,
                                            const std::vector<T> & Vec2)
    {
        // ???
    }
};

Working under the following specifications:

std::vector<int> v1, v2, v3, v4, v5, v6, v7, v8;

// Returns false when not all the elements are matching between vectors
v1.push_back(1);
v1.push_back(3);
v1.push_back(5);
v2.push_back(2);
v2.push_back(3);
v2.push_back(8);
Utility::CheckIfVectorsEquivalent(v1, v2);  // Must return false

// Returns true when all the elements match, even if the are not in the same order
v3.push_back(3);
v3.push_back(1);
v3.push_back(7);
v4.push_back(7);
v4.push_back(3);
v4.push_back(1);
Utility::CheckIfVectorsEquivalent(v3, v4);  // Must return true

// Returns false when one of the vectors is subset of the other one
v5.push_back(3);
v5.push_back(1);
v5.push_back(7);
v6.push_back(7);
v6.push_back(3);
v6.push_back(1);
v6.push_back(18);
v6.push_back(51);
Utility::CheckIfVectorsEquivalent(v5, v6);  // Must return false

// Returns true when the both vectors are empty
Utility::CheckIfVectorsEquivalent(v7, v8);  // Must return true

Is there any standard (with STL) way of doing this? If not, how can I write this algorithm? It confused me too much.

Answer 1

The standard way will be sorting these two vectors and using operator ==, which compares corresponding values.

The sample solution realizing this algorithm is:

#include <vector>
#include <algorithm>

template<typename T>
bool compare(std::vector<T>& v1, std::vector<T>& v2)
{
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    return v1 == v2;
}

Its complexity is O(n*log(n)), because of the sorting.

Answer 2

If you can live with just a c++11 solution, then std::is_permutation is exactly what you want

template <class FI1, class FI2>
bool is_permutation ( FI1 first, FI1 last, FI2 d_first );

If you can't do that, then in the upcoming boost 1.50 release, there will be

boost::algorithm::is_permutation

with the same interface.

Answer 3

  v7.push_back(3);
  v7.push_back(1);
  v7.push_back(7);

  v8.push_back(7);
  v8.push_back(3);
  v8.push_back(1);
  v8.push_back(1);
  v8.push_back(7);

  std::cout << compare(v7, v8) << " true or false" << std::endl;  

the condition as above, the function compare will return true or false.I lost count. if return true. we can't use the way: The standard way will be sorting these two vectors and using operator ==, which compares corresponding values.

Answer 4

If we consider an int to be large enough for the computations done in the following algorithm, there is a simple O(N) algorithm.

0: initialization: There are primes to the size of max(v1,v2), product1=1, product2=1

1: return false if size of v1 != size of v2

2:

foreach (  i in v1 ) {
   product1 *= primes[v1[i]]
   product2 *= primes[v2[i]]
}

3.

result product1 == product2;

Answer 5

Simplest way to do it is to create copies of Vec1 and Vec2, sort them and compare using ==.

Another way to do it is to build two multisets from Vec1 and Vec2 and compare them using ==.

Yet another way to do it is to use maps (std::map or unordered_map) to store counters - i.e. increment stored value for every element of Vec1 and decrement for every stored element of Vec2, then check if map contains non-zero elements. If there are non-zero elements stored in map, vectors are non-equal.

messy pseudocode example:

std::vector<Value> vec1, vec2;
//initialize vec1 and vec2, fill with data
typedef int Counter;
typedef unordered_map<Value, Counter> CounterMap;

CounterMap counters;
for (size_t i = 0; i < vec1.size(); i++)
    counters[vec1[i]]++;
for (size_t i = 0; i < vec2.size(); i++)
    counters[vec2[i]]--;

bool equal = true;
for (CounterMap::const_iterator i = coutners.begin(); equal && (i != counters.end()); i++)
    if (i->second != 0)
        equal = false;

Depending on your STL (or boost) implementation, data type, and order of stored data in vectors) one of those methods will be faster, but it is hard to tell which one.

Answer 6

There's an O(n) solution to this problem for unsorted inputs:

#include <vector>
#include <algorithm>
#include <iostream>
#include <boost/function_output_iterator.hpp>

template <typename T>
T xorfunc(const T& a, const T& b) {
  return a^b;
}

template <typename T>
bool compare(const std::vector<T>& v1, const std::vector<T>& v2) {
  if (v1.size() != v2.size())
    return false;

  T result = 0;
  std::transform(v1.begin(), v1.end(), v2.begin(), boost::make_function_output_iterator([&result](const T& r) { result ^= r; }), std::ptr_fun(&xorfunc<T>));
  return !result;
}

that works for integer inputs and exploits the fact that a ^ b ^ c ^ d == 0 for any combination of paired values. It will never give false negatives, it might give false positives potentially, but you can reduce those further in O(n) space/time. If you're mostly hitting negatives then this might be useful as a pre-sort+compare step to rule them out quickly. It works for all the test cases you've shown:

int main() {
    std::vector<int> v1, v2, v3, v4, v5, v6, v7, v8;

    // Returns false when not all the elements are matching between vectors
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v2.push_back(2);
    v2.push_back(3);
    v2.push_back(8);
    std::cout << compare(v1, v2) << " (false)" << std::endl;  // Must return false

    // Returns true when all the elements match, even if the are not in the same order
    v3.push_back(3);
    v3.push_back(1);
    v3.push_back(7);
    v4.push_back(7);
    v4.push_back(3);
    v4.push_back(1);
    std::cout << compare(v3, v4) << " (true)" << std::endl;  // Must return true

    // Returns false when one of the vectors is subset of the other one
    v5.push_back(3);
    v5.push_back(1);
    v5.push_back(7);
    v6.push_back(7);
    v6.push_back(3);
    v6.push_back(1);
    v6.push_back(18);
    v6.push_back(51);
    std::cout << compare(v5, v6) << " false" << std::endl;  // Must return false

    // Returns true when the both vectors are empty
    std::cout << compare(v7, v8) << " true" << std::endl;  // Must return true

}

Gives:

0 (false)
1 (true)
0 false
1 true

Answer 7

Create a multiset from each vector, then just compare them for equality.