Programming Forums - checkCollisions() function

Page 1 of 2

Show 40 post(s) from this thread on one page

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - checkCollisions() function (http://www.programmingforums.org/showthread.php?t=10855)

andro

Jul 27th, 2006 12:26 AM

checkCollisions() function

I have a function that I am using to look for any collisions between 2 std::map's before I try and combine them.

I'm lacking a little bit of confidence with C++, and was wondering if you guys can take a look at this for me.... is there a more efficient way to look for collisions between 2 maps? A better algorithm? Something in the STL I missed? Can you point out any potential problems with my code or problems that need called to my attention?

Thanks :o

keymap is typdef'd in CQUtil.h as:

typedef std::map<char, char> keymap;

[PHP]
bool CQUtil :: checkCollisions(keymap master, keymap candidate)
{
char mKey, mValue;
char cKey, cValue;

keymap::iterator mIter;
keymap::iterator cIter;

for (mIter = master.begin(); mIter != master.end(); ++mIter)
{
for (cIter = candidate.begin(); cIter != candidate.end(); ++cIter)
{
mKey = mIter->first;
mValue = mIter->second;

cKey = cIter->first;
cValue = cIter->second;

// Does the candidate map have any keys that map to a different
// value than the master map?
if (mKey == cKey && mValue != cValue)
return true;

// Does the candidate map have any values that are mapped to a
// different key in the master map?
if (cValue == mValue && cKey != mKey)
return true;
}
}

return false;
}
[/PHP]

grumpy

Jul 27th, 2006 7:00 AM

I haven't checked to see if there are any of the standard algorithms that will help. I suggest you read up on them.

But you can make use of the fact that a map is actually sorted on the keys. Also a few tweaks such as passing the maps to the function by const reference, and moving some repeated operations out of the inner loop.

//warning:  I haven't tested this by feeding into compiler or with

//    useful test cases



bool CQUtil :: checkCollisions(const keymap &master, const keymap &candidate)

{

    char                mKey, mValue;

    char                cKey, cValue;



    keymap::const_iterator    mIter, mEnd = master.end();

    keymap::const_iterator    cBegin = candidate.begin(), cIter, cEnd = candidate.end();



    for (mIter = master.begin(); mIter != mEnd; ++mIter)

    {

         mKey   = mIter->first;

         mValue = mIter->second;



        for (cIter = cBegin; cIter != cEnd; ++cIter)

        {

            cKey   = cIter->first;

            cValue = cIter->second;



            //  Does the candidate map have any keys that map to a different

            //  value than the master map?

            //  Does the candidate map have any values that are mapped to a

            //  different key in the master map?

            //     If keys are the same, the values must be different.

            //     If values are the same, the keys must be different.

            //

            //   Warning:  I spent 4 hours in travelling today, so I may have

            //     mucked up the boolean algebra



            if ((mKey == cKey) == (mValue != cValue))

                return true;

            else if (cKey > mKey)

                break;

        }

    }



    return false;

}

Cache

Jul 27th, 2006 7:08 AM

Efficient for you or the comp?

bool CheckCollisions(const keymap& master, 

                     const keymap& candidate)

{

    return (candidate != master);

}

J/K.

DaWei

Jul 27th, 2006 7:55 AM

He's probably less concerned with efficiency than with something that does what he wants.

Cache

Jul 27th, 2006 8:07 AM

Quote:

Originally Posted by DaWei

He's probably less concerned with efficiency than with something that does what he wants.

Yup.

Note to self: never post until you've properly woken up.

Narue

Jul 27th, 2006 10:04 AM

>is there a more efficient way to look for collisions between 2 maps? A better
>algorithm? Something in the STL I missed?
set_intersection in <algorithm>?

[edit]
And before you come back telling us that it won't work, keep in mind that you need to use the predicate argument to set_intersection since maps use a compound type (pair) for the contained item.
[/edit]

andro

Jul 27th, 2006 4:22 PM

From what I've read about set_intersection, it is used in the actual combining of 2 ranges into a single sorted range, with ordering criteria to be determined by the predicate.

This function is just supposed to find collisions or inconsistencies BEFORE I attemp to combine them.

For example, this represents the scenario where the candidate contains a key which maps to a different value than the master:

master['a'] = 'z';

master['b'] = 'y';



candidate['a'] = ['z'];

candidate['b'] = ['x'];

This scenario represents a candidate that maps a key to a value that is already mapped to something else in the master:

master['a'] = 'z';

master['b'] = 'y';



candidate['e'] = 'w';

candidate['f'] = 'z';

Maybe I am misunderstanding the use of set_intersection though, but it seems like it's what I want to use once I've determined there is no "collisions" or inconsistencies between my 2 maps, and need to combine them with combineMaps().

Thank you for the feedback guys (and gals) :)

Narue

Jul 27th, 2006 4:53 PM

>This function is just supposed to find collisions or inconsistencies BEFORE I attemp to combine them.
What better way than to combine them and weed out the collisions? set_intersection doesn't actually merge the two input ranges unless you specify one of them as the output range as well. For example:

#include <algorithm>

#include <iostream>

#include <iterator>

#include <map>

#include <utility>

#include <vector>



using namespace std;



template <typename T, typename U>

struct map_cmp {

  bool operator() ( const pair<T, U>& lhs,

    const pair<T, U>& rhs )

  {

    return lhs.first < rhs.first;

  }

};



template <typename U, typename V>

void show_range ( const map<U, V>& container )

{

  typename map<U, V>::const_iterator it = container.begin();

  typename map<U, V>::const_iterator end = container.end();



  while ( it != end ) {

    cout<< it->first <<" -- "<< it->second <<'\n';

    ++it;

  }



  cout<<'\n';

}



int main()

{

  map<int, int> m;

  map<int, int> n;

  map<int, int> result;



  m[0] = 0;

  m[1] = 1;

  m[2] = 2;

  m[3] = 3;



  n[5] = 9;

  n[4] = 8;

  n[3] = 7;

  n[2] = 6;



  set_intersection ( m.begin(), m.end(),

    n.begin(), n.end(),

    inserter ( result, result.begin() ),

    map_cmp<int, int>() );



  cout<<"Range of M:\n";

  show_range ( m );



  cout<<"Range of N:\n";

  show_range ( n );



  cout<<"Collisions (key based):\n";

  show_range ( result );

}

>but it seems like it's what I want to use once I've determined there is
>no "collisions" or inconsistencies between my 2 maps, and need to combine them with combineMaps().
It sounds like you're thinking of set_union.

andro

Jul 27th, 2006 5:02 PM

Quote:

Originally Posted by Narue

>This function is just supposed to find collisions or inconsistencies BEFORE I attemp to combine them.
What better way than to combine them and weed out the collisions?

That's exactly what I can't have happen. If 2 maps have inconsistencies, then in the context of my program they should never get a chance to combine.

Narue

Jul 27th, 2006 5:24 PM

>That's exactly what I can't have happen.
*sigh* Did you completely miss the rest of my post by latching onto that comment? The only difference between what you were trying to do and what set_intersection does, is set_intersection uses temporary storage (the result container). This is a good thing. Unless your checkCollisions function is very trivial, you'll want to know where the collisions are so that they can be dealt with in a user-friendly way. If you simply return true or false after finding a collision, what are you going to do? Throw an error?

All times are GMT -5. The time now is 12:24 AM.

Page 1 of 2

Show 40 post(s) from this thread on one page