467,905 Members | 1,714 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 467,905 developers. It's quick & easy.

Best way of comparing two containers?

I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?

Jul 22 '05 #1
  • viewed: 3989
Share:
13 Replies
Dylan wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?


I am not sure if this is optimal, but the obvious way should be worth
trying: copy into two new containers, sort them and check whether they
are equal. That would work in O(n*log(n)) time:

#include <vector>
#include <algorithm>

template < typename T, template <typename> class C >
bool sort_compare ( const C<T> & c_1, const C<T> & c_2 ) {
std::vector<T> v_1 ( c_1.begin(), c_1.end() );
std::vector<T> v_2 ( c_2.begin(), c_2.end() );
std::sort( v_1.begin(), v_1.end() );
std::sort( v_2.begin(), v_2.end() );
return( v_1 == v_2 );
}

#include <iostream>

int main ( void ) {
std::vector< int > c_1;
c_1.push_back( 1 );
c_1.push_back( 1 );
c_1.push_back( 3 );
std::vector< int > c_2;
c_2.push_back( 3 );
c_2.push_back( 1 );
c_2.push_back( 1 );
std::vector< int > c_3;
c_3.push_back( 3 );
c_3.push_back( 0 );
c_3.push_back( 1 );
std::cout << sort_compare( c_1, c_2 )
<< " "
<< sort_compare( c_2, c_3 )
<< "\n";
}
Do you suspect that there is a linear time method?
Best

Kai-Uwe Bux
Jul 22 '05 #2
On Thu, 08 Jul 2004 21:08:11 -0400, Kai-Uwe Bux <jk********@gmx.net>
wrote:
Dylan wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?


I am not sure if this is optimal, but the obvious way should be worth
trying: copy into two new containers, sort them and check whether they
are equal. That would work in O(n*log(n)) time:

#include <vector>
#include <algorithm>

template < typename T, template <typename> class C >
bool sort_compare ( const C<T> & c_1, const C<T> & c_2 ) {
std::vector<T> v_1 ( c_1.begin(), c_1.end() );
std::vector<T> v_2 ( c_2.begin(), c_2.end() );
std::sort( v_1.begin(), v_1.end() );
std::sort( v_2.begin(), v_2.end() );
return( v_1 == v_2 );
}

#include <iostream>

int main ( void ) {
std::vector< int > c_1;
c_1.push_back( 1 );
c_1.push_back( 1 );
c_1.push_back( 3 );
std::vector< int > c_2;
c_2.push_back( 3 );
c_2.push_back( 1 );
c_2.push_back( 1 );
std::vector< int > c_3;
c_3.push_back( 3 );
c_3.push_back( 0 );
c_3.push_back( 1 );
std::cout << sort_compare( c_1, c_2 )
<< " "
<< sort_compare( c_2, c_3 )
<< "\n";
}
Do you suspect that there is a linear time method?
Best

Kai-Uwe Bux


Thanks for your answer, but the reason I stipulated that the elements
can be in any order is that, for the problem I'm working on, it's
unreasonable to assume there is a sorting criteria defined for the
element type (or that one can be defined using the type interface).

Jul 22 '05 #3
Dylan wrote:
...
Thanks for your answer, but the reason I stipulated that the elements
can be in any order is that, for the problem I'm working on, it's
unreasonable to assume there is a sorting criteria defined for the
element type (or that one can be defined using the type interface).
...


In that case you should specify what kind of criteria you _do_ have
defined. Boolean equality criteria only? Something else?

--
Best regards,
Andrey Tarasevich

Jul 22 '05 #4
Dylan wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?


Your *equivalence relationship* is *ill-defined*.

Is [3, 1, 1] equal to [3, 3, 1] for example?

What do you mean by "order"?
1 < 2 < . . . < INT_MAX?
Jul 22 '05 #5
On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
<an**************@hotmail.com> wrote:
Dylan wrote:
...
Thanks for your answer, but the reason I stipulated that the elements
can be in any order is that, for the problem I'm working on, it's
unreasonable to assume there is a sorting criteria defined for the
element type (or that one can be defined using the type interface).
...


In that case you should specify what kind of criteria you _do_ have
defined. Boolean equality criteria only? Something else?

Boolean equality criteria only (==)

Jul 22 '05 #6
On Thu, 08 Jul 2004 18:16:33 -0700, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote:
Dylan wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?
Your *equivalence relationship* is *ill-defined*.


Is it?


Is [3, 1, 1] equal to [3, 3, 1] for example?
no, see above

What do you mean by "order"?
1 < 2 < . . . < INT_MAX?

replace "order" with "position".
Jul 22 '05 #7
Dylan wrote:
On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
<an**************@hotmail.com> wrote:
Dylan wrote:
...
Thanks for your answer, but the reason I stipulated that the elements
can be in any order is that, for the problem I'm working on, it's
unreasonable to assume there is a sorting criteria defined for the
element type (or that one can be defined using the type interface).
...


In that case you should specify what kind of criteria you _do_ have
defined. Boolean equality criteria only? Something else?

Boolean equality criteria only (==)


Hm,
in this case, I only see a quadratic way of doing it:
template < typename T, template <typename> class C >
bool nosort_compare ( const C<T> & c_1, const C<T> & c_2 ) {
std::vector<T> v_1 ( c_1.begin(), c_1.end() );
std::vector<T> v_2 ( c_2.begin(), c_2.end() );
if ( v_1.size() != v_2.size() ) {
return( false );
}
typename std::vector<T>::size_type i_1 = 0;
typename std::vector<T>::size_type i_2 = 0;
while ( i_1 < v_1.size() ) {
if ( v_1[i_1] == v_2[i_2] ) {
std::swap( v_2[i_1], v_2[i_2] );
++ i_1;
i_2 = i_1;
continue;
} else if ( i_2 == v_2.size() ) {
return( false );
} else {
++ i_2;
}
}
return( true );
}
Beware: as this code is not as transparent as the sorting method, it
may be deeply flawed.
Best

Kai-Uwe Bux
Jul 22 '05 #8
On Fri, 09 Jul 2004 01:07:57 +0100, Dylan <sp******@ontheball.com> wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?


Isn't that a multiset?
http://mathworld.wolfram.com/Multiset.html

If so, use the STL multiset implementation
http://www.sgi.com/tech/stl/multiset.html

Markus
Jul 22 '05 #9
Dylan wrote:
E. Robert Tisdale wrote:
Dylan wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?


Your *equivalence relationship* is *ill-defined*.


Is it?


Yes.
Is [3, 1, 1] equal to [3, 3, 1] for example?


no, see above


What above disqualifies this example?
What do you mean by "order"?
1 < 2 < . . . < INT_MAX?


replace "order" with "position".


What *type* of container are you talking about?
Apparently, it's *not* a set.
Can you extract the set of elements from each container
and compare them for equality
to get the equivalence relationship that you want?
Jul 22 '05 #10
Dylan wrote:

On Thu, 08 Jul 2004 18:48:52 -0700, Andrey Tarasevich
<an**************@hotmail.com> wrote:
Dylan wrote:
...
Thanks for your answer, but the reason I stipulated that the elements
can be in any order is that, for the problem I'm working on, it's
unreasonable to assume there is a sorting criteria defined for the
element type (or that one can be defined using the type interface).
...


In that case you should specify what kind of criteria you _do_ have
defined. Boolean equality criteria only? Something else?

Boolean equality criteria only (==)


Hmm. Would it be possible to make up some artificial 'less'
relationship just for the purpose of sorting? It doesn't
matter if that 'less' actually makes some sense in the
assignment space.
(Such a thing is almost always possible to do)
--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #11
Dylan wrote:
I'd like to compare two containers. They should be considered
equivalent if both containers have the same number of elements with
the same values, no matter what order the values are in.

For instance the containers

A = [1, 2, 3]
B = [1, 2, 3]

are obviously equal, but so would be

A = [3, 2, 1]
B = [2, 1, 3]

as would

A = [2, 2, 5, 1]
B = [2, 1, 5, 2]

What's the best (quickest) way of comparing containers in this way?


I think you need to use std::set or std::multiset.


Regards,

Ioannis Vranos
Jul 22 '05 #12
Example:
#include <iostream>
#include <set>
int main()
{
using namespace std;

multiset<int>t1, t2;

t1.insert(2);
t1.insert(2);
t1.insert(5);
t1.insert(1);

t2.insert(2);
t2.insert(1);
t2.insert(5);
t2.insert(2);

if(t1==t2)
cout<<"\nEqual!\n";

}


Regards,

Ioannis Vranos
Jul 22 '05 #13

"Ioannis Vranos" <iv*@guesswh.at.grad.com> wrote in message
news:cc**********@ulysses.noc.ntua.gr...
Example:
#include <iostream>
#include <set>
int main()
{
using namespace std;

multiset<int>t1, t2;

t1.insert(2);
t1.insert(2);
t1.insert(5);
t1.insert(1);

t2.insert(2);
t2.insert(1);
t2.insert(5);
t2.insert(2);

if(t1==t2)
cout<<"\nEqual!\n";

}


Which works for int, but the OP said his T only implements operator==, and
not any of the inequalities.

Jeff F
Jul 22 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

10 posts views Thread by BoŇ°tjan Jerko | last post: by
14 posts views Thread by Howard | last post: by
21 posts views Thread by John Salerno | last post: by
2 posts views Thread by Mark P | last post: by
10 posts views Thread by rAinDeEr | last post: by
2 posts views Thread by Praveen | last post: by
13 posts views Thread by jehugaleahsa | last post: by
17 posts views Thread by fgh.vbn.rty | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.