CODEWITHSUNDEEP
c++algorithmsetequality
Mr. Boy
Mr. Boy

Reputation: 63720

Compare two (non-STL) maps for equality

A 3rd-party library we're using is essentially a map/dictionary. It doesn't provide any way of equality testing two objects against each other and we need this.

More specifically, two maps S1 & S2 are considered equal if:

  1. Every key in S1 is a key in S2
  2. Every key in S2 is a key in S1
  3. For every key K in S1, S1[K] == S2[K]

Note, the internal ordering in each map is irrelevant and may not be relied on, so direct comparison of internal structure/members isn't possible. We do have ways to compare keys and values for equality.

What is the neatest algorithm to do this? Pseudo C++ is just fine since the exact API on the set class is close enough to std::map I can translate.

Upvotes: 3

Views: 2592

Answers (4)

Ulrich Eckhardt
Ulrich Eckhardt

Reputation: 17415

I think that one main question to answer is how expensive a single lookup in that dictionary structure is. If you have e.g. a hashmap's O(1), a comparison loop like what utnapistim suggests would be O(n) * O(1) = O(n) in complexity. If the underlying dictionary is a std::map, you would have O(log n) lookups, making it O(n * log n) overall. If your dict was implemented on top of an unsorted array or list, you would have O(n) lookups making it overall O(n^2).

The reason I'm mentioning these is that you can also sort the two dictionaries and compare the results. Sorting them is O(n * log n), like for std::map, so without knowing the lookup complexity you can't decide whether sorting the sequence is more or less expensive.

There is another aspect I'd like to mention and that is the ordering of the dictionary. You say that you can't assume anything there but there is only one common structure that I'm aware of that doesn't provide a guarantee that equal content means equal order, an unsorted array or linked list. However, that performs badly as dictionary because lookup is O(n), so it is very unlikely that someone chose it as underlying container. Writing this, I wonder whether hashmaps give the guarantee if they have different bucket sizes and perhaps histories, I'm really not sure. Where I'm sure though is that the best algorithm depends on the lookup complexity of the dictionary, so I would try to find out more about this. Even measuring would be preferable to knowing nothing. A well-documented hack that relies on a certain behaviour for performance is IMHO acceptable.

Upvotes: 0

TemplateRex
TemplateRex

Reputation: 70516

Assuming your map API has iterators (or indices), is ordered, contains no duplicates and also stores its key and mapped types as nested typedefs, you could implement the same semantics of std::map::operator== in O(N) time:

#include <functional> // less
#include <algorithm>  // includes

// O(N) complexity
template<class MyMap, class KeyCmp = std::less<typename MyMap::key_type, class TCmp = std::equal<typename MyMap::mapped_type> >
bool set_equality(MyMap const& lhs, MyMap const& rhs, KeyCmp keycmp, TCmp tcmp) 
{
    typedef typename MyMap::value_type Pair;

    return 
        lhs.size() == rhs.size() && 
        std::includes(
            lhs.begin(), lhs.end(), 
            rhs.begin(), rhs.end(), 
            [](Pair const& p1, Pair const& p2){
            return keycmp(p1.first, p2.first) && tcmp(p1.second, p2.second);
        })
    ;
}

Upvotes: 0

nitish712
nitish712

Reputation: 19764

Well this method is valid as long as the maximum value stored in the set is known correctly. Take an array of size of maximum value+1 and initialize it to 0. Then iterate through the first set and increment the array values at 'key' position by its corresponding value.

Now iterate through the second set and decrement the values in the array at the index key by its value.

At the end check if all the array values are zero. If not, then they are unequal, else they are equal.

Time Complexity: O(N)

Memory:O(max_value)

Upvotes: 0

utnapistim
utnapistim

Reputation: 27365

Compare sizes

  • if the sizes are equal

    • iterate the keys in the first set and for each key:

      • check that the key exists in the second set

      • check that the elements for the key are equal

  • If at least one element is not equal, one key in first set does not exist in the second or the sizes are not equal, the sets are unequal.

Upvotes: 8

Related Questions