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? 13 4940
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
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).
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
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?
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 (==)
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".
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
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
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?
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
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
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
"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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Boštjan Jerko |
last post by:
Hello !
I need to know if the result of math formula is nan (Not a number).
How can I do that?
Thanks,
B.
|
by: Howard |
last post by:
Hi,
I recently had a problem where I decided to store objects in a vector.
(Previously, I had always stored pointers in vectors). Well, naturally,
when storing an object in a vector, using...
|
by: MLH |
last post by:
I'm developing an app that I'd like to backup each time I open it for
modifications. Is it too late to do so after opening the file with
Access? Here's what I've been trying... Trevor Best posted...
|
by: John Salerno |
last post by:
If I want to make a list of four items, e.g. L = ,
and then figure out if a certain element precedes another element, what
would be the best way to do that?
Looking at the built-in list...
|
by: Mark P |
last post by:
For STL Containers, is it well-defined what happens when comparing (for
equality) an iterator and a const_iterator which "point" to the same
container element?
|
by: rAinDeEr |
last post by:
Hi,
I am trying to create around 70 tablespaces for around 100 tables..
Am using DB2 UDB 8.2 in Linux environment...
This is one i generated through Control centre....
CREATE REGULAR...
|
by: Praveen |
last post by:
DateTime.UtcNow is added as root attribute, 'Modified' of an xml whenever
xml is changed.
Every 5 secs a check is made whether xml is changed or not, by comparing
previous 'Modified' and current...
|
by: jehugaleahsa |
last post by:
Hello:
I got tired of trying to find good implementations of collections and
other data structures in C#. So, I started implementing my own.
However, data structures is a wholly different...
|
by: fgh.vbn.rty |
last post by:
I know that std::vector<boolis specialized to store individual bools
as single bits. I have a question about the comparison operation on a
pair of vector<bool>s.
Is the comparison done bit by...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
| |