I have a sort statement for vectr like this,
sort(vec.begin( ), vec.end(), EleSmaller);
in running I find that the sort procedure falls into an endless loop, by
adding some debug statement I see sort is endlessly doing some
comparision on non-exist number!
Then I replace sort() with stable_sort(), it works fine. This really
confuses me, what might be the reason of such problem? The vector seems
fine, as I can go over it specifically to print out all its elements.
Thanks! 6 2880
"John Black" <bl***@eed.co m> wrote in message
news:40******** *******@eed.com ... I have a sort statement for vectr like this,
sort(vec.begin( ), vec.end(), EleSmaller);
in running I find that the sort procedure falls into an endless loop, by adding some debug statement I see sort is endlessly doing some comparision on non-exist number!
Then I replace sort() with stable_sort(), it works fine. This really confuses me, what might be the reason of such problem? The vector seems fine, as I can go over it specifically to print out all its elements.
Almost certainly that your EleSmaller function is bugged.
EleSmaller must be defined so that
1) a < a is never true
2) a < b and b < c implies a < c
3) its never the case that a < b and b > a are both true
If your EleSmaller function does not satisfy those conidtions then sort can
loop forever. If you are not sure, why not post the code of EleSmaller.
john
John Black <bl***@eed.co m> wrote in message news:<40******* ********@eed.co m>... I have a sort statement for vectr like this,
sort(vec.begin( ), vec.end(), EleSmaller);
in running I find that the sort procedure falls into an endless loop, by adding some debug statement I see sort is endlessly doing some comparision on non-exist number!
Then I replace sort() with stable_sort(), it works fine. This really confuses me, what might be the reason of such problem? The vector seems fine, as I can go over it specifically to print out all its elements.
Perhasps EleSmaller(a,b) and EleSmaller(b,a) are both true for some
a,b in vec? Or in general, there might be loop such that v1 > v2 > vn
but vn > v1.
Whether this loop is discovered can depend on the exact comparisions
made.
Regards,
Michiel Salters
John Harrison wrote: "John Black" <bl***@eed.co m> wrote in message news:40******** *******@eed.com ... I have a sort statement for vectr like this,
sort(vec.begin( ), vec.end(), EleSmaller);
in running I find that the sort procedure falls into an endless loop, by adding some debug statement I see sort is endlessly doing some comparision on non-exist number!
Then I replace sort() with stable_sort(), it works fine. This really confuses me, what might be the reason of such problem? The vector seems fine, as I can go over it specifically to print out all its elements.
Almost certainly that your EleSmaller function is bugged.
EleSmaller must be defined so that
1) a < a is never true
2) a < b and b < c implies a < c
3) its never the case that a < b and b > a are both true
If your EleSmaller function does not satisfy those conidtions then sort can loop forever. If you are not sure, why not post the code of EleSmaller.
john
This makes sense, but I wonder how this applies to my problem: in the vector I
am sorting I know there are some elements are equal to each other, for
example, the vector is a collection of 2 type objects, I want type 1 objects
are before type 2 objects, so in my element comparision function, I do this,
bool EleSmaller(Type o1, Type o2){
if (...o1 is of Type2...){
return false;
}
else{
return true;
}
}
Then if in the vector all the objects are of same type, then that is a>b and
b>a, this violates Strict Less Ordering, but I can not think of another way to
define the comparision. Is stable_sort the only solution here? Does
stable_sort not care Strict Less Ordering?
Thanks.
John Black wrote: This makes sense, but I wonder how this applies to my problem: in the vector I am sorting I know there are some elements are equal to each other, for example, the vector is a collection of 2 type objects, I want type 1 objects are before type 2 objects, so in my element comparision function, I do this,
bool EleSmaller(Type o1, Type o2){ if (...o1 is of Type2...){ return false; } else{ return true; } }
When you're working with anything that isn't a numeric type you have to
be extra careful. Lots of people get this sort of thing wrong. Make sure
you've analysed all of the cases.
In this case, it sounds like if o1 and o2 are of the same type, they're
equal. If not, then if o1 is of Type1 (hence o2 is of Type2) o1 < o2,
otherwise o2 < o1.
--
Pete Becker
Dinkumware, Ltd. ( http://www.dinkumware.com)
"John Black" <bl***@eed.co m> wrote in message
news:40******** *******@eed.com ... This makes sense, but I wonder how this applies to my problem: in the
vector I am sorting I know there are some elements are equal to each other, for example, the vector is a collection of 2 type objects, I want type 1
objects are before type 2 objects, so in my element comparision function, I do
this, bool EleSmaller(Type o1, Type o2){ if (...o1 is of Type2...){ return false; } else{ return true; } }
Then if in the vector all the objects are of same type, then that is a>b
and b>a, this violates Strict Less Ordering, but I can not think of another
way to define the comparision. Is stable_sort the only solution here? Does stable_sort not care Strict Less Ordering?
In this case, I don't think you need to use sort() at all. There is
another STL algorithm called partition() that is much better suited to your
purposes.
bool isType1(const Type &o)
{
return (... o is of Type1 ...);
}
Then if you call
partition(vec.b egin(), vec.end(), isType1);
all Type1 elements will be placed before all Type2 elements. Note that
partition returns an iterator that points to the end of the range containing
all the elements that evaluate to true; thus if you stored the result of the
above call in the iterator mid, then
[vec.begin(), mid) will contain all Type1 elements and [mid, vec.end())
will contain all Type2 elements. Also, there is a variation
stable_partitio n which ensures that the relative positions of two elements
that either both evaluate to true or both evaluate to false are unchanged.
Joe Gottman
"John Black" <bl***@eed.co m> wrote in message
news:40******** *******@eed.com ... John Harrison wrote:
"John Black" <bl***@eed.co m> wrote in message news:40******** *******@eed.com ... I have a sort statement for vectr like this,
sort(vec.begin( ), vec.end(), EleSmaller);
in running I find that the sort procedure falls into an endless loop,
by adding some debug statement I see sort is endlessly doing some comparision on non-exist number!
Then I replace sort() with stable_sort(), it works fine. This really confuses me, what might be the reason of such problem? The vector
seems fine, as I can go over it specifically to print out all its elements.
Almost certainly that your EleSmaller function is bugged.
EleSmaller must be defined so that
1) a < a is never true
2) a < b and b < c implies a < c
3) its never the case that a < b and b > a are both true
If your EleSmaller function does not satisfy those conidtions then sort
can loop forever. If you are not sure, why not post the code of EleSmaller.
john
This makes sense, but I wonder how this applies to my problem: in the
vector I am sorting I know there are some elements are equal to each other, for example, the vector is a collection of 2 type objects, I want type 1
objects are before type 2 objects, so in my element comparision function, I do
this, bool EleSmaller(Type o1, Type o2){ if (...o1 is of Type2...){ return false; } else{ return true; } }
Then if in the vector all the objects are of same type, then that is a>b
and b>a, this violates Strict Less Ordering, but I can not think of another
way to define the comparision.
bool eleSmaller(Type o1, Type o2)
{
return o1 is of Type1 && o2 is of Type2;
}
That's works doesn't it? Essentially you must return false for the case
where o1 and o2 are equal.
Is stable_sort the only solution here? Does stable_sort not care Strict Less Ordering?
I think any total sort algorithm would require strict weak ordering.
Otherwise a total ordering isn't necessarilly defined. But I think you have
a strict weak ordering, you just haven't defined it correctly in your
comparison function.
john This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Kitty |
last post by:
Hi, everyone.
Given a vector<int>, what is the fastest way to find out whether there is a
repeated element in it? The result is just "true" or "false". Thanks.
Kitty
|
by: Xiaozhu |
last post by:
say, if you had parallel arrays containing the sales person id, the month, and
the sales figures (for that person in that month), sorting on sales figure and
preserve the order of figures within the data about the same person:
Original Data:
id month sales
+-----+ +-----+ +-----+
| 432 | | 8 | | 89 |
+-----+ ...
|
by: Dr. Ann Huxtable |
last post by:
Hello All,
I am reading a CSV (comma seperated value) file into a 2D array. I want
to be able to sort multiple columns (ala Excel), so I know for starters,
I cant be using the array, I need something more sophistictated like a
vector of row objects.
The data is of this format (same number of columns for each row):
A, x, y, z, ...
|
by: Andreas Schmitt |
last post by:
Is it possible to do something like this:
Team* League;
for (int team=0; team<4; team++)
{
League = new Team;
|
by: Gerhard Menzl |
last post by:
Has anyone ever tried to sort a Standard Library container of gcroots? I
have run into the problem that somewhere deep in the Library logic (in
line 338 of <memory>, to be precise) the destructor of a class
_Temp_iterator tries to obtain the address of a gcroot, but fails
because gcroot::operator& is private.
--
Gerhard Menzl
#dogma int...
| |
by: Varun Kacholia |
last post by:
Hi,
I have a question regarding SGI STL sort implementation:
In case of equal elements, will they be output in the same order each
time I sort?
(I understand that it is not a stable sort, and by "same order" I mean
"same order
*each time I sort*"). Or is there a random number used in the splitter
for qsort?
Thanks
|
by: Timothee Groleau |
last post by:
Hi all,
My name is Tim, I'm just getting started with C++ and this is my first post
to the group.
Is there a standard recommended approach to use a vector of pointers along
with <algorithm>?
To be specific, here is my situation, I have 2 classes A and B. Class A
contains a private vector of pointers to B objects and I need to sort this
|
by: boheman |
last post by:
Hi, I am wondering if there is a simple and quick way to return the
indices of sorted vector.
for example, I have a vector<intx containing {5, 2, 3, 0, 2}.
I can use
sort(x.begin(), x.end(), less<int>());
to sort the vector x. Then the sorted x becomes {0, 2, 2, 3, 5}. But
how can I obtain the indices of sorted x, which is {3, 1, 4, 2,...
|
by: jeremit0 |
last post by:
I'm trying to sort a vector<complex<double and can't figure it
out. I recognize the problem is that there isn't a default operator<
for complex data types. I have written my own operator and can use
it, but std::sort doesn't seem to find it. I have copied a very
simple example below. Everything compiles just fine when the line
with...
|
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...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language...
| |
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. ...
|
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...
|
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 Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
|
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...
|
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...
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
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...
| |