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 4984
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******@onthe ball.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? 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 push_back, the object I had in
hand was getting copied (twice, in fact). That led to a problem, in that my
object contained a "handle" to another object, and when the object being
pushed went out of scope and was destroyed, the referenced object was...
|
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
this code in 1995...
On frmMainMenu, I have a Fn that I launch with a button. Here
is the function:
Sub CopySingleFile (szSrc As String, szTgt As String)
|
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 functions, I thought I could do something like:
if L.index('A') < L.index('D'):
# do some stuff
But I didn't know if maybe there was a preferred method for this type of
|
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 TABLESPACE SNCI001 IN DATABASE PARTITION GROUP
IBMDEFAULTGROUP PAGESIZE 4096 MANAGED BY SYSTEM
USING ('/db2home/db2inst1/dnci1d/user_tblspace')
|
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 'Modified'.
By considering performance in mind whats best to way of stroring and
calculating date in this case?
Is UtcNow best for comparing every 5 secs.?
Or is it better saving UtcNow.ticks and comparing it.?
|
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 process in C# compared
to C++. I have to be a lot more careful about dangling pointers to
make sure things don't get pushed into further GC generations.
When I started learning about Comparer and similar classes, I got a
|
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 bit? That would be slow. In theory it's
possible to just do a bit-wise XOR on all bits and then OR it all
together and compare the single bit right? That would make it O(1)
instead of O(n). What's bad about this method?
Does the size of the...
|
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, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
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, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
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 tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
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, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
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 presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
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 then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |